|
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.
|