Ph.D Thesis

Ph.D StudentScalosub Gabriel
SubjectRouting and Scheduling Problems in Data Networks
DepartmentDepartment of Computer Science
Supervisors PROF. Joseph Naor
PROF. Dan Raz
MR Adi Rosen
Full Thesis textFull thesis text - English Version


Modern data communication networks call for novel algorithms and protocols that can deliver higher throughput rates and provide various Quality-of-Service guarantees. We study several fundamental problems arising in modern networks, concentrating on real-life scenarios where we suffer from lack of information regarding future events or from 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. 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 where collisions are 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 while uncoordinated selfish behavior may result in an exponential degradation in throughput, there exists a penalizing scheme which guarantees at least a 1/e fraction of the optimal throughput. Based on these techniques, we develop a robust fully distributed protocol, and show using extensive simulation that it outperforms several natural protocols for the problem.