Flare: Responsive Load Balancing Without Packet Reordering

Srikanth Kandula, Dina Katabi, Shan Sinha, Arthur W. Berger
Computer Communication Review, March 2007

Dynamic load balancing is a popular recent technique that protects ISP networks from sudden congestion caused by load spikes or link failures. Dynamic load balancing pro-tocols, however, require schemes for splitting traffic across multiple paths at a fine granularity. Current splitting schemes present a tussle between slicing granularity and packet reordering. Splitting traffic at the granularity of packets quickly and accurately assigns the desired traffic share to each path, but can reorder packets within a TCP fl ow, confusing TCP congestion control. Splitting traffic at the granularity of a flow avoids packet reordering but may overshoot the desired shares by up to 60% in dynamic envi-ronments, resulting in low end-to-end network goodput.

Contrary to popular belief, we show that one can sys-tematically split a single ow across multiple paths without causing packet reordering. We propose FLARE, a new traffic splitting algorithm that operates on bursts of packets, carefully chosen to avoid reordering. Using a combination of analysis and trace-driven simulations, we show that FLARE attains accuracy and responsiveness comparable to packet switching without reordering packets. FLARE is simple and can be implemented with a few KB of router state.

[PDF (258KB)]

Bibtex Entry:

   author =       "Srikanth Kandula and Dina Katabi and Shan Sinha and Arthur W. Berger",
   title =        "{Flare: Responsive Load Balancing Without Packet Reordering}",
   booktitle =    {Computer Communication Review},
   year =         {2007},
   month =        {March},
   address =      {, }