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 ca= ses.

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.

Gurewitz O, Sidi M.
Estimating One-Way Delays from Cyclic Path Delay Measurements.
16th IEEE INFOCOM 2001, Anchorage, Alaska. [PDF]

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

knowledge of topology, and the assumption of additivit= y of propagation delays.

The idea is that nodes measure round-trip times to var= ious other nodes,

knowing which nodes are traversed.

For example, assume three nodes connected in a triangl= e

=           1

= ;      /      \

= ;    /          \

=    2  --------  3

and we measure the times for the following paths<= /o:p>

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 variab= les 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 m= ath PCE-style,

but solves a problem that I don't know any other way t= o solve.

Y(J)S

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:= tictoc-bounces@ietf.org [mailto:tictoc-bounces@ietf.org] On Behalf Of = Yaakov Stein
Sent: Wednesday, January 06, 2010 9:16 AM
To: tictoc@ietf.org
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,

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.

Gurewitz O, Sidi M.
Estimating One-Way Delays from Cyclic Path Delay Measurements.
16th IEEE INFOCOM 2001, Anchorage, Alaska. [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.

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

&= nbsp;         1

/    =   \

/    =       \

&= nbsp;  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.

Y(J)S

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 bette= r 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 th= e topology, but could optimize the timing paths).

=

Y(J)S<= /p>

=

From: Doug Arnold [mailto:darnold@symmetricom.com]
Sent: Wednesday, January 06, 2010 20:22
To: Yaakov Stein; tictoc@ietf.org
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: tictoc-bounces@ietf.org [mailto:tictoc-bounces@ietf.org] On Behalf Of Yaakov Stein
Sent: Wednesday, January 06, 2010 9:16 AM
To: tictoc@ietf.org
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,

and have come across a method that helps in certain ca= ses.

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.

Gurewitz O, Sidi M.
Estimating One-Way Delays from Cyclic Path Delay Measurements.
16th IEEE INFOCOM 2001, Anchorage, Alaska. [PDF]

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

knowledge of topology, and the assumption of additivit= y of propagation delays.

The idea is that nodes measure round-trip times to var= ious other nodes,

knowing which nodes are traversed.

For example, assume three nodes connected in a triangl= e

=           1

/    &n= bsp; \

/    &n= bsp;     \

=    2  --------  3

and we measure the times for the following paths<= /o:p>

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 variab= les 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 m= ath PCE-style,

but solves a problem that I don't know any other way t= o solve.

Y(J)S

What do we mean by optimize the timing=20 paths?

is this least hops, minimised=20 jitter?

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

Regards,

Mike

From: tictoc-bounces@ietf.org=20 [mailto:tictoc-bounces@ietf.org] On Behalf Of Yaakov=20 Stein
Sent: 11 January 2010 07:49
To: Doug Arnold;=20 tictoc@ietf.org
Subject: Re: [TICTOC] interesting article on a = global=20 mechanism for one-way delay measurement

Doug

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

For ToD distribution = it is a bit=20 less elegant than running full CTP,

but it gives you a = better=20 feeling for what is happening.

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

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

Y(J)S

From: Doug = Arnold=20 [mailto:darnold@symmetricom.com]
Sent: Wednesday, January 06, = 2010=20 20:22
To: Yaakov Stein; tictoc@ietf.org
Subject: RE: = [TICTOC] interesting article on a global mechanism for one-way delay=20 measurement

Thanks=20 Yaakov,

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

//Doug

From:=20 tictoc-bounces@ietf.org [mailto:tictoc-bounces@ietf.org] On Behalf Of = Yaakov Stein
Sent: Wednesday, January 06, 2010 9:16=20 AM
To: tictoc@ietf.org
Subject: [TICTOC] interesting = article=20 on a global mechanism for one-way delay=20 measurement

Hi all,

I have recently been working time distribution in = the=20 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=20 brought up before

(and presented at IETF-74).

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

Gurewitz=20 O, Sidi M.
Estimating One-Way Delays from Cyclic Path Delay=20 Measurements.
16th IEEE INFOCOM 2001, Anchorage, Alaska. [PDF]

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

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

The idea is that nodes measure round-trip times to = various=20 other nodes,

knowing which nodes are traversed.

For example, assume three nodes connected in a=20 triangle

&= nbsp;        =20 1

=20         /    =  =20 \

=20         /    =     =20  \

&= nbsp; =20 2  --------  3

and we measure the times for the following=20 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=20 D1-2, D2-1, D2-3, D3-2, D1-3, D3-1 ).

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

which minimizes the error of these = equations.

The solution requires a centralized server to do = the math=20 PCE-style,

but solves a problem that I don't know any other = way to=20 solve.

Y(J)S

Mike

=

Yes, the idea for real c= ases 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 s= pecify that the path from A to B went through C and D (in that order)=

in order to be able to s= ay that the time from A to B equals the time from A to C plus the time

from C to D plus the tim= e from D to B. This additivity is the major assumption.

=

However, there is no ass= umption of symmetry and no need to use intermediate timestamps.

Instead we find the asym= metric time delays, and then can directly compute the ToD corrections.<= /span>

=

Y(J)S<= /p>

=

From: mike.gilson@b= t.com [mailto:mike.gilson@bt.com]
Sent: Tuesday, January 12, 2010 13:20
To: Yaakov Stein; darnold@symmetricom.com; tictoc@ietf.org
Subject: RE: [TICTOC] interesting article on a global mechanism for one-way delay measurement

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: tictoc-bounces@ietf.org [mailto:tictoc-bounces@ietf.org] On Behalf Of Yaakov Stein
Sent: 11 January 2010 07:49
To: Doug Arnold; tictoc@ietf.org
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.=

=

For ToD distribution it = is a bit less elegant than running full CTP,

but it gives you a bette= r 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 th= e topology, but could optimize the timing paths).

=

Y(J)S<= /p>

=

From: Doug Arnold [mailto:darnold@symmetricom.com]
Sent: Wednesday, January 06, 2010 20:22
To: Yaakov Stein; tictoc@ietf.org
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: tictoc-bounces@ietf.org [mailto:tictoc-bounces@ietf.org] On Behalf Of Yaakov Stein
Sent: Wednesday, January 06, 2010 9:16 AM
To: tictoc@ietf.org
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,

and have come across a method that helps in certain ca= ses.

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.

Gurewitz O, Sidi M.
Estimating One-Way Delays from Cyclic Path Delay Measurements.
16th IEEE INFOCOM 2001, Anchorage, Alaska. [PDF]

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

knowledge of topology, and the assumption of additivit= y of propagation delays.

The idea is that nodes measure round-trip times to var= ious other nodes,

knowing which nodes are traversed.

For example, assume three nodes connected in a triangl= e

=           1

/    &n= bsp; \

/    &n= bsp;     \

=    2  --------  3

and we measure the times for the following paths<= /o:p>

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 variab= les 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 m= ath PCE-style,

but solves a problem that I don't know any other way t= o solve.