Workload modeling and performance evaluation for Internet forwarding systems

The exponential growth of the Internet has presented great challenges for its infrastructure. Moreover, the rapid pace of the innovations in Internet applications mandates that the routers that forward packets between networks offer not only high throughput but also huge computation power and maximum flexibility.; In this thesis, we are concerned with the design and performance evaluation of Internet forwarding systems. We attack system performance problems through the study of its workload characteristics, which leads to sound system designs.; First, we characterize temporal locality in router workloads. Temporal locality is critical to cache performance and thus important to overall forwarding system throughput. We derive a mixed distribution which combines the Weibull and Pareto distributions and accurately captures the locality in destination IP address sequences of Internet traffic. Our model is generative; synthetic traffic can be produced with projected temporal locality.; Second, we show that flow popularity characteristics have a significant impact, on load balancing in a parallel forwarding system where a hash-based scheduler dispatches incoming packets to individual forwarding engines. We model the flow popularity distribution using Zipf-like distributions and develop a scheme to incorporate large flows into the generative model that captures temporal locality.; Third, we further explore performance implications of flow-level Internet traffic characteristics and develop a highly efficient and effective packet scheduling scheme for parallel forwarding system load balancing. We find that under certain Zipf-like distributions, hash-based scheduling scheme alone can not achieve load balance for a parallel forwarding system. The presence of a few dominating flows in Internet traffic has motivated us to develop a novel load balancer that capitalizes on this phenomenon by scheduling these high-rate flows to balance workload among the forwarding engines in a parallel forwarding system. The effectiveness of our scheme is demonstrated via simulation.