Transcript Evaluation of network distance properties

UMR 5205
Evaluation of network distances properties:
NDS, the Network Distance Service.
Julien Gossa
GridNets 2006 - 2006/10/01
{firstname.lastname}@liris.cnrs.fr - http://liris.cnrs.fr/
Laboratoire d'InfoRmatique en Image et Systèmes d'information
LIRIS UMR 5205 CNRS/INSA de Lyon/Université Claude Bernard Lyon 1/Université Lumière Lyon 2/Ecole Centrale de Lyon
Université Claude Bernard Lyon 1, bâtiment Nautibus
43, boulevard du 11 novembre 1918 — F-69622 Villeurbanne cedex
http://liris.cnrs.fr
GridNets 2006 - 2006/10/01
Network Distances (1)
Network distances are used for many purposes
Distance Vector Protocols
RIV, IGRP, EIGRP, OSPF…
Network problem solving
data management
network topology discovering
resource brokering
nodes clustering…
Using distance is comfortable
It makes the network looking like the real world
Distances are also called metrics
GridNets 2006 - 2006/10/01
2
Network Distances (2)
Generally very simple:
Latency (or RTT) only
IDMaps (Francis et al. 2001)
Global Network Positioning (GPN) (Eugene et al. 2002)
“Automatic clustering of grid nodes” (Xu et al. 2005}
Rarely Bandwidth
IDMaps (Francis et al. 2001) “when available“
But with a strong assumption: Euclidean Space
Mostly the properties: symmetry and triangle inequality
Comes from the will to refer to the real world
GridNets 2006 - 2006/10/01
3
Network Distances (2)
But isn’t this assumption too strong?
For instance,
because of asymmetric IP routes or
asymmetric connection (ADSL)
Moreover
The satisfaction can differ from a network to another one
According to the infrastructure homogeneity and condition
The satisfaction might not be perfect, but acceptable
For instance, latency uplink and downlink can differ of 0.5%
We propose to identify exhaustively what are the
interesting properties of network distances
GridNets 2006 - 2006/10/01
4
Network Distance Properties
The first 4 refer to Euclidean Space properties
The last 2 are useful in peculiar cases only
GridNets 2006 - 2006/10/01
5
Properties’ Satisfaction Degree
But:
Distance are measured and thus approximate
For instance
The measure uplink and downlink may differ of 1%
This difference can be acceptable or not
According to the end use of the distance
Thus, its necessary to compute satisfaction degree
For each property
Based on actual measurements
Thus for each environment
And even at each time in case of great instability
GridNets 2006 - 2006/10/01
6
Properties’ Satisfaction Degree
One satisfaction degree
Per property
Per distance
Per couple of end-points
statistics
network:
for
the
whole
Min/Max
Mean/Variance
And RoutesRatio:
GridNets 2006 - 2006/10/01
7
Properties’ Satisfaction Degree
Finally, the global satisfaction degree is obtained
with the RouteRatio
of a given property p
for a given metric m
It gives the ratio of routes which satisfaction
degree is higher than a threshold t
t has to be defined by the user
According to its use of the distance
And the impact of the properties dissatisfaction
GridNets 2006 - 2006/10/01
8
Experimentation
Experimentation has been done
On our (small) test grid:
5 computers located in 3 cities (Lyon, Toulouse and Lille)
Connected through the Internet (shared network)
With measurements from the Network Distance Service (NWS)
Which treatment are embedded in the Network Distance Service
We evaluated the satisfaction of:
Symmetry, Triangle Inequality
Substitutability and Splitability
Of the metrics:
Latency Lat
Bandwidth BW
A compound metrics DTT=3xLat+data_size/BW
 For several values of data_size
GridNets 2006 - 2006/10/01
9
Experimentation
GridNets 2006 - 2006/10/01
10
Experimentation - Conclusion
The symmetry is well satisfied by latency and DTT but not by
Bandwidth.
 For instance, IDMaps should not be used with bandwidth in our test
grid
The triangle inequality is not fully satisfied by Latency and
Bandwidth
 This property should be taken with extreme care (which compromise
the use of most of the works using distances)
The splitability is very well satisfied by Latency but not by
Bandwidth.
 This meets the property of latency at routing level where packets are
transferred from a routing device to one other, adding latency along the
route.
Then substitutability is well satisfied by all the metrics.
 This results is biased because of the small size of our test grid: no
conclusion can be done.
GridNets 2006 - 2006/10/01
11
Conclusion
Network distance are popularly used
But with potentially too strong assumptions
To treat this issue, we have
Identify the different interesting properties of network
distances
Define a satisfaction degree for each and a method to
check the satisfaction of a property at network-scale
Embed these computations in a globus Web Service
The
Network Distance Service (NDS)
GridNets 2006 - 2006/10/01
12
Conclusion
Thanks for attention !
GridNets 2006 - 2006/10/01
13