What is olsrd

Interaction with External Routing Domains. Node Identity. Flow and congestion control. IANA Considerations. Authors' Addresses. Full Copyright Statement. It operates as a table driven, proactive protocol, i. 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. Additional available link-state information may be utilized, e. 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 "symmetric", i. OLSR is developed to work independently from other protocols.

Likewise, OLSR makes no assumptions about the underlying link-layer. It is the address of one of the OLSR interfaces of the node. It is of no importance which address is chosen, however a node SHOULD always use the same address as its main address. A node is said to have a link to another node when one of its interface has a link to one of the interfaces of the other node.

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, i. 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.

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 partial link state to be flooded in order to provide shortest path routes. Additional topological information, if present, MAY be utilized e. 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. 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 re-ordered while in transmission. Such extensions may be introduced as additions to the protocol without breaking backwards compatibility with earlier versions.

Thus any existing IP stack can be used as is: the protocol only interacts with routing table management. Multipoint Relays 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 1-hop neighborhood which may retransmit its messages.

Each node selects its MPR set from among its 1-hop symmetric neighbors. This set is selected such that it covers in terms of radio range all symmetric strict 2-hop nodes. The smaller a 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 MPR. A broadcast message, intended to be diffused in the whole network, coming from any of the MPR selectors of node N is assumed to be retransmitted by node N, if N has not received it yet.

This set can change over time i. Protocol Functioning This section outlines the overall 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. Each auxiliary function provides additional functionality, which may be applicable in specific scenarios, e. 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, i. The purpose of dividing the functioning of OLSR into a 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.

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 mechanism serves as the transport mechanism for all OLSR control traffic. A separate HELLO message is generated for each interface and emitted in correspondence with the provisions in section 7.

Resulting from Link Sensing is a local link set, describing links between "local interfaces" and "remote interfaces" - i. 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 in order to map interface addresses to main addresses and, thereby, to nodes. This additional information is acquired through multiple interface declaration MID messages, described in section 5.

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 2 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, as described in section 6. MPR selection procedures are detailed in section 8. MPR signaling is provided in correspondence with the provisions in the section 6. 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.

Topology Control messages are diffused in correspondence with the provisions in section 9. 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. This is detailed in section The following table specifies the component of the core functionality of OLSR, as well as their relations to this document.

Auxiliary Functioning In addition to the core functioning of OLSR, there are situations where additional functionality is desired. This includes situations where a node has multiple interfaces, some of which participate in another routing domain, where the programming interface to the networking hardware provides additional information in form of link layer notifications and where it is desired to provide redundant topological information to the network on expense of protocol overhead.

The following table specifies auxiliary functions and their relation to this document. The purpose of this is to facilitate extensibility of the protocol without breaking backwards compatibility. This also provides an easy way of piggybacking different "types" of information into a single transmission, and thus for a given implementation to optimize towards utilizing the maximal frame-size, provided by the network.

These packets are embedded in UDP datagrams for transmission over the network. The present document is presented with IPv4 addresses.

Considerations regarding IPv6 are given in section Each packet encapsulates one or more messages. The messages share a common header format, which enables nodes to correctly accept and if applicable retransmit messages of an unknown type. Messages can be flooded onto the entire network, or flooding can be limited to nodes within a diameter in terms of number of hops from the originator of the message.

Thus transmitting a message to the neighborhood of a node is just a special case of flooding. When flooding any control message, duplicate retransmissions will be eliminated locally i. Furthermore, a node can examine the header of a message to obtain information on the distance in terms of number of hops to the originator of the message.

This feature may be useful in situations where, e. A separate Packet Sequence Number is maintained for each interface such that packets transmitted over an interface are sequentially enumerated. If the packet contains no messages i. Message types in the range of are reserved for messages in this document and in possible extensions. Vtime This field indicates for how long time after reception a node MUST consider the information contained in the message as valid, unless a more recent update to the information is received.

The validity time is represented by its mantissa four highest bits of Vtime field and by its exponent four lowest bits of Vtime field.

