Distributed flow scheduling in an unknown environment

摘要

Flow scheduling is crucial in the next-generation network but hard to address due to fast changing link states and tremendous cost to explore the global structure. In this paper, we first design a distributed virtual game to solve the optimization of flow scheduling problem assuming the priori knowledge of the distribution of edge cost as a random variable. In our virtual game, we use incentives to stimulate selfish users to reach a Nash Equilibrium Point which is suboptimum based on the analysis of the ‘Price of Anarchy’. This algorithm is then generalized into the situation with unknown cost distribution, where the ultimate goal is to minimize the cost in the long run. In order to achieve a reasonable tradeoff between exploration of cost distribution and exploitation with limited information, we model this problem as a Multi-armed Bandit Game and combine the newly proposed DSEE with our virtual game design. Armed with these powerful tools, we find a totally distributed algorithm to ensure the logarithmic growing of regret with time, which is optimum in classic Multi-armed Bandit problem. Theoretical proof and simulation results both confirm the effectiveness of our algorithm. To the best of our knowledge, this is the first work to combine multi-armed bandit with distributed flow scheduling.