Optimized Link State Protocol (OLSR) is a proactive routing protocol, so the routes are always immediately available when needed. OLSR is an optimization version of a pure link state protocol. So the topological changes cause the flooding of the topological information to all available hosts in the network. To reduce the possible overhead in the network protocol uses Multi-point Relays (MPR). The idea of MPR is to reduce flooding of broadcasts by reducing the same broadcast in some regions in the network. Another reduce is to provide the shortest path. The reducing the time interval for the control messages transmission can bring more reactivity to the topological changes . OLSR uses three control messages for routing as,
a. TC Message
b. Hello Message
c. MID Message
There is also Multiple Interface Declaration (MID) messages which are used for informing other host that the announcing host can have multiple OLSR interface addresses. The MID message is broadcasted throughout the entire network only by MPRs. There is also a “Host and Network Association” (HNA) message which provides the external routing information by giving the possibility for routing to the external addresses. The HNA message provides information about the network- and the netmask addresses, so that OLSR host can consider that the announcing host can act as a gateway to the announcing set of addresses. The HNA is considered as a generalized version of the TC message with only difference that the TC message can inform about route cancelling while HNA message information is removed only after expiration time.
Hello Message:
The link in the ad hoc network can be either unidirectional or bidirectional so the host must know this information about the neighbors. The Hello messages are broadcasted periodically for the neighbor sensing. The Hello messages are only broadcasted one hop away so that they are not forwarded further. When the first host receives the Hello message from the second host, it sets the second host status to asymmetric in the routing table. When the first host sends a Hello message and includes that, it has the link to the second host as asymmetric, the second host set first host status to symmetric in own routing table. Finally, when second host send again Hello message, where the status of the link for the first host is indicated as symmetric, then first host changes the status from asymmetric to symmetric. In the end both hosts knows that their neighbor is alive and the corresponding link is bidirectional.
Hello messages are used for finding the information about the link status and the host’s neighbors. With the Hello message the Multi-point Relay (MPR) Selector set is constructed which describes which neighbors has chosen this host to act as MPR and from this information the host can calculate its own set of the MPRs. The Hello messages are sent only one hop away but the TC messages are broadcasted throughout the entire network. TC messages are used for broadcasting information about own advertised neighbors which includes at least the MPR Selector list. The TC messages are broadcasted periodically and only the MPR hosts can forward the TC messages.
MPR:
The Multipoint Relays (MPR) is the key idea behind the OLSR protocol to reduce the information exchange overhead. Instead of pure flooding the OLSR uses MPR to reduce the number of the host which broadcasts the information throughout the network. The MPR is a host’s one hop neighbor which may forward its messages. The MPR set of host is kept small in order for the protocol to be efficient. In OLSR only the MPRs can forward the data throughout the network. Each host must have the information about the symmetric one hop and two hop neighbors in order to calculate the optimal MPR set. Information about the neighbors is taken from the Hello messages. The two hop neighbors are found from the Hello message because each Hello message contains all the hosts’ neighbors. Selecting the minimum number of the one hop neighbors which covers all the two hop neighbors is the goal of the MPR selection algorithm. Also each host has the Multipoint Relay Selector set, which indicates which hosts has selected the current host to act as a MPR.
Proposed algorithm for selecting Multi-point Relay set:
1. Take all the symmetric one hop neighbors which are willing to act as an MPR.
2. Calculate for every neighbor host a degree, which is a number of the symmetric
neighbors that are two hops away from the calculating source and does not
include the source or its one hop neighbors.
Add the neighbor symmetric host to the MPR set. If it is the only neighbor form which is possible to get to the specific two hop neighbor, then remove the chosen host neighbors from the two hop neighbor set.
If there are still some hosts in the two hop neighbor set, then calculate the reachability of the each one hop neighbor, meaning the number of the two hop neighbors, that are yet uncovered by MPR set. Choose the node with highest willing value, if the values are the same then takes the node with greater number of reachability. If the reachability is the same, then take the one with greater degree counted in the second step. After choosing the neighbor for MPR set remove the reachable two hop neighbor from the two hop neighbor set.
Repeat previous step until the two hop neighbors set is empty.
For the optimization, set the hosts in the MPR set in the increasing order basing on the willingness. If one host is taken away and all the two hop neighbors, covered by at least one host and the willingness of the host are smaller than WILL_ALWAYS, then the host may be removed.
TC Message:
In order to exchange the topological information and build the topology information base the host that were selected as MPR need to sent the topology control (TC) message. The TC messages are broadcasted throughout the network and only MPR are allowed to forward TC messages. The TC messages are generated and broadcasted periodically in the network. The TC message is sent by a host in order to advertise own links in the network. The host must send at least the links of its MPR selector set. The TC message includes the own set of advertised links and the sequence number of each message. The sequence number is used to avoid loops of the messages and for indicating the freshness of the message, so if the host gets a message with the smaller sequence number it must discard the message without any updates.
The host must increment the sequence number when the links are removed from the TC message and also it should increment the sequence number when the links are added to the message. The sequence numbers are wrapped around. When the hosts advertised links set becomes empty, it should still send empty TC messages for specified amount of time, in order to invalidate previous TC messages. This should stop sending the TC messages until it has again some information to send. The size of the TC message can be quite big, so the TC message can be sent in parts, but then the receiver must combine all parts during some specified amount of time. Host can increase its transmission rate to become more sensible to the possible link failures. When the change in the MPR Selector set is noticed, it indicates that the link failure has happened and the host must transmit the new TC message as soon as possible.
