Subject: [6lowpan] fragment reassembly

From: Matus Harvan <[email-masked]>
Date: Tue, 19 Jun 2007 01:43:33 +0200

Hi,

my understanding of the the 6lowpan format draft version 13 is that it
specifies different behavior for different types of overlapping
fragments. If a fragment is received that overlaps another fragment and
differs from the overlapped fragment in either size or datagram_offset
then the already accumulated fragments shall be discarded. However, if
the fragment were just a duplicate of another already received fragment,
the already accumulated fragments do not need to be discarded.

The problem with requiring a different behavior depending on whether it
is just a duplicate or really a a different overlapping fragment is that
to determine which type it is, the information about the size and
datagram_offset of each already accumulated fragment has to be stored
until the complete datagram is reassembled. While this may allow to
detect a broken fragment sender, it requires additional complexity in
the implementation as well as potentially more memory. An incorrectly
reassembled datagram should be detected anyway, as ICMP,TCP and UDP all
use a checksum with IPv6. Hence, I am not sure it is worth the effort.

My understanding of the memory requirements is that one could use a
bitmap or a linked list in order to keep track of already received
fragments.

Assuming a maximum datagram length of 1280 bytes after fragment
reassembly and given the offset unit of 8-octet increments, one could
use one bit for each 8 octets of the datagram. For a 1280 octets long
datagram a 160 bit or 20 byte bitmap would be required to keep track of
which parts of the datagram (fragments) have already been received.
However, the information in the bitmap would not be sufficient to
determine whether a received overlapping fragment is really a differing
overlap or just a duplicate.

With a linked list approach, one way is to store the length and
datagram_length for each received fragment. These alone, without any
pointer the the next element of the linked list, would be 2 bytes per
fragment. Given 4 octets length of the first fragment header and 5
octets length of subsequent fragment headers, the complete datagram
should fit into 15 fragments if maximum length 802.15.4 frames are used.
 Hence, at least 30 bytes would be needed to accumulate for the longest
possible 6lowpan datagram assuming the best possible fragmentation. The
linked list, on the other hand allows to determine whether a fragment is
just a duplicate or really a differing overlap.

The above discussion assumes the best possible fragmentation. If the
sender sends smaller fragments then even more fragments may be needed,
up to 1280/8 = 160 fragments. Clearly, keeping the size and
datagram_offset for each fragment gets much worse in terms of required
memory than a simple bitmap.

Instead of a linked list one could also use an array and save the memory
that would be used for the pointer to the next element of the linked
list. However, one could then not take the list elements out of a common
pool for reassembling several datagrams concurrently.

In case of shorter datagrams, the linked list may actually require less
memory as less fragments would be used. However, if an implementation
should be able to cope with the largest allowed datagram size, then the
memory would have to be available or reserved anyway and hence the
discussion with the maximum datagram length is relevant.

In short, the requirement to treat duplicated fragments differently from
different overlapping fragments seems to hurt when one implements
fragment reassembly and IMHO is not worth the effort. Would it be
possible to reconsider this requirement and possibly leave it out in a
future version of the format draft?

Matus

_______________________________________________
6lowpan mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/6lowpan