Adaptive Load Sharing for Network Processors

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. \emph{No state information} on individual flow mapping has to be stored, but for each packet, a mapping function is computed over an \emph{identifier vector}, a predefined set of fields in the packet. An \emph{adaptive extension} to the HRW scheme is provided to cope with biased traffic patterns. We prove that our adaptation possesses the \emph {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.