The Optimized Link State Routing Protocol (OLSR) is an
IP routing protocol optimized for
mobile ad hoc network
A wireless ad hoc network (WANET) or mobile ad hoc network (MANET) is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as routers in wired networks or access points ...
s, which can also be used on other
wireless ad hoc network
A wireless ad hoc network (WANET) or mobile ad hoc network (MANET) is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as routers in wired networks or access points ...
s. OLSR is a proactive
link-state routing protocol
Link-state routing protocols are one of the two main classes of routing protocols used in packet switching networks for computer communications, the others being distance-vector routing protocols. Examples of link-state routing protocols include ...
, which uses ''hello'' and ''topology control'' (TC) messages to discover and then disseminate link state information throughout the mobile ad hoc network. Individual nodes use this topology information to compute next hop destinations for all nodes in the network using shortest hop forwarding paths.
Features specific to OLSR
Link-state routing protocols such as
Open Shortest Path First
Open Shortest Path First (OSPF) is a routing protocol for Internet Protocol (IP) networks. It uses a link state routing (LSR) algorithm and falls into the group of interior gateway protocols (IGPs), operating within a single autonomous sys ...
(OSPF) and
Intermediate System to Intermediate System
Intermediate System to Intermediate System (IS-IS, also written ISIS) is a routing protocol designed to move information efficiently within a computer network, a group of physically connected computers or similar devices. It accomplishes this b ...
(IS-IS) elect a ''designated router'' on every link to perform flooding of topology information. In wireless ad hoc networks, there is different notion of a link, packets can and do go out the same interface; hence, a different approach is needed in order to optimize the flooding process. Using Hello messages the OLSR protocol at each node discovers 2-hop neighbor information and performs a distributed election of a set of ''
multipoint relay
The Optimized Link State Routing Protocol (OLSR) is an IP routing protocol optimized for mobile ad hoc networks, which can also be used on other wireless ad hoc networks. OLSR is a proactive link-state routing protocol, which uses ''hello'' ...
s'' (MPRs). Nodes select MPRs such that there exists a path to each of its 2-hop neighbors via a node selected as an MPR. These MPR nodes then source and forward TC messages that contain the MPR selectors. This functioning of MPRs makes OLSR unique from other link state routing protocols in a few different ways: The forwarding path for TC messages is not shared among all nodes but varies depending on the source, only a subset of nodes source link state information, not all links of a node are advertised but only those that represent MPR selections.
Since link-state routing requires the topology database to be synchronized across the network, OSPF and IS-IS perform topology flooding using a reliable algorithm. Such an algorithm is very difficult to design for ad hoc wireless networks, so OLSR doesn't bother with reliability; it simply floods topology data often enough to make sure that the database does not remain unsynchronized for extended periods of time.
Multipoint relays
Multipoint relays (MPRs) relay messages between nodes. They also have the main role in
routing
Routing is the process of selecting a path for traffic in a network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched telephone netw ...
and selecting the proper route from any source to any desired destination node.
MPRs advertise link-state information for their MPR selectors (a node selected as a MPR) periodically in their control messages. MPRs are also used to form a route from a given node to any destination in route calculation. Each node periodically broadcasts a Hello message for the link sensing, neighbor detection and MPR selection processes.
Benefits
Being a proactive protocol, routes to all destinations within the network are known and maintained before use. Having the routes available within the standard routing table can be useful for some systems and network applications as there is no route discovery delay associated with finding a new route.
The routing overhead generated, while generally greater than that of a reactive protocol, does not increase with the number of routes being created.
Default and network routes can be injected into the system by HNA messages allowing for connection to the internet or other networks within the OLSR
MANET
A wireless ad hoc network (WANET) or mobile ad hoc network (MANET) is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as routers in wired networks or access points ...
cloud. Network routes are something reactive protocols do not currently execute well.
Timeout values and validity information is contained within the messages conveying information allowing for differing timer values to be used at differing nodes.
Criticisms
The original definition of OLSR does not include any provisions for sensing of link quality; it simply assumes that a link is up if a number of hello packets have been received recently. This assumes that links are bi-modal (either working or failed), which is not necessarily the case on wireless networks, where links often exhibit intermediate rates of packet loss. Implementations such as the open source OLSRd (commonly used on
Linux
Linux ( or ) is a family of open-source Unix-like operating systems based on the Linux kernel, an operating system kernel first released on September 17, 1991, by Linus Torvalds. Linux is typically packaged as a Linux distribution, which ...
-based mesh routers) have been extended (as of v. 0.4.8) with link quality sensing.
Being a proactive protocol, OLSR uses power and network resources in order to propagate data about possibly unused routes. While this is not a problem for wired access points, and laptops, it makes OLSR unsuitable for sensor networks that try to sleep most of the time.
For small scale wired access points with low
CPU power, the open sourc
OLSRdproject showed that large scale mesh networks can run with OLSRd on thousands of nodes with very little CPU power on embedded devices.
Being a link-state protocol, OLSR requires a reasonably large amount of
bandwidth
Bandwidth commonly refers to:
* Bandwidth (signal processing) or ''analog bandwidth'', ''frequency bandwidth'', or ''radio bandwidth'', a measure of the width of a frequency range
* Bandwidth (computing), the rate of data transfer, bit rate or thr ...
and CPU power to compute optimal paths in the network. In the typical networks where OLSR is used (which rarely exceed a few hundreds of nodes), this does not appear to be a problem.
By only using MPRs to flood topology information, OLSR removes some of the redundancy of the flooding process, which may be a problem in networks with moderate to large packet loss rates – however the MPR mechanism is self-pruning (which means that in case of packet losses, some nodes that would not have retransmitted a packet, may do so).
Messages
OLSR makes use of "Hello" messages to find its one hop neighbors and its two hop neighbors through their responses. The sender can then select its multipoint relays (MPR) based on the one hop node that offers the best routes to the two hop nodes. Each node has also an MPR selector set, which enumerates nodes that have selected it as an MPR node. OLSR uses topology control (TC) messages along with MPR forwarding to disseminate neighbor information throughout the network. ''Host and network association'' (HNA) messages are used by OLSR to disseminate network route advertisements in the same way TC messages advertise host routes.
Hello
Topology control (TC)
Other approaches
The problem of routing in ad hoc wireless networks is actively being researched, and OLSR is but one of several proposed solutions. To many, it is not clear whether a whole new protocol is needed, or whether
OSPF
Open Shortest Path First (OSPF) is a routing protocol for Internet Protocol (IP) networks. It uses a link state routing (LSR) algorithm and falls into the group of interior gateway protocols (IGPs), operating within a single autonomous sys ...
could be extended with support for wireless interfaces.
In bandwidth- and power-starved environments, it is interesting to keep the network silent when there is no traffic to be routed. Reactive routing protocols do not maintain routes, but build them on demand. As link-state protocols require database synchronisation, such protocols typically use the distance vector approach, as in
AODV
Ad hoc On-Demand Distance Vector (AODV) Routing is a routing protocol for mobile ad hoc networks (MANETs) and other wireless ad hoc networks. It was jointly developed in July 2003 in Nokia Research Center, University of California, Santa Barbara an ...
and
DSDV
Destination-Sequenced Distance-Vector Routing (DSDV) is a table-driven routing scheme for ad hoc mobile networks based on the Bellman–Ford algorithm. It was developed by C. Perkins and P. Bhagwat in 1994. The main contribution of the algorithm w ...
, or more ad hoc approaches that do not necessarily build optimal paths, such as
Dynamic Source Routing
Dynamic Source Routing (DSR) is a routing protocol for wireless mesh networks. It is similar to AODV in that it forms a route on-demand when a transmitting node requests one. However, it uses source routing instead of relying on the routing tab ...
.
For more information see the
list of ad hoc routing protocols
An ad hoc routing protocol is a convention, or standard, that controls how nodes decide which way to route packets between computing devices in a mobile ad hoc network.
In ad hoc networks, nodes are not familiar with the topology of their network ...
.
OLSR version 2
OLSRv2 has been published by the IETF in April 2014.
[RFC 7181] It maintains many of the key features of the original including MPR selection and dissemination. Key differences are the flexibility and modular design using shared components: packet format packetbb, and neighborhood discovery protocol NHDP. These components are being designed to be common among next generation IETF MANET protocols. Differences in the handling of multiple address and interface enabled nodes is also present between OLSR and OLSRv2.
Implementations
OLSR.ORG– Downloadable code for OLSR on Linux, Windows, Mac OS X, FreeBSD, NetBSD and
OpenBSD
OpenBSD is a security-focused, free and open-source, Unix-like operating system based on the Berkeley Software Distribution (BSD). Theo de Raadt created OpenBSD in 1995 by forking NetBSD 1.0. According to the website, the OpenBSD project em ...
systems. Features a great deal of documentation, including an informative survey of related work.
NRL-OLSR– Open source code of NRL-OLSR. Works on Windows, MacOS, Linux, and various embedded PDA systems such as Arm/Zaurus and PocketPC as well as simulation environments
ns2 and OPNET., http://cs.itd.nrl.navy.mil/focus/
SOURCEFORGE.NET-OLSR– Created by MOVIQUITY and based on studies within the project Workpad, it offers a code in C# to deploy a MANET (Ad Hoc, Meshnet) with protocol OLSR. Developed for WM 6, Win XP and can be adapted to other platforms using .Net Framework and Compact. http://sourceforge.net/projects/wmolsr/
See also
*
B.A.T.M.A.N., Better Approach To Mobile Adhoc Networking
*
IEEE 802.1aq
Shortest Path Bridging (SPB), specified in the IEEE 802.1aq standard, is a computer networking technology intended to simplify the creation and configuration of Ethernet networks while enabling multipath routing.
It is the replacement for the ...
*
TRILL
TRILL (Transparent Interconnection of Lots of Links) is an Internet Standard implemented by devices called TRILL switches. TRILL combines techniques from bridging and routing, and is the application of link-state routing to the VLAN-aware cus ...
TRansparent Interconnection of Lots of Links
References
External links
IETF Home PageThe Internet Engineering Task Force standards body
olsr.funkfeuer.atcurrently advancing the olsr.org implementation to improve scalability
Optimized Link State Routing which includes thi
Pyramid Linux– an embedded distro fo
embedded x86 boardswith OLSR, web interface, etc. Primarily used in Community Networks.
NRL's Networks and Communication Systems Branch– includes project information and open source networking tools and software developed by the U.S. Naval Research Lab.
{{Routing protocols
Wireless networking
Routing
Routing algorithms
Ad hoc routing protocols
Routing protocols