A reliable and scalable striping protocol
Adiseshu Hari, Guru M. Parulkar, George Varghese · 1996
Link striping algorithms are often used to overcome transmission bottlenecks in computer networks. Traditional striping algorithms suffer from two major disadvantages. They provide inadequateload sharing in the presence of variable length packets, and may result in non-FIFOdelivery of data. We describe a new family of link striping algorithms that solves both problems. Our scheme applies to any layer that can provide multiple FIFO channels. We deal with variable sized packets by showing how fair queuing algorithms can be transformed into load sharing algorithms. Our transformation results in practical load sharing protocols, and shows a theoretical connection between two seemingly different problems. The same transformation can be applied to obtain load sharing protocols for links with different capacities. We deal with the FIFO requirement for two separate cases. If a sequencenumber can be added to each packet, we show how to speed up packet processing by letting the receiver simulate the sender algorithm. If no header can be added, we show how to provide quasi-FIFO delivery. Quasi-FIFO is FIFO except during occasional periods of loss of synchronization. We argue that quasi-FIFOis adequatefor most applications. We also describe a simple technique for speedy restoration of synchronization in the event of loss. We develop an architectural framework for transparently embedding our protocol at the network level by striping IP packetsacross multiple physical interfaces. The resulting strIPe protocol has been implemented within the NetBSD kernel. Our measurementsand simulations showthat the protocol offers scalable throughputeven when striping is done over dissimilar links, and that the protocol synchronizes quickly after packet loss. Measurements show performance improvements over conventional round robin striping schemes and striping schemes that do not resequence packets. 1