# Estimating the Memory Consumption of a Hardware IP Defragmentation Block
## 2 Related Work
### Ip Defragmentation
#### 2.1.2 Ip Defragmentation Algorithm  
This section presents a brief overview of the IP defragmentation algorithm. The algorithm is generalized to work for both IPv4 and IPv6. The difference is in the packet structure. Figure 1 presents the difference between IPv4 and IPv6 fragments. The payload is exemplified by the TCP packet (it may by any payload, however). In the case of IPv4, the fragmentation status is embedded in the IPv4 header. In the case of IPv6, there is an extra header (Fragment Header) that resides between the payload and the main IPv6 header. In IPv4, all relevant fields (contained in the IPv4 header) are:  
* id--a 16-bit field identifying the fragment series;
* total length--length of the entire IP datagram;
* offset--a 16-bit data offset from the beginning of the original (not fragmented) IP packet;
* MF--\"more fragments\" flag indicating that this is not the last fragment;
* DF--\"do not fragment\" flag preventing fragmentation by gateways and routers;
* proto--type of the payload, e.g., TCP or UDP. In the case of IPv6, some fields are moved to the fragment header (retaining similar semantics to IPv4). Overall, the relevant fields are:  
* id--a 32-bit field identifying the fragment series;
* payload length--length of the payload (including extension headers);
* offset--a 16-bit data offset from the beginning of the original (not fragmented) IP packet;
* M--\"more fragments\" flag indicating that this is not the last fragment;
* next--type of the next header: e.g.,: TCP or UDP or an extension header. Figure 1: Structure of fragmented IPv4 (**a**) and IPv6 (**b**) packets. The IPv6 protocol prevents fragmentation by the intermediate nodes, so a packet may be treated as having the \(DF=1\) flag. The source and destination address fields are left out from the picture as they require no explanation in this context. The fragment series is identified by the tuple:  
1. \((Source,Destination,ID,Proto)\)--for IPv4
2. \((Source,Destination,ID)\)--for IPv6. A fragment flow or a fragment series is thus uniquely identified by the tuple number 1 if the _Proto_ field is left \"blank\" for IPv6. Note that the bit width of the fields is different, so the implementation may choose to zero-extend the fields in the case of IPv4 to retain generality. Figure 2 depicts a transformation process from a \"whole\" IPv4 packet to a fragment series. When a transmitting device detects that the IP datagram does not fit into the Maximum Transmission Unit (MTU), then the packet payload is split into several parts and each part gets its own IP header. If an original payload is 2000 bytes, then the size of an IPv4 packet is at least 2020 bytes due to the packet header overhead (the 20-byte length assumes no IP options in the header). Subsequently, two-part fragment series has 1520 and 520 bytes, respectively. In the case of IPv6, the overhead consists of the length of all the extension headers between the IPv6 packet header and the data beyond the extension header (there may be many extension headers). The last header in the series (containing the final bytes of the payload) has the \(MF=0\) flag (or \(M=0\) for IPv6), thus indicating the final size of the packet. Since IP delivery is not reliable, the packets may be reordered, dropped, or duplicated and the receiving node must attempt to reconstruct the original payload in all those cases. As a consequence, each fragment series must be buffered in the receiving device until a complete reconstruction is made. This process, if left uncompleted, is eventually interrupted by a timeout. The process of IP reassembly is serviced by the flow table. A flow table is a lookup structure that keeps a state and payload for each active fragment flow. The data kept in the flow table should represent a sorted list of received fragments. When the list is complete, the original IP packet is reconstructed, and the entry is removed from the table. Figure 3 contains such a list (the length field is a payload-only length without the header overhead).