Optimized Link State Routing (OLSR)

des-olsr is our Optimized Link State Routing (OLSR) protocol implementation as a variant for underlay routing. The implementation can be considered as a hybrid of version 1 and the draft version of OLSRv2. The latter one basically only modifies the first version by introducing a new message format (RFC 5444) and the Neighborhood Discovery Protocol (NHDP). The DES-SERT extension mechanism is similar to the approach in RFC 5444 but not compatible.

Description:

OLSR belongs to the group of topology-based proactive routing protocols and was designed for use in ad-hoc networks. It is a optimization of the classic link state routing scheme. Since routing control packets in LSR algorithms are sent periodically, this overhead should be minimized. Therefore OLSR has an improved flooding method.

The main idea of this protocol is that each node gets to know its neighborhood and broacdcasts this information through the network. This is the main difference to distance vector algorithms, where topology information is only is exchanged with neighbours. In the first version of OLSR (RFC 3626), hop count is used as routing metric. The second version of the protocol, that is at the time of writing still under developement, will probably allow other link metrics to be used.

With OLSR every node should have information about all links in the network. To discover this topology two different packets are used: neighborhood discovery is based on HELLO packets and link state information is flooded in topology control (TC) packets. OLSR selects a minimal set of one hop neighbours to reach all two hop neighbors: multipoint relays (MPRs). Nodes can advertise their willingness to be selected as MPR, e.g., advertise a low willingness if their energy is low. Only the MPRs will forward TC packets. In this way less packets are sent over the medium compared to flooding where each node will forward each packet once.

The following figure depicts the neighborhood detection based on HELLOs:

The following figure depicts nodes that have been selected as MPRs (marked with an 'M') bei the MPR selector (marked by an 'S'):

TC packets are broadcast packets that contain information about the one hop neighborhood of nodes. When TC packets are received from all nodes in the network, each node can get a complete view of the network topology. Since not all TC packets arrive at the same time and TC packets can be lost, the nodes maintain different data structures: link information base set, topology set, and the routing table. The latter is updated when one of the former two is modified. The Dijkstra shortest path algorithm is applied for each destination and the best next hops are determined and stored in the routing table.

Deviations from the RFC 3626:

• MPR selection algorithm, section 8.3., page 37. The original MPR selection is based on an algorithm that has a complexity O(n³) where n is the number of neighbors. Our algorithm has a complexity of O(n²) and prefers neighbors to be included in the MPR set that have a lower willingness but more neighbors. Thus energy contrains are a secondary concern compared to the improvement of the flooding.
• Gateways, section 12.2., page 51 and section 12.6., page 53 and section 20.3., page 68. The des-olsr implementation currently provides no gateways to other networks as it is out of our focus of research.

Optional features of the RFC 3626:

• While OLSRv1 specifies hop count as metric, many implementations also provide ETX. Currently, there is a discussion on the IETF MANET mailing list about the default metric for version 2. The consensus will probably be that a separate RFC will be written which discusses different metrics that can be used. In des-olsr, hop count and packet loss ratio, and ETX are currently available.