Abstract

In a few years, the Internet has quickly evolved from a research
network connecting a handful of users to the largest distributed
system ever built. The Internet connects more than 20,000 Autonomous
Systems (ASs) which are administratively independent networks. While
the initial Internet was designed to provide a best-effort
connectivity among these ASs, there is nowadays a growing trend to
deploy new services such as Voice/Video over IP or VPNs. To support
these emergent services, ASs need to better engineer their Internet
traffic. Traffic Engineering encompasses several goals such as better
spreading the traffic load inside a network and obtaining better
end-to-end performance (lower latency or higher bandwidth).

Engineering the traffic inside a single AS is feasible and pretty well
understood. To the opposite, interdomain traffic engineering is still
a difficult problem. The main issue comes from the current Internet
routing architecture, articulated around the Border Gateway Protocol
(BGP). BGP propagates a subset of the Internet topology for
scalability and stability reasons and does not optimize a single
global objective. This limits the control each AS has on its routing
and has dramatic implications for interdomain traffic engineering.

In this thesis, we evaluate the primitive BGP-based routing control
mechanisms. For this purpose, we designed and implemented a new
approach for modeling BGP on large Internet-scale network
topologies. Finally, to overcome the limitations of BGP in terms of
routing control, we propose Virtual Peerings, a new mechanism based on
a combination of BGP and IP tunneling. We apply Virtual Peerings to
solve various interdomain traffic engineering problems such as
balancing the load of Internet traffic received by an AS or decreasing
the end-to-end latency of Internet paths.