Conjecture-Based Load Balancing for Delay-Sensitive Users Without Message Exchanges

摘要

In this paper, we study how multiple users can balance their traffic loads to share common resources in an efficient and distributed manner, without message exchanges. Specifically, we study a deployment scenario where users deploy delay-sensitive applications over a wireless multipath network and aim to minimize their own expected delays. Since the performance of a user's load balancing strategy depends on the strategies that are deployed by other users, it becomes important that a user considers the multiuser coupling when making its own load balancing decisions. We model this multiuser interaction as a load balancing game (LBG) and show that users can converge to a $varepsilon$-consistent conjectural equilibrium by building near-accurate beliefs about the remaining capacities on each path. Based on these beliefs, users can make load balancing decisions without explicitly knowing the actions of the other users. In such a conjecture-based LBG, we analytically show that, if a leader is elected to build beliefs about how the users' aggregate transmission strategies affect the remaining resources, then this leader can use this knowledge to shape its traffic such that the multiuser interaction can achieve an efficient allocation across paths. Even if no leader is present in the game, as long as the users follow a set of prescribed rules for building beliefs, they can reach efficient outcomes in a distributed manner. Importantly, the proposed distributed load balancing solution can be also applied to other multiuser communication and networking problems where message exchanges are prohibited (or prohibitively expensive in terms of delay or bandwidth), ranging from multichannel selection in wireless networks to relay assignment in multivehicle networks.