Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

A novel scheme for processing packets in a router is presented that provides load sharing among multiple network processors distributed within the router. It is complemented by a feedback control mechanism designed to prevent processor overload. Incoming traffic is scheduled to multiple processors based on a deterministic mapping. The mapping formula is derived from the robust hash routing (also known as the highest random weight--HRW) scheme, introduced in K. W. Ross, IEEE Network, 11(6), 1997, and D. G. Thaler et al., IEEE Trans. Networking, 6(1), 1998. No state information on individual flow mapping has to be stored, but for each packet, a mapping function is computed over an identifier vector, a predefined set of fields in the packet. An adaptive extension to the HRW scheme is provided to cope with biased traffic patterns. We prove that our adaptation possesses the minimal disruption property with respect to the mapping and exploit that property to minimize the probability of flow reordering. Simulation results indicate that the scheme achieves significant improvements in processor utilization. A higher number of router interfaces can thus be supported with the same amount of processing power.

REFERENCES

• 1: [1] A. Asthana, C. Delph, H. V. Jagadish, and P. Krzyzanowski, "Towards a gigabit IP router," J. High Speed Netw., vol. 1, no. 4, pp. 281-288, 1992.
• 2: [2] "AIX-MAE West Interconnection at NASA Ames OC-3 Trace," National Laboratory for Applied Network Research (NLANR), Mar. 19, 2000 [Online]. Available: http://www.moat.nlanr.net/PMA/
• 3: [3] G. Barish and K. Obraczka, "World Wide Web caching: Trends and techniques," IEEE Commun. Mag., vol. 38, no. 5, pp. 178-184, May 2000.
• 4: 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]
• 5: [5] H. C. B. Chan, H. M. Alnuweiri, and V. C. M. Leung, "A framework for optimizing the cost and performance of next-generation IP routers," IEEE J. Sel. Areas Commun., vol. 17, no. 6, pp. 1013-1029, Jun. 1999.
• 6: [6] "Cisco Express Forwarding (CEF)," Cisco Systems, White Paper, 1997 [Online]. Available: http://www.cisco.com
• 7: [7] H. J. Chao, "Next generation routers," Proc. IEEE, vol. 90, no. 9, pp. 1518-1558, Sep. 2002.
• 8: 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]
• 9: Mark E. Crovella , Murad S. Taqqu , Azer Bestavros, Heavy-tailed probability distributions in the World Wide Web, A practical guide to heavy tails: statistical techniques and applications, Birkhauser Boston Inc., Cambridge, MA, 1998
• 10: [10] Z. Cao, Z. Wang, and E. W. Zegura, "Performance of hashing-based schemes for Internet load balancing," in Proc. IEEE INFOCOM, 2000, pp. 332-341.
• 11: Mikael Degermark , Andrej Brodnik , Svante Carlsson , Stephen Pink, Small forwarding tables for fast routing lookups, ACM SIGCOMM Computer Communication Review, v.27 n.4, p.3-14, Oct. 1997
• 12: Craig Partridge , Philip P. Carvey , Ed Burgess , Isidro Castineyra , Tom Clarke , Lise Graham , Michael Hathaway , Phil Herman , Allen King , Steve Kohalmi , Tracy Ma , John Mcallen , Trevor Mendez , Walter C. Milliken , Ronald Pettyjohn , John Rokosz , Joshua Seeger , Michael Sollins , Steve Storch , Benjamin Tober , Gregory D. Troxel, A 50-Gb/s IP router, IEEE/ACM Transactions on Networking (TON), v.6 n.3, p.237-248, June 1998 [doi>10.1109/90.700888]
• 13: F. Baker, Requirements for IP Version 4 Routers, RFC Editor, 1995
• 14: 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
• 15: Hesham El-Rewini , Hesham H. Ali , Ted Lewis, Task Scheduling in Multiprocessing Systems, Computer, v.28 n.12, p.27-37, December 1995 [doi>10.1109/2.476197]
• 16: [16] G. C. Fedorkow, "Cisco 10000 Edge Services Router (ESR) Technology Overview," 2000 [Online]. Available: http://www.cisco.com
• 17: [17] G. Goldszmidt and G. Hunt, "Scaling Internet services by dynamic allocation of connections," in Proc. 6th IFIP/IEEE Int. Symp. Integrated Network Management, May 1999, pp. 171-184.
• 18: [18] R. Jain, The Art of Computer Systems Performance Analysis. New York: Wiley, 1991.
• 19: [19] A. Jayasumana, "Reorder density and reorder buffer-occupancy density metrics for packet reordering measurements," Internet Draft draft-jayasumana-reorder-density-06.txt, 2006.
• 20: [20] V. P. Kumar, T. V. Lakshman, and D. Stilliadis, "Beyond best effort: Router architectures for the differentiated services of tomorrow's Internet," IEEE Commun. Mag., pp. 152-164, May 1998.
• 21: 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
• 22: [22] O. G. Koufopavlou, A. N. Tantawy, and M. Zitterbart, "Analysis of TCP/IP for high performance parallel implementations," presented at the 17th IEEE Conf. Local Computer Networks, Minneapolis, MN, Sep. 1992.
• 23: Thomas Kunz, The Influence of Different Workload Descriptions on a Heuristic Load Balancing Scheme, IEEE Transactions on Software Engineering, v.17 n.7, p.725-730, July 1991 [doi>10.1109/32.83908]
• 24: [24] A. Morton, L. Ciavattone, G. Ramachandran, S. Shalunov, and J. Perser, "Packet reordering metric for IPPM," Internet Draft draft-ietf-ippm-reordering-13.txt, 2006.
• 25: K. McCloghrie , M. T. Rose, Management Information Base for Network Management of TCP/IP-based internets:MIB-II, RFC Editor, 1991
• 26: [26] Juniper Networks, Product Portfolio. [Online]. Available: www.juniper.net/products/
• 27: S. Nilsson , G. Karlsson, Fast address look-up for internet routers, Proceedings of the IFIP TC6/WG6.2 Fourth International Conference on Broadband Communications: The future of telecommunications, p.11-22, April 01-03, 1998
• 28: [28] "WAN Traffic Distribution by Address Size, Fix-West Trace," National Laboratory for Applied Network Research (NLANR), May 1997 [On-line]. Available: http://www.nlanr.net/NA/Learn/Class
• 29: [29] M. Przybylski, B. Belter, and A. Binczewski, "Shall we worry about packet reordering?," in TERENA Networking Conf., Poznan, Poland, Jun. 2005.
• 30: [30] R. Russo, L. Kencl, B. Metzler, and P. Droz, "Scalable and adaptive load balancing on IBM PowerNP," IBM Zurich Research Lab., Research Report RZ 3431, Jul. 2002.
• 31: [31] K. W. Ross, "Hash routing for collections of shared web caches," IEEE Network, vol. 11, no. 6, pp. 37-44, Nov.-Dec. 1997.
• 32: [32] C. Semeria, "Internet backbone routers and evolving Internet design," Juniper Networks White Paper, Sep. 1999 [Online]. Available: http:// www.juniper.net
• 33: Behrooz A. Shirazi , Krishna M. Kavi , Ali R. Hurson, Scheduling and Load Balancing in Parallel and Distributed Systems, IEEE Computer Society Press, Los Alamitos, CA, 1995
• 34: 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]
• 35: 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
• 36: [36] Routers for Service Providers. Cisco Systems [Online]. Available: http://www.cisco.com/en/US/products/hw/routers/
• 37: [37] K. Thompson, G. J. Miller, and R. Wilder, "Wide-area Internet traffic patterns and characteristics," IEEE Network, vol. 11, no. 6, pp. 10-27, Nov.-Dec. 1997.
• 38: 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]
• 39: [39] J. Turner and T. Wolf, "Design issues for high performance active routers," IEEE J. Sel. Areas Commun., vol. 19, no. 3, pp. 404-409, Mar. 2001.
• 40: Ahmed N. Tantawy , Martina Zitterbart, Multiprocessing in High Performance IP Routers, Proceedings of the IFIP WG6.1/WG6.4 Third International Workshop on Protocols for High-Speed Networks III, p.235-254, May 13-15, 1992
• 41: Yin Zhang , Lee Breslau , Vern Paxson , Scott Shenker, On the characteristics and origins of internet flow rates, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 42: [42] G. K. Zipf, Human Behavior and the Principle of Least-Effort. Cambridge, MA: Addison-Wesley, 1949.
• 43: Huican Zhu , Tao Yang , Qi Zheng , David Watson , Oscar H. Ibarra , Terence Smith, Adaptive Load Sharing for Clustered Digital Library Servers, Proceedings of the 7th IEEE International Symposium on High Performance Distributed Computing, p.235, July 28-31, 1998

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Design, Management, Performance

Keywords:
computer networks, feedback control, load balancing, load sharing, packet processing, router architecture