The proposed value of the scaling factor C is specified in section Message Size This gives the size of this message, counted in bytes and measured from the beginning of the "Message Type" field and until the beginning of the next "Message Type" field or - if there are no following messages - until the end of the packet. Originator Address This field contains the main address of the node, which has originally generated this message.

Time To Live This field contains the maximum number of hops a message will be transmitted. Normally, a node would not receive a message with a TTL of zero. Thus, by setting this field, the originator of a message can limit the flooding radius. Hop Count This field contains the number of hops a message has attained. Initially, this is set to '0' by the originator of the message. Message Sequence Number While generating a message, the "originator" node will assign a unique identification number to each message.

This number is inserted into the Sequence Number field of the message. The sequence number is increased by 1 one for each message originating from the node. Message sequence numbers are used to ensure that a given message is not retransmitted more than once by any node. Packet Processing and Message Flooding Upon receiving a basic packet, a node examines each of the "message headers".

Based on the value of the "Message Type" field, the node can determine the fate of the message. A node may receive the same message several times. Thus, to avoid re-processing of some messages which were already received and processed, each node maintains a Duplicate Set.

In this set, the node records information about the most recently received messages where duplicate processing of a message is to be avoided. In a node, the set of Duplicate Tuples are denoted the "Duplicate set". In this section, the term "Originator Address" will be used for the main address of the node which sent the message. The term "Sender Interface Address" will be used for the sender address given in the IP header of the packet containing the message of the interface which sent the message.

The term "Receiving Interface Address" will be used for the address of the interface of the node which received the message. Thus, upon receiving a basic packet, a node MUST perform the following tasks for each encapsulated message: 1 If the packet contains no messages i. Default Forwarding Algorithm The default forwarding algorithm is the following: 1 If the sender interface address of the message is not detected to be in the symmetric 1-hop neighborhood of the node, the forwarding algorithm MUST silently stop here and the message MUST NOT be forwarded.

If after those steps, the message is not considered for forwarding, then the processing of this section stops i. If, and only if, according to step 4, the message must be retransmitted then: 6 The TTL of the message is reduced by one.

Considerations on Processing and Forwarding It should be noted that processing and forwarding messages are two different actions, conditioned by different rules. Processing relates to using the content of the messages, while forwarding is related to retransmitting the same message for other nodes of the network.

Notice that this specification includes a description for both the forwarding and the processing of each known message type. Forwarding and setting the correct message header in the forwarded, known, message is the responsibility of the algorithm specifying how the message is to be handled and, if necessary, retransmitted.

This enables a message type to be specified such that the message can be modified while in transit e. It also enables bypassing of the MPR flooding mechanism if for some reason classical flooding of a message type is required, the algorithm which specifies how such messages should be handled will simply rebroadcast the message, regardless of MPRs.

By defining a set of message types, which MUST be recognized by all implementations of OLSR, it will be possible to extend the protocol through introduction of additional message types, while still being able to maintain compatibility with older implementations.

Emission of control traffic from neighboring nodes may, for various reasons mainly timer interactions with packet processing , become synchronized such that several neighbor nodes attempt to transmit control traffic simultaneously. Depending on the nature of the underlying link-layer, this may or may not lead to collisions and hence message loss - possibly loss of several subsequent messages of the same type.

To avoid such synchronizations, the following simple strategy for emitting control messages is proposed. The jitter must be a random value for each message generated. Notice that when the node sends a control message, the opportunity to piggyback other messages before their keeping period is expired may be taken to reduce the number of packet transmissions. Notice, that a minimal rate of control messages is imposed.

A node MAY send control messages at a higher rate, if beneficial for a specific deployment. Information Repositories Through the exchange of OLSR control messages, each node accumulates information about the network. This information is stored according to the descriptions in this section. Link Sensing: Local Link Information Base The local link information base stores information about links to neighbors. In a node, the set of Link Tuples are denoted the "Link Set".

In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor Set". Their main addresses are listed in the MPR Set. Topology Information Base Each node in the network maintains topology information about the network.

