Re: delay as a metric, aggregation

[Cedric de Launois <delaunois@info.ucl.ac.be>]

Le mercredi 28 septembre 2005 à 16:40 +0200, Iljitsch van Beijnum a
écrit :
> On 28-sep-2005, at 14:48, Cedric de Launois wrote:
> 
> > I elaborated a solution some months ago to estimate delays associated
> > with a couple of src-dst prefixes. I proposed to associate synthetic
> > coordinates to a prefix. The euclidean distance between two  
> > coordinates
> > aims to predict the delay between the prefixes. The synthetic
> > coordinates are computed in a very scalable way by using an algorithm
> > taken from the p2p litterature.
> 
> Yes, I remember your paper and our discussion in Brussels.
> 
> I don't remember off the top of my head whether your system had  
> significant downsides or what those are, but do you feel it's so good  
> that it negates the need for actual measurements?

Actual measurements are still performed of course, but only for
computing the synthetic coordinates, and with a limited number of nodes.
This number is constant, and does not increase with the total number of
nodes using the coordinates.

Here is an example :

Site A has prefixes P1 and P2,
       with coordinates (15, 25) and (21, 30) respectively

Site B has prefixes P3 and P4,
       with coordinates (5, 12) and (2, 16) respectively

Site A has four possible prefix pairs to join Site B. To know which
prefix pair yields to the lowest delay path, it follows these steps :

- Site A queries the DNS for prefixes and coordinates of Site B
- Site A receives P3 with coord (5, 12) and P4 with coord (2, 16)
- Site A computes locally the euclidean distances between the
  coordinates of its own prefixes and the coordinates of the prefixes
  of Site B :

  P1->P3 :   || (15, 25) - (5, 12) || = 16.4 ms
  P2->P3 :   || (21, 30) - (5, 12) || = 24.1 ms
  P1->P4 :   || (15, 25) - (2, 16) || = 15.8 ms  <-- best
  P2->P4 :   || (21, 30) - (2, 16) || = 23.6 ms

- Site A selects the best prefix pair according to the delay predicted
  by the coordinates, i.e. (P1, P4) here, with a predicted delay of
  15.8ms.

Notes :
- 2-D euclidean coordinates are used here. In practice, this can be
  any coordinate system
- A single DNS request can be used to retrieve prefixes AND coordinates,
  as Francis pointed out. The overload is low, especially if we take  
  care that the coordinates do not change often (and thus can be heavily
  cached)
- The system is fully distributed, no infrastructure needed
- coordinates are assigned to a prefix, but can also be assigned to a
  particular host when a better precision is needed


The challenge is to compute good enough coordinates. But there is
abundant literature from the P2P world on how to do that. I personnally
used in my simulations an improved version of the Vivaldi algorithm.
This was sufficient to avoid all really bad paths.

Cedric