Towards robust traffic engineering in IP networks

Sammanfattning: To deliver a reliable communication service it is essential for the network operator to manage how traffic flows in the network. The paths taken by the traffic is controlled by the routing function. Traditional ways of tuning routing in IP networks are designed to be simple to manage and are not designed to adapt to the traffic situation in the network. This can lead to congestion in parts of the network while other parts of the network are far from fully utilized. In this thesis we explore issues related to optimization of the routing function to balance load in the network. We investigate methods for efficient derivation of the traffic situation using link count measurements. The advantage of using link counts is that they are easily obtained and yield a very limited amount of data. We evaluate and show that estimation based on link counts give the operator a fast and accurate description of the traffic demands. For the evaluation we have access to a unique data set of complete traffic demands from an operational IP backbone. Furthermore, we evaluate performance of search heuristics to set weights in link-state routing protocols. For the evaluation we have access to complete traffic data from a Tier-1 IP network. Our findings confirm previous studies that use partial traffic data or synthetic traffic data. We find that optimization using estimated traffic demands has little significance to the performance of the load balancing. Finally, we device an algorithm that finds a routing setting that is robust to shifts in traffic patterns due to changes in the interdomain routing. A set of worst case scenarios caused by the interdomain routing changes is identified and used to solve a robust routing problem. The evaluation indicates that performance of the robust routing is close to optimal for a wide variety of traffic scenarios. The main contribution of this thesis is that we demonstrate that it is possible to estimate the traffic matrix with good accuracy and to develop methods that optimize the routing settings to give strong and robust network performance. Only minor changes might be necessary in order to implement our algorithms in existing networks.