networking - which data structure to choose for ip datagram reassembly at receiver end?

Question

While reassembling datagram at receiver which data structure would be better in terms of

1. if 1-2 fragment got lost we should discard complete datagram
2. sorting of fragments should be faster
3. if fragments are further fragmented then reassembling all should be smooth.

Answer 1

Short answer: Array, usually termed as Buffer.

Long answer:

You can read RFC 791 for all the details.

1. Apparently, you can start reading from [Page 24] "Fragmentation and Reassembly". You don't sort. Sorting is costly. You do some math and put the fragments in the right place instead.

[Page 28] mentions the Reassembly Procedure:

2. I had earlier worked with Contiki OS. You can see how a buffer is declared and used there.

3. You can also have some fun going through Google's Efficient IP datagram reassembly patent.