Sorting Items by a Cyclical Sequence Number

Question

I am developing an algorithm to reorder packets in a transmission. Each packet has an associated sequence number in [0, 256). The first packet's sequence number can take on any one of those values, after which the next packet takes the next value, and the next packet the value after that, and so forth (rolling over after 255).

The sequence numbers of the packets, in the correct order, would appear as follows, where "n" is the first packet's sequence number:

n, n+1, n+2, ..., 254, 255, 0, 1, 2, ..., 254, 255, 0, 1, 2, ..., 254, 255, 0, 1, ...

Each packet is given a timestamp when it arrives at its destination, and they all arrive approximately in order. (I don't have an exact figure, but given a list of packets sorted by arrival timestamp, it is safe to say that a packet will never be more than five spots away from its position in the list indicated by its sequence number.)

I feel that I cannot have been the first person to deal with a problem like this, given the prevalence of telecommunications and its historical importance to the development of computer science. My question, then:

1. Is there a well-known algorithm to reorder an approximately-ordered sequence, such as the one described above, given a cyclically-changing key?

2. Is there a variation of this algorithm that is tolerant of large chunks of missing items? Let us assume that these chunks can be of any length. I am specifically worried about chunks of 256 or more missing items.

I have a few ideas for algorithms for the first, but not for the second. Before I invest the man-hours to verify that my algorithms are correct, however, I wanted to make sure that somebody at Bell Labs (or anywhere else) hadn't already done this better thirty years ago.

Answer 1

I don't know if this solution is actually used anywhere, but here is what I would try (assuming no missing packets, a maximum "shuffeling" of five positions, and a maximum sequence number of 255):

n = 0;
max_heap h = empty;
while( true ) do
  while( h.top().index != 0 ) do
    p = next_packet;
    i = n - p.seq;
    if( i > 0 ) i = i - 255;
    h.add( i, p );
  done

  p = h.pop();
  n = n + 1;
  p.increase_indexes( 1 );
  // Do something with it
done

Basically in the priority queue we store how many packets there are between the last handled packet and the packets still waiting to be handled. The queue will stay very small, because packets are handled as soon as they can, when they come in. Also increasing the keys will be very simple, since no reordering of the heap is necessary.

I am not sure how you could adapt this to missing packets. Most likely by using some timeout, or maximum offset, after which the packtets are declared the "next" and the heap is updated accordingly.

I do not think this problem is possible at all however, if you miss more than 256 packets. Take the subsequences

127,130,128,129

There could be several causes for this

1) Packets 128 and 129 were out of order and should be reordered

2) Packets 128 and 129 were lost, then 253 packtets were lost, so the order is correct

3) A mixture of 1 and 2

Answer 2

Interesting problem!

My solution would be sort the packets according to time of arrival and locally sorting a window of elements (say 10) circularly according to their packet number. You can refine this in many ways. If difference between two consecutive packet numbers (arranged according to time of arrival) is greater than certain threshold you might put a barrier between them (i.e. you cannot sort across barriers). Also, if time difference between packets (arranged according to time of arrival) is greater than some threshold you might want to put a barrier (this should probably take care of problem 2).

Answer 3

Use a priority queue.

After each receiving each packet:

• put it in the queue.
• repeatedly remove the top element of the queue as long as it is the one you're waiting for.

For the second question:

• In general, no, there's no way to solve it.
• If the packet arrival has some periodicity (eg: expecting a packet in every 20ms), then you can easily detect this, clean up the queue, and after receiving 5 packets, you'll know how to process again...