Technical Report MSC-2017-01

Title: On Routing Schemes that are Robust to Changes in Bandwidth Demand
Authors: Gal Cohen
Supervisors: Danny Raz
PDFCurrently accessibly only within the Technion network
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.

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 MSC technical reports of 2017
To the main CS technical reports page

Computer science department, Technion