Congestion Control: Model and Algorithms
To which sources are the sun and the moon linked? In what formation are the stars deployed?
–Qu Yuan (340–278 BC), ‘Heavenly Questions'
Congestion avoidance mechanisms serve as a keystone of a huge communication network like the Internet. This chapter introduces basic notions, algorithms and system models of end-to-end congestion control. The congestion control problem is modeled as an optimization problem of resource allocation in the network under link capacity constraints, and the congestion control algorithms are treated as distributed real-time gradient-descent algorithms of seeking for the optimal solution of the resource allocation problem.
4.1 An Introduction to Congestion Control
Consider a network containing S sources each of which is identified as an origin. Denote by the set of source nodes. It is supposed that each user uses a fixed route between its origin and destination. Denote by the set of all the links contained in the network, and by the set of links used by the user of source i. Note that each link may be used by multiple sources. Denote by the set of sources using link l. From the viewpoint of graph theory, ...