Subject: [ledbat] clock drift compensation

From: [email-masked]
Date: Thu, 10 Jun 2010 19:10:47 +0200

At BitTorrent we have come up with a way to compensate for drift between the
clocks of
the endpoints in a uTP connection.

The conflicting findings we made was that:

1. On some DSL connections, it may take up to 10 minutes for a single packet to
get through
   without any queuing delay, when the connection is saturated.

2. Some computers have a clock drift of up to 15 ms per 10 minutes.

This poses the problem of how frequent the base delay should be updated. If it
is updated
every 10 minutes, the clock drift will have a significant impact on the delay
measurements.
If it is updated more frequent than every 10 minutes, some connections may have
it set
artificially high, becuase no delay-free packet has gotten through.

One important observation regarding clock drift is that it is only ever a
problem for
one of the endpoints. Whichever endpoint sees lower and lower delay
measurements
is not
really affected negatively by the clock drift, since the base delay will be
updated
continuously by the lower delays. However, for the other end, which sees bigger
and bigger
delay measurements, it will be a real problem. For that endpoint, the percieved
delay
will grow and not be reset for at least 10 minutes (or whatever base delay
update frequency
is chosen).

We compensate for the drift by taking advantage of the fact that each endpoint
has all the same
time measurement information as the other endpoint. Since the suggested
protocol
header
(and the actual header in BitTorrent's uTP) includes both a timestamp and the
time stamp
difference from last received packet, we can keep track of the other end's base
delay as well
as our own.

We essentially factored out the logic to compare each received delay sample
with
the base
delay, and to progress a counter in the circular buffer which keeps the history
of our
lowest seen samples. We then apply the same logic to the other end's
measurements. The assumption 
is that every packet we send with a delay measurement in it, will actually be
received.
This assumption seems fairly safe given that packet loss is not part of the
steady state
of LEDBAT connections.

Now that both endpoints know the other's base delay, it can detect all
instances
of
the other ends base delay decreasing. The other end's base delay decreasing
indicates
that there is a clock drift "in their favor", i.e. we'll see artificially high
delays. We
compensate for this by increasing our own base delay by the same amount as the
other end's
base delay is decreasing. From our experiments, this improved the quality of
our
delay
measurements significantly.

We think that this is a strong argument in favor of keeping both the timestamp
and
the time difference in the suggested header.

The slides from our presentation at IPTPS 2010 are available here:

   http://www.usenix.org/event/iptps10/tech/slides/cohen.pdf

The effect of this is especially favorable in our tests since it was a one-way
data
transfer, so the return path was delay-free, which meant that the clock drift
was detected essentially continuously.

--
Arvid Norberg

---

From: Murari Sridharan <[email-masked]>
Date: Fri, 11 Jun 2010 14:40:02 +0000

I haven't read your paper and the framing itself is out of scope for the congestion control document. However one thing that concerns me in your findings is that it may take up to 10 minutes to measure base delay. Can you explain this better why is there such a bias? If this were true then the problem of intra-protocol fairness may be significant. So unless it's a fairly long lived flow this bias will be significant and throughput for different flows may not converge. Right?

Thanks
Murari 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of [email-masked]
Sent: Thursday, June 10, 2010 10:11 AM
To: [email-masked]
Subject: [ledbat] clock drift compensation

At BitTorrent we have come up with a way to compensate for drift between the clocks of the endpoints in a uTP connection.

1. On some DSL connections, it may take up to 10 minutes for a single packet to get through
   without any queuing delay, when the connection is saturated.

This poses the problem of how frequent the base delay should be updated. If it is updated every 10 minutes, the clock drift will have a significant impact on the delay measurements.
If it is updated more frequent than every 10 minutes, some connections may have it set artificially high, becuase no delay-free packet has gotten through.

One important observation regarding clock drift is that it is only ever a problem for one of the endpoints. Whichever endpoint sees lower and lower delay measurements is not really affected negatively by the clock drift, since the base delay will be updated continuously by the lower delays. However, for the other end, which sees bigger and bigger delay measurements, it will be a real problem. For that endpoint, the percieved delay will grow and not be reset for at least 10 minutes (or whatever base delay update frequency is chosen).

We compensate for the drift by taking advantage of the fact that each endpoint has all the same time measurement information as the other endpoint. Since the suggested protocol header (and the actual header in BitTorrent's uTP) includes both a timestamp and the time stamp difference from last received packet, we can keep track of the other end's base delay as well as our own.

We essentially factored out the logic to compare each received delay sample with the base delay, and to progress a counter in the circular buffer which keeps the history of our lowest seen samples. We then apply the same logic to the other end's measurements. The assumption is that every packet we send with a delay measurement in it, will actually be received.
This assumption seems fairly safe given that packet loss is not part of the steady state of LEDBAT connections.

Now that both endpoints know the other's base delay, it can detect all instances of the other ends base delay decreasing. The other end's base delay decreasing indicates that there is a clock drift "in their favor", i.e. we'll see artificially high delays. We compensate for this by increasing our own base delay by the same amount as the other end's base delay is decreasing. From our experiments, this improved the quality of our delay measurements significantly.

We think that this is a strong argument in favor of keeping both the timestamp and the time difference in the suggested header.

The effect of this is especially favorable in our tests since it was a one-way data transfer, so the return path was delay-free, which meant that the clock drift was detected essentially continuously.

--
Arvid Norberg
_______________________________________________
ledbat mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/ledbat

---

From: "Rolf Winter" <[email-masked]>
Date: Sat, 12 Jun 2010 10:40:07 +0200

Hi,

Another interesting thing from the slides is that uTP still has 100ms as a delay target. Are there plans to adjust that? In other words will uTP be LEDBAT compliant?

Best,

	Rolf

NEC Europe Limited | Registered Office: NEC House, 1 Victoria Road, London W3 6BL | Registered in England 2832014 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Murari Sridharan
Sent: Freitag, 11. Juni 2010 16:40
To: [email-masked]; [email-masked]
Subject: Re: [ledbat] clock drift compensation

Thanks
Murari