This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Shi, W. Articles by Gburzynski, P. Search for Related Content Social Bookmarking                         What's this?

An Adaptive Load Balancer for Multiprocessor Routers

Department of Computing Science University of Alberta Edmonton, AB, T6G 2E8, Canada, wgshi{at}cs.ualberta.ca

M. H. MacGregor

Department of Computing Science University of Alberta Edmonton, AB, T6G 2E8, Canada

P. Gburzynski

Department of Computing Science University of Alberta Edmonton, AB, T6G 2E8, Canada

By investigating flow-level characteristics of Internet traffic, the authors are able to trace the root of load imbalance in hash-based load-splitting schemes. They model flow popularity distributions as Zipf-like and prove that for typical Internet traffic, a hashing scheme cannot balance workload statistically, not even in the long run. They then develop a novel load-balancing packet scheduler for parallel forwarding systems. The scheduler capitalizes on the nonuniform flow reference pattern and especially the presence of a few high-rate flows in Internet traffic. The authors show that detecting and scheduling these flows can be very effective in balancing workloads among network processors. They introduce an important metric, adaptation disruption, to measure the scheduling efficiency of load-balancing mechanisms in parallel forwarding systems. Because there are relatively few large flows, reassigning them in the load balancer results in little disruption to the states of individual processors. The ideas are validated by simulation results. Finally, the authors discuss the effects on cache performance when classifying flows using two different flow definitions: the destination IP address and the five-tuple. The latter results in finer flow granularity but worse route cache hit rate, which can lead to the degradation of routing table lookup performance.

Key Words: Workload modeling • parallel forwarding • hashing • load balancing

SIMULATION, Vol. 82, No. 3, 173-192 (2006)
DOI: 10.1177/0037549706067079


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?