# Predicting Topology Propagation Messages in Mobile Ad Hoc Networks: The Value of History
## 4 Implementation of the OLSR-HBP
### Implementation Aspects  
As mentioned before, the predictor was implemented over the OLSR (optimized link state routing) protocol [35], a well-known proactive link state routing algorithm. When using OLSR, the network nodes periodically exchange routing information to keep a map of the network topology using HELLO and topology propagation (TP) messages. HELLO messages allow each node to discover its neighbouring nodes and obtain information about the state of the links with them, and TP messages allow multi-point relay (MPR) nodes to disseminate neighbour information throughout the network. The MPR nodes are the network nodes selected for propagating the topology information. The implementation of the predictor, named OLSR-HBP, addresses the prediction of TP messages through an extension to the C++ code of the NS-3 OLSR module. NS-3 is a simulation tool that allows modelling networking scenarios, collecting statistics, defining initial network topologies, configuring wireless network interfaces and setting the mobility patterns of the nodes [39]. In order to make a prediction, OLSR-HBP analyses the historical information, recorded through sequences of TP messages, at both origin and destination nodes. Origin nodes (i.e., the MPR nodes) broadcast TP messages to different destination nodes. Due to the nodes mobility, the topology information changes in an independent way, therefore it is necessary to keep the sequences of TP messages separated for each pair of origin-destination nodes, and the prediction should be also made for each separated sequence. Every node should keep the sequences of TP messages updated for the nodes that receive these messages from it, and also for the nodes that send TP messages to it. At the origin, the OLSR-HBP considers that the next TP message can be omitted (not transmitted) if all destination nodes can predict correctly (hit) such a TP message from their corresponding local information of TP sequences; we call this prediction situation a _global hit_. We have added data structures to the NS-3 OLSR module to keep the information of the individual sequences of TP messages for every pair of origin-destination nodes that interchange TP messages. OLSR-HBP uses these data structures to detect _global hits_ at origin nodes and therefore, to prevent broadcasting this TP message. At destination nodes, the predictor uses a timer to determine the potential arrival of TP messages from every possible origin node. If the timer expires and its expected TP message is not received, the destination node considers that the next TP message is a hit, therefore it can be predicted. In that case, a new message is generated by the predictor and processed as if it had been received from the origin. This information is also used to update the local topology historical information. TP messages contain diverse information, particularly the IPv4 addresses of the originator node and their neighbours, the advertised neighbour sequence number (ANSN--a number that is incremented every time the topology information of the node changes), and the message sequence number (MSN--incremented every time a node sends a new control message). When predicting a new TP message at the destination node, all this information should be generated. The address of the MPR nodes and the list of neighbours are generated using the historical information stored in the local tables of the nodes. To generate the ANSN, we use the last ANSN value received from the origin node. To produce MSNs, we introduced \"gaps\" in the sequence of MSNs, so that the destination nodes can detect these \"gaps\" and use them as MSN for the generated TP. If the last MSN received is not consecutive to the previous one, a gap is detected and the missing MSN is put in a buffer. When a new TP message is generated, its MSN value is taken from this buffer. If the buffer is empty, then the predictor uses an MSN value equal to 0. In case of some transmission delay, destination nodes should wait extra time for a new TP message to arrive.