Optimal network flow control: time-optimal queue control and max-min fair bandwidth allocation
Mahadevan Iyer, Wei Kang Tsai · 2004
Rate-based feedback flow control at the network layer has the potential to dramatically alleviate the Internet's artificial bottleneck problems created by bursty, uncoordinated and uncontrolled traffic flows. A good feedback flow control scheme will control traffic rates entering the network such as to keep network queue sizes stably close to a targeted ideal value while maximizing bandwidth utilizations and allocating the bandwidths fairly among different users. Moreover, it will be robust in achieving these objectives in the face of dynamic and unpredictable available link bandwidth and flow routes. This thesis contributes news results towards a fundamental understanding of how to achieve these objectives jointly. Specifically it formulates queue and link bandwidth utilization control as a time-optimal control problem: starting from any initial condition, control the traffic rates entering the network so as to converge the network queue sizes to a desired level in the minimum possible time while still keeping at least one link fully utilized in the path of every flow at all times. The robustness goal is automatically satisfied by the time-optimal control law; we formally prove this for case of a single-queue. Traditional control-theoretic approaches have been based on simplified linear models of the network invalid under severe bandwidth and route disturbances and yet have been intractable for general network topologies, delays and congestion conditions. Typically they lead to local stability or robustness results. In contrast, the time-optimal approach leads to exact global solutions valid even under nonlinear queue dynamics. Formal proofs are given for all results. Moreover, these solutions are computationally simple and lend themselves nicely to designing distributed asynchronous protocols. With a gradual approach, we first solve for time-optimal control of a single queue shared by multiple flows and of a single flow crossing multiple queues. From these, the solution for a general network of queues, with a target queue size of zero, is intuited. The heart of this solution is a spatio-temporal link capacity allocation among the flows: to guarantee time-optimality, it is sufficient for the allocation to be both feasible and maximally-utilizing with respect to “queue-reduced” link capacities. To these two conditions, different fairness criteria can be added thereby resulting in different specific control laws. Thus fairness is neatly separated out from queue control. Specifically, we focus on the max-min fairness criterion. We formally analyze convergence speeds of max-min fair link capacity allocation algorithms and show that previous estimates of their worst-case convergence speeds have been very pessimistic. We also develop a theory of spatio-temporal bandwidth allocation. For networks with consistent link delay differences as seen at different flows, we show how to construct spatio-temporal bandwidth allocation protocols from any available distributed algorithm for a spatially defined allocation such as max-min fair allocation.