Internet traffic engineering without full mesh overlaying

The overlay approach has been widely used by many service providers for traffic engineering in large Internet backbones. In the overlay approach, logical connections are set up between edge nodes to form a full mesh virtual network on top of the physical topology. IP routing is then run over the virtual network. Traffic engineering objectives are achieved through carefully routing logical connections over the physical links. Although the overlay approach has been implemented in many operational networks, it has a number of well-known scaling issues. This paper proposes a new approach, which we call the integrated approach, to achieve traffic engineering without full-mesh overlaying. In the integrated approach, IP routing runs natively over the physical topology rather than over the virtual network. Traffic engineering objectives are realized by setting appropriate link metrics in IP routing protocols. We first illustrate our approach with a simple network, then present a formal analysis of the integrated approach and a method for deriving the appropriate link weights. Our analysis shows that for any given set of optimal routes of the overlay approach with respect to a set of traffic demands, the integrated approach can achieve exactly the same result by reproducing them as shortest paths. We further extend the result to a more generic one: for any arbitrary set of routes, as long as they are not loopy, they can be converted to shortest-paths with respect to some set of positive link weights. A theoretical insight of our result is that the optimal routing (with respect to any objective function) is always shortest path routing with respect to some appropriate positive link weights