Dynamic Load Balancing Without Packet Reordering

Srikanth Kandula, Dina Katabi, Shantanu Sinha, and Arthur Berger
Appears in: 
CCR April 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 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 ow 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.

Public Review By: 
Matthew Roughan

When there are multiple paths across a network it is common for network operators to use some form of load balancing. Load-balancing allows more flexible and efficient allocation of resources, and thereby extends the lifetime of a network. The trick in load balancing is to decide which packets take which path. Until now, this forwarding decision was made either per packet with the result that reordering could occur within a flow (a potential problem TCP performance), or at the flow level (e.g. based on the IP source and destination address of packets). Splitting traffic at the level of flows removes the problem of reordering, but at the cost of a restriction in the granularity with which we can split traffic. This paper presents a new approach dubbed FLARE that operates on bursts of packets (flowlets) carefully chosen to avoid reordering, but allowing a finer granularity of balancing.
The reviewers reported enjoying the paper, in particular the insight into how the bursty behaviour of TCP could be exploited by the load-balancer. They noted that the authors were sensitive to the amount of state information required (keeping this to a minimum), and that the authors’ proofs, and evaluations of FLARE using tracedriven simulations were quite thorough.
However, the common limitations pointed to by all reviewers lie around the practical issues of such an approach. It is intrinsically linked to TCP traffic via the burstiness introduced by the congestion control. All of the presented work considered TCP traffic without interference from devices such as packet shapers, other sources of traffic, or multiple bottlenecks. It will be very interesting to see if the ideas in this paper are taken further, most importantly whether they are implemented and validated in practical settings.