Robust IP routing optimization

OData support
Vincze Gábor
Department of Telecommunications and Media Informatics

The new demands for quality of service, the continuous growth of Internet traffic as well as stricter network security requirements force the Internet Service Providers (ISPs) and operators to a continuous adaptation of their infrastructure and communication. However, it is difficult to predict the traffic demand for IP networks and it is becoming more and more volatile. This constitutes a major obstacle to the use of traditional techniques of traffic engineering which supposes the knowledge of the traffic matrix.

Taking into account the uncertainties in the traffic matrix and the search for robust solutions for planning problems are major issues for future networks. This is a very recent research topic which is rapidly developing.

The first part of the work introduces various network problems and models, the Lagrange relaxation and the problem of multi-commodity flows. Then, we will describe the state of the art of robust optimization techniques and we will analyze the available information for planning to derive the tightest uncertainty sets possible.

Then we will discuss the problem of optimal routing in IP networks by studying a heuristic approach. We will use a method based on a local search algorithm and Lagrange relaxation. We will show that our heuristic algorithm provides IP routing which is close to optimal with a low computing time compared to known algorithms for optimizing the OSPF link weights.

Finally, we propose a framework for dynamic optimization of link weights. The main idea is to use SNMP measures on the link loads to define an uncertainty set on the traffic matrix and regularly optimizing OSPF weights by taking into account the demand uncertainty. We will formulate the uncertainty set obtained by aggregating SNMP measures as linear constraints. We will use CPLEX to solve the given linear program and then we will apply the same local search algorithm as in the case of robust optimization of link weights.

The practical effectiveness of the algorithms and methods developed in this report will be illustrated and validated by a series of simulations on real life data.


Please sign in to download the files of this thesis.