Free Steering Update Schemes for Distributed Flow Control

摘要

We study two adaptive, distributed optimal flow control algorithms for virtual circuit flow control in a network. These algorithms are based on greedy heuristics. Each virtual circuit (or user) attempts to adjust its message rate to achieve an ideal tradeoff point between high throughput and low delay. The first algorithm is the bottleneck flow control algorithm where each user adjusts its rate based on a saturation measure for the throughput verse delay tradeoff at the bottleneck link. The second algorithm is called the greedy algorithm. Each user iteratively optimizes its individual performance measure, power, by using currently available information about network bandwidth.rnOur work focuses on individual (or user) optimization as opposed to system optimization. Convergence analyses are based on a noncooperative game theoretical formulation. Under this formulation, we show that both the greedy algorithm and the bottleneck flow control algorithm converge to a unique Nash equilibrium point for n users sharing a single link in a free steering updating schedule. Also, we provide the necessary and sufficient conditions for both algorithms to converge; moreover, we derive the necessary and sufficient conditions for both algorithms to always remain feasible for n users sharing a single link in the asynchronous order. Finally, we show some convergence properties for the generalized version of the optimal flow control algorithms.