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 protected]]
Sent: Wednesday, January 20, 2010 06:21
To: [email protected]
Cc: [email protected]; Yaakov Stein; [email protected]
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:
> Danny Mayer wrote:
>
>> 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
>
> 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
>
>
_______________________________________________
TICTOC mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/tictoc
