Subject: [TICTOC] interesting article on a global mechanism for one-way delay measurement

From: Yaakov Stein <[email-masked]>
Date: Wed, 6 Jan 2010 19:16:17 +0200

Hi all,

I have recently been working time distribution in the presence of strong asymmetry,
and have come across a method that helps in certain cases.

I am sure that you all remember the CTP algorithm that I have brought up before
(and presented at IETF-74).

The same academic group has an earlier article that I had previously overlooked.
I am talking about :

Gurewitz O, Sidi M.
Estimating One-Way Delays from Cyclic Path Delay Measurements.
16th IEEE INFOCOM 2001, Anchorage, Alaska. [PDF<http://www.owlnet.rice.edu/~gurewitz/4.pdf>]

This article gives a procedure for determining one-way delays
based purely on round-trip delay measurements (i.e., what we would call T4-T1),
knowledge of topology, and the assumption of additivity of propagation delays.

The idea is that nodes measure round-trip times to various other nodes,
knowing which nodes are traversed.
For example, assume three nodes connected in a triangle
                   1
                /      \
              /          \
            2  --------  3
and we measure the times for the following paths
 1 2 3
 2 3 2
 3 1 3
 1 2 3 1
We thus have 4 equations for 6 variables
(since the links are not assumed symmetric, the variables are D1-2, D2-1, D2-3, D3-2, D1-3, D3-1 ).
Using additivity and non-negativity it turns out that one can solve an optimization problem
which minimizes the error of these equations.

The solution requires a centralized server to do the math PCE-style,
but solves a problem that I don't know any other way to solve.

Comments ?

Y(J)S

---

From: "Doug Arnold" <[email-masked]>
Date: Wed, 6 Jan 2010 10:21:47 -0800

Thanks Yaakov,

This is an interesting idea.  It does require the that complete paths be
known and controlled.  Perhaps it could be used in conjunction with
MPLS.

//Doug

From: [email-masked] [mailto:[email-masked]] On Behalf
Of Yaakov Stein
Sent: Wednesday, January 06, 2010 9:16 AM
To: [email-masked]
Subject: [TICTOC] interesting article on a global mechanism for one-way
delay measurement

Hi all, 

I have recently been working time distribution in the presence of strong
asymmetry,

I am sure that you all remember the CTP algorithm that I have brought up
before

The same academic group has an earlier article that I had previously
overlooked.

I am talking about :

Gurewitz O, Sidi M.
Estimating One-Way Delays from Cyclic Path Delay Measurements.
16th IEEE INFOCOM 2001, Anchorage, Alaska. [PDF
<http://www.owlnet.rice.edu/~gurewitz/4.pdf> ]

based purely on round-trip delay measurements (i.e., what we would call
T4-T1),

knowledge of topology, and the assumption of additivity of propagation
delays.

                   1

                /      \

              /          \

            2  --------  3

 1 2 3

 2 3 2

 3 1 3

 1 2 3 1

(since the links are not assumed symmetric, the variables are D1-2,
D2-1, D2-3, D3-2, D1-3, D3-1 ).

Using additivity and non-negativity it turns out that one can solve an
optimization problem

Comments ?

Y(J)S

---

From: Yaakov Stein <[email-masked]>
Date: Mon, 11 Jan 2010 09:49:16 +0200

Doug

Yes, the topology has be known, although it can change (reroute events) as long as we are informed of this.

For ToD distribution it is a bit less elegant than running full CTP,
but it gives you a better feeling for what is happening.

I think it could go well with MPLS-TP, or even better with MPLS and a PCE box
(which not only knows the topology, but could optimize the timing paths).

Y(J)S

From: Doug Arnold [mailto:[email-masked]]
Sent: Wednesday, January 06, 2010 20:22
To: Yaakov Stein; [email-masked]
Subject: RE: [TICTOC] interesting article on a global mechanism for one-way delay measurement

Thanks Yaakov,

This is an interesting idea.  It does require the that complete paths be known and controlled.  Perhaps it could be used in conjunction with MPLS.

//Doug

From: [email-masked] [mailto:[email-masked]] On Behalf Of Yaakov Stein
Sent: Wednesday, January 06, 2010 9:16 AM
To: [email-masked]
Subject: [TICTOC] interesting article on a global mechanism for one-way delay measurement

Hi all,

Gurewitz O, Sidi M.

Comments ?

Y(J)S

---

From: <[email-masked]>
Date: Tue, 12 Jan 2010 11:19:32 -0000

What do we mean by optimize the timing paths?
 
is this least hops, minimised jitter?
 
When we say the paths are known and controlled i am assuming we need to
know the underlying architecture in detail and minimise the hop / jitter
etc.
 
Regards, 

Mike 

________________________________

From: [email-masked] [mailto:[email-masked]] On Behalf
Of Yaakov Stein
Sent: 11 January 2010 07:49
To: Doug Arnold; [email-masked]
Subject: Re: [TICTOC] interesting article on a global mechanism for
one-way delay measurement

Doug

Yes, the topology has be known, although it can change (reroute events)
as long as we are informed of this.

I think it could go well with MPLS-TP, or even better with MPLS and a
PCE box 

(which not only knows the topology, but could optimize the timing
paths).

Y(J)S

From: Doug Arnold [mailto:[email-masked]] 
Sent: Wednesday, January 06, 2010 20:22
To: Yaakov Stein; [email-masked]
Subject: RE: [TICTOC] interesting article on a global mechanism for
one-way delay measurement

Thanks Yaakov,

//Doug

Hi all, 

I am talking about :

Gurewitz O, Sidi M.

                   1

                /      \

              /          \

            2  --------  3

 1 2 3

 2 3 2

 3 1 3

 1 2 3 1

Comments ?

Y(J)S

---

From: Yaakov Stein <[email-masked]>
Date: Thu, 14 Jan 2010 18:18:24 +0200

Mike

Yes, the idea for real cases would be employ the usual filtering algorithms for the end-point pair round-trip times,
and to use these results in the optimization procedure.

You need to be able to specify that the path from A to B went through C and D (in that order)
in order to be able to say that the time from A to B equals the time from A to C plus the time
from C to D plus the time from D to B. This additivity is the major assumption.

However, there is no assumption of symmetry and no need to use intermediate timestamps.
Instead we find the asymmetric time delays, and then can directly compute the ToD corrections.

Y(J)S

From: [email-masked] [mailto:[email-masked]]
Sent: Tuesday, January 12, 2010 13:20
To: Yaakov Stein; [email-masked]; [email-masked]
Subject: RE: [TICTOC] interesting article on a global mechanism for one-way delay measurement

When we say the paths are known and controlled i am assuming we need to know the underlying architecture in detail and minimise the hop / jitter etc.

Regards,

Mike

Subject: Re: [TICTOC] interesting article on a global mechanism for one-way delay measurement
Doug

Y(J)S

Thanks Yaakov,

//Doug

Hi all,

Gurewitz O, Sidi M.

Comments ?

Y(J)S

---

From: Danny Mayer <[email-masked]>
Date: Sun, 17 Jan 2010 21:48:12 -0500

I'm copying Dave Mills on this, maybe he can say more and that's also
the reason that I'm top-posting. . My feeling on this is that is a very
restricted set of possible problems and is unlikely to be useful for NTP
since most packets go through multiple hops and you are unlikely to get
the outbound path and the return path follow the same paths.

URL: http://www.owlnet.rice.edu/~gurewitz/4.pdf

Danny

Yaakov Stein wrote:
> <http://www.owlnet.rice.edu/~gurewitz/4.pdf>]
> 
>  
> 
>  
> 

-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

---

From: Stewart Bryant <[email-masked]>
Date: Mon, 18 Jan 2010 08:59:37 +0000

Danny

You are correct that in the general case this will not work. However I 
would not write it off so easily. There are subnetworks where this would 
prove useful and which are either sufficiently constrained, or where the 
TWTT packets could be sufficiently constrained, that this would work. 
This is a good example of how applying both time transfer and routing  
to the problem can produce a better solution than can be achieved 
without both sets of expertise.

Just because we can't improve the time transfer for all NTP clients does 
not mean that we should not improve it for some.

- Stewart

---

From: Yaakov Stein <[email-masked]>
Date: Thu, 21 Jan 2010 08:30:51 +0200

Dave, 

Thanks for your comments.

Unfortunately, your numbers became a bit confused.
The original matrix was (I adopt your notation)
          0  10  40
Di,j =   40   0  10
         10  220  0   (not 215)
which symmetrized becomes
          0  25  25
Ei,j =   25   0 115
         25 115  0   .

Your student's dissertation conclusion is not contradicted by 
the Gurewitz and Sidi paper, in fact it is a direct consequence
of the first point of their paper - their Theorem 1. 
Theorem 1 states quite plainly that in a network with N nodes and E edges, 
you can never get more than E - (N-1) equations for the E variables, 
that is, you can never uniquely determine all E delays.

Their next point is that despite the non-uniqueness,
the requirement of non-negativity of the delays 
puts constraints on the space of possible solutions.

I can demonstrate this result using your method.
You quite correctly state that given any delay matrix Dij,
adding an antisymmetric matrix does not change the
symmetrized version Eij.  However, you have to add the fact
that there is an additional constraint - that of the 1 - 2 - 3 trip.
This introduces an additional condition on the elements of the
antisymmetric matrix. Using your notation, we can add
          0  e1 e2
Fij =   -e1   0 e3
        -e2 -e3  0
but only when e1 - e2 + e3 = 0, i.e., when e2 = e1+e3.
Thus the full space of solutions under the measurements 
for the case we described is :
          0          10+e1      40+(e1+e3)
Di,j =   40-e1        0         10+e3
         10-(e1+e3)  220-e3      0 
which indeed leaves a lot of play.
However, note that nonnegativity of 
D1,2 requires e1 > -10
D2,3 requires e3 > -10
D2,1 requires e1 < 40
D3,2 requires e3 < 220 
D3,1 requires that e1+e3<10
D1,3 requires that e1+e3 > -40
so that the space of compliant solutions has
   -10 < e1 < 40
   -10 < e3 < 220
   -40 < e1+e3 < 10  

Note that the symmetrized solution Ei,j is NOT in this space, 
since it corresponds to e1=15, e2=-15, e3=105, which does not obey e2=e1+e3.
This is because it does not obey the curl equations.  

When used for time of day distribution, this method is a definite
improvement over using the symmetrized delay matrix, simply because
its centralized mechanism adds more information. It leaves a bit of "spiel",
but you can estimate its error bounds.

And of course it can be integrated into a distributed (i.e. without centralized swerver)
mechanism  for time distribution described in their later paper.

Y(J)S

-----Original Message-----
From: David Mills [mailto:[email-masked]] 
Sent: Wednesday, January 20, 2010 06:21
To: [email-masked]
Cc: [email-masked]; Yaakov Stein; [email-masked]
Subject: Re: [TICTOC] interesting article on a global mechanism for one-way delay measurement

Guys,

I followed the link to the IEEE paper and was most bemused. About twenty 
years ago one of my students produced a dissertation that concluded an 
unambiguous set of one-way delays cannot be determined for an arbitrary 
network unless at least one clock offset between two nodes or one pair 
of one-way delays are known. The paper makes an alternative claim, so of 
course I am intrigued.

First, both the paper and the analysis here assume only cyclic delays; 
that is, the only known quantities are roundtrip delays dij + dji. 
However, roundtrip paths can span other nodes as described later. 
Furthermore, the paper and this analysis assume the node clocks all run 
at the same rate, but are not necessarily synchronized in time. With 
these assumptions the residence time spent in a node can be detected and 
removed from the cyclic computations

The paper gives as example a three-node, fully connected network with 
delay matrix
           0  10   40
Dij =  40   0   30
          40 215   0

Obviously, D shows highly asymmetric delays. Roundtrip delays can be 
represented by the delay matrix

Eij = (Dij + Dji) / 2,

Where Dji is the transpose of Dij and is symmetric

            0  25   25
Dij =  25    0 115
         25 115     0

as measured by NTP. We have dij + dji roundtrip delays and in addition 
the delays on each directed path

c1 = d12 + d23 + d31 and c2 = d13 + d32 + d21.
With apologies to Maxwell we will call the quantities (c1, c2) the curl. 
For a symmetric matrix where all links are
symmetric, c1 and c2 are equal, in this case (115, 115); for the example 
matrix it is (30, 300). Note that c1 + c2
is the total roundtrip delay of the path from any node around the cycle 
to the same node. It is important to note that these cyclic delays are 
the only values observable; there is no other available information.
Now consider the matrix

           0 +e1 +e2
Fij = -e1    0 +e3
        -e2 -e3     0

and the matrix sum G = D + E. Given values for e1, e2 and e3, the total 
roundtrip delays are unchanged; only the curl is changed. Starting with 
ei = (-15, 15, -105) yields the example delay matrix in the paper. 
Starting with ei = (-15, 20, -100), we get the matrix
 
           0    10  45
Fij =  40      0  15
           5  215    0

which has curl (30, 300) as does the example matrix. There may be other 
choices as well that yield the same cyclic delays and curl.

I am not here to trash the paper and there may be hidden consequences I 
have missed, especially since the PDF is fuzzy and some typeset 
adornments hard to read. However, while the paper does find a consistent 
set of one-way delays, it fails to note that this is not the only 
solution and the conclusion reached in the dissertation cited is correct.

Dave

Stewart Bryant wrote:

> would not write it off so easily. There are subnetworks where this 
> would prove useful and which are either sufficiently constrained, or 
> where the TWTT packets could be sufficiently constrained, that this 
> would work. This is a good example of how applying both time transfer 
> and routing  to the problem can produce a better solution than can be 
> achieved without both sets of expertise.
>
> Just because we can't improve the time transfer for all NTP clients 
> does not mean that we should not improve it for some.
>
> - Stewart
>
>

---

From: Stewart Bryant <[email-masked]>
Date: Mon, 25 Jan 2010 11:27:24 +0000

Yaakov

I ran the exhaustive search for solutions just to get a feel for the 
properties of this approach.

In increments of 1 there are 406 solutions* that meet both the known 
delay constraints and the non-zero constraints.

28 of these solutions set x12 = 1, and one set x12 to 28.

The average of the solutions was indeed

x12 = 10, x21 = 40, x23 = 10, x32 = 220, x13 = 40, x31 = 10

but there were 405  other valid solutions such as

n = 397, x12 = 25, x21 = 25, x23 = 1, x32 = 229, x13 = 46, x31 = 4
n = 398, x12 = 25, x21 = 25, x23 = 2, x32 = 228, x13 = 47, x31 = 3
n = 399, x12 = 25, x21 = 25, x23 = 3, x32 = 227, x13 = 48, x31 = 2
n = 400, x12 = 25, x21 = 25, x23 = 4, x32 = 226, x13 = 49, x31 = 1
(meets the x12 = x21 approximation)

Nothing meets the x23 = x32 approximation, indeed x23 never get out of 
the range 220:229,  and there are four cases that meet the x13 = x31 
approximation.

The assertion here is that taking an average of the solutions over a 
number of cycles in the graph is better than taking an approximation 
over a single cycle in the graph (the standard TWTT approach), and the 
example above which includes gross asymmetry  illustrates  this.

However we need to get a better handle on the  mathematics  before we 
fully understand this. For example what if this are a lot of symmetric 
paths  and a few asymmetric paths. Without doing either the math or the 
simulation, I would expect that this would result in the asymmetric 
paths degrading the symmetric approximation, the question is by how much?

This approach is interesting and definitely warrants further 
investigation. It would be interesting to run the model over the 
measured data from a number of real networks.

If the approximation had greater validity than the standard single cycle 
approach (and it might, although there might be a better set of 
weighting depending on the size of the cycle for example), building a 
protocol to support it in a link state IGP would be easy.

- Stewart

* There was only one solution in incs of 10, and it was x12 = 10, x21 = 
40, x23 = 10, x32 = 220, x13 = 40, x31 = 10

---

From: Yaakov Stein <[email-masked]>
Date: Mon, 25 Jan 2010 18:23:51 +0200

Stewart

Your simplistic approach found exactly what the authors found.
Once they saw that there were two variables that could not be pinned down
(from their paper since when N=3, N-1-2, so they defined beta_1 and beta_2;
 in the language of the exchange between Dave Mills and myself, e1 and e3) 
they mapped out the area of possible solutions, and took the average.
What you did was to discretize the area of possible solutions
by looking for them using a brute force method, and to average them.

I was thinking of solving this kind of problem in a more graded way.

If you think about it, before any measurements are made all delays are possible.
Every measurement reduces the area in solution space, until when you have
the maximum number of independent equations, E - (N-1) you are left with
a subspace of dimension N-1 with limitations due to the non-negativity constraints.

In the 3 node ring example, there are 6 unknowns, so you start off with
knowing nothing about where in 6-dimensional space the true delays are.
After accruing 4 equations, you are left with a 2 dimensional plane
upon which the delays must lie. Furthermore, the constraints give
a polygonal area on this plane inside which the delays must be.
If the symmetrized solution is not inside this polygonal area,
then it can't be the right solution.
As a best guess take the center of mass of the polygonal area.

Note that information of a different kind can reduce the area of possible solutions
even further. For example, if there is another point with the same ToD (e.g. from GPS)
then you can find one delay precisely, and this collapses the area.

I think this is a genuinely useful technique to use in cases of strong asymmetry,
when other information is not available.

Of course, you need to know the topology, so perhaps this is an algorithm
that routers should use, rather than endpoints.
Of course, routers may have much better ways of determining delays,
such as BFD echo mode.

Y(J)S

-----Original Message-----
From: Stewart Bryant [mailto:[email-masked]] 
Sent: Monday, January 25, 2010 13:27
To: Yaakov Stein
Cc: David Mills; [email-masked]; [email-masked]; Mike Shand
Subject: Re: [TICTOC] interesting article on a global mechanism for one-way delay measurement

Yaakov

- Stewart

---

From: Stewart Bryant <[email-masked]>
Date: Mon, 25 Jan 2010 17:02:47 +0000

> by looking for them using a brute force method, and to average them.

Yaakov, the reason that I took this approach was a practical one - there 
are a lot of triangular loops in a network, particularly and enterprise 
network, so with some very simple network technology we can determine 
the asymmetry in a large number of sub-networks within the network as a 
whole. So we can mechanistically determine these paths and probe them.

I also not that in the second example the information gathered at node 1 
is essentially the next neighbour delays for all nodes plus the three 
shortest indirect paths back to 1 via the next hop, which could be 
approached mechanistically.

In general what you need is the time on your own SPF tree, not the whole 
set of times that exist in the network. So it would be logical for 1 to 
work with the loops 1-2-3-5-6 and 1-10-9-8-6 and for 1 to gather the 
2-4-7-9 times from the measurements taken by one of those nodes.

Also note that if 4-7 did not exist and the clock was at 4 of 7 all 
nodes would have to make the standard symmetry assumption for the 4-2 
and the 9-7 hops.

- Stewart

---

From: Yaakov Stein <[email-masked]>
Date: Wed, 27 Jan 2010 11:59:37 +0200

Stewart

I agree that for finding times between routers this is a good approach.

However, you only need this approach when there is asymmetry.
Between two directly connected routers there will not usually be asymmetry,
and simpler approaches are possible (e.g., BFD echo mode).

The exceptions would be routers connected over one-way SONET rings,
routers connected over a complex (not necessarily symmetric) L2 network,
or routers connected with different rates in the two directions.

Y(J)S

-----Original Message-----
From: Stewart Bryant [mailto:[email-masked]] 
Sent: Monday, January 25, 2010 19:03
To: Yaakov Stein
Cc: David Mills; [email-masked]; [email-masked]; Mike Shand
Subject: Re: [TICTOC] interesting article on a global mechanism for one-way delay measurement

- Stewart