Optimized link state routing protocol

OLSR ( Optimized Link State Routing Protocol ) is a protocol of Routage intended for the mobile networks. The protocol is defined in RFC 3626 of IETF.

Origin

The team HIPERCOM-inria project proposed OLSR in 2001. She also implemented the first version of OLSR. The Hipercom team is not has her first success-story, it is also at the origin of Hiperlan which uses the concept of MPRs that one finds in OLSR.

General operation

The principal concept used in the protocol is that of the multipoint relay, (MPRs). MPRs are selected nodes which dispatch messages of diffusion during the process of flood. This technique appreciably reduces the overload due to the messages compared to a traditional mechanism of flood, where each node retransmet each message when it receives the first copy of the message. In OLSR, the information of state of bond is produced only by nodes elected like MPRs, thus, the second optimization is realized by to the minimum reducing the number of the messages of control flooded in the network and like the third optimization, a node of MPR must bring back only bonds between itself and its selectors.

Type of packages

Hello message

Sender: Each node of the network sends messages HELLO

Recipient: Addresses broadcast

Function: Message HELLO transmits several information and has several utilities. It is initially used to discover the whole of the network. It transmits then the state and the type of bond between the shipper and each close node. Lastly, it specifies the MPR (Multipoint Relays) chosen by the shipper.

Datagram:

“Reserved”: This field must contain “0000000000000000”
“Htime”: Interval of emission of messages HELLO
“Willigness”: allows to force the passage of a node in MPR
“Link Code”: Code identifying the type of bond (not information, symmetrical, asymmetrical, etc) between the shipper and the listed interfaces (“Neighbor Interface Address”)

Messages HELLO are intended only for the nodes close (with a jump) to the shipper, it must thus never not be road by a MPR (an exception: To choose the MPR).

Message TC (Topology Control)

Sender: Only the MPR send messages TC

Recipient: Addresses broadcast

Function: The message TC makes it possible the MPR to transmit the list of its neighbors who chose it like MPR. It is used to draw up the tables of routing. Also, so that it is diffused on all the network, the value of the TTL in the Header of the message is 255, the maximum value. (see “standard package envoy by the protocol”)

Datagram:

“Reserved”: This field must contain “0000000000000000”
“ANSN (Advertized Neighbor Sequence Number)”: Entirety incremented with each change of topology. It makes it possible not to take account of obsolete information, to hold tables the most up to date possible.
“Advertized Neighbor Address Hand”: Address IP of the nodes to a jump (which are announced by the Hello packages)

Message MID

Algorithm of selection of the MPR

Definition

The unit NR is consisted of the neighbors to a jump of the node (here in red), which one wants to determine the MPR. A jump corresponds to all the neighbors who answered the Hello message, that corresponds to carried radio operator for the networks Wi-Fi.

The unit N2 is consisted of the neighbors with 2 jumps of the same node as previously. All the neighbors with a jump of the red node by using the messages hello, will declare their neighbors with a jump. Thus the red node will know the nodes with a jump which it will be necessary to request to transmit a package to a neighbor for 2 jumps.

An asymmetrical bond is represented by a simple red feature. They are detected thanks to the Hello messages, but are not used as much as they are not symmetrical.

A symmetrical bond is represented by a double red feature.

D (U) is the number of bond symmetrical of a node U of NR| |}

Algorithm

1 stage: One forces all the elements of NR to rerouter the messages.

2 stage: One calculates D for each node of NR

3 stage: For all the nodes in N2 which have only one and one symmetrical bond with a node of NR, one defines this node of NR like MPR, and one removes the N2 nodes connected by this MPR (one regards them as connected).

4 stage: One reiterates these 3 stages, until there is no more node not connected in N2

Implementations

http://hipercom.inria.fr/oolsr/ an implementation of OLSR (for Linux, Windows, and for simulator NS-2)
http://www.olsr.org/ source code of OLSR for GNU/Linux, Windows, OS X, FreeBSD and NetBSD, with a rich documentation and studies of the protocol.
LUCEOR, continuation of routing integral OLSR, compatible with various radio technologies (Wi-Fi, WiMax,…) & telegraphic (CPL, fiber, Ethernet), opened with equipment télécoms, the embarked industrial systems and the terminals, enriching OLSR with modules with added-value e.g.: Management & discovered topology of the network, multicast, fast Mobility, Routing radio operator multi optimized and Radio operator Aware (RA-OLSR)
6WINDGate, continuation of routing open-source integrating OLSR with the other protocols of routings unicast (OSPF, BGP, RIP)

Bonds

RFC3626 specification of OLSR
http://hipercom.inria.fr/olsr/ studies, simulations and extentions multicast and Qos for olsr
http://olsr.funkfeuer.at studies on the limits of scalability of olsr.org
http://hipercom.inria.fr/olsr/mpr-flooding.html demonstration flash
http://freifunk.net/wiki/FreifunkFirmwareEnglish Freifunk Firmware (English) - a firmware based on OpenWRT using OLSR. It is conceived to establish external networks mesh with AP WiFi, like LinksysWRT54G
http://pyramid.metrix.net/ Linux Pyramid, a distribution embarked for chart x86 with OLSR, interface WEB, etc
http://fr.wikipedia.org/wiki/Topologie_Mesh topology Mesh

Random links: