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 protected]] Sent: Monday, January 25, 2010 13:27 To: Yaakov Stein Cc: David Mills; [email protected]; [email protected]; Mike Shand Subject: Re: [TICTOC] interesting article on a global mechanism for one-way delay measurement 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 _______________________________________________ TICTOC mailing list [email protected] https://www.ietf.org/mailman/listinfo/tictoc
