Dynamic load balancing without packet reordering

TLDR

Dynamic load balancing protects ISP networks from congestion by splitting traffic across multiple paths, but fine‑grained splitting trades packet reordering against accurate share assignment, while flow‑level splitting avoids reordering yet can overshoot desired shares by up to 60%, reducing goodput. The authors propose FLARE, a traffic‑splitting algorithm that operates on bursts of packets to avoid packet reordering while maintaining accurate path shares. FLARE selects bursts of packets for each path, timing them so that packets within a TCP flow are delivered in order across multiple paths. Trace‑driven simulations demonstrate that FLARE achieves packet‑level accuracy and responsiveness comparable to packet switching while preserving packet order, and it requires only a few kilobytes of router state.

Abstract

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 protocols, 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 flow, 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 environments, resulting in low end-to-end network goodput Contrary to popular belief, we show that one can systematically split a single flow 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