Load balancing for parallel forwarding

ABSTRACT

Workload distribution is critical to the performance of network processor based parallel forwarding systems. Scheduling schemes that operate at the packet level, e.g., round-robin, cannot preserve packet-ordering within individual TCP connections. Moreover, these schemes create duplicate information in processor caches and therefore are inefficient in resource utilization. Hashing operates at the flow level and is naturally able to maintain per-connection packet ordering; besides, it does not pollute caches. A pure hash-based system, however, cannot balance processor load in the face of highly skewed flow-size distributions in the Internet; usually, adaptive methods are needed.In this paper, based on measurements of Internet traffic, we examine the sources of load imbalance in hash-based scheduling schemes. We prove that under certain Zipf-like flow-size distributions, hashing alone is not able to balance workload. We introduce a new metric to quantify the effects of adaptive load balancing on overall forwarding performance. To achieve both load balancing and efficient system resource utilization, we propose a scheduling scheme that classifies Internet flows into two categories: the aggressive and the normal, and applies different scheduling policies to the two classes of flows. Compared with most state-of-the-art parallel forwarding schemes, our work exploits flow-level Internet traffic characteristics.

REFERENCES

• 1: 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]
• 2: Ethan Blanton , Mark Allman, On making TCP more robust to packet reordering, ACM SIGCOMM Computer Communication Review, v.32 n.1, p.20-30, January 2002 [doi>10.1145/510726.510728]
• 3: {3} W. Shi, M. H. MacGregor, and P. Gburzynski, "Effects of a hash-based scheduler on cache performance in a parallel forwarding system," in Proc. Communication Networks and Distributed Systems Modeling and Simulation Conf. (CNDS'2003), Orlando, FL, Jan. 2003, pp. 130-138.
• 4: {4} R. Jain, "A comparison of hashing schemes for address lookup in computer networks," IEEE Trans. Commun., vol. 40, no. 3, pp. 1570-1573, Oct. 1992.
• 5: 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]
• 6: {6} Z. Cao, Z. Wang, and E. Zegura, "Performance of hashing-based schemes for Internet load balancing," in Proc. IEEE INFOCOM, Tel-Aviv, Israel, Mar. 2000, pp. 332-341.
• 7: {7} G. Dittmann and A. Herkersdorf, "Network processor load balancing for high-speed links," in Proc. Int. Symp. Performance Evaluation of Computer and Telecommunication Systems (SPECTS'2002), San Diego, CA, Jul. 2002, pp. 727-735.
• 8: {8} L. Kencl and J. L. Boudec, "Adaptive load sharing for network processors," in Proc. IEEE INFOCOM, New York, Jun. 2002, pp. 545-554.
• 9: {9} L. Kencl, "Load Sharing for Multiprocessor Network Nodes," Ph.D. dissertation, Swiss Federal Institute of Technology (EPFL), Jan. 2003.
• 10: The War between Mice and Elephants, Proceedings of the Ninth International Conference on Network Protocols, p.180, November 11-14, 2001
• 11: {11} N. Brownlee and K. Claffy, "Understanding Internet traffic streams: Dragonflies and tortoises," IEEE Commun., vol. 40, no. 10, pp. 110-117, Oct. 2002.
• 12: 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]
• 13: {13} W. Shi, M. H. MacGregor, and P. Gburzynski, "Synthetic trace generation for the Internet: An integrated model," in Proc. SPECTS'04, San Jose, CA, Jul. 2004, pp. 471-477.
• 14: {14} G. K. Zipf, Human Behavior and the Principle of Least-Effort. Cambridge, MA: Addison-Wesley, 1949.
• 15: {15} S. Nilsson and G. Karlsson, "IP-address lookup using LC-tries," IEEE J. Sel. Areas Commun., vol. 17, no. 6, pp. 1083-1092, Jun. 1997.
• 16: {16} Packet Header Traces. NLANR (National Laboratory for Applied Network Research) Measurement and Operations Analysis Team (MOAT). {Online}. Available: http://moat.nlanr.net
• 17: {17} P. Newman, G. Minshall, and L. Huston, "IP switching and gigabit routers," IEEE Commun. Mag., vol. 35, no. 1, pp. 64-68, Jan. 1997.
• 18: {18} Y. Rekhter, B. Davie, E. Rosen, G. Swallow, D. Farinacci, and D. Datz, "Tag switching architecture overview," Proc. IEEE, vol. 85, no. 12, pp. 1973-1983, Dec. 1997.
• 19: Anja Feldmann , Jennifer Rexford , Ramón Cáceres, Efficient policies for carrying Web traffic over flow-switched networks, IEEE/ACM Transactions on Networking (TON), v.6 n.6, p.673-685, Dec. 1998 [doi>10.1109/90.748081]
• 20: Anees Shaikh , Jennifer Rexford , Kang G. Shin, Load-sensitive routing of long-lived IP flows, ACM SIGCOMM Computer Communication Review, v.29 n.4, p.215-226, Oct. 1999
• 21: Michele Colajanni , Philip S. Yu , Daniel M. Dias, Analysis of Task Assignment Policies in Scalable Distributed Web-Server Systems, IEEE Transactions on Parallel and Distributed Systems, v.9 n.6, p.585-600, June 1998 [doi>10.1109/71.689446]
• 22: {22} K. W. Ross, "Hash routing for collections of shared web caches," IEEE Network, vol. 11, no. 7, pp. 37-44, Nov.-Dec. 1997.
• 23: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 24: {24} R. Jain and S. Routhier, "Packet trains: Measurements and a new model for computer network traffic," IEEE J. Sel. Areas Commun., vol. SAC-4, no. 6, pp. 986-995, Sep. 1986.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance

Keywords:
Zipf-like distribution, load balancing, parallel IP forwarding