Maximizing Throughput of Reliable Bulk Network Transmissions

TitleMaximizing Throughput of Reliable Bulk Network Transmissions
Publication TypeTechnical Report
Year of Publication1998
AuthorsByers, J. W.
Other Numbers1125

We study combinatorial optimization and on-line scheduling problems which arise in the context of supporting applications which transmit bulk data over high-speed networks. One of our primary objectives in this thesis work is to formulate appropriate theoretical models in which to develop and analyze efficient algorithms for these problems - models which reflect both the experience of network architects, the design of network protocols, and contributions of theoretical research.We first consider the optimization problem of maximizing the utilization of a shared resource, network bandwidth, across a set of point-to-point connections. A feasible solution to this allocation problem is an assignment of transmission rates to the connections which does not violate the capacity constraints of the network links. The connections and routers which are responsible for establishing this allocation must do so with incomplete information and limited communication capabilities. We develop a theoretical model which addresses these considerations and study the tradeoff between the quality of the solution we can obtain and the distributed running time. Our main theoretical result is a distributed algorithm for this problem which generates a feasible (1 + e)-approximation to the optimal allocation in a polylogarithmic number of distributed rounds. A sequential implementation of our distributed algorithm gives a simple, efficient approximation algorithm for general positive linear programming. Subsequent experience with an implementation of the algorithm indicates that it is well suited to future deployment in high-speed networks.The next problem we consider is the following on-line scheduling problem, which the sender of a point-to-point bulk transmission must address. Given an on-line sequence of transmission times, determine which data item to transmit at each transmission time, so as to maximize effective throughput to the receiver at all points in time. For this application, we measure effective throughput as the length of the intact prefix of the message at the receiver. This problem is made difficult in practice by factors beyond the sender's control, such as packet loss and wide variance in packet round-trip times.Using the method of competitive analysis, we compare the performance of our algorithm to that of an omniscient algorithm. We prove that while all deterministic policies perform poorly in this model, a simple randomized policy delivers near-optimal performance at any given point in time with high probability. Moreover, our theoretical result ensures that typical performance does not degrade significantly - a claim which our empirical studies bear out. Using the models and tools developed for these problems, we then consider analogous problems which arise for multicast bulk transmissions, transmissions targeted to multiple destinations. We show how to tune our bandwidth allocation policy to still deliver a (1 + e)-approximation to the optimal allocation in a polylogarithmic number of distributed rounds. For the scheduling problem, we prove that no on-line scheduling policy can deliver high performance which scales with the number of receivers without using encoding. We then show that by using forward error correction coding techniques, a simple multicast policy delivers effective throughput within a constant factor of optimal independent of the number of receivers.

Bibliographic Notes

ICSI Technical Report TR-98-002

Abbreviated Authors

J. W. Byers

ICSI Publication Type

Technical Report