tocLoad Balancing for Parallel ForwardingWeiguang Shi, M. H. MacGregor, Senior Member, IEEE, and Pawel GbI. I NTRODUCTIONFig.€1. Multi-processor forwarding system.II. R ELATED W ORKIII. S YSTEM M ODELIV. S OURCES OF L OAD I MBALANCEA. Hash FunctionB. Burstiness of Internet TrafficC. Skewed Flow Size Distribution1) Flow-Level Internet Traffic Characteristics: To study flow le2) Implications for Load Balancing: The flow size distribution aTABLE I T RACES U SED IN E XPERIMENTSFig.€2. IP address popularity distribution follows Zipf's law.TABLE II N umber OF P ACKETS OF 10 L ARGEST F LOWS IN THE T RACEV. L OAD B ALANCERA. GoalsB. DesignFig.€3. Load balancing packet scheduler.C. Triggering PoliciesVI. D ETECTING A GGRESSIVE F LOWSA. Definition of Aggressive FlowsB. Detecting Aggressive FlowsFig.€4. Effects of $W$ on $\Delta (F=5)$ .TABLE III A RRIVAL R ATES (N umber OF P ACKETS /S ECOND ) OF F OVII. S IMULATIONSA. Trace Driven SimulationB. Hash SplitterC. Triggering PoliciesD. Adaptation DisruptionE. Packet Reordering and LossFig.€5. Loss Rate vs Buffer Size (For PM, BOT, and MQLT, the sysF. Simulation ResultsFig.€6. Loss rate versus buffer size (with the IPLS trace).Fig.€7. Adaptation disruption versus buffer size (the same settiFig.€8. Loss rate versus checking period. (The buffer size is 40Fig.€9. Adaptation disruption versus checking period (the same sFig.€10. The effectiveness of scheduling more aggressive flows. Fig.€11. The effects of scheduling more flows on adaptation disrFig.€12. The effects of scheduling more flows on packet reorderiTABLE IV C OMPARISON B ETWEEN S HIFTING O NLY THE M OST A GGRESSVIII. C ONCLUSIONJ. Bennett, C. Partridge, and N. Shectman, Packet reordering is E. Blanton and M. Allman, On making TCP more robust to packet reW. Shi, M. H. MacGregor, and P. Gburzynski, Effects of a hash-baR. Jain, A comparison of hashing schemes for address lookup in cD. G. Thaler and C. V. Ravishankar, Using name-based mappings toZ. Cao, Z. Wang, and E. Zegura, Performance of hashing-based schG. Dittmann and A. Herkersdorf, Network processor load balancingL. Kencl and J. L. Boudec, Adaptive load sharing for network proL. Kencl, Load Sharing for Multiprocessor Network Nodes, Ph.D. dL. Guo and I. Matta, The war between mice and elephants, in ProcN. Brownlee and K. Claffy, Understanding Internet traffic streamS. Sarvotham, R. Riedi, and R. Baraniuk, Connection-level analysW. Shi, M. H. MacGregor, and P. Gburzynski, Synthetic trace geneG. K. Zipf, Human Behavior and the Principle of Least-Effort . CS. Nilsson and G. Karlsson, IP-address lookup using LC-tries, IEPacket Header Traces . NLANR (National Laboratory for Applied NeP. Newman, G. Minshall, and L. Huston, IP switching and gigabit Y. Rekhter, B. Davie, E. Rosen, G. Swallow, D. Farinacci, and D.A. Feldmann, J. Rexford, and R. Cáceres, Efficient policies for A. Shaikh, J. Rexford, and K. G. Shin, Load-sensitive routing ofM. Colajanni, P. S. Yu, and D. M. Dias, Analysis of task assignmK. W. Ross, Hash routing for collections of shared web caches, ID. E. Knuth, The Art of Computer Programming: Sorting and SearchR. Jain and S. Routhier, Packet trains: Measurements and a new m790 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 13, NO. 4, AUGUST 2005Load Balancing for Parallel ForwardingWeiguang Shi, M. H. MacGregor, Senior Member, IEEE, and Pawel GburzynskiAbstract—Workload distribution is critical to the performanceof network processor based parallel forwarding systems. Sched-uling schemes that operate at the packet level, e.g., round-robin,cannot preserve packet-ordering within individual TCP connec-tions. Moreover, these schemes create duplicate information in pro-cessor caches and therefore are inefficient in resource utilization.Hashing operates at the flow level and is naturally able to maintainper-connection packet ordering; besides, it does not pollute caches.A pure hash-based system, however, cannot balance processor loadin 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, weexamine the sources of load imbalance in hash-based schedulingschemes. We prove that under certain Zipf-like flow-size distribu-tions, hashing alone is not able to balance workload. We introducea new metric to quantify the effects of adaptive load balancing onoverall forwarding performance. To achieve both load balancingand efficient system resource utilization, we propose a schedulingscheme that classifies Internet flows into two categories: the ag-gressive and the normal, and applies different scheduling policiesto the two classes of flows. Compared with most state-of-the-artparallel forwarding schemes, our work exploits flow-level Internettraffic characteristics.Index Terms—Load balancing, parallel IP forwarding, Zipf-likedistribution.I. INTRODUCTIONTOGETHER, the continuing Internet bandwidth explosionand the advent of new applications have created great chal-lenges for network forwarding devices, e.g., Internet routers.They have to offer high throughput, computation power, as wellas flexibility. One answer to these challenges is network pro-cessors (NP) which provide the right balance between perfor-mance and flexibility. (In this paper, we use the two terms,for-warding engine (FE) and NP, interchangeably.) To achieve highthroughput, NPs are optimized for key packet forwarding al-gorithms and high-speed I/O. More importantly, multiple net-work processors are employed to forward packets in parallel toachieve scalability.Although designs from vendors vary, Fig. 1 shows a gen-eralized conceptual model where the forwarding engines arethe basic packet processing units. Essential to such a multi-FEsystem is the scheduler that dispatches incoming packets to theFEs. It is necessary for the scheduler to distribute workload ina balanced manner so that the system can achieve its full for-warding potential. In this paper, we divide a scheduler into twoManuscript received June 3, 2003; revised February 20, 2004, May 4,2004, and August 20, 2004; approved by IEEE/ACM TRANSACTIONS ONNETWORKING Editor K. Ross.The authors are with the Department of Computing Science, University ofAlberta, Edmonton, AB, T6G 2E8, Canada (e-mail: [email protected];[email protected]; [email protected]).Digital Object Identifier 10.1109/TNET.2005.852881Fig. 1. Multi-processor forwarding system.functional units: the load splitter and the