Sprinklers: A Randomized Variable-Size Striping Approach to Reordering-Free Load-Balanced Switching

Internet traffic continues to grow exponentially, calling for switches that can scale well in both size and speed. While load-balanced switches can achieve such scalability, they suffer from a fundamental packet reordering problem. Existing proposals either suffer from poor worst-case packet delays or require sophisticated matching mechanisms. In this paper, we propose a new family of stable load-balanced switches called “Sprinklers ” that has comparable implementation cost and performance as the baseline load-balanced switch, but yet can guarantee packet or-dering. The main idea is to force all packets within the same virtual output queue (VOQ) to traverse the same “fat path ” through the switch, so that packet reordering cannot occur. At the core of Sprinklers are two key innovations: a randomized way to determine the “fat path” for each VOQ, and a way to determine its “fatness ” roughly in proportion to the rate of the VOQ. These innovations enable Sprinklers to achieve near-perfect load-balancing under arbi-trary admissible traffic. Proving this property rigorously using novel worst-case large deviation techniques is another key contribution of this work.