Skip to main content
CAIDA home

Bibliography Details

The contents of this legacy page are no longer maintained nor supported, and are made available only for historical purposes.

Bibliography Details

H. Chang, S. Jamin, and W. Willinger, "Internet Connectivity at the AS-level: An Optimization-Driven Modeling Approach", in ACM SIGCOMM Workshop on MoMeTools, August 2003.
Internet Connectivity at the AS-level: An Optimization-Driven Modeling Approach
Authors: H. Chang
S. Jamin
W. Willinger
Published: ACM SIGCOMM Workshop on MoMeTools, 2003
URL: http://citeseer.ist.psu.edu/577612.html
Entry Date: 2004-06-30
Abstract: Two ASs are connected in the Internet AS graph only if they have a business "peering relationship." By focusing on the AS subgraph AS-PC whose links represent provider-customer relationships, we develop a new optimization-driven model for Internet growth at the AS-PC level. The model's defining feature is an explicit construction of a novel class of intuitive, multi-objective, local optimizations by which the different customer ASs determine in a fully distributed and decentralized fashion their "best" upstream provider AS. Key criteria that are explicitly accounted for in the formulation of these multi-objective optimization problems are (i) AS-geography, i.e., locality and number of PoPs within individual ASs; (ii) AS-specific business models, abstract toy models that describe how individual ASs choose their "best" provider; and (iii) AS evolution, a historic account of the "lives" of individual ASs in a dynamic ISP market. We show that the resulting model is broadly robust, perforce yields graphs that match inferred AS connectivity with respect to a number of different metrics, and is ideal for exploring the impact of new peering incentives or policies on AS-level connectivity.
Datasets:
  • Oregon RouteViews (late May 2001)
  • Additional information from BGP routing tables, Looking Glass, the Routing Registry database, adding 40% more links (late May 2001)
Experiments:
  • AS-PC subraph of Internet derived from BGP routing information using different relationship inferrence techniques by Gao and Subramanian et. al.
  • Successive refinements of Optimization-Driven model run for 10,000 nodes.
  • For each iteration, one node is added with one PoP. Each existing node has a probability of gaining a new Point of Presence (PoP).
  • First model: new node chooses a provider based on the closest Point of Presence (PoP).
  • Second model: based on some number of metrics with uniform random values, new node makes a local Pareto optimal choice amongst providers within a certain distance (no other provider among the choices is better in all metrics).
  • Third model: nodes are regularly randomly removed, causing customers to choose a new provider.
Results:
  • With more realistic assumptions, other model does not match node degree of Internet.
  • Model is robust to changes in parameters and AS/node degree matches that of inferred Internet AS-PC subgraph.
  • Change of provider makes node age distribution more like Internet's.
References: Similar approach advocated and outlined in:
  • D. Alderson, J. Doyle, R. Govindan, and W. Willinger. Toward an Optimization-Driven Framework for Designing and Generating Realistic Internet Topologies. In Proc. of HotNets-I, 2002.
Compares against model of:
  • A. Fabrikant, E. Koutsoupias, and C. H. Papadimitriou. Heuristically Optimized Trade-offs: A New Paradigm for Power Laws in the Internet. In Proc. of ICALP, 2002.