The tussle between reliability and functionality of the Internet is firmly biased on the side of reliability. New enabling technologies fail to achieve traction across the majority of ISPs. We believe that the greatest challenge is not in finding solutions and improvements to the Internet's many problems, but in how to actually deploy those solutions and re-balance the tussle between reliability and functionality. Network virtualization provides a promising approach to enable the coexistence of innovation and reliability. We describe a network virtualization architecture as a technology for enabling Internet innovation. This architecture is motivated from both business and technical perspectives and comprises four main players. In order to gain insight about its viability, we also evaluate some of its components based on experimental results from a prototype implementation.

Formally, the Internet inter-domain routing system is a collection of networks, their policies, peering relationships and organizational affiliations, and the addresses they advertize. It also includes components like Internet exchange points. By its very definition, each and every aspect of this system is impacted by BGP, the de-facto standard inter-domain routing protocol. The element of this inter-domain routing system that has attracted the single-most attention within the research community has been the "inter-domain topology". Unfortunately, almost from the get go, the vast majority of studies of this topology, from definition, to measurement, to modeling and analysis, have ignored the central role of BGP in this problem. The legacy is a set of specious findings, unsubstantiated claims, and ill-conceived ideas about the Internet as a whole. By presenting a BGP-focused state-of-the-art treatment of the aspects that are critical for a rigorous study of this inter-domain topology, we demystify in this paper many "controversial" observations reported in the existing literature. At the same time, we illustrate the benefits and richness of new scientific approaches to measuring, modeling, and analyzing the inter-domain topology that are faithful to the BGP-specific nature of this problem domain.

This paper presents a methodology for identifying the autonomous system (or systems) responsible when a routing change is observed and propagated by BGP. The origin of such a routing instability is deduced by examining and correlating BGP updates for many prefixes gathered at many observation points. Although interpreting BGP updates can be perplexing, we find that we can pinpoint the origin to either a single AS or a session between two ASes in most cases. We verify our methodology in two phases. First, we perform simulations on an AS topology derived from actual BGP updates using routing policies that are compatible with inferred peering/customer/provider relationships. In these simulations, in which network and router behavior are "ideal", we inject inter-AS link failures and demonstrate that our methodology can effectively identify most origins of instability. We then develop several heuristics to cope with the limitations of the actual BGP update propagation process and monitoring infrastructure, and apply our methodology and evaluation techniques to actual BGP updates gathered at hundreds of observation points. This approach of relying on data from BGP simulations as well as from measurements enables us to evaluate the inference quality achieved by our approach under ideal situations and how it is correlated with the actual quality and the number of observation points.

This conference paper is closed access.The definitive version is available at: http://dx.doi.org/10.1145/1644893.1644923Reachability is thought of as the most basic service provided by today's Internet. Unfortunately, this does not imply that the community has a deep understanding of it. Researchers and operators rely on two views of reachability: control/routing- and data-plane measurements, but both types of measurements suffer from biases and limitations. In this paper, we illustrate some of these biases, and show how to design controlled experiments which allow us to "see" through the limitations of previous measurement techniques. For example, we discover the extent of default routing and its impact on reachability. This explains some of the previous unexpected results from studies that compared control- and data-plane measurements. However, not all limitations of visibility given by routing and probing tools can be compensated for by methodological improvements. We will show in this paper, that some of the limitations can be carefully addressed when designing an experiment, e.g. not seeing the reverse path taken by a probe can be partly compensated for by our methodology, called dual probing. However, compensating for other biases through more measurements may not always be possible. Therefore, calibration of expectations and checks of assumptions are critical when conducting measurements that aim at making conclusions about topological properties of the Internet. Copyright 2009 ACM

An understanding of the topological structure of the Internet is needed for quite a number of networking tasks, e. g., making decisions about peering relationships, choice of upstream providers, inter-domain traffic engineering. One essential component of these tasks is the ability to predict routes in the Internet. However, the Internet is composed of a large number of independent autonomous systems (ASes) resulting in complex interactions, and until now no model of the Internet has succeeded in producing predictions of acceptable accuracy.We demonstrate that there are two limitations of prior models: (i) they have all assumed that an Autonomous System (AS) is an atomic structure - it is not, and (ii) models have tended to oversimplify the relationships between ASes. Our approach uses multiple quasi-routers to capture route diversity within the ASes, and is deliberately agnostic regarding the types of relationships between ASes. The resulting model ensures that its routing is consistent with the observed routes. Exploiting a large number of observation points, we show that our model provides accurate predictions for unobserved routes, a first step towards developing structural mod-els of the Internet that enable real applications.

Internet routing table size growth and BGP update churn are two prominent Internet scaling issues. There is widespread belief in a high and fast growing number of ASs that deaggregate prefixes, e.g., due to multi-homing and for the purpose of traffic engineering. Moreover, researchers often blame specific classes of ASs for generating a disproportionate amount of BGP updates. Our primary objective is to challenge such widespread assumptions (“myths”) and not solely to confirm previous findings. Surprisingly, we find severe discrepancies between existing myths and reality. According to our results, there is no trend towards more aggressive prefix deaggregation or traffic engineering over time. With respect to update dynamics, we observe that deaggregated prefixes generally do not generate a disproportionate number of BGP updates, with respect to their share of the BGP routing table. On the other side, we observe much more widespread traffic engineering in the form of AS path prepending and scoped advertisements compared to previous studies. Overall, our work gives a far more positive picture compared to the alarming discourses typically heard: The impact of “bad guys” on routing table size growth and BGP churn has not changed for the worse in recent years. Rather, it increases at the same pace as the Internet itself.