CS9263 Ad-hoc Networks 4th unit

 OLSR

OPTIMIZED LINK STATE ROUTING (OLSR) PROTOCOL

                      OLSR is developed for mobile ad hoc networks. It operates as a table-driven, pro- active protocol, that is, it exchanges topology information with other nodes of the network regularly. Each node selects a set of its neighbor nodes as “multipoint relays” (MPR). In OLSR, only nodes, selected as such MPRs, are responsible for forwarding control traffic, intended for diffusion into the entire network. MPRs provide an efficient mechanism for flooding control traffic by reducing the number of transmissions required. Nodes, selected as MPRs, also have a special responsibility when declaring link state information in the network. Indeed, the only requirement for OLSR to provide shortest path routes to all destinations is that MPR nodes declare link state information for their MPR selectors. Additional available link state information may be utilized, for example for redundancy.
Nodes which have been selected as multipoint relays by some neighbor node(s) announce this information periodically in their control messages. Thereby, a node announces to the network that it has reachability to the nodes which have selected it as an MPR. In route calculation, the MPRs are used to form the route from a given node to any destination in the network. Furthermore, the protocol uses the MPRs to facilitate efficient flooding of control messages in the network. A node selects MPRs from among its one-hop neighbors with “symmetrical” (i.e., bidirectional) linkages. Therefore, selecting the route through MPRs automatically avoids the problems associated with data packet transfer over unidirectional links (such as the problem of not getting link-layer acknowledgments for data packets at each hop, for link layers employing this technique for unicast traffic). OLSR is developed to work independently from other protocols. Likewise, OLSR makes no assumptions about the underlying link layer. OLSR inherits the concept of forwarding and relaying from HIPERLAN (a MAC layer protocol), which is standardized by European Telecommunications Standards Institute (ETSI). The protocol is developed in the IPANEMA project (part of the Euclid program) and in the Perception Recognition Integration for Observation of Activity (PRIMA) project (part of the RNRT program). OLSR is a proactive routing protocol for mobile ad hoc networks. It is well suited to large and dense mobile networks, as the optimization achieved using the MPRs works well in this context. The larger and more dense a network, the more optimization can be achieved as compared to the classic link state algorithm. OLSR uses hop-by-hop routing, that is, each node uses its local information to route packets. OLSR is well suited for networks, where the traffic is random and sporadic between a larger set of nodes rather than being almost exclusively between a small specific set of nodes. As a proactive protocol, OLSR is also suitable for scenarios where the communicating pairs change over time: no additional control traffic is generated in this situation because routes are maintained for all known destinations at all times.

PROTOCOL OVERVIEW

              OLSR is, as discussed in the previous subsection, a proactive routing protocol for mobile ad hoc networks. The protocol inherits the stability of a link state algorithm and has the advantage of having routes immediately available when needed due to its proactive nature. OLSR is an optimization over the classical link state protocol, tailored for mobile ad hoc networks. OLSR minimizes the overhead from flooding of control traffic by using only selected nodes, called MPRs, to retransmit control messages. This technique significantly reduces the number of retransmissions required to flood a message to all nodes in the network. Secondly, OLSR requires only a partial link state to be flooded to provide shortest path routes. The minimal set of link state information required is that all nodes selected as MPRs must declare the links to their MPR selectors. Additional topological information, if present, may be utilized, for example for redundancy purposes. OLSR may optimize the reactivity to topological changes by reducing the maximum time interval for periodic control message transmission. Furthermore, as OLSR continuously maintains routes to all destinations in the network, the protocol is beneficial for traffic patterns where a large subset of nodes are communicating with another large subset of nodes, and where the source–destination pairs are changing over time. The protocol is particularly suited for large and dense networks, as the optimization done using MPRs works well in this context. The larger and more dense a network, the more optimization can be achieved as compared to the classic link state algorithm. OLSR is designed to work in a completely distributed manner and does not depend on any central entity. The protocol does not require reliable transmission of control messages: each node sends control messages periodically, and can therefore sustain a reasonable loss of some such messages. Such losses occur frequently in radio networks due to collisions or other transmission problems. Also, OLSR does not require sequenced delivery of messages. Each control message contains a sequence number, which is incremented for each message. Thus the recipient of a control message can, if required, easily identify which information is more recent—even if messages have been reordered while in transmission. Furthermore, OLSR provides support for protocol extensions such as sleep mode operation and multicast routing. Such extensions may be introduced as additions to the protocol without breaking backwards compatibility with earlier versions. OLSR does not require any changes to the format of Internet Protocol (IP) packets. Thus any existing IP stack can be used as is; the protocol only interacts with routing table management.

