Technical Report PHD-2007-14

Title: Routing and Scheduling Problems in Data Networks
Authors: Gabriel Scalosub
Supervisors: Seffi Naor, Danny Raz, Adi Rosen
Abstract: Data communication networks have a major effect on many aspects of modern day life. The complexity of these networks, both in terms of architecture, and in terms of the services these network are required to provide, necessitate the design of novel algorithms and protocols that can deliver higher throughput rates and guarantee the needed Quality-of-Service. In this work we study several fundamental problems arising in modern networks, concentrating on real-life scenarios where limitations are imposed on solving the problem, either in terms of lack of information regarding future events or in terms of lack of coordination between the various system's components. We take on a competitive approach in the design and analysis of our proposed algorithms, which enables us to provide worst-case performance guarantees compared to the optimal performance. This makes our algorithms globally applicable, independent of specific traffic patterns or underlying traffic distributions.

We first consider the problem of bufferless routing and scheduling in optical networks, and present the first online algorithms for the problem. Our algorithms apply to the case where the underlying topology is a line or a ring. We give guarantees as to the worst-case performance of our algorithms, and present matching lower bounds.

Next we consider the problem of guaranteeing low jitter for multiple streams using a shared buffer. We show that while the problem can be solved optimally in an offline setting, in the online setting a substantial resource augmentation is required in order to provide optimal jitter. The amount of resource augmentation depends linearly on the number of streams, thus our results indicate that jitter regulation does not scale well when the number of streams increases.

We then consider the problem of information gathering on the line, with limited buffer space at each node. We extend the common model for such problems by considering the adversary's rate. This enables us to provide better guarantees which depend not only on the network size, but also on the adversary's rate and the amount of buffer space available at the nodes. Our results can also guide better buffer provisioning in some cases which can guarantee optimal throughput.

Lastly, we consider the problem of multiple access in wireless networks with soft collisions. In this model collisions may occur due to proximity between transmitting nodes, but not every simultaneous transmission results in a collision. We take on a game theoretic approach and show that for the case where interferences are homogeneous, selfish behavior may result in an exponential degradation in throughput. However, there exists a penalizing scheme on the selfish agents which can guarantee at least a 1/e fraction of the optimal throughput. Based on these techniques, we develop a fully distributed protocol for non-homogeneous interferences, which outperforms natural protocols for the problem. We also show using simulation that this protocol is very robust in the sense that it performs well under varying load situations.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2007
To the main CS technical reports page

Computer science department, Technion