Per-Flow Re-Sequencing in Load-Balanced Switches by Using Dynamic Mailbox Sharing

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 mis-sequencing. 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 re-sequencing even when the load is very high. The results also demonstrate that the size of mailbox is in the hundreds.