An Adaptive Load Balancer for Multiprocessor Routers Keywords: Workload Modeling, Parallel Forwarding, Hashing, Load Balancing

By investigating flow level characteristics of Internet traffic, we are able to trace the root of load imbalance in hash-based load-splitting schemes. We model flow popularity distributions of flows as Zipf-like and prove that under typical Internet traffic mix, a hash scheme cannot balance workload statistically, not even in the long run. We then develop a novel load-balancing packet scheduler for parallel forwarding systems. Our scheduler capitalizes on the non-uniform flow reference pattern and especially the presence of a few high-rate flows in Internet traffic. We show that detecting and scheduling these flows can be very effective in balancing workloads among network processors. We introduce an important metric, adaptation disruption, for load balancing mechanisms in parallel forwarding systems. Since the number of large flows is small, reassigning them in our load balancer makes low disruption to the states of individual processors. Our ideas are validated by simulation results.