Per-flow re-sequencing in load-balanced switches by using dynamic mailbox sharing

Hong Cheng, Yaohui Jin, Yu Gao, Ying Di Yu, Weisheng Hu, Nirwan Ansari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations


Load-balanced switches have received much attention because they are more scalable than other switch architectures. However, a load-balanced switch has the problem of packet missequencing. In this paper, we propose a Dynamic Mailbox Sharing (DMS) scheme to eliminate the mis-sequencing problem of load-balanced switches only at the cost of a very small increase of delay. The key idea is to keep packets of the same flow in order in the load-balanced switch. The DMS scheme is based on two statistical facts in operational networks: the number of simultaneous active flows in the router buffer is far less than that of in-progress flows, and most of the intra-flow packet intervals are longer than the packet delay in the high speed router. In DMS, the packet sequence of the same flow arrived in the input ports is recorded in the mailbox maintained in the output ports. Then, packets of the same flow are delivered according to the order of their arrivals. The mailbox becomes the bottleneck in order to accommodate a large number of flows. We thus propose a dynamic sharing scheme to alleviate the bottleneck and greatly enhance the scalability of the mailbox. By simulations using the real internet traffic traces, we show that with a simple flow splitter mechanism restraining mis-sequencing, the average packet delay using DMS is considerably lower than that of other schemes including Uniform Frame Spreading, Padded Frame and the CR switch, and it is close to the ideal case without resequencing even when the load is very high. The results also demonstrate that the size of mailbox is in the hundreds.

Original languageEnglish (US)
Title of host publicationICC 2008 - IEEE International Conference on Communications, Proceedings
Number of pages5
StatePublished - 2008
EventIEEE International Conference on Communications, ICC 2008 - Beijing, China
Duration: May 19 2008May 23 2008

Publication series

NameIEEE International Conference on Communications
ISSN (Print)0536-1486


OtherIEEE International Conference on Communications, ICC 2008

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


  • Dynamic sharing
  • Load-balanced switch
  • Mailbox


Dive into the research topics of 'Per-flow re-sequencing in load-balanced switches by using dynamic mailbox sharing'. Together they form a unique fingerprint.

Cite this