Presented by Soudeh Ghorbani
Most works on load balancing in data centers need global information. DRILL proposed a solution in the reverse direction: load balancing based on local decisions at each switch. DRILL performs per-packet load balancing according to the queue occupancy. But sending packets to the shortest queue may result in suboptimal performance globally, so DRILL introduces randomness. Specifically, it leverages the “power of two choices”: each engine compares queue lengths of two random ports plus the previously least-loaded port, and sends the packet to the least loaded of these.
In DRILL, the forwarding decisions for each packet is independent of other packets in the flow, so there might be excessive packet reordering and TCP will suffer. But surprisingly, DRILL experiences very minimal reordering. This is because the queue length has little variance and packets experience similar queueing delay. Although the packets take very different paths, the delays of packets along those paths differs little. So, packet reordering is uncommon in DRILL.
Another challenge is asymmetric network, which may have an asymmetric topology by design or be caused by link failures. In this case, the load balancers that split individual flows among available paths may waste bandwidth. The solution is to decompose the network into symmetric components. DRILL decomposes the graph by assigning scores of paths by a hash map. Paths with the same score are symmetric. DRILL iteratively assigns the scores and picks the set of symmetric paths.
Q: Have you compared with prior works doing round robin load balancing on virtual symmetric topologies?
A: Yes, we did some comparisons using randomized algorithm over two samples. But we miss round robin is because they don’t work well on asymmetric topologies. Even for symmetric topologies, we have some benefits over round robin. Because of the two mechanisms in DRILL, we expect even more advantage on asymmetric topologies.
Q: We did micro load balancing and we found it does not optimize downlink from the core, because there’s no alternative paths. It’s no better than per-packet random by our experience.
A: If the topology is symmetric, you will expect the same load balancing from all switches. The queuing happens at the first and the last hop, so we have very little queuing from the spine to the leaves.
