8

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.

HardlyKnowEm
  • 3,196
  • 20
  • 30

3 Answers3

1

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).

ElKamina
  • 7,747
  • 28
  • 43
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

LiKao
  • 10,408
  • 6
  • 53
  • 91
  • How would you make a provision if we were not guaranteed that the first packet's sequence number (`n` in your example, I believe) is 0? In the worst case: what if packet 255 was sent first, but packet 0 and 1 arrive first? – HardlyKnowEm Feb 01 '12 at 19:31
  • Hmm, not sure. Actually I do not think this problem is so common, from my experience. Usually sequence numbers are much larger to account for this. The only place where I have ever seen something as low as this in a sequence number are concatenated gsm-sms, which go up to 255 AFAIK. However this is 256 sms per sender before wrapping and even there is a different encoding wich allows for larger sequence numbers in concatenated sms. Some protocols even have globaly unique ids. What was the reason for choosing such a small range? – LiKao Feb 01 '12 at 21:38
  • To make a long story short, the sequence numbers were never meant for recreating a transmission. The data was originally transmitted over a short serial cable. The sequence numbers were primarily a debugging tool and sanity check. Then, all of a sudden, project requirements changed, but this feature has long since been frozen. I think I might be able to do it if I examine the particular datasets and can characterize the average rate of transmission (I suspect it's close to <1 per second). – HardlyKnowEm Feb 02 '12 at 06:03
0

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...
Karoly Horvath
  • 94,607
  • 11
  • 117
  • 176
  • To clarify: 1) What should I use as the key in the priority queue? 2) How will I know which packet is supposed to come first? – HardlyKnowEm Feb 01 '12 at 18:26
  • a) you can use the sequence number, in which case you have to do the comparison in a circular fashion... (255 < 0, you can use a simple rule like anything that greater than 240 is < than anything smaller than 10). b) you can use internal sequencing, which always increases... (0..255 maps to 0..255, the next run maps to 256..511, etc..). since packets are at most 5 places away from their orig position you always know how to map. – Karoly Horvath Feb 01 '12 at 22:25