Transcript Π f(Xij)

A Survey on Physical Network
Topology Estimation
October 21, 2005
Chikayama-Taura Lab.
Tatsuya Shirai
2005/10/21
1
Background


Progress of parallel processing
technologies
Costs of parallel processing



Cost of computation
Cost of communication
Clusters, Grid Environments

Cost of communication becomes bigger
with larger scale
2005/10/21
2
Allocation Policy

Needs to closely allocate hosts frequently
communicating with each other


With multiple clusters, allocate within clusters
In single cluster, allocate to use the same
switches
2005/10/21
3
Difficulty of estimate the cost
of communication

Shared link



Each hosts can solely communicate at
100Mbps
But all hosts can communicate at less than
50Mbps at a time
All hosts need to work together to know this
relation
1
2005/10/21
2
3
100Mbps
4
4
Desired Functions

Ideally,



Present network information to users
Configure allocation automatically
Needs to analyze network topology
2005/10/21
5
Other applications





Network trouble shooting
Discovery of bottlenecks
Research on routing protocol
Simplification of local network
etc…
2005/10/21
6
Agenda





Background
Network Topology
End-to-End Measurement
Researches
Conclusion
2005/10/21
7
Agenda





Background
Network Topology
End-to-End Measurement
Researches
Conclusion
2005/10/21
8
Network Topology

A structure of a network

node




host
router
switch, hub
link
2005/10/21
9
IP Layer Topology

Structure of network

node





host
router
switch, hub
Link
Difficulty in collecting
information of LAN
structure
2005/10/21
10
Protocol-Based Algorithms

Protocol


[Richard et al, ‘04]
, etc.
Hardware-dependent


SNMP [Yuri et al, ’01] ,
Customized Protocol
Some hubs or switches doesn’t support
required protocols.
Deterministic estimation
2005/10/21
11
End-to-End Measurement

Metric


Hardware independent


Packet loss rates [Bestavros et al, ‘02]
Delays [Coates et al, ‘01]
Always possible to measure topologies of
hosts who can communicate with root
Probabilistic
2005/10/21
12
Classification
IP layer
Protocol
based
End-to-End
Measurement
Nodes
Hosts,
routers
Hosts,
routers,
switches
Hosts,
routers,
switches,
hubs, …
Hardware
dependency
dependent
dependent
independent
Estimation
Deterministic Deterministic Probabilistic
2005/10/21
13
Agenda





Background
Network Topology
End-to-End Measurement
Researches
Conclusion
2005/10/21
14
End-to-End Measurement

Assume topologies are Tree-structured



Only one route exists between two hosts.
Does not be changed while measuring
Estimate branches of routes connecting
hosts
2005/10/21
15
Estimated topology using
End-to-End Measurement
unused
non-branching
branching
actual topology
2005/10/21
estimated topology
16
End-to-End Measurement

Assume topologies are Tree-structured




Only one route exists between two hosts.
Does not be changed while measuring
Estimate branches of routes connecting
hosts
Variance in the measurements
2005/10/21
17
Variance of measurements


With a small variance, estimation is
deterministic
With a large variance, estimation is
probabilistic


Use statistics
Search the topology that fits the most with
measurement
2005/10/21
18
End-to-End Measurement

Assume topologies are Tree-structured





Only one route exists between two hosts.
Does not be changed while measuring
Estimate branches of routes connecting hosts
Variance in the measurements
Procedures consist of 2 steps
1. Measurement
2. Estimation
2005/10/21
19
Agenda





Background
Network Topology
End-to-End Measurement
Researches
Conclusion
2005/10/21
20
Researches

Maximum Likelihood Network Topology
Identification from edge-based unicast
measurements [Coates et al. ’01 SIGMETRICS]


Metric : Delay
Estimation: Maximum Likelihood Estimation
2005/10/21
21
Measurement –Sandwich Probe –
1
Measure delay of a link
shared 2 hosts (e.g. 2 and 4) d
1. Send a small packet to 4
2. After constant time, send a
large packet to 2
3. Without break, send a small
packet to 4 again

2
3
4
d+⊿d
2005/10/21
22
Measurement



The arrival of the second
packet is delayed because
the large packet is slower
Assume that all branched
nodes are not store &
forward
Can measure delay (or
bandwidth) of shared link
X42 = μ1+d
X32 = μ1+μ2+d
2005/10/21
1
d
μ1
μ2
2
3
4
X32
X42
23
Estimation


Assume delay of each shared link obeys
Gaussian f(x)
Search the topology best fitting the
measurements
⇒ Maximum Likelihood Estimation
(MLE)
2005/10/21
24
Likelihood



The value of “fitting”
1
μ1
Set particular topology and
delay as a parameter
Likelihood = Π f(Xij)
3
2
X32= μ1+μ2
2005/10/21
μ1
4
X42= μ1
μ1
25
Search Space of MLE



Give many possible topologies to search
for MLE
Too wide to compute all topologies
Premise

Similar topologies have similar likelihoods
⇒ Markov Chain Monte Carlo (MCMC)
(e.g. Hill Climbing)
2005/10/21
26
Similar Topologies –Step–
Birth step



Insert a node
1
2
3
2005/10/21
Death step

1
4
2
3
Delete a node
1
4
2
3
1
4
2
3
4
27
Procedure of MLE
1. Give a topology at random
2. Make a small modification
3. If the new topology has greater likelihood,
adopt new topology
4. If a likelihood is at local maximum,
return to procedure 1
5. Otherwise goto2
 Can get a great likelihood topology in feasible
time
2005/10/21
28
Experiment

Experimental Setup


Measurement



The root host and ten other hosts
2
Sent 8600 probes (O(n ))
For 8 minutes
MLE

For 30-120 seconds
2005/10/21
29
The estimated
topology using
traceroute
The estimated
topology using
Coates’ method
2005/10/21
30
Agenda





Background
Network Topology
End-to-End Measurement
Researches
Conclusion
2005/10/21
31
Conclusion

Conclusion


I Indicated importance of topology
estimation and introduced one methods
with End-to-End measurement
Future Works

Topology Estimation within LAN of many
nodes
2005/10/21
32