The problem of time-optimal network queue control is solved: what are the input data rates that make network queue sizes converge to their ideal size in the least possible time after a disturbance while still maintaining maximum link utilization at all times, even in the transient? The problem is nontrivial especially because of the vast possible heterogeneity in packet propagation delays in the network. In this paper, we derive the time-optimal queue control for a single congested network node with a single finite queue shared by flows with arbitrary network delays. We neatly separate the derivation of the optimal arrival rate sequence from that of the feedback control protocol to achieve it. The time-optimal control is robust to bandwidth and queue size estimation errors. Its complexity is only a function of the size of the network delays and no per-flow computation is needed. The time-optimality and robustness properties are proven to hold under all queue operating regimes with no need for linearizing approximations.

This paper considers STMM, a spatio-temporal max-min fair rate allocation for virtual circuits (VCs) in networks with time-varying link capacities. This is a direct generalization of conventional steady-state max-min fair rate allocation. In an STMM allocation, all links are fully utilized while maintaining feasibility and fairness among VCs at all times. It is shown that if and only if the propagation delay differences between VCs as seen at different switches is consistent, the STMM problem gets decoupled into a time-sequence of independent steady-state max-min fair allocation problems. A generic protocol to achieve STMM allocation in such networks is presented. Practical temporal flow control protocols which take link delays into account, can be then designed as approximations of this ideal protocol.

This paper proves a tight lower and upper bound for the convergence of max-min rate allocation protocols for connection-oriented networks. The theory is based on the concept of a constraint precedence graph. The analysis and simulation results show that the previously known convergence time estimates are too pessimistic.

This paper introduces a scalable maxmin flow control protocol which guarantees the minimum rate for each connection-oriented flow without requiring per-flow information. The protocol is called MR-ASAP (minimum rate guaranteeing adaptive source-link accounting protocol). MR-ASAP is an extension of ASAP, the first exact maxmin flow control protocol for best-effort connection-oriented traffic in integrated service networks, without requiring per-flow accounting at the intermediate network node. In the classical maxmin computation, only the maximum rate constraints are considered; in this paper the minimum rate requirements are treated similarly as the maximum rate constraints. Existing protocols that achieve exact maxmin optimality with minimum rate guarantee require per-flow information and complex computation such as sorting of the minimum rates at the switch. By generalizing the concept of constraint, the complex sorting and per-flow accounting required in the existing protocols are avoided. Simulation demonstrates fast convergence to optimality.