Sequence-preserving adaptive load balancers

ABSTRACT

Load balancing in packet-switched networks is a task of ever-growing importance. Network traffic properties, such as the Zipf-like flow length distribution and bursty transmission patterns, and requirements on packet ordering or stable flow mapping, make it a particularly difficult and complex task, needing adaptive heuristic solutions. In this paper, we present two main contributions:Firstly, we evaluate and compare two recently proposed algorithmic heuristics that attempt to adaptively balance load among the destination units. The evaluation on real life traces confirms the previously conjectured impact of the Zipf-like flow length distribution and traffic burstiness. Furthermore, we identify the distinction between the goals of preserving either the sequence order of packets, or the flow-to-destination mapping, showing different strengths of each algorithm. Secondly, we demonstrate a novel hybrid scheme that combines best of the flow-based and burst-based load balancing techniques and excels in both of the key metrics of flow remapping and packet reordering.

REFERENCES

• 1: Hari Adiseshu , Guru Parulkar , George Varghese, A reliable and scalable striping protocol, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.131-141, August 28-30, 1996, Palo Alto, California, United States
• 2: Jon C. R. Bennett , Craig Partridge , Nicholas Shectman, Packet reordering is not pathological network behavior, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.789-798, Dec. 1999 [doi>10.1109/90.811445]
• 3: Z. Cao, Z. Wang, and E. Zegura. Performance of hashing-based schemes for Internet load balancing. In IEEE INFOCOM 2000, pages 332--341, Tel-Aviv, Israel, March 2000.
• 4: T. L. Casavant , J. G. Kuhl, A taxonomy of scheduling in general-purpose distributed computing systems, IEEE Transactions on Software Engineering, v.14 n.2, p.141-154, February 1988 [doi>10.1109/32.4634]
• 5: Douglas E. Comer, Network Systems Design with Network Processors, Agere Version, Prentice-Hall, Inc., Upper Saddle River, NJ, 2004
• 6: G. Dittmann and A. Herkersdorf. Network processor load balancing for high-speed links. In 2002 International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS 2002), pages 727--735, San Diego, CA, USA, July 2002.
• 7: Derek L. Eager , Edward D. Lazowska , John Zahorjan, Adaptive load sharing in homogeneous distributed systems, IEEE Transactions on Software Engineering, v.12 n.5, p.662-675, May 1986
• 8: R. Haas, P. Droz, L. Kencl, A. Kind, B. Metzler, C. Jeffries, R. Pletka, and M. Waldvogel. Creating advanced functions on network processors: Experience and perspectives. IEEE Network, 2003.
• 9: J. Jo, Y. Kim, H. Chao, and F. Merat. Internet traffic load balancing using dynamic hashing with flow volumes. In Internet Performance and Control of Network Systems III at SPIE ITCOM 2002, pages 154--165, Boston, MA, USA, July 2002.
• 10: L. Kencl and J.-Y. L. Boudec. Adaptive load sharing for network processors. In Proceedings of IEEE Infocom, New York, 2002.
• 11: M. Laor and L. Gendel. The effect of packet reordering in a backbone link on application throughput. IEEE Network, 16(5):28--36, 2002.
• 12: A. Moore, J. Hall, E. Harris, C. Kreibich, and I. Pratt. Architecture of a network monitor. In Proceedings of the Fourth Passive and Active Measurement (PAM)Workshop, April 2003.
• 13: NLANR (National Laboratory for Applied Network Research) Measurement and Operations Analysis Team (MOAT). Packet header traces. http://moat.nlanr.net.
• 14: K. W. Ross. Hash routing for collections of shared Web caches. IEEE Network ,11(7):37--44, Nov-Dec 1997.
• 15: Shriram Sarvotham , Rudolf Riedi , Richard Baraniuk, Connection-level analysis and modeling of network traffic, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505215]
• 16: Anees Shaikh , Jennifer Rexford , Kang G. Shin, Load-sensitive routing of long-lived IP flows, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.215-226, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 17: W. Shi, M. H. MacGregor, and P. Gburzynski. Traffic locality charateristics in a parallel forwarding system. International Journal of Communication Systems, 16(9):823--839, November 2003.
• 18: Weiguang Shi , M. H. MacGregor , Pawel Gburzynski, Load balancing for parallel forwarding, IEEE/ACM Transactions on Networking (TON), v.13 n.4, p.790-801, August 2005 [doi>10.1109/TNET.2005.852881]
• 19: Weiguang Shi , Mike H. MacGregor , Pawel Gburzynski, A scalable load balancer for forwarding internet traffic: exploiting flow-level burstiness, Proceedings of the 2005 symposium on Architecture for networking and communications systems, October 26-28, 2005, Princeton, NJ, USA [doi>10.1145/1095890.1095911]
• 20: S. Sinha, S. Kandula, and D. Katabi. Harnessing TCP 's burstiness with flowlet switching. In HotNets 2004, San Diego, CA, USA, November 2004.
• 21: Jeffrey R. Spirn, Program Behavior: Models and Measurements, Elsevier Science Inc., New York, NY, 1977
• 22: David G. Thaler , Chinya V. Ravishankar, Using name-based mappings to increase hit rates, IEEE/ACM Transactions on Networking (TON), v.6 n.1, p.1-14, Feb. 1998 [doi>10.1109/90.663936]
• 23: G. K. Zipf. Human Behavior and the Principle of Least-Effort. Addison-Wesley, Cambridge, MA, 1949.

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
adaptive methods, load balancing, multiprocessor systems