Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1995-01-01

Filename

WUCS-95-11.PDF

DOI:

10.7936/K75B00NR

Technical Report Number

WUCS-95-11

Abstract

Link striping algorithms are often used to overcome transmission bottlenecks in computer networks. However, traidtional striping algorithms suffer from two major disadvantages. They provide inadequate load sharing in the presence of variable length packets, and may result in non-FIFO delivery of data. We describe a new family of link striping algorithms that solve both problems. Our scheme applies to packets at any layer (physical, data, link, network, and transport) that work over multiple FIFO channels. We deal with variable sized packets by showing how a class of fair queueing algorithms can be converted into load sharing algorithms. Our transformation results in practical load sharing protocols, and also shows a theoretical connection between two seemingly different problem areas. We deal with the FIFO requirement for two separate cases. If a header (with a sequence number) 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 (e.g., ATM cells), we show how to provide quasi-FIFO delivery. Quasi-FIFO is FIFO except during occasional periods of loss of synchronization between the sender and the receiver. We argue that quasi-FIFO should be adequate for most applications. To deal with loss of synchronization between the sender and receiver, we present simple recovery protocols. We provide performance analysis, experimental results, and proofs of our assertions.

Comments

Permanent URL: http://dx.doi.org/10.7936/K75B00NR

Download

Share

COinS