Title :
A Uniform Fine-Grain Frame Spreading Algorithm for Avoiding Packet Reordering in Load-Balanced Switches
Author :
Dai, Yi ; Su, Jin-Shu ; Sun, Zhi-Gang ; Guan, Jian-bo
Author_Institution :
Nat. Univ. of Defense Technol., Changsha
Abstract :
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.
Keywords :
packet switching; resource allocation; centralized crossbar-based architecture; fixed mapping relationship; high capacity router architecture; load-balanced switch architecture; load-balanced switches; network operators; packet reordering; rotation mapping; uniform fine-grain frame spreading algorithm; Communication switching; Computer architecture; Internet; Packet switching; Round robin; Scalability; Scheduling algorithm; Switches; Throughput; Traffic control;
Conference_Titel :
Asia-Pacific Service Computing Conference, The 2nd IEEE
Conference_Location :
Tsukuba Science City
Print_ISBN :
0-7695-3051-6
DOI :
10.1109/APSCC.2007.61