TCP Adaption Algorithms

Before we look at the mechanisms to multimedia adaption, it is worth explaining how the current system survives at all for data flows! It is essentially achieved by smoothly degrading everyone's performance smoothly as load increases (rather than blocking access) that the current Internet continues to function. This is done through a variety of adaption algorithms, both for data and for multimedia applications. Adaption in protocols was first introduced in TCP in around 1988[#!van:88!#].

Adaption in TCP is both to the round trip time, in order to dynamically tune retransmit timers for reliable delivery, and of the send rate in order to adapt to the achievable transfer rate between the sender and receiver (possible due to network bottlenecks, or receiver interface performance problems). The same techniques can often be applied in other protocols, in particular for multimedia services to operate over time varying network services.

Adaption to delay at the receiver can be used for two things:

1.

Adaptive playout buffer to smooth playout so that a fixed rate media device (e.g. within a single video frame scan, or a dumb CBR audio device) isn't starved of data, or overrun.

2.

Syncronisation of streams from different source (timestamp) can be achieved at a receiver.

The first of these is done by looking at the Inter-Arrival Time variation, and calculating a "rolling average".

It is needed to deal with the fact that there are variations in network delay for two reasons:

• Other traffic causes long term average to vary.
• Bursts of one's own traffic cause ones own delay to vary quickly.

The usual algorithm for this is an ``Exponential Weighted Moving Average'':

Assume we measure the arrival time for each (i'th) packet as IAT i then the simple average would be: sum_i=1ⁿ IAT_i, divided by the number of packets.

But since the average is not fixed, we give the most recent measurements a lot more weight than the older ones by using:

$\bar{IAT_i} = IAT_i * alpha + (1 - alpha) * \bar{IAT_{i-1}}$

In other words, we give alpha's worth of credence to the latest measurement, and only 1 - alpha to ALL the previous ones. It is only a coincidence that the equation for a rolling, moving average for IAT estimation is the same as the one for TCP's RTT estimation. It is worth noting, however, that in both cases, the requirement is only for local clocks not to drift too fast so that the measurement of successive arrival times of packets is accurate w.r.t the previous ones; but no clock synchronisation is needed.

This is sometimes not used, as it includes all the past, and if there is a fundamental change in the network (e.g. a re-route) then a system that eliminates outlying points quickly may be better. Henning Sculzrinne's paper suggests a "band pass filter" approach to the estimation of mean IAT, based on taking only the sum of the smallest of a set of measurements recently, over the number of them.

Once you have a mean IAT, then you can calculate the current required playout buffer, since it is roughly twice the variation in interarrival.

Given two streams, to synchronise their playout at a receiver we need to know the delay from each source to each destination, and the clock offsets in case the clocks in the two (or more) senders are out of step with the receiver. This requires the exchange of packets including each senders statement of the current clock from its view. Assume that the delay in each direction on the net is the same (and if you don't it is impossible to solve this):

1.

send a packet from s to d with source time in it (t1) and it arrives at d when d's clock reads t2

2.

send the packet back to s with t1, t2 and t3, the time on d's clock when it sends it

3.

s gets the response at t4 by its clock.

4.

if s and d have clocks that differ by offset, and the network delay is d then

t4 = t3+offset+delay

but

t2=t1-offset+delay

so

delay = (t4+t2-t3+t1)/2

and offset can be similarly calculated. we then do this for several goes, and keep a mean and variance.

 

Table 5.1: Status of Protocols with Adaption Algorithms

TCP Adaption Status: IETF Proposed Standard RFC 2001

RTP Status: IETF Proposed Standard RFC 1889.