Optimization issues in network routing
Serge A. Plotkin, Omri Palmon · 2001
This Thesis concentrates on network routing algorithms. The main focus is on problems related to allocating bandwidth in high speed communications networks such as ATM. The major areas of work are: (1) Developing algorithms for off-line routing and design of communication network topology. (2) Designing algorithms for on-line routing. (3) Probabilistic analysis of on-line routing algorithms. The contribution of this Thesis can be divided to 2 areas: off-line and on-line routing algorithms. In the off-line content the main contribution is several algorithms for multicommodity flow. The Thesis also explains their relation to network routing. Significant improvements in the running time are presented for the case where an approximate solution is needed. In the on-line contest the Thesis presents analysis of on-line network routing algorithm, where routing decision are done without knowledge of future request. The Thesis proves that average performance of the algorithm is within a small additive constant from any alternative off-line algorithm.