skip to main content
article

Adaptive load sharing for network processors

Published: 02 April 2008 Publication History

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]
{4} J. Bennett, C. Partridge, and N. Shectman, "Packet reordering is not pathological network behavior," IEEE ACM Trans. Networking, vol. 7, no. 6, pp. 789-798, Dec. 1999.
[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]
{8} T. L. Casavant and J. G. Kuhl, "A taxonomy of scheduling in general-purpose distributed computing systems," IEEE Trans. Software Eng., vol. 14, no. 2, pp. 141-154, Feb. 1988.
[9]
{9} M. Crovella, M. Taqqu, and A. Bestavros, "Heavy-tailed probability distributions in the World Wide Web," in A Practical Guide to Heavy Tails. New York: Chapman & Hall, 1998, ch. 1, pp. 3-26.
[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]
{11} M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, "Small forwarding tables for fast routing lookups," ACM Comput. Commun. Rev., vol. 27, no. 4, pp. 3-14, Oct. 1997.
[12]
{12} C. Partridge et al., "A fifty gigabit per second IP router," IEEE/ACM Trans. Networking, vol. 6, no. 3, pp. 237-248, Jun. 1998.
[13]
{13} F. Baker, Ed., "Requirements for IP Version 4 routers," IETF RFC 1812, Jun. 1995.
[14]
{14} D. L. Eager, E. D. Lazowska, and J. Zahorjan, "Adaptive load sharing in homogenous distributed systems," IEEE Trans. Software Eng., vol. 12, no. 5, pp. 662-675, May 1986.
[15]
{15} H. El-Rewini, H. H. Ali, and T. Lewis, "Task scheduling in multiprocessing systems," IEEE Computer, vol. 28, no. 12, pp. 27-37, Dec. 1995.
[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]
{21} D. E. Knuth, Sorting and Searching, The Art of Computer Programming , 2nd ed. Cambridge, MA: Addison-Wesley, 1998, vol. 3.
[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]
{23} T. Kunz, "The influence of different workload descriptions on a heuristic load balancing scheme," IEEE Trans. Software Eng., vol. 17, no. 7, pp. 725-730, Jul. 1991.
[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]
{25} K. McCloghrie and M. T. Rose, "Management information base for network management of TCP/IP-Based Internets: MIB-II," IETF RFC 1213, Mar. 1991.
[26]
{26} Juniper Networks, Product Portfolio. {Online}. Available: www.juniper.net/products/
[27]
{27} S. Nilsson and G. Karlsson, "Fast address lookup for Internet router," in Proc. IFIP 4th Int. Conf. Broadband Communications, 1998, pp. 11-22.
[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]
{33} B. A. Shirazi, A. R. Hurson, and K. M. Kavi, Eds., Scheduling and Load Balancing in Parallel and Distributed Systems. New York: IEEE Computer Soc. Press, 1995.
[34]
{34} W. Shi, M. H. MacGregor, and P. Gburzynski, "Load balancing for parallel forwarding," IEEE ACM Trans. Networking, vol. 13, no. 4, 2005.
[35]
{35} A. Shaikh, J. Rexford, and K. G. Shin, "Load-sensitive routing of long-lived IP flows," in ACM SIGCOMM'99, Cambridge, MA, Sep. 1999.
[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]
{38} D. G. Thaler and C. V. Ravishankar, "Using name-based mappings to increase hit rates," IEEE/ACM Trans. Networking, vol. 6, no. 1, pp. 1-14, Feb. 1998.
[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]
{40} A. Tantawy and M. Zitterbart, "Multiprocessing in high performance IP routers," in 3rd IFIP WG 6.1/6.4 Workshop on Protocols for High Speed Networks, Stockholm, Sweden, May 1992.
[41]
{41} Y. Zhang, L. Breslau, V. Paxson, and S. Shenker, "On the characteristics and origins of Internet flow rates," in ACM SIGCOMM'02, Pittsburgh, PA, Aug. 2002.
[42]
{42} G. K. Zipf, Human Behavior and the Principle of Least-Effort. Cambridge, MA: Addison-Wesley, 1949.
[43]
{43} H. Zhu, T. Yang, Q. Zheng, D. Watson, O. H. Ibarra, and T. Smith, "Adaptive load sharing for clustered digital library servers," in Proc. 7th Int. Symp. High Performance Distributed Computing, Jul. 1998, pp. 235-242.

Cited By

View all
  • (2019)Self-adaptive load-balancing strategy based on a time series pattern for concurrent user access on Web map serviceComputers & Geosciences10.1016/j.cageo.2019.06.015131:C(60-69)Online publication date: 1-Oct-2019
  • (2018)Polymorphic Load Balancing Algorithm Based on Packet ClassificationProceedings of the 2nd International Conference on Telecommunications and Communication Engineering10.1145/3291842.3291911(258-261)Online publication date: 28-Nov-2018
  • (2018)Flow-based load-balancing architecture for the agile all-photonic networkPhotonic Network Communications10.1007/s11107-011-0360-924:1(1-11)Online publication date: 16-Dec-2018
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 16, Issue 2
April 2008
244 pages

Publisher

IEEE Press

Publication History

Published: 02 April 2008
Published in TON Volume 16, Issue 2

Author Tags

  1. computer networks
  2. feedback control
  3. load balancing
  4. load sharing
  5. packet processing
  6. router architecture

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2019)Self-adaptive load-balancing strategy based on a time series pattern for concurrent user access on Web map serviceComputers & Geosciences10.1016/j.cageo.2019.06.015131:C(60-69)Online publication date: 1-Oct-2019
  • (2018)Polymorphic Load Balancing Algorithm Based on Packet ClassificationProceedings of the 2nd International Conference on Telecommunications and Communication Engineering10.1145/3291842.3291911(258-261)Online publication date: 28-Nov-2018
  • (2018)Flow-based load-balancing architecture for the agile all-photonic networkPhotonic Network Communications10.1007/s11107-011-0360-924:1(1-11)Online publication date: 16-Dec-2018
  • (2017)Minimizing Communication Overhead in Window-Based Parallel Complex Event ProcessingProceedings of the 11th ACM International Conference on Distributed and Event-based Systems10.1145/3093742.3093914(54-65)Online publication date: 8-Jun-2017
  • (2017)Robust dynamic network traffic partitioning against malicious attacksJournal of Network and Computer Applications10.1016/j.jnca.2016.04.01387:C(20-31)Online publication date: 1-Jun-2017
  • (2014)Dynamic core affinity for high-performance file upload on Hadoop Distributed File SystemParallel Computing10.1016/j.parco.2014.07.00540:10(722-737)Online publication date: 1-Dec-2014
  • (2012)An efficient parallelized L7-filter design for multicore serversIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2011.217785820:5(1426-1439)Online publication date: 1-Oct-2012
  • (2011)E-AHRWProceedings of the 2011 ACM/IEEE Seventh Symposium on Architectures for Networking and Communications Systems10.1109/ANCS.2011.15(45-56)Online publication date: 3-Oct-2011
  • (2009)A Novel Multipath Load Balancing Algorithm in Fat-Tree Data CenterProceedings of the 1st International Conference on Cloud Computing10.1007/978-3-642-10665-1_37(405-412)Online publication date: 22-Nov-2009
  • (2009)A Buffer Space Optimal Solution for Re-establishing the Packet Order in a MPSoC Network ProcessorProceedings of the 15th International Euro-Par Conference on Parallel Processing10.1007/978-3-642-03869-3_23(216-227)Online publication date: 23-Aug-2009

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media