Routing high-bandwidth traffic in max-min fair share networks

ABSTRACT

We study how to improve the throughput of high-bandwidth traffic such as large file transfers in a network where resources are fairly shared among connections. While it is possible to devise priority or reservation-based schemes that give high-bandwidth traffic preferential treatment at the expense of other connections, we focus on the use of routing algorithms that improve resource allocation while maintaining max-min fair share semantics. In our approach, routing is closely coupled with congestion control in the sense that congestion information, such as the rates allocated to existing connections, is used by the routing algorithm. To reduce the amount of routing information that must be distributed, an abstraction of the congestion information is introduced. Using an extensive set of simulation, we identify a link-cost or cost metric for "shortest-path" routing that performs uniformly better than the minimal-hop routing and shortest-widest path routing algorithms. To further improve throughput without reducing the fair share of single-path connections, we propose a novel prioritized multi-path routing algorithm in which low priority paths share the bandwidth left unused by higher priority paths. This leads to a conservative extension of max-min fairness called prioritized multi-level max-min fairness. Simulation results confirm the advantages of our multi-path routing algorithm.

REFERENCES

• 1: J.M. Akinpelu. The Overload Performance of Engineered Networks with Nonhierarchical and Hierachical Routing. Bell System Technical Journal, pages 1261- 1281, September 1984.
• 2: Saewoong Bahk , Magda El Zarki, Dynamic multi-path routing and how it compares with other dynamic routing algorithms for high speed wide area network, Conference proceedings on Communications architectures & protocols, p.53-64, August 17-20, 1992, Baltimore, Maryland, United States
• 3: Jochen Behrens , J. J. Garcia-Luna-Aceves, Distributed, scalable routing based on link-state vectors, Proceedings of the conference on Communications architectures, protocols and applications, p.136-147, August 31-September 02, 1994, London, United Kingdom
• 4: F. Bonomi and K. Fendick. The Rate-Based Flow Control Framework for the Available Bit Rate ATM Service. IEEE Network, 9(2):25-39, March/April 1995.
• 5: L. Breslau, D. Estrin, and L. Zhang. A Simulation Study of Adaptive Source Routing in Integrated Service Networks. USU USD Technical Report, Sep., 1993.
• 6: A. Charny, D.D. Clark, and R. Jain. Congestion Control With Explicit Rate Indication. In Proc, IUU'95, June 1995.
• 7: A. Charny, K.K. Ramakrishnan, and A. Lauck. Scalability Issues for Distributed Explicit Rate Allocation in ATM. In Proc, IEEE INFOCOM'96, 1996.
• 8: David D. Clark. Adding Service Discrimination to the Internet. Preprint, 1995.
• 9: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, ACM SIGCOMM Computer Communication Review, v.19 n.4, p.1-12, Sep. 1989
• 10: PNNI SWG Doug Dykeman (ed.). PNNI Draft Specification. ATM Forum 94-0471R10, October 1995.
• 11: E.W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numcrischc Mathcmatik, pages 1:269- 271, 1959.
• 12: A. Fraser. Towards a Universal Data Transport System. IEEE JSAU, pages 803-816, Nov 1983.
• 13: R.J. Gibbens, F.P. Kelley, and P.B. Key. Dynamic Alternative Routing- Modelling and Behaviour. In Proceedings of the 12th International Teletraffic Congress, June 1988.
• 14: J.M. Jaffe. Bottleneck flow control. IEEE Transactions on Communications, COM-29(7):954-962, July 1981. Correspondence.
• 15: R. Jain. The Art of Computer Performance Analysis. Wiley, 1991.
• 16: Kevin Lang , Satish Rao, Finding near-optimal cuts: an empirical evaluation, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.212-221, January 25-27, 1993, Austin, Texas, United States
• 17: J. Liebeherr, I.F. Akyildiz, and A. Tai. A Multi-level Explicit Rate Control Scheme for ABR Traffic with Heterogeneous Service Requirements. Submitted for Publication, July 1995.
• 18: J.M. McQuillan, I. Richer, and E. Rosen. The New Routing Algorithm for the ARPANET. IEEE Transactions on Communications, COM-28(5):711-719, May 1980.
• 19: D.J. Nelson, K. Sayood, and H. Chang. An Extended Least-hop Distributed Routing Algorithm. IEEE Transactions on Communications, COM-38(4):520- 528, April 1990.
• 20: M. Schwartz and T.E. Stern. Routing Techniques Used in Computer Communication Networks. IEEE Transactions on Communications, COM-28(4), April 1980.
• 21: S. Shenker, D.D. Clark, and L. Zhang. A Scheduling Service Model and a Scheduling Architecture for an Integrated Service Packet Network. preprint, 1993.
• 22: J. Sole-Pareta, D. Sarkar, J. Liebeherr, and I.F. Akyildiz. Adaptive Multipath Routing of Connectionless Traffic in an ATM Network. In Proc. IEEE ICC'95, May 1995.
• 23: M. Steenstrup. Inter-Domain Policy Routing Protocol Specification: Version 1. Technical Report Internet Draft, May 1992.
• 24: Hiroshi Suzuki , Fouad A. Tobagi, Fast bandwidth reservation scheme with multi-line & multi-path routing in ATM networks, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 3), p.2233-2240, May 1992, Florence, Italy
• 25: Z. Wang , J. Crowcroft, Shortest path first with emergency exits, Proceedings of the ACM symposium on Communications architectures & protocols, p.166-176, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 26: Z. Wang and J. Crowcroft. QoS Routing for Supporting Resource Reservation. IEEE JSAC, to appear 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Performance