Building an AS-topology model that captures route diversity

Fri, 05/11/2007 - 00:20 by Olivier Bonaventure


An understanding of the topological structure of the Internet is
needed for quite a number of networking tasks, e.g., making de-
cisions 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 In-
ternet 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
acceptible 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 over-
simplify the relationships between ASes. Our approach uses multi-
ple 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.

W. Muhlbauer, A. Feldmann, O. Maennel, M. Roughan and S. Uhlig
ACM SIGCOMM2006, Pisa, Italy, September 2006.
Full text
pdf    (372.86 KB)
Cite it
See here

IEEE Copyright Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

ACM Copyright Notice: Copyright 1999 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page or intial screen of the document. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM Inc., fax +1 (212) 869-0481, or

Springer-Verlag LNCS Copyright Notice: The copyright of these contributions has been transferred to Springer-Verlag Berlin Heidelberg New York. The copyright transfer covers the exclusive right to reproduce and distribute the contribution, including reprints, translations, photographic reproductions, microform, electronic form (offline, online), or any other reproductions of similar nature. Online available from Springer-Verlag LNCS series.