Optimization Problems in Congestion Control

One of the crucial elements in the Internet's success is its ability to adequately control congestion. The paper defines and solves several optimization problems related to Internet congestion control, as a step toward understanding the virtues of the TCP congestion control algorithm currently used and comparing it with alternative algorithms. We focus on regulating the rate of a single unicast flow when the bandwidth available to it is unknown and may change over time. We determine near-optimal policies when the available bandwidth is unchanging, and near-optimal competitive policies when the available bandwidth is changing in a restricted manner under the control of an adversary.

Authors

• Richard M. Karp
• Elias Koutsoupias
• Christos H. Papadimitriou
• Scott Shenker

Keywords

• Bandwidth
• Internet
• Computer science
• Unicast
• Delay
• Degradation
• Protocols
• Algorithm design and analysis
• Turning
• Probes
• Lower Bound
• Upper Bound
• Performance Of Algorithm
• Cost Function
• Less Than Or Equal
• Greater Than Or Equal
• Probability Density Function
• Positive Integer
• Static Case
• Binary Search
• Online Algorithm
• Optimal Gain
• Family Of Algorithms
• Deterministic Case
• Transmission Failure
• Left Child
• Packet Drop
• Competitive Ratio
• Binary Tree
• Proof Of Theorem