RFC 7181
The Optimized Link State Routing Protocol Version 2
Internet Engineering Task Force (IETF) T. Clausen Request for Comments: 7181 LIX, Ecole Polytechnique Category: Standards Track C. Dearlove ISSN: 2070-1721 BAE Systems ATC P. Jacquet Alcatel-Lucent Bell Labs U. Herberg Fujitsu Laboratories of America April 2014 The Optimized Link State Routing Protocol Version 2Abstract
This specification describes version 2 of the Optimized Link State Routing Protocol (OLSRv2) for Mobile Ad Hoc Networks (MANETs). Status of This Memo This is an Internet Standards Track document. This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). Further information on Internet Standards is available in Section 2 of RFC 5741. Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/rfc7181. Copyright Notice Copyright (c) 2014 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
This document may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The person(s) controlling the copyright in some of this material may not have granted the IETF Trust the right to allow modifications of such material outside the IETF Standards Process. Without obtaining an adequate license from the person(s) controlling the copyright in such materials, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process, except to format it for publication as an RFC or to translate it into languages other than English.Table of Contents
1. Introduction ....................................................5 2. Terminology .....................................................6 3. Applicability Statement .........................................9 4. Protocol Overview and Functioning ..............................10 4.1. Overview ..................................................10 4.2. Routers and Interfaces ....................................12 4.3. Information Base Overview .................................13 4.3.1. Local Information Base .............................13 4.3.2. Interface Information Base .........................14 4.3.3. Neighbor Information Base ..........................14 4.3.4. Topology Information Base ..........................14 4.3.5. Received Message Information Base ..................16 4.4. Signaling Overview ........................................16 4.5. Link Metrics ..............................................17 4.6. Flooding MPRs and Routing MPR .............................18 4.7. Routing Set Use ...........................................19 5. Protocol Parameters and Constants ..............................19 5.1. Protocol and Port Numbers .................................19 5.2. Multicast Address .........................................20 5.3. Interface Parameters ......................................20 5.3.1. Received Message Validity Time .....................20 5.4. Router Parameters .........................................20 5.4.1. Local History Times ................................20 5.4.2. Link Metric Parameters .............................21 5.4.3. Message Intervals ..................................21 5.4.4. Advertised Information Validity Times ..............22 5.4.5. Processing and Forwarding Validity Times ...........22 5.4.6. Jitter .............................................23 5.4.7. Hop Limit ..........................................23 5.4.8. Willingness ........................................24 5.5. Parameter Change Constraints ..............................25 5.6. Constants .................................................27 5.6.1. Link Metric Constants ..............................27 5.6.2. Willingness Constants ..............................28
5.6.3. Time Constant ......................................28
6. Link Metric Values .............................................28
6.1. Link Metric Representation ................................28
6.2. Link Metric Compressed Form ...............................29
7. Local Information Base .........................................29
7.1. Originator Set ............................................30
7.2. Local Attached Network Set ................................30
8. Interface Information Base .....................................31
8.1. Link Set ..................................................31
8.2. 2-Hop Set .................................................32
9. Neighbor Information Base ......................................32
10. Topology Information Base .....................................34
10.1. Advertising Remote Router Set ............................34
10.2. Router Topology Set ......................................35
10.3. Routable Address Topology Set ............................35
10.4. Attached Network Set .....................................36
10.5. Routing Set ..............................................37
11. Received Message Information Base .............................37
11.1. Received Set .............................................38
11.2. Processed Set ............................................38
11.3. Forwarded Set ............................................39
12. Information Base Properties ...................................39
12.1. Corresponding Protocol Tuples ............................39
12.2. Address Ownership ........................................40
13. Packets and Messages ..........................................41
13.1. Messages .................................................41
13.2. Packets ..................................................41
13.3. TLVs .....................................................42
13.3.1. Message TLVs ......................................42
13.3.2. Address Block TLVs ................................42
14. Message Processing and Forwarding .............................45
14.1. Actions When Receiving a Message .........................45
14.2. Message Considered for Processing ........................46
14.3. Message Considered for Forwarding ........................47
15. HELLO Messages ................................................49
15.1. HELLO Message Generation .................................49
15.2. HELLO Message Transmission ...............................51
15.3. HELLO Message Processing .................................51
15.3.1. HELLO Message Discarding ..........................51
15.3.2. HELLO Message Usage ...............................52
16. TC Messages ...................................................56
16.1. TC Message Generation ....................................56
16.2. TC Message Transmission ..................................58
16.3. TC Message Processing ....................................59
16.3.1. TC Message Discarding .............................59
16.3.2. TC Message Processing Definitions .................61
16.3.3. Initial TC Message Processing .....................61
16.3.4. Completing TC Message Processing ..................65
17. Information Base Changes ......................................66 17.1. Originator Address Changes ...............................66 17.2. Link State Changes .......................................66 17.3. Neighbor State Changes ...................................67 17.4. Advertised Neighbor Changes ..............................67 17.5. Advertising Remote Router Tuple Expires ..................68 17.6. Neighborhood Changes and MPR Updates .....................68 17.7. Routing Set Updates ......................................70 18. Selecting MPRs ................................................71 18.1. Overview .................................................72 18.2. Neighbor Graph ...........................................72 18.3. MPR Properties ...........................................73 18.4. Flooding MPRs ............................................74 18.5. Routing MPRs .............................................76 18.6. Calculating MPRs .........................................77 19. Routing Set Calculation .......................................78 19.1. Network Topology Graph ...................................78 19.2. Populating the Routing Set ...............................80 20. Proposed Values for Parameters ................................81 20.1. Local History Time Parameters ............................82 20.2. Message Interval Parameters ..............................82 20.3. Advertised Information Validity Time Parameters ..........82 20.4. Received Message Validity Time Parameters ................82 20.5. Jitter Time Parameters ...................................82 20.6. Hop Limit Parameter ......................................82 20.7. Willingness Parameters ...................................82 21. Sequence Numbers ..............................................83 22. Extensions ....................................................83 23. Security Considerations .......................................84 23.1. Security Architecture ....................................84 23.2. Integrity ................................................85 23.3. Confidentiality ..........................................86 23.4. Interaction with External Routing Domains ................87 23.5. Mandatory Security Mechanisms ............................87 23.6. Key Management ...........................................88 24. IANA Considerations ...........................................90 24.1. Expert Review: Evaluation Guidelines .....................91 24.2. Message Types ............................................91 24.3. Message-Type-Specific TLV Type Registries ................91 24.4. Message TLV Types ........................................92 24.5. Address Block TLV Types ..................................93 24.6. NBR_ADDR_TYPE and MPR Values .............................96 25. Contributors ..................................................96 26. Acknowledgments ...............................................97 27. References ....................................................97 27.1. Normative References .....................................97 27.2. Informative References ...................................98 Appendix A. Constraints .........................................100
Appendix B. Example Algorithm for Calculating MPRs ..............104 B.1. Additional Notation ......................................104 B.2. MPR Selection Algorithm ................................. 105 Appendix C. Example Algorithm for Calculating the Routing Set ...105 C.1. Local Interfaces and Neighbors ...........................106 C.2. Add Neighbor Routers .....................................107 C.3. Add Remote Routers .......................................107 C.4. Add Neighbor Addresses ...................................108 C.5. Add Remote Routable Addresses ............................109 C.6. Add Attached Networks ....................................110 C.7. Add 2-Hop Neighbors ......................................110 Appendix D. TC Message Example ..................................111 Appendix E. Flow and Congestion Control .........................1141. Introduction
The Optimized Link State Routing Protocol version 2 (OLSRv2) is the successor to OLSR (version 1) as published in [RFC3626]. Compared to [RFC3626], OLSRv2 retains the same basic mechanisms and algorithms, enhanced by the ability to use a link metric other than hop count in the selection of shortest routes. OLSRv2 also uses a more flexible and efficient signaling framework and includes some simplification of the messages being exchanged. OLSRv2 is developed for Mobile Ad Hoc Networks (MANETs). It operates as a table-driven, proactive protocol, i.e., it exchanges topology information with other routers in the network regularly. OLSRv2 is an optimization of the classic link state routing protocol. Its key concept is that of multipoint relays (MPRs). Each router selects two sets of MPRs, each being a set of its neighbor routers that "cover" all of its symmetrically connected 2-hop neighbor routers. These two sets are "flooding MPRs" and "routing MPRs", which are used to achieve flooding reduction and topology reduction, respectively. Flooding reduction is achieved by control traffic being flooded through the network using hop-by-hop forwarding, but with a router only needing to forward control traffic that is first received directly from one of the routers that have selected it as a flooding MPR (its "flooding MPR selectors"). This mechanism, denoted "MPR flooding", provides an efficient mechanism for information distribution within the MANET by reducing the number of transmissions required [MPR]. Topology reduction is achieved by assigning a special responsibility to routers selected as routing MPRs when declaring link state information. A sufficient requirement for OLSRv2 to provide shortest routes to all destinations is that routers declare link state information for their routing MPR selectors, if any. Routers that
are not selected as routing MPRs need not send any link state information. Based on this reduced link state information, routing MPRs are used as intermediate routers in multi-hop routes. Thus, the use of MPRs allows reduction of the number and the size of link state messages and reduction in the amount of link state information maintained in each router. When possible (in particular if using a hop count metric), the same routers may be picked as both flooding MPRs and routing MPRs. A router selects both routing and flooding MPRs from among its one- hop neighbors connected by "symmetric", i.e., bidirectional, links. Therefore, selecting routes through routing MPRs avoids the problems associated with data packet transfer over unidirectional links (e.g., the problem of not getting link-layer acknowledgments at each hop, for link layers employing this technique). OLSRv2 uses and extends the MANET Neighborhood Discovery Protocol (NHDP) defined in [RFC6130] and also uses the Generalized MANET Packet/Message Format [RFC5444], the TLVs specified in [RFC5497] and, optionally, message jitter as specified in [RFC5148]. These four other protocols and specifications were all originally created as part of OLSRv2 but have been specified separately for wider use. OLSRv2 makes no assumptions about the underlying link layer. OLSRv2, through its use of [RFC6130], may use link-layer information and notifications when available and applicable. In addition, OLSRv2 uses link metrics that may be derived from link layer or any other information. OLSRv2 does not specify the physical meaning of link metrics but specifies a means by which new types of link metrics may be specified in the future but used by OLSRv2 without modification. OLSRv2, like OLSR [RFC3626], inherits its concept of forwarding and relaying from the High Performance Radio Local Area Network (HIPERLAN) (a MAC-layer protocol), which is standardized by ETSI [HIPERLAN] [HIPERLAN2]. This document does not obsolete [RFC3626], which is left in place for further experimentation.2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. All terms introduced in [RFC5444], including "packet", "Packet Header", "message", "Message Header", "Message Body", "Message Type", "message sequence number", "hop limit", "hop count", "Address Block",
"TLV Block", "TLV", "Message TLV", "Address Block TLV", "type" (of TLV), "type extension" (of TLV), "value" (of TLV), "address", "address prefix", and "address object" are to be interpreted as described there. All terms introduced in [RFC6130], including "interface", "MANET interface", "network address", "link", "symmetric link", "symmetric 1-hop neighbor", "symmetric 2-hop neighbor", "symmetric 1-hop neighborhood" "constant", "interface parameter", "router parameter", "Information Base", and "HELLO message" are to be interpreted as described there. Additionally, this specification uses the following terminology: Router: A MANET router that implements this protocol. OLSRv2 interface: A MANET interface running this protocol. A router running this protocol MUST have at least one OLSRv2 interface. Routable address: A network address that may be used as the destination of a data packet. A router that implements this protocol will need to distinguish a routable address from a non-routable address by direct inspection of the network address, based on global-scope address allocations by IANA and/or administrative configuration (consistently across the MANET). Broadcast and multicast addresses, and addresses that are limited in scope to less than the entire MANET, MUST NOT be considered as routable addresses. Anycast addresses may be considered as routable addresses. Originator address: An address that is unique (within the MANET) to a router. A router MUST select an originator address; it MAY choose one of its interface addresses as its originator address; and it MAY select either a routable or non-routable address. A broadcast, multicast, or anycast address MUST NOT be chosen as an originator address. If the router selects a routable address, then it MUST be one that the router will accept as destination. An originator address MUST NOT have a prefix length, except when included in an Address Block where it MAY be associated with a prefix of maximum prefix length (e.g., if the originator address is an IPv6 address, it MUST have either no prefix length or have a prefix length of 128).
Message originator address:
The originator address of the router that created a message, as
deduced from that message by its recipient. For all messages used
in this specification, including HELLO messages defined in
[RFC6130], the recipient MUST be able to deduce an originator
address. The message originator address will usually be included
in the message as its <msg-orig-addr> element as defined in
[RFC5444]. However, an exceptional case, which does not add a
<msg-orig-addr> element to a HELLO message, may be used by a
router that only has a single address.
Willingness:
A numerical value between WILL_NEVER and WILL_ALWAYS (both
inclusive) that represents the router's willingness to be selected
as an MPR. A router has separate willingness values to be a
flooding MPR and a routing MPR.
Willing symmetric 1-hop neighbor:
A symmetric 1-hop neighbor that has willingness not equal to
WILL_NEVER.
Multipoint relay (MPR):
A router, X, is an MPR for a router, Y, if router Y has indicated
its selection of router X as an MPR in a recent HELLO message.
Router X may be a flooding MPR for Y if it is indicated to
participate in the flooding process of messages received from
router Y, or it may be a routing MPR for Y if it is indicated to
declare link state information for the link from X to Y. It may
also be both at the same time.
MPR selector:
A router, Y, is a flooding/routing MPR selector of router X if
router Y has selected router X as a flooding/routing MPR.
MPR flooding:
The optimized MANET-wide information distribution mechanism,
employed by this protocol, in which a message is relayed by only a
reduced subset of the routers in the network. MPR flooding is the
mechanism by which flooding reduction is achieved.
EXPIRED:
Indicates that a timer is set to a value clearly preceding the
current time (e.g., current time - 1).
This specification employs the same notational conventions as
[RFC5444] and [RFC6130].
3. Applicability Statement
This document specifies OLSRv2, a proactive routing protocol intended for use in Mobile Ad Hoc Networks (MANETs) [RFC2501]. The protocol's applicability is determined by its characteristics, which are that this protocol: o Is designed to work in networks with a dynamic topology and in which messages may be lost, such as due to collisions over wireless media. o Supports routers that each have one or more participating OLSRv2 interfaces, which will consist of some or all of its MANET interfaces using [RFC6130]. The set of a router's OLSRv2 interfaces, and the sets of its other MANET and non-MANET interfaces, may change over time. Each interface may have one or more network addresses (which may have prefix lengths), and these may also be dynamically changing. o Enables hop-by-hop routing, i.e., each router can use its local information provided by this protocol to route packets. o Continuously maintains routes to all destinations in the network, i.e., routes are instantly available and data traffic is subject to no delays due to route discovery. Consequently, no data traffic buffering is required. o Supports routers that have non-OLSRv2 interfaces that may be local to a router or that can serve as gateways towards other networks. o Enables the use of bidirectional additive link metrics to use shortest distance routes (i.e., routes with smallest total of link metrics). Incoming link metric values are to be determined by a process outside this specification. o Is optimized for large and dense networks; the larger and more dense a network, the more optimization can be achieved by using MPRs, compared to the classic link state algorithm [MPR]. o Uses [RFC5444] as described in its "Intended Usage" appendix and by [RFC5498]. o Allows "external" and "internal" extensibility (adding new Message Types and adding information to existing messages) as enabled by [RFC5444]. o Is designed to work in a completely distributed manner and does not depend on any central entity.
(next page on part 2)
