# Predicting Topology Propagation Messages in Mobile Ad Hoc Networks: The Value of History
## 5 Evaluation of OLSR-HBP in Mobile Scenarios
### Performance of OLSR-HBP
#### 5.3.2 Memory Overhead  
The last analysis conducted to determine the performance of OLSR-HBP was to compute the amount of memory occupation. The aim was to compute the amount of memory used by each node to store all the historical information needed by the predictor. OLSR-HBP basically uses two data structures: a vector to store the identifiers of the TP messages, and a table to store the HBP information (such as in Table 1). Each TP message contains an IPv4 address (4 bytes) to identify the originator node, and a list of the IPv4 addresses of its neighbour nodes. The greatest number of neighbours contained in a TP message was 8 (for 10 nodes cases) and 14 (for 20 nodes cases). The identifier assigned to each TP message requires 2 bytes. The table that contains the HBP information has entries with data for the pattern (a sequence of up to 5 identifiers), and the identifier of the most recent TP message received for this pattern. To compute the amount of memory used by OLSR-HBP, we did not consider the confidence bits nor the counters used by the most-frequent TP message algorithm.  
Figure 7 plots the average amount of memory (in KBytes) per node and per hour used, considering the four test cases. Each average value is computed from the same 40 executions as in the previous section. The grid 4 \(\times\) 4 is the case with less memory requirements, because the number of different TP messages is very small. The memory used by OLSR-HBP in this last case is just about 128 KBytes (KB) per node.  
The SLAW mobility pattern produces more variety in the TP messages, and therefore results in higher memory requirements. Such a mobility pattern involving 10 nodes needs 190 KB for the 1 h window, and 199 KB per hour for the 4 h window--it means a total of 796 KB for the whole execution (4 h). When the execution lasts 4 h, there is an increment of 4.8% in the memory requirements with respect to the case when the execution lasts 1 h. This slight increase may be caused by a greater variety of TP messages present when the execution lasts longer.  
When the SLAW is used with 20 nodes, the average memory occupation increases to 652 KB (1 h window), and 930 KB per hour (4 h window; 3720 KB in total, a little less than 4 MBytes). These values represent an increase of 3.4 and 4.7 times for 1 h and 4 h executions respectively, compared to the values obtained with 10 nodes. This means that the memory occupation has a quadratic relationship with the number of nodes (when the number of nodes doubles, the memory occupation quadruples). The increase in the average memory used between 1 and 4 h is 24%. This value is larger than the previous 4.8% obtained for the 10 nodes cases. However, this increment is consistent with  
Figure 7: Average memory occupation (in KBytes) per node and per hour.  
the quadratic increase observed in the number of nodes dimension. In summary, considering the worst case (20 nodes and 4 h), the amount of memory needed is 3.63 MBytes per node. This value is affordable for the memory capacities we can currently find on standard communication devices. Moreover, if the historical information is cleared every hour (as it is recommended to take into account the results of Section 5.3.1), the average memory requirements per node are reduced to just 420 KBytes. It is important to remark that the memory requirements of OLSR-HBP are much lower than those required by deep learning routing methods and its associated data structures [11; 40; 41; 42].