Approximating max-min fair rates via distributed local scheduling with partial information
Alain J. Mayer, Y. Ofek, Moti M. Yung · 2002
Max-min fairness has been recognized as an optimal throughput-fairness definition. However, its realization in packet switching networks and its computational requirements have not yet been understood. We attempt to take a step in this direction, in the context of local area network (LAN) traffic. The max-min definition is given in terms of transmission rates of sources sending to their destinations (sessions). In order to realize max-min rates in a packet switching environment, transmission schedules of packets need to be realized. We first show that finding max-min fair schedules (with given rates) requires global state and timing information of all the nodes in the network. We then design a local scheduling algorithm for ring and bus networks with minimum transmission-delay, concurrent access, and spatial bandwidth reuse. This distributed algorithm uses only partial state information and is based on locally exchanging simple signals only between directly conflicting sessions (sessions which share at least one link) rather than collecting global information. The results of this algorithm are novel in various ways: (1) we prove that each session has an access-delay of at most twice its bottleneck link; (2) we show that the algorithm operates adaptively with an optimal access-delay in a dynamic environment (bursty traffic sources); and (3) by means of simulation experiments we further show that this algorithm achieves, in a steady-state, max-min fair rates for a vast majority of sessions and an average aggregate throughput which is 99 percent the throughput obtained by max-min fair rates.