# Estimating the Memory Consumption of a Hardware IP Defragmentation Block
## 3 Materials and Methods  
### Software Simulation of the Ip Reassembly Module  
#### 3.1.1 Flow Table Design  
The main subject of this work is to assess the required size (memory consumption) of an IP reassembly flow table required to keep the fragmented payload. The primary goal is a hardware design space exploration, the flow table is constructed in a hardware-friendly manner. The results do not lose generality as the same scheme (or even more sophisticated) can be efficiently implemented in software. The design attempts to maximize performance while keeping the memory organization simple and deterministic. This is especially important for high-speed fiber networks where the 100 Gb/s throughput (and beyond) mandates a pipelined architecture [15]. The conceptual organization of the flow table is presented in Figure 4. The main design factors are:  
* Constant associativity \(A\), which is a design parameter;
* Constant number of flow table entries \(A\times B\), where \(B\) is a number of buckets or \"sets\" (also a design parameter);
* Least Recently Used (LRU) replacement policy based on a timestamp (e.g., a cycle or a packet counter). The flow table design resembles the CPU data cache organization, hence the term \"associativity\" or \"ways\" is being preferred over the \"bucket size\" (used for hash tables). The address of the memory entry is generated by the hashing procedure, which is not present in data caches (which use a physical and virtual address as a key). The LRU policy is working within a \"set\" or a bucket. For example, for a four-way memory, the replacement policy can overwrite the oldest out of the four entries. The main design challenge for such an algorithmic block is to choose a memory organization that is capable of holding all concurrent fragment flows without sacrificing too much silicon space. The rest of the article lays out the methodology and results of an experiment that systematically explores the solution space. Figure 4: Schematic of a flow table. The IP reassembly algorithm has been implemented in software to perform a simulation of the proposed hardware block. Every attempt at implementing such a block in hardware should be preceded by algorithmic analysis. An additional benefit of the simulation is that the results are applicable for software implementation as well. It can be safely assumed that a software variant can be much more sophisticated when it comes to control logic and thus outperform hardware on the algorithmic level (e.g., using cuckoo hashing or dynamic allocation). Thus, any benefit of this simulation can be applied to software with equal or even greater success. Design space exploration parameters:  
1. Finite flow table with a predefined size \(A\times B\) in the range from 16 to 512 entries. 2. Fixed associativity \(A\) from 1 to 16
3. Infinite packet buffer space. Payload buffering limitations are not simulated. 4. Constant 40-byte flow key constructed from \(\{IP_{src},IP_{dst},ID_{frag},Proto_{LA}\}\). 5. LRU replacement policy based on a timestamp. 6. IP Fragments are properly defragmented even when they arrive out of order or duplicated. 7. Infinite fragment list. 8. No data flow modeling. 9. No cycle-level modeling. The size of the flow table \(A\times B\) (point 1) was chosen to be relatively small, which is typical for the network accelerators based on SRAM memory (e.g., Intel X700 [11]). Other hardware-oriented publications (e.g., Yamaki [14]) also consider the size in the order of a thousand entries. Associativity of a table \(A\) defined in point 2 is an important parameter for the hardware design, as the complexity of implementation rises significantly beyond the four entries. Especially, the idealized LRU policy is often replaced by the pseudo-LRU, which is a design trade-off [40]. Furthermore, as discussed in Section 4, the benefits of increased associativity tend to diminish beyond 8. Two design parameters, namely packet buffer space and fragment memory size (points 3 and 7) are considered \"infinite\".