December 1999 | Steven H. Low, Senior Member, IEEE, and David E. Lapsley
This paper proposes an optimization-based approach to flow control, where the goal is to maximize the aggregate source utility over their transmission rates. The network is viewed as a distributed computation system, with sources and links acting as processors to solve the dual problem using a gradient projection algorithm. Sources select transmission rates that maximize their own utility minus bandwidth cost, while links adjust bandwidth prices to coordinate the sources' decisions. The algorithm is designed to handle asynchronous updates, different feedback delays, and varying update frequencies. It is proven to converge in a static environment and is tested in a slowly time-varying environment. The algorithm is also shown to have fair resource allocation properties.
The paper introduces a dual problem formulation, where the objective is to minimize the dual objective function. The dual problem is solved using gradient projection, with link prices adjusted in the opposite direction of the gradient. The algorithm is shown to converge to the optimal rate allocation under certain conditions. The algorithm is extended to an asynchronous setting, where sources and links may update at different times and with different frequencies. The asynchronous algorithm is proven to converge under the assumption that the intervals between updates are bounded.
The paper also discusses the fairness properties of the algorithm, showing that it can provide proportionally fair resource allocation. It extends the algorithm to a time-varying environment, where the link capacities and source sets may change over time. The algorithm is shown to track the optimal rates when network conditions change slowly. The paper also discusses the implementation of the algorithm, including a prototype that demonstrates its convergence in a slowly time-varying environment. The algorithm is shown to be robust to large feedback delays and can be implemented using binary feedback. The paper concludes that the optimization approach provides a systematic way to design and refine flow control schemes, with the potential for application in a multicasting environment.This paper proposes an optimization-based approach to flow control, where the goal is to maximize the aggregate source utility over their transmission rates. The network is viewed as a distributed computation system, with sources and links acting as processors to solve the dual problem using a gradient projection algorithm. Sources select transmission rates that maximize their own utility minus bandwidth cost, while links adjust bandwidth prices to coordinate the sources' decisions. The algorithm is designed to handle asynchronous updates, different feedback delays, and varying update frequencies. It is proven to converge in a static environment and is tested in a slowly time-varying environment. The algorithm is also shown to have fair resource allocation properties.
The paper introduces a dual problem formulation, where the objective is to minimize the dual objective function. The dual problem is solved using gradient projection, with link prices adjusted in the opposite direction of the gradient. The algorithm is shown to converge to the optimal rate allocation under certain conditions. The algorithm is extended to an asynchronous setting, where sources and links may update at different times and with different frequencies. The asynchronous algorithm is proven to converge under the assumption that the intervals between updates are bounded.
The paper also discusses the fairness properties of the algorithm, showing that it can provide proportionally fair resource allocation. It extends the algorithm to a time-varying environment, where the link capacities and source sets may change over time. The algorithm is shown to track the optimal rates when network conditions change slowly. The paper also discusses the implementation of the algorithm, including a prototype that demonstrates its convergence in a slowly time-varying environment. The algorithm is shown to be robust to large feedback delays and can be implemented using binary feedback. The paper concludes that the optimization approach provides a systematic way to design and refine flow control schemes, with the potential for application in a multicasting environment.