טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentCohen Gal
SubjectOn routing schemes that are robust to changes in
bandwidth demand
DepartmentDepartment of Computer Science
Supervisor Professor Dan Raz
Full Thesis textFull thesis text - English Version


Abstract

A major challenge in optimizing network utilization is handling changes in bandwidth demand with minimal route changes.

Most traffic engineering algorithms try to address this challenge either by minimizing the load on the most congested link, or by assuming uniform future demand increases for all the flows.

However, these approaches fail to adapt to the actual changes in the network, as the changes are often non-uniform.


In this work, we present a novel traffic-engineering algorithm, which considers the more realistic scenario where only an arbitrary subset (up to some predefined limit) of the flows change their demand.

An exact solution to this problem is exponential in the initial number of demands; however, we show that some of the constraints can be omitted without affecting the solution, thereby easing the computation complexity.

We use this observation to design traffic-engineering algorithms that are robust to non-uniform demand increase.

We prove that the reduced set of constraints still yields the same optimal value.


We evaluate our algorithms in two realistic network settings and compare the performance to previous work. The experimental results indicate that our algorithms address demand changes better, and can accommodate up to 10% more traffic without changing the route of exiting flows.