Routing, flow control and fairness in computer networks
Hak-Wai Chan · 1986
The success of computer networks is based on efficient sharing of resources among users. Routing and flow control have been designed to enhance the sharing of common resources and to optimize overall system performance. A key performance criterion in this optimization is fairness i.e., the ability to provide equal satisfaction to all users. We propose a measure of fairness based on balanced interference among users for wide-area, packet-switched computer network. This measure guarantees that the throughput of the individual user cannot be zero and the actual throughput achieved by a user tends to be proportional to his traffic demand. Assuming input rate flow control, an integrated routing and flow control algorithm is developed to optimize this fairness measure, and yet satisfy an overall average delay constraint. Open network model is used in the optimization. We then develop an approximate algorithm to optimize the same fairness measure and satisfy an overall average network delay constraint using this time window flow control. Closed network model and fixed routing are used in the optimization. The algorithm is computationally very efficient and provides nearly optimal solution. It provides guidelines for window selection so that for a given delay constraint, the optimal set of windows is readily available. Finally, the performance characteristics (delay, throughput and fairness) of a passive flow control known as backpressure are studied. Network performance under a combination of this control mechanism and window control is compared to that using window flow control alone. It is found that the combination of backpressure with window control is beneficial in that it provides a fair allocation of resources at heavy load.