This information is acquired from TC-messages and is used for routing table calculations. In a node, the set of Topology Tuples are denoted the "Topology Set". This section describes how MID messages are exchanged and processed. Each node with multiple interfaces MUST announce, periodically, information describing its interface configuration to other nodes in the network. This is accomplished through flooding a Multiple Interface Declaration message to all nodes in the network through the MPR flooding mechanism.

Each node in the network maintains interface information about the other nodes in the network. This information acquired from MID messages, emitted by nodes with multiple interfaces participating in the MANET, and is used for routing table calculations.

Specifically, multiple interface declaration associates multiple interfaces to a node and to a main address through populating the multiple interface association base in each node. All interface addresses other than the main address of the originator node are put in the MID message. If the maximum allowed message size as imposed by the network is reached while there are still interface addresses which have not been inserted into the MIDmessage, more MID messages are generated until the entire interface addresses set has been sent.

The list of addresses can be partial in each MID message e. The information diffused in the network by these MID messages will help each node to calculate its routing table. The "default forwarding algorithm" described in section 3. The remaining parts of OLSR operate on nodes, uniquely identified by their "main addresses" effectively, the main address of a node is its "node id" - which for convenience corresponds to the address of one of its interfaces.

In a network with only single interface nodes, the main address of a node will, by definition, be equal to the interface address of the node. In networks with multiple interface nodes operating within a common OLSR area, it is required to be able to map any interface address to the corresponding main address. The exchange of MID messages provides a way in which interface information is acquired by nodes in the network.

This permits identification of a node's "main address", given one of its interface addresses. Thus this section describes the general HELLO message mechanism, followed by a description of link sensing and topology detection, respectively.

HELLO Message Format To accommodate for link sensing, neighborhood detection and MPR selection signalling, as well as to accommodate for future extensions, an approach similar to the overall packet format is taken. This is sent as the data-portion of the general packet format described in section 3.

Reserved This field must be set to "" to be in compliance with this specification. The HELLO emission interval is represented by its mantissa four highest bits of Htime field and by its exponent four lowest bits of Htime field. Willingness This field specifies the willingness of a node to carry and forward traffic for other nodes.

Link Code This field specifies information about the link between the interface of the sender and the following list of neighbor interfaces. It also specifies information about the status of the neighbor. Link codes, not known by a node, are silently discarded. Link Message Size The size of the link message, counted in bytes and measured from the beginning of the "Link Code" field and until the next "Link Code" field or - if there are no more link types - the end of the message.

Neighbor Interface Address The address of an interface of a neighbor node. A node must perform link sensing on each interface, in order to detect links between the interface and neighbor interfaces.

Furthermore, a node must advertise its entire symmetric 1-hop neighborhood on each interface in order to perform neighbor detection. Hence, for a given interface, a HELLO message will contain a list of links on that interface with associated link types , as well as a list of the entire neighborhood with an associated neighbor types.

The Willingness field is set such that it corresponds to the node's willingness to forward traffic on behalf of other nodes see section A node MUST advertise the same willingness on all interfaces. Link Sensing Link sensing populates the local link information base. The process of populating this set is denoted "link sensing" and is performed using HELLO message exchange, updating a local link information base in each node. Each node should detect the links between itself and neighbor nodes.

Uncertainties over radio propagation may make some links unidirectional. Consequently, all links MUST be checked in both directions in order to be considered valid. A "link" is described by a pair of interfaces: a local and a remote interface. For the purpose of link sensing, each neighbor node more specifically, the link to each neighbor has an associated status of either "symmetric" or "asymmetric". The information, acquired through and used by the link sensing, is accumulated in the link set.

This allows neighbors to detect the link breakage. Neighbor Detection Neighbor detection populates the neighborhood information base and concerns itself with nodes and node main addresses. The relationship between OLSR interface addresses and main addresses is described in section 5. Populating the Neighbor Set A node maintains a set of neighbor tuples, based on the link tuples. This information is updated according to changes in the Link Set. The Link Set keeps the information about the links, while the Neighbor Set keeps the information about the neighbors.