MULTIPOINT RELAYS (MPRS)

                    The idea of multipoint relays is to minimize the overhead of flooding messages in the network by reducing redundant retransmissions in the same region. Each node in the network selects a set of nodes in its symmetric one-hop neighborhood, which may retransmit its messages. This set of selected neighbor nodes is called the MPR set of that node. The neighbors of node N which are not in its MPR set receive and process broadcast messages but do not retransmit broadcast messages received from node N.

                            Each node selects its MPR set from among its one-hop symmetric neighbors. This set is selected such that it covers (in terms of radio range) all symmetric strict two-hop nodes. The MPR set of N, denoted as MPR (N), is then an arbitrary subset of the symmetric one-hop neighborhood of N which satisfies the following condition: every node in the symmetric strict two-hop neighborhood of N must have a symmetric link toward MPR (N). The smaller an MPR set, the less control traffic overhead results from the routing protocol. Each node maintains information about the set of neighbors that have selected it as an MPR. This set is called the “MPR selector set” of a node. A node obtains this information from periodic Hello messages received from the neighbors. Upon receipt of this MPR selector information, each node calculates and updates its route to each destination. Therefore, the route is a sequence of hops through the multipoint relays from source to destination.

PROTOCOL FUNCTIONING

           OLSR is modularized into a “core” of functionality, which is always required for the protocol to operate, and a set of auxiliary functions. The core specifies, in its own right, a protocol able to provide routing in a stand-alone MANET. Each auxiliary function provides additional functionality, which may be applicable in specific scenarios (e.g., in case a node is providing connectivity between the MANET and another routing domain). All auxiliary functions are compatible, to the extent where any (sub-) set of auxiliary functions may be implemented with the core. Furthermore, the protocol allows heterogeneous nodes—that is, nodes which implement different subsets of the auxiliary functions—to coexist in the network. The purpose of dividing the functioning of OLSR into core functionality and a set of auxiliary functions is to provide a simple and easy-to-comprehend protocol, and to provide a way of only adding complexity where specific additional functionality is required.

CORE FUNCTIONING

                        The core functionality of OLSR specifies the behavior of a node, equipped with OLSR interfaces participating in the MANET and running OLSR as a routing protocol. This includes a universal specification of OLSR protocol messages and their transmission through the network, as well as link sensing, topology diffusion, and route calculation. Specifically, the core is made up from the following components.

Packet Format and Forwarding

             A universal specification of the packet format and an optimized flooding mecha- nism serves as the transport mechanism for all OLSR control traffic.

Link Sensing

             Link sensing is accomplished through periodic emission of Hello messages over the interfaces through which connectivity is checked. A separate Hello message is generated for each interface. Resulting from link sensing is a local link set describ- ing links between “local interfaces” and “remote interfaces,” that is, interfaces on neighbor nodes. If sufficient information is provided by the link layer, this may be utilized to populate the local link set instead of a Hello message exchange.

 Neighbor Detection

                 Given a network with only single interface nodes, a node may deduct the neighbor set directly from the information exchanged as part of link sensing: the “main address” of a single interface node is, by definition, the address of the only interface on that node. In a network with multiple interface nodes, additional information is required to map interface addresses to main addresses (and, thereby, to nodes). This additional information is acquired through Multiple Interface Declaration (MID) messages.

MPR Selection and   MPR Signaling

               The objective of MPR selection is for a node to select a subset of its neighbors such that a broadcast message, retransmitted by these selected neighbors, will be received by all nodes two hops away. The MPR set of a node is computed such that it, for each interface, satisfies this condition. The information required to perform this calculation is acquired through the periodic exchange of Hello messages.

Topology Control Message  

                Diffusion Topology control messages are diffused with the purpose of providing each node in the network with sufficient link state information to allow route calculation.

Route  Calculation

               Given the link state information acquired through periodic message exchange, as well as the interface configuration of the nodes, the routing table for each node can be computed.