Global Optimization Using Local Information with Applications to Flow Control

Flow control in high speed networks requires distributed routers to make fast decisions based only on local information in allocating bandwidth to connections. While most previous work on this problem focuses on achieving local objective functions, in many cases it may be necessary to achieve global objectives such as maximizing the total flow. This problem illustrates one of the basic aspects of distributed computing: achieving global objectives using local information. Papadimitriou and Yannakakis (1993) initiated the study of such problems in a framework of solving positive linear programs by distributed agents. We take their model further, by allowing the distributed agents to acquire more information over time. We therefore turn attention to the tradeoff between the running time and the quality of the solution to the linear program. We give a distributed algorithm that obtains a (1+/spl epsiv/) approximation to the global optimum solution and runs in a polylogarithmic number of distributed rounds. While comparable in running time, our results exhibit a significant improvement on the logarithmic ratio previously obtained by Awerbuch and Azar (1994). Our algorithm, which draws from techniques developed by Luby and Nisan (1993) is considerably simpler than previous approximation algorithms for positive linear programs, and thus may have practical value in both centralized and distributed settings.

Authors

• Yair Bartal
• John W. Byers
• Danny Raz

Keywords

• Bandwidth
• Distributed computing
• High-speed networks
• Distributed algorithms
• Computer science
• Bit rate
• Communication system traffic control
• Strain control
• Local Information
• Flow Control
• Running Time
• Linear Programming
• Optimum Solution
• Solution Quality
• Distributed Algorithm
• Global Objective
• Values Of Variables
• Specific Form
• End Of Phase
• Feasible Solution
• Value Of Solution
• Quality Estimation
• Network Bandwidth
• Sequential Algorithm
• Approximate Ratio
• Global Operations
• Algorithm Execution
• Dual Variables
• Dual Solution
• Linear Programming Algorithm
• Fast Implementation
• Network Routing