There is a clear association between those two sets, since a node is a neighbor of another node if and only if there is at least one link between the two nodes. Populating the 2-hop Neighbor Set The 2-hop neighbor set describes the set of nodes which have a symmetric link to a symmetric neighbor.

This information set is maintained through periodic exchange of HELLO messages as described in this section. Populating the MPR set MPRs are used to flood control messages from a node into the network while reducing the number of retransmissions that will occur in a region. Thus, the concept of MPR is an optimization of a classical flooding mechanism.

Each node in the network selects, independently, its own set of MPRs among its symmetric 1-hop neighborhood. Notice that a node, a, which is a direct neighbor of another node, b, is not also a strict 2-hop neighbor of node b. This means that the union of the symmetric 1-hop neighborhoods of the MPR nodes contains the symmetric strict 2-hop neighborhood. MPR set recalculation should occur when changes are detected in the symmetric neighborhood or in the symmetric strict 2-hop neighborhood.

While it is not essential that the MPR set is minimal, it is essential that all strict 2-hop neighbors can be reached through the selected MPR nodes. Keeping the MPR set small ensures that the overhead of the protocol is kept at a minimum. The MPR set can coincide with the entire symmetric neighbor set. This could be the case at network initialization and will correspond to classic link-state routing. The following terminology will be used in describing the heuristics: neighbor of an interface a node is a "neighbor of an interface" if the interface on the local node has a link to any one interface of the neighbor node.

N: N is the subset of neighbors of the node, which are neighbor of the interface I. For example, if node b in N2 can be reached only through a symmetric link to node a in N, then add node a to the MPR set. Remove the nodes from N2 which are now covered by a node in the MPR set. In case of multiple choice select the node which provides reachability to the maximum number of nodes in N2.

In case of multiple nodes providing the same amount of reachability, select the node as MPR whose D y is greater. Other algorithms, as well as improvements over this algorithm, are possible. For example, assume that in a multiple-interface scenario there exists more than one link between nodes 'a' and 'b'.

If node 'a' has selected node 'b' as MPR for one of its interfaces, then node 'b' can be selected as MPR without additional performance loss by any other interfaces on node 'a'. Deletion of MPR selector tuples occurs in case of expiration of the timer or in case of link breakage as described in the "Neighborhood and 2-hop Neighborhood Changes".

This is considered as a neighbor loss if the link described by the expired tuple was the last link with a neighbor node on the contrary, a link with an interface may break while a link with another interface of the neighbor node remains without being observed as a neighborhood change.

This is considered as a neighbor appearance if there was previously no link tuple describing a link with the corresponding neighbor node. A change in the 2-hop neighborhood is detected when a 2-hop neighbor tuple expires or is deleted according to section 8.

Topology Discovery The link sensing and neighbor detection part of the protocol basically offers, to each node, a list of neighbors with which it can communicate directly and, in combination with the Packet Format and Forwarding part, an optimized flooding mechanism through MPRs. Based on this, topology information is disseminated through the network. The present section describes which part of the information given by the link sensing and neighbor detection is disseminated to the entire network and how it is used to construct routes.

Routes are constructed through advertised links and links with neighbors. A node must at least disseminate links between itself and the nodes in its MPR-selector set, in order to provide sufficient information to enable routing.

Every time a node detects a change in its advertised neighbor set, it increments this sequence number "Wraparound" is handled as described in section When a node receives a TC message, it can decide on the basis of this Advertised Neighbor Sequence Number, whether or not the received information about the advertised neighbors of the originator node is more recent than what it already has.

If you are interested in coming join the event's Mailing List to stay up to date with the latest news. Sometimes these networks are called "mesh networks". The development of the implementation was continued in an open source project as the routing protocol was used by Freifunk , Funkfeuer and others to build Community Mesh Networks.

The basis of the olsrd2 implementation is the OLSR. BattlemeshV9 1. Personal tools Log in.