Load-balancing multipath switching system with flow slice

Lei Shi, Bin Liu, Changhua Sun, Zhengyu Yin, Laxmi N. Bhuyan, H. Jonathan Chao

Research output: Contribution to journalArticlepeer-review


Multipath Switching systems (MPS) are intensely used in state-of-the-art core routers to provide terabit or even petabit switching capacity. One of the most intractable issues in designing MPS is how to load balance traffic across its multiple paths while not disturbing the intraflow packet orders. Previous packet-based solutions either suffer from delay penalties or lead to O(N 2 ) hardware complexity, hence do not scale. Flow-based hashing algorithms also perform badly due to the heavy-tailed flow-size distribution. In this paper, we develop a novel scheme, namely, Flow Slice (FS) that cuts off each flow into flow slices at every intraflow interval larger than a slicing threshold and balances the load on a finer granularity. Based on the studies of tens of real Internet traces, we show that setting a slicing threshold of 1-4 ms, the FS scheme achieves comparative load-balancing performance to the optimal one. It also limits the probability of out-of-order packets to a negligible level (10 -6) on three popular MPSes at the cost of little hardware complexity and an internal speedup up to two. These results are proven by theoretical analyses and also validated through trace-driven prototype simulations.

Original languageEnglish (US)
Article number5674025
Pages (from-to)350-365
Number of pages16
JournalIEEE Transactions on Computers
Issue number3
StatePublished - 2012


  • Load balancing
  • switching theory
  • traffic measurement

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Load-balancing multipath switching system with flow slice'. Together they form a unique fingerprint.

Cite this