Impact of traffic and network information on routing performance

Traffic engineering is aimed at distribution of traffic within a network so as to optimize a given performance criterion. It typically takes as input, a certain characterization of the traffic, network topology and routing constraints, and outputs a set of paths that optimize a specified objective. The ability to carry out such an optimal distribution depends on the routing and forwarding mechanisms, the traffic information available, the network characteristics and finally, the route computation algorithm. The goal of this thesis is to explore the interplay between these factors and their impact on performance, both in terms of cost and robustness, as well as the associated complexity. We approach this objective from the perspective of analyzing the impact of information in a problem. In particular, the volume of traffic and network information along with the routing constraints play a vital role in determining the complexity of computing and implementing a good routing solution as well as its performance. The focus of our investigation is on identifying what type and amount of information in the input is relevant and how they affect the trade-off between improvement in performance and the increase in complexity associated with the use of a larger volume of information. In order to aid our study, several algorithms are derived that are shown, through analysis and experimental evidence, to efficiently exploit input information and still yield good performance. An important aspect of our investigation is that we explore these issues under realistic constraints imposed by both MPLS type environments as well as shortest path protocols like OSPF and IS-IS, which govern the paths that are allowed within a network as well as the distribution of traffic over these paths. These constraints are utilized to identify the relevant information present in the traffic matrix and the network. With regard to traffic matrices, we study the impact of information present in the form of traffic granularity. In practice, the traffic matrix is granular in nature, with traffic distributed over a set of discrete entities or streams, which constitute our measure of information. The distribution of traffic in the network is governed by the routing and forwarding decisions made for each such stream. Present day forwarding mechanisms constrain traffic on each stream to be split in a very limited number of ways. (Abstract shortened by UMI.