Transcript Internet Structure

The structure of the Internet
How are routers connected?
• Why should we care?
– While communication protocols will work
correctly on ANY topology
– ….they may not be efficient for some
topologies
– Knowledge of the topology can aid in
optimizing protocols
The Internet as a graph
• Remember: the Internet is a collection of
networks called autonomous systems
(ASs)
• The Internet graph:
– The AS graph
• Nodes: ASs, links: AS peering
– The router level graph
• Nodes: routers, links: fibers, cables, MW channels,
etc.
• How does it looks like?
Random graphs in Mathematics
The Erdös-Rényi model
• Generation:
– create n nodes.
– each possible link is added with probability p.
• Number of links: np
• If we want to keep the
number of links linear,
what happen to p as
n?
Poisson distribution
The Waxman model
• Integrating distance with the E-R model
• Generation
– Spread n nodes on a large enough grid.
– Pick a link uar and add it with prob. that
exponentially decrease with its length
– Stop if enough links
• Heavily used in the 90s
100
90
80
70
60
50
40
30
20
10
0
0
10
20
30
40
50
60
70
80
90
100
1999
The Faloutsos brothers
• Measured the Internet
AS and router graphs.
• Mine, she looks
different!
Notre Dame
• Looked at complex
system graphs: social
relationship, actors,
neurons, WWW
• Suggested a dynamic
generation model
The Faloutsos Graph
1995 Internet router topology
3888 nodes, 5012 edges, <k>=2.57
SCIENCE CITATION INDEX
Nodes: papers
Links: citations
25
Witten-Sander
PRL 1981
1736 PRL papers (1988)
2212
P(k) ~k-
( = 3)
(S. Redner, 1998)
Sex-web
Nodes: people (Females; Males)
Links: sexual relationships
4781 Swedes; 18-74;
59% response rate.
Liljeros et al. Nature 2001
Web power-laws
GROWING SCALE-FREE NETWORKS
(1) The number of nodes (N) is NOT fixed.
Networks continuously expand by
the addition of new nodes
Examples:
WWW : addition of new documents
Citation : publication of new papers
(2) The attachment is NOT uniform. (Rich get Richer)
A node is linked with higher probability to a node
that already has a large number of links.
Examples :
WWW : new documents link to well known sites
(CNN, YAHOO, NewYork Times, etc)
Citation : well cited papers are more likely to be cited again
Barabasi Scale-free model
(1) GROWTH :
At every timestep we add a new node with m edges
(connected to the nodes already present in the system).
(2) PREFERENTIAL ATTACHMENT :
The probability Π that a new node will be connected to
node i depends on the connectivity ki of that node
ki
 ( ki ) 
 jk j
P(k) ~k-3
A.-L.Barabási, R. Albert, Science 286, 509 (1999)
The Faloutsos Graph
node degree for AS20000102.m
4
10
3
10
2
10
1
10
0
10
0
10
1
10
2
10
3
10
4
10
The Internet Topology as a
Jellyfish
Shells: 1
3
2
Core
 Core: High-degree clique
 Shell: adjacent nodes of
previous shell, except 1degree nodes
 1-degree nodes: shown
hanging
 The denser the 1-degree
node population the
longer the stem
But is it?
Not necessarily
ER in disguise?
• Our sampling practices are far from being
perfect:
– Few traceroute hosts measure multitude of
addresses
– The problem of the blind mice…
– However, the Internet is probably much more
broad scale than ER (the Jellyfish still stands)
Past Attempts
• Measurements were done from a few (up
to 10s) points
►too many links are missed – especially in the
periphery - Hidden peer connections
►measurements traffic was too dense
• Some maps were created based on
central databases
►data was not up to date
Past Measurements
DIMES@Home
Distributed Internet MEasurement & Simulation
• Creating a distributed platform that will enable:
– Global scale measurement of Internet graph
structure, packet traffic statistics, demography
– Simulation of Internet behavior under different
conditions (let the net simulate itself)
– Simulation of the Internet future:
• Active networks
• Novel routing algorithms
• Distributed resource allocation – grid computing
• P2P
DIMES@Home
Challenges
• Get A growing community of users to download
and install our DIMES agent
• Optimize the architecture:
– Minimize the number of measurements
– Expedite the discovery rate
•
•
•
•
Flying under the NOC radar screens
Study self-emerging agent collaboration
Data analysis
and more ….
When will DIMES solve the
puzzle?
• Connectivity statistics (links power law)
including hidden links – 12 months
• Delay map – 12 months
• Topology (K-Core, small worldness) including
hidden links – 18 months
• Corresponding I/O traffic statistics – 24
months
– Usage mode statistics (e.g. HTTP vs. P2P)
– Traffic flow mapping
you’ll just have to wait and see…