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.