A Uniform Fine-Grain Frame Spreading Algorithm for Avoiding Packet Reordering in Load-Balanced Switches

Network operators need high capacity router architectures that can offer scalability, provide throughput guarantees, and maintain packet ordering. However, current centralized crossbar-based architectures cannot scale to fast line rates and high port counts. On the other hand, while load-balanced switch architectures that rely on two identical stages of fixed configuration meshes appear to be an effective way to scale Internet routers to very high capacities, they incur a large worst-case packet reordering that is at best quadratic to the switch size. In this paper, we propose a Uniform Fine-grain Frame Spreading (UFFS) algorithm to avoid packet reordering throughout the load-balanced switch by assigning cells of the same flow to the fixed successive intermediate inputs. In order to distribute traffic equally among the intermediate inputs, a rotation mapping algorithm is used to construct a fixed mapping relationship between flows of different inputs and intermediate inputs in a round-robin fashion. The UFFS algorithm is distributed and can operate independently in each input. It spreads each flow to intermediate inputs according to the mapping relationship that is precomputed by the rotation mapping algorithm. We show that the UFFS algorithm can enforce packet ordering and achieve 100 % throughput with no additional communication of information among linecards.