Models and algorithms for effective traffic engineering of tunnel-based backbone networks

In this dissertation, we explore the problem of effective traffic engineering of tunnel-based backbone networks. The approach is drawn from the observation that current techniques only account for requirements of the data plane towards engineering of networks. The impact is compounded by the stateful nature of tunnel-based networks. Our approach here is to incorporate control plane requirements through tunneling restriction to address a class of traffic engineering problems.;First, we consider networks having heterogeneous streams (in terms of first and second order characteristics). Traffic streams are known to be heterogeneous due to diverse nature of applications which translates into distortion when they share tunnels with other streams. Using separate tunnels for each source could lead to overwhelming number of tunnels. Hence, we model and solve the problem of traffic engineering such networks so as to minimize the distortions in traffic characteristics of individual flows while bounding the number of tunnels on each link. We present results demonstrating the benefits of the approach in terms of distortion in the streams.;Next, we consider networks which provide survivability by enforcing diversity requirements. The diversity constraint restricts the fraction of flow that can be allocated to a path. The approach enforces that for single link failures only a fraction of demand can get lost. But, presence of diversity constraint leads to high number of active tunnels in the network. Hence, we present a traffic engineering formulation and an accompanied solution approach to model the diversity and tunneling restriction. We then present results demonstrating the impact of diversity parameter upon the capacity and tunnel requirements. We also extend the mentioned models to incorporate a tunnel cost based on flow and hop based routing.;Third network scenario that we consider provides guaranteed survivability to demands using backup path based restoration. Note that the diversity based approach towards survivability is inadequate in providing guaranteed survivability. The presence of primary and backup paths could lead to unmanageable number of tunnels in the network. We model service classes having three levels of survivability: zero-survivable, fractional survivable and fully survivable. We present the integrated formulation with tunneling restriction and discuss two solution techniques. Using the solution techniques, we study the impact of survivable services on the overall traffic engineering of a network. Since, such services share the network with other best-effort services, we also study the impact on their performance.