# Predicting Topology Propagation Messages in Mobile Ad Hoc Networks: The Value of History
## 3 History-Based Prediction Approach
### Basis  
Link state routing protocols are typically used to support mobile applications in ad hoc interaction environments. These protocols, e.g., optimized link state routing protocol (OLSR) or open shortest path first (OSPF), use two types of messages to establish the current topology of the network and the quality of their links. Particularly, HELLO messages are used to detect the state and quality of adjacent links, and topology propagation (TP) messages to inform the current links to the rest of the nodes. This proposal focuses on predicting only the TP messages using a history-based approach. In this approach, each node in charge of communicating a topology change in the network (e.g., Node 1 in Figure 1) must determine if the TP message to be sent can be predicted by the destination (e.g., Node 2), and as a result, the message transmission could be prevented. Consequently, when a TP message expected at the destination is not received, a prediction is made by such a node (e.g., Node 2) to generate the \"missing\" TP message. This message is passed to the upper routing layer as if the TP message had actually been received through the network. Thus, the source node reduces the amount of TP messages transmitted through the network without modifying the signalling information, and its processing by the destination nodes. As shown in Figure 1, this prediction approach requires the participation of twin predictors (Predictors 1 and 2), which must have a high rate of accurate predictions in order to reduce the number messages delivered through the network. This prediction process is based on the fact that some topological states of the network have already appeared in the past; therefore, they can be predicted. In order to do that, each node keeps a table with the recent history of the TP messages requested to or received from its neighbours. When a prediction process is required, past topology information is used as input to determine the future topology of the network. Particularly, unbounded tables are used to store this information, since these structures provide flexibility to identify the mobility patterns of the nodes, and thus, to determine the next evolution of the network topology. When required, Node 1 generates a TP message and Predictor 1 predicts the same message using historical information (Figure 1). If both messages are equal, it means that the TP message can be predicted by the destination (Node 2); therefore, such a message is not sent through the network. Algorithm 1 shows the operation of Predictor 1 at the nodes where TP messages originate. The algorithm assumes that every TP message can be predicted by all neighbour nodes; i.e., generated by the routing layer. In order to be sure that such a prediction is feasible, the sender node checks that all current neighbours will be able to correctly generate the TP message (\(TPg\)) at destination. Therefore, the algorithm uses its \(neighbourHistory_{i}\) to make a prediction for every neighbour node. If a neighbour is not able to make a right prediction, then the \(TPg\) message should be broadcast to neighbours through the network layer. In other cases, the \(TPg\) message is not broadcast (i.e., it is omitted). Additionally, the \(TPg\) message should be appended to every \(neighbourHistory_{i}\).