next up previous contents
Next: Multiple Source Ordering Up: Ordering Previous: Ordering

Single Source Reordering

Addressing reordering of messages from a single source first; there are many possible schemes, almost all of which require a sequence number or a timestamp. A few examples are:

1.
Ignore the problem. A suitable example is for session messages reporting presence in a conference.

2.
Deal with messages immediately. Discard any packets that are older than the latest seen. Quite a number of applications may be able to operate effectively in the manner. However, some networks can cause very severe reordering, and it is questionable as to whether this is desirable.

3.
Using the timestamp in a message and the local clock, estimate the perceived delay from the packet being sourced that allows (say) 90% of packets to arrive. When a packet arrives out of order, buffer it for this delay minus the perceived trip time to give the missing packet(s) time to arrive. If a packet arrives after this timeout, discard it. A similar adaptive playout buffer is used in vat for removal of audio jitter. This is useful where ordering of requests is necessary and where packet loss can be tolerated, but where delay should be bounded.

4.
Similar to above, specify a fixed maximum delay above minimum perceived trip time, before deciding that a packet really has been lost. If a packet arrives after this time, discard it.

5.
A combination of [3] and [4]. Some delay patterns may be so odd that they upset the running estimate in [3]. Many conference control functions fall into this category, i.e. time bounded, but tolerant of loss.

6.
Use a sliding window protocol with retransmissions as used in TCP. Only useful where loss cannot be tolerated, and where delay can be unbounded. Very tightly coupled conferences may fall into this category, but will be very intolerant to failure. Should probably only be used along with application level timeouts in the transmitting application.

It should be noted that all except [1] require state to be held in a receiver for every source. As not every message from a particular source will be received at a particular receiver due to CCCP's multiple destination group model, receiver based mechanisms requiring knowing whether a packet has been lost will not work unless the source and receiver use a different sequence space for every (source, destination group) pair. If we wish to avoid this (and I think we usually do!), we must use mechanisms that do not require knowing whether a packet has been lost.

Thus the above list of mechanisms becomes:

1.
Have CCCP ignore the problem. Let the application sort it out.

2.
Have CCCP deal pass messages to the application immediately. Discard any packets that are older than the latest seen.

3.
As above, estimate the perceived delay within which (say) 90% of packets a particular source arrive, but delay all packets from this source by the perceived delay minus the perceived trip time.

4.
As above, calculate the minimum perceived trip time. Add a fixed delay to this, and buffer all packets for this time minus their perceived trip time.

5.
A combination of [3] and [4], buffering all packets by the smaller of the two amounts.

6.
Explicitly ack every packet. Do not use a sliding window.

Note that just because CCCP cannot provide more elaborate mechanisms, this does not mean an application itself (with some semantic knowledge) cannot build a more elaborate mechanism on top of any of [1]..[5]. However it does mean that message timestamps and sequence numbers must be available at the application level.


next up previous contents
Next: Multiple Source Ordering Up: Ordering Previous: Ordering
Jon CROWCROFT
1998-12-03