idnits 2.17.1 draft-ietf-manet-olsrv2-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 19. -- Found old boilerplate from RFC 3978, Section 5.5 on line 2965. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 2942. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 2949. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 2955. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There is 1 instance of too long lines in the document, the longest one being 6 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 1463 has weird spacing: '.... This allow...' == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (March 6, 2006) is 6597 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: '0-7' on line 2162 ** Downref: Normative reference to an Experimental RFC: RFC 3626 (ref. '1') ** Obsolete normative reference: RFC 1991 (ref. '3') (Obsoleted by RFC 4880) == Outdated reference: A later version (-17) exists of draft-ietf-manet-packetbb-00 -- Possible downref: Non-RFC (?) normative reference: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '6' -- Possible downref: Non-RFC (?) normative reference: ref. '7' Summary: 8 errors (**), 0 flaws (~~), 5 warnings (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Mobile Ad hoc Networking (MANET) T. Clausen 3 Internet-Draft LIX, Ecole Polytechnique, France 4 Expires: September 7, 2006 C. Dearlove 5 BAE Systems Advanced Technology 6 Centre 7 The OLSRv2 Design Team 8 MANET Working Group 9 March 6, 2006 11 The Optimized Link-State Routing Protocol version 2 12 draft-ietf-manet-olsrv2-01 14 Status of this Memo 16 By submitting this Internet-Draft, each author represents that any 17 applicable patent or other IPR claims of which he or she is aware 18 have been or will be disclosed, and any of which he or she becomes 19 aware will be disclosed, in accordance with Section 6 of BCP 79. 21 Internet-Drafts are working documents of the Internet Engineering 22 Task Force (IETF), its areas, and its working groups. Note that 23 other groups may also distribute working documents as Internet- 24 Drafts. 26 Internet-Drafts are draft documents valid for a maximum of six months 27 and may be updated, replaced, or obsoleted by other documents at any 28 time. It is inappropriate to use Internet-Drafts as reference 29 material or to cite them other than as "work in progress." 31 The list of current Internet-Drafts can be accessed at 32 http://www.ietf.org/ietf/1id-abstracts.txt. 34 The list of Internet-Draft Shadow Directories can be accessed at 35 http://www.ietf.org/shadow.html. 37 This Internet-Draft will expire on September 7, 2006. 39 Copyright Notice 41 Copyright (C) The Internet Society (2006). 43 Abstract 45 This document describes version 2 of the Optimized Link State Routing 46 (OLSRv2) protocol for mobile ad hoc networks. The protocol is an 47 optimization of the classical link state algorithm tailored to the 48 requirements of a mobile wireless LAN. 50 The key optimization of OLSRv2 is that of multipoint relays, 51 providing an efficient mechanism for network-wide broadcast of link- 52 state information. A secondary optimization is, that OLSRv2 employs 53 partial link-state information: each node maintains information of 54 all destinations, but only a subset of links. This allows that only 55 select nodes diffuse link-state advertisements (i.e. reduces the 56 number of network-wide broadcasts) and that these advertisements 57 contain only a subset of links (i.e. reduces the size of each 58 network-wide broadcast). The partial link-state information thus 59 obtained allows each OLSRv2 node to at all times maintain optimal (in 60 terms of number of hops) routes to all destinations in the network. 62 OLSRv2 imposes minimum requirements to the network by not requiring 63 sequenced or reliable transmission of control traffic. Furthermore, 64 the only interaction between OLSRv2 and the IP stack is routing table 65 management. 67 OLSRv2 is particularly suitable for large and dense networks as the 68 technique of MPRs works well in this context. 70 Table of Contents 72 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 73 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . 6 74 1.2 Applicability Statement . . . . . . . . . . . . . . . . . 7 75 2. Protocol Overview and Functioning . . . . . . . . . . . . . . 9 76 2.1 Protocol Extensibility . . . . . . . . . . . . . . . . . . 11 77 3. Processing and Forwarding Repositories . . . . . . . . . . . . 13 78 3.1 Received Message Set . . . . . . . . . . . . . . . . . . . 13 79 3.2 Fragment Set . . . . . . . . . . . . . . . . . . . . . . . 13 80 3.3 Processed Set . . . . . . . . . . . . . . . . . . . . . . 14 81 3.4 Forwarded Set . . . . . . . . . . . . . . . . . . . . . . 14 82 3.5 Relay Set . . . . . . . . . . . . . . . . . . . . . . . . 14 83 4. Packet Processing and Message Forwarding . . . . . . . . . . . 16 84 4.1 Actions when Receiving an OLSRv2 Packet . . . . . . . . . 16 85 4.2 Actions when Receiving an OLSRv2 Message . . . . . . . . . 16 86 4.3 Message Considered for Processing . . . . . . . . . . . . 16 87 4.4 Message Considered for Forwarding . . . . . . . . . . . . 18 88 5. Information Repositories . . . . . . . . . . . . . . . . . . . 21 89 5.1 Neighborhood Information Base . . . . . . . . . . . . . . 21 90 5.1.1 Link Set . . . . . . . . . . . . . . . . . . . . . . . 21 91 5.1.2 2-Hop Neighbor Set . . . . . . . . . . . . . . . . . . 22 92 5.1.3 Neighborhood Address Association Set . . . . . . . . . 23 93 5.1.4 MPR Set . . . . . . . . . . . . . . . . . . . . . . . 23 94 5.1.5 MPR Selector Set . . . . . . . . . . . . . . . . . . . 23 95 5.1.6 Advertised Neighbor Set . . . . . . . . . . . . . . . 23 96 5.2 Topology Information Base . . . . . . . . . . . . . . . . 24 97 5.2.1 Topology Set . . . . . . . . . . . . . . . . . . . . . 24 98 5.2.2 Attached Network Set . . . . . . . . . . . . . . . . . 24 99 5.2.3 Routing Set . . . . . . . . . . . . . . . . . . . . . 25 100 6. OLSRv2 Control Message Structures . . . . . . . . . . . . . . 26 101 6.1 General OLSRv2 Message TLVs . . . . . . . . . . . . . . . 26 102 6.1.1 VALIDITY_TIME TLV . . . . . . . . . . . . . . . . . . 26 103 6.1.2 INTERVAL_TIME TLV . . . . . . . . . . . . . . . . . . 27 104 6.2 Local Interface Blocks . . . . . . . . . . . . . . . . . . 28 105 6.3 HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 28 106 6.3.1 HELLO Message: Message TLVs . . . . . . . . . . . . . 29 107 6.3.2 HELLO Message: Address Blocks TLVs . . . . . . . . . . 29 108 6.4 TC Messages . . . . . . . . . . . . . . . . . . . . . . . 30 109 7. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 31 110 7.1 HELLO Message: Transmission . . . . . . . . . . . . . . . 33 111 8. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 34 112 8.1 Populating the Link Set . . . . . . . . . . . . . . . . . 34 113 8.2 Populating the 2-Hop Neighbor Set . . . . . . . . . . . . 36 114 8.3 Populating the MPR Selector Set . . . . . . . . . . . . . 37 115 8.4 Neighborhood and 2-Hop Neighborhood Changes . . . . . . . 38 116 9. TC Message Generation . . . . . . . . . . . . . . . . . . . . 40 117 9.1 TC Message: Transmission . . . . . . . . . . . . . . . . . 41 119 10. TC Message Processing . . . . . . . . . . . . . . . . . . . 42 120 10.1 Checking Freshness & Validity of a TC message . . . . . . 42 121 10.2 Updating the Topology Set . . . . . . . . . . . . . . . . 43 122 10.3 Purging Old Entries from the Topology Set . . . . . . . . 44 123 10.4 Updating the Attached Networks Set . . . . . . . . . . . . 44 124 10.5 Purging Old Entries from the Attached Network Set . . . . 45 125 10.6 Processing Unfragmented TC Messages . . . . . . . . . . . 45 126 10.7 Processing Partially or Wholly Self-Contained 127 Fragmented TC Messagess . . . . . . . . . . . . . . . . . 45 128 11. Populating the MPR Set . . . . . . . . . . . . . . . . . . . 47 129 12. Populating Derived Sets . . . . . . . . . . . . . . . . . . 48 130 12.1 Populating the Relay Set . . . . . . . . . . . . . . . . . 48 131 12.2 Populating the Advertised Neighbor Set . . . . . . . . . . 48 132 13. Populating the Neighborhood Address Association Set . . . . 49 133 14. Routing Table Calculation . . . . . . . . . . . . . . . . . 50 134 15. Proposed Values for Constants . . . . . . . . . . . . . . . 53 135 15.1 Message Intervals . . . . . . . . . . . . . . . . . . . . 53 136 15.2 Holding Times . . . . . . . . . . . . . . . . . . . . . . 53 137 15.3 Willingness . . . . . . . . . . . . . . . . . . . . . . . 53 138 15.4 Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 139 16. Representing Time . . . . . . . . . . . . . . . . . . . . . 55 140 17. IANA Considerations . . . . . . . . . . . . . . . . . . . . 56 141 17.1 Multicast Addresses . . . . . . . . . . . . . . . . . . . 56 142 17.2 Message Types . . . . . . . . . . . . . . . . . . . . . . 56 143 17.3 TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 56 144 18. References . . . . . . . . . . . . . . . . . . . . . . . . . 57 145 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 58 146 A. Example Heuristic for Calculating MPRs . . . . . . . . . . . . 59 147 B. Example Algorithms for Generating Control Traffic . . . . . . 62 148 B.1 Example Algorithm for Generating HELLO messages . . . . . 62 149 B.2 Example Algorithm for Generating TC messages . . . . . . . 63 150 C. Protocol and Port Number . . . . . . . . . . . . . . . . . . . 65 151 D. Packet and Message Layout . . . . . . . . . . . . . . . . . . 66 152 D.1 OLSRv2 Packet Format . . . . . . . . . . . . . . . . . . . 66 153 E. Node Configuration . . . . . . . . . . . . . . . . . . . . . . 73 154 F. Security Considerations . . . . . . . . . . . . . . . . . . . 74 155 F.1 Confidentiality . . . . . . . . . . . . . . . . . . . . . 74 156 F.2 Integrity . . . . . . . . . . . . . . . . . . . . . . . . 74 157 F.3 Interaction with External Routing Domains . . . . . . . . 75 158 F.4 Node Identity . . . . . . . . . . . . . . . . . . . . . . 76 159 G. Flow and Congestion Control . . . . . . . . . . . . . . . . . 77 160 H. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . 78 161 I. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 79 162 J. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 80 163 Intellectual Property and Copyright Statements . . . . . . . . 81 165 1. Introduction 167 The Optimized Link State Routing Protocol version 2 (OLSRv2) is an 168 update to OLSRv1 as published in RFC3626 [1]. Compared to RFC3626, 169 OLSRv2 retains the same basic mechanisms and algorithms, while 170 providing an even more flexible signaling framework and some 171 simplification of the messages being exchanged. Also, OLSRv2 takes 172 care to accomodate both IPv4 and IPv6 addresses in a compact fashion. 174 OLSRv2 is developed for mobile ad hoc networks. It operates as a 175 table driven, proactive protocol, i.e. it exchanges topology 176 information with other nodes of the network regularly. Each node 177 selects a set of its neighbor nodes as "MultiPoint Relays" (MPRs). 178 In OLSRv2, only nodes that are selected as such MPRs are then 179 responsible for forwarding control traffic intended for diffusion 180 into the entire network. MPRs provide an efficient mechanism for 181 flooding control traffic by reducing the number of transmissions 182 required. 184 Nodes selected as MPRs also have a special responsibility when 185 declaring link state information in the network. Indeed, the only 186 requirement for OLSRv2 to provide shortest path routes to all 187 destinations is that MPR nodes declare link-state information for 188 their MPR selectors. Additional available link-state information may 189 be utilized, e.g., for redundancy. 191 Nodes which have been selected as multipoint relays by some neighbor 192 node(s) announce this information periodically in their control 193 messages. Thereby a node announces to the network that it has 194 reachability to the nodes which have selected it as an MPR. Thus, as 195 well as being used to facilitate efficient flooding, MPRs are also 196 used for route calculation from any given node to any destination in 197 the network. 199 A node selects MPRs from among its one hop neighbors with 200 "symmetric", i.e., bi-directional, linkages. Therefore, selecting 201 the route through MPRs automatically avoids the problems associated 202 with data packet transfer over uni-directional links (such as the 203 problem of not getting link-layer acknowledgments for data packets at 204 each hop, for link-layers employing this technique for unicast 205 traffic). 207 OLSRv2 is developed to work independently from other protocols. 208 Likewise, OLSRv2 makes no assumptions about the underlying link- 209 layer. However, OLSRv2 may use link-layer information and 210 notifications when available and applicable. 212 OLSRv2, as OLSRv1, inherits the concept of forwarding and relaying 213 from HIPERLAN (a MAC layer protocol) which is standardized by ETSI 214 [5]. 216 1.1 Terminology 218 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 219 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 220 document are to be interpreted as described in RFC2119 [2]. 222 Additionally, this document uses the following terminology: 224 node - a MANET router which implements the Optimized Link State 225 Routing protocol as specified in this document. 227 OLSRv2 interface - A network device participating in a MANET running 228 OLSRv2. A node may have several OLSRv2 interfaces, each interface 229 assigned one or more IP addresses. 231 neighbor - A node X is a neighbor of node Y if node Y can hear node X 232 (i.e., a link exists from an OLSRv2 interface on node X to an 233 OLSRv2 interface on node Y). A neighbor may also be called a 234 1-hop neighbor. 236 2-hop neighbor - A node X is a 2-hop neighbor of node Y if node X is 237 a neighbor of a neighbor of node Y, but is not node Y itself. 239 strict 2-hop neighbor - a 2-hop neighbor which is not a neighbor of 240 the node, and is not a 2-hop neighbor only through a neighbor with 241 willingness WILL_NEVER. 243 multipoint relay (MPR) - A node which is selected by its 1-hop 244 neighbor, node X, to "re-transmit" all the broadcast messages that 245 it receives from node X, provided that the message is not a 246 duplicate, and that the time to live field of the message is 247 greater than one. 249 multipoint relay selector (MPR selector, MS) - A node which has 250 selected its 1-hop neighbor, node X, as one of its multipoint 251 relays, will be called an MPR selector of node X. 253 link - A link is a pair of OLSRv2 interfaces from two different 254 nodes, where at least one interface is able to hear (i.e. receive 255 traffic from) the other. 257 symmetric link - A link where both interfaces are able to hear (i.e. 258 receive messages from) the other. 260 asymmetric link - A link which is not symmetric. 262 symmetric 1-hop neighborhood - The symmetric 1-hop neighborhood of 263 any node X is the set of nodes which have at least one symmetric 264 link to node X. 266 symmetric 2-hop neighborhood - The symmetric 2-hop neighborhood of 267 node X is the set of nodes, excluding node X itself, which have a 268 symmetric link to the symmetric 1-hop neighborhood of X. 270 symmetric strict 2-hop neighborhood - The symmetric strict 2-hop 271 neighborhood of node X is the set of nodes in its symmetric 2-hop 272 neighborhood that are neither in its symmetric 1-hop neighborhood 273 nor reachable only through a symmetric 1-hop neighbor of node X 274 with willingness WILL_NEVER. 276 1.2 Applicability Statement 278 OLSRv2 is a proactive routing protocol for mobile ad hoc networks 279 (MANETs) [6], [7]. It is well suited to large and dense networks of 280 mobile nodes, as the optimization achieved using the MPRs works well 281 in this context. The larger and more dense a network, the more 282 optimization can be achieved as compared to the classic link state 283 algorithm. OLSRv2 uses hop-by-hop routing, i.e., each node uses its 284 local information to route packets. 286 As OLSRv2 continuously maintains routes to all destinations in the 287 network, the protocol is beneficial for traffic patterns where the 288 traffic is random and sporadic between a large subset of nodes, and 289 where the [source, destination] pairs are changing over time: no 290 additional control traffic need be generated in this situation since 291 routes are maintained for all known destinations at all times. Also, 292 since routes are maintained continously, traffic is subject to no 293 delays due to buffering/route-discovery. This continued route 294 maintenance may be done using periodic message exchange, as detailed 295 in this specification, or triggered by external events if available. 297 OLSRv2 supports nodes which have multiple interfaces which 298 participate in the MANET. OLSRv2, additionally, supports nodes which 299 have non-MANET interfaces which can serve as (if configured to do so) 300 gateways towards other networks. 302 The message exchange format, contained in previous versions of this 303 specification, has been factored out to an independant specification 304 [4], which is used for carrying OLSRv2 control signals. OLSRv2 is 305 thereby able to accommodate for extensions via "external" and 306 "internal" extensibility. External extensibility implies that a 307 protocol extension may specify and exchange new message types which 308 can be forwarded and delivered correctly according to [4]. Internal 309 extensibility implies, that a protocol extension may define 310 additional attributes to be carried embedded in the OLSRv2 control 311 messages, detailed in this specification, while these OLSRv2 control 312 messages with additional attributes can still be correctly understood 313 by all OLSRv2 nodes. 315 2. Protocol Overview and Functioning 317 OLSRv2 is a proactive routing protocol for mobile ad hoc networks. 318 The protocol inherits the stability of a link state algorithm and has 319 the advantage of having routes immediately available when needed due 320 to its proactive nature. OLSRv2 is an optimization over the 321 classical link state protocol, tailored for mobile ad hoc networks. 322 The main tailoring and optimizations of OLSRv2 are: 324 o periodic, unacknowledged transmission of all control messages; 326 o optimized flooding for global link-state information diffusion; 328 o partial topology maintenance -- each node will know of all 329 destinations and a subset of links in the network. 331 More specifically, OLSRv2 consists of the following main components: 333 o A general and flexible signaling framework, allowing for 334 information exchange between OLSRv2 nodes. This framework allows 335 for both local information exchange (between neighboring nodes) 336 and global information exchange using an optimized flooding 337 mechanism denoted "MPR flooding". 339 o A specification of local signaling, denoted HELLO messages. HELLO 340 messages in OLSRv2 serve to: 342 * discover links to adjacent OLSR nodes; 344 * perform bidirectionality check on the discovered links; 346 * advertise neighbors and hence discover 2-hop neighbors; 348 * signal MPR selection. 350 HELLO messages are emitted periodically, thereby allowing nodes to 351 continuously track changes in their local neighborhoods. 353 o A specification of global signaling, denoted TC messages. TC 354 messages in OLSRv2 serve to: 356 * inject link-state information into the entire network. 358 * inject addresses of hosts and networks for which they may serve 359 as a gateway into the entire network. 361 * allow nodes with multiple interface addresses to ensure that 362 nodes within two hops can associate these addresses with a 363 single node for efficient MPR Set determination. 365 TC messages are emitted periodically, thereby allowing nodes to 366 continuously track global changes in the network. 368 Thus, through periodic exchange of HELLO messages, a node is able to 369 acquire and maintain information about its immediate neighborhood. 370 This includes information about immediate neighbors, as well as nodes 371 which are two hops away. By HELLO messages being exchanged 372 periodically, a node learns about changes in the neighborhood (new 373 nodes emerging, old nodes disappearing) without requiring explicit 374 mechanisms for doing so. 376 Based on the local topology information, acquired through the 377 periodic exchange of HELLO messages, an OLSRv2 node is able to make 378 provisions for ensuring optimized flooding, denoted "MPR flooding", 379 as well as injection of link-state information into the network. 380 This is done through the notion of Multipoint Relays. 382 The idea of multipoint relays is to minimize the overhead of flooding 383 messages in the network by reducing redundant retransmissions in the 384 same region. Each node in the network selects a set of nodes in its 385 symmetric 1-hop neighborhood which may retransmit its messages. This 386 set of selected neighbor nodes is called the "Multipoint Relay" (MPR) 387 Set of that node. The neighbors of node N which are *NOT* in its MPR 388 set, receive and process broadcast messages but do not retransmit 389 broadcast messages received from node N. The MPR Set of a node is 390 selected such that it covers (in terms of radio range) all symmetric 391 strict 2-hop nodes. The MPR Set of N, denoted as MPR(N), is then an 392 arbitrary subset of the symmetric 1-hop neighborhood of N which 393 satisfies the following condition: every node in the symmetric strict 394 2-hop neighborhood of N MUST have a symmetric link towards MPR(N). 395 The smaller a MPR Set, the less control traffic overhead results from 396 the routing protocol. [7] gives an analysis and example of MPR 397 selection algorithms. Notice, that as long as the condition above is 398 satisfied, any algorithm selecting MPR Sets is acceptable in terms of 399 implementation interoperability. 401 Each node maintains information about the set of neighbors that have 402 selected it as MPR. This set is called the "Multipoint Relay 403 Selector Set" (MPR Selector Set) of a node. A node obtains this 404 information from periodic HELLO messages received from the neighbors. 405 Each node also maintains a Relay Set, which is the set of nodes for 406 which a node is to relay broadcast traffic. The Relay Set is derived 407 from the MPR Selector Set in that the Relay Set MUST contain all the 408 nodes in the MPR Selector set and MAY contain additional nodes. 410 A broadcast message, intended to be diffused in the whole network, 411 coming from any of the nodes in the Relay Set of node N is assumed to 412 be retransmitted by node N, if N has not received it yet. This set 413 can change over time (e.g., when a node selects another MPR Set) and 414 is indicated by the selector nodes in their HELLO messages. 416 Using the MPR flooding mechanism, link-state information can be 417 injected into the network. For this purpose, a node maintains an 418 Advertised Neighbor Set which MUST contain all the nodes in the MPR 419 selector set and MAY contain additional nodes. If the Advertised 420 Neighbor Set of a node is non-empty, TC messages, containing the 421 links between the node and the nodes in the Advertised Neighbor Set, 422 are not generated, unless needed for gateway reporting or multiple 423 interface address association (if the latter case only, with minimal 424 scope). 426 OLSRv2 is designed to work in a completely distributed manner and 427 does not depend on any central entity. The protocol does not require 428 reliable transmission of control messages: each node sends control 429 messages periodically, and can therefore sustain a reasonable loss of 430 some such messages. Such losses occur frequently in radio networks 431 due to collisions or other transmission problems. 433 Also, OLSRv2 does not require sequenced delivery of messages. Each 434 control message contains a sequence number which is incremented for 435 each message. Thus the recipient of a control message can, if 436 required, easily identify which information is more recent - even if 437 messages have been re-ordered while in transmission. Furthermore, 438 OLSRv2 provides support for protocol extensions such as sleep mode 439 operation, multicast-routing etc. Such extensions may be introduced 440 as additions to the protocol without breaking backwards compatibility 441 with earlier versions. 443 OLSRv2 does not require any changes to the format of IP packets. 444 Thus any existing IP stack can be used as is: OLSRv2 only interacts 445 with routing table management. OLSR sends its own control messages 446 using UDP. 448 2.1 Protocol Extensibility 450 This specification defines and uses two OLSRv2 message types, HELLO 451 and TC. As for OLSRv1 [1] extensions to OLSRv2 may define new 452 message types to carry additional information. This may be 453 considered as "external" extensibility. New message types are 454 divided into two ranges, those which may be added by standards 455 actions (with types up to 127) and those made available for private/ 456 local use (with types 128 to 255). 458 All new messages must be syntactically OLSRv2 messages, as defined in 460 [4]. (Some additional constraints to that specification are added 461 for OLSRv2 packets and messages, requiring full packet and message 462 headers.) Note that if it is required to include one or more blocks 463 of unstructured data in such a message (possibly as its only content) 464 this may be achieved by including each block as a single message TLV 465 block, with an appropriately defined message TLV. (Like message 466 types, TLV types are divided into those up to 127 which may be added 467 by standards action, and those from 128 to 255 available for private/ 468 local use.) 470 A network may contain nodes both aware of, and unaware of, any new 471 message types. The originator of a message can control whether a 472 message flooded through the network is forwarded by nodes which are 473 unaware of the message type, thus reaching all nodes in the network, 474 or is only flooded by nodes which recognise the message type. 476 OLSRv2 also supports an alternative, and more powerful, extension 477 mechanism which was not supported by OLSRv1, that of adding new 478 information to an already defined message type, whilst still leaving 479 the predefined information unchanged and usable, including by a node 480 which does not recognise the new information. This may be considered 481 to be "internal" extensibility of a message. 483 The mechanism for this extensibility is the use of TLV (type-length- 484 value) structures in the message format defined in [4] to carry 485 information associated with either the message as a whole, or with 486 one or more addresses carried in the message. The messages defined 487 in this specification carry two types of addresses, those of the 488 originating node's own interfaces participating in OLSRv2, and those 489 of neighbouring nodes or networks to which it has a route. (New 490 message types may define other relationships to addresses which they 491 carry.) All information associated with these addresses, or the 492 message as a whole, in messages defined in this specification is in 493 TLV format; additional TLVs may be defined and added to these 494 messages. 496 Those nodes which do not recognise newly defined TLV types ignore the 497 added TLVs. (This is facilitated by that the TLVs defined in this 498 specification, or in [4], have the lowest type numbers and that TLVs 499 must be included in type order, as specified in [4].) It is 500 important that newly defined TLV types permit this behaviour. 502 3. Processing and Forwarding Repositories 504 The following data-structures are employed in order to ensure that a 505 message is processed at most once and is forwarded at most once per 506 interface of a node, and that fragmented content is treated 507 correctly. 509 3.1 Received Message Set 511 Each node maintains, for each OLSRv2 interface it possesses, a set of 512 signatures of messages, which have been received over that interface, 513 in the form of "Received Tuples": 515 (RX_type, RX_addr, RX_seq_number, RX_time) 517 where: 519 RX_type is the received message type, or zero if the received message 520 sequence number is not type-specific. 522 RX_addr is the originator address of the received message; 524 RX_seq_number is the message sequence number of the received message; 526 RX_time specifies the time at which this record expires and *MUST* be 527 removed. 529 In a node, this is denoted the "Received Message Set" for that 530 interface. 532 3.2 Fragment Set 534 Each node stores messages containing fragmented content until all 535 fragments are received and the message processing can be completed, 536 in the form of "Fragment Tuples": 538 (FG_message, FG_time) 540 where: 542 FG_message is the message containing fragmented content; 544 FG_time specifies the time at which this record expires and MUST be 545 removed. 547 In a node, this is denoted the "Fragment Set". 549 3.3 Processed Set 551 Each node maintains a set of signatures of messages which have been 552 processed by the node, in the form of "Processed Tuples": 554 (P_type, P_addr, P_seq_number, P_time) 556 where: 558 P_type is the processed message type, or zero if the processed 559 message sequence number is not type-specific. 561 P_addr is the originator address of the processed message; 563 P_seq_number is the message sequence number of the processed message; 565 P_time specifies the time at which this record expires and *MUST* be 566 removed. 568 In a node, this is denoted the "Processed Set". 570 3.4 Forwarded Set 572 Each node maintains a set of signatures of messages which have been 573 retransmitted/forwarded by the node, in the form of "Forwarded 574 Tuples": 576 (FW_type, FW_addr, FW_seq_number, FW_time) 578 where: 580 FW_type is the forwarded message type, or zero if the forwarded 581 message sequence number is not type-specific. 583 FW_addr is the originator address of the forwarded message; 585 FW_seq_number is the message sequence number of the forwarded 586 message; 588 FW_time specifies the time at which this record expires and *MUST* be 589 removed. 591 In a node, this is denoted the "Forwarded Set". 593 3.5 Relay Set 595 Each node maintains a set of neighbor interface addresses for which 596 it is to relay flooded messages, in the form of "Relay Tuples": 598 (RY_if_addr) 600 where: 602 RY_if_addr is the address of a neighbor interface for which the node 603 SHOULD relay flooded messages. 605 In a node, this is denoted the "Relay Set". 607 4. Packet Processing and Message Forwarding 609 Upon receiving a basic packet, a node examines each of the message 610 headers. If the message type is known to the node, the message is 611 processed locally according to the specifications for that message 612 type. The message is also independently evaluated for forwarding. 614 4.1 Actions when Receiving an OLSRv2 Packet 616 Upon receiving a packet, a node MUST perform the following task: 618 1. If the packet contains no messages (i.e. the packet length is 619 less than or equal to the size of the packet header) or if the 620 packet cannot be parsed into messages, the packet MUST be 621 silently discarded. 623 2. Otherwise, each message in the packet is treated according to 624 Section 4.2. 626 4.2 Actions when Receiving an OLSRv2 Message 628 A node MUST perform the following tasks for each received OLSRv2 629 message: 631 1. If the received OLSRv2 message header cannot be correctly parsed 632 according to the specification in [4], or if the originator 633 address of the message is an interface address of the receiving 634 node then the message MUST be silently discarded; 636 2. Otherwise: 638 1. If the message is of a known type then the message is 639 considered for processing according to Section 4.3; 641 2. If for the received message TTL > 0, and if either the 642 message is of a known type, or bit 3 of the message semantics 643 octet in the message header is clear, as indicated in [4], 644 then the message is considered for forwarding according to 645 Section 4.4. 647 4.3 Message Considered for Processing 649 If a message is considered for processing, the following tasks MUST 650 be performed: 652 1. If an entry exists in the Processed Set where: 654 * P_type == the message type, or 0 if bit 2 of the message 655 semantics octet (in the message header) is clear, AND; 657 * P_addr == the originator address of the message, AND; 659 * P_seq_number == the sequence number of the message. 661 then the message MUST NOT be processed. 663 2. Otherwise: 665 1. Create an entry in the Processed Set with: 667 + P_type = the message type, or 0 if bit 2 of the message 668 semantics octet (in the message header) is clear; 670 + P_addr = originator address of the message; 672 + P_seq_number = sequence number of the message; 674 + P_time = current time + P_HOLD_TIME. 676 2. If the message does not contain a message TLV of type 677 Fragment (or if it does and the indicated number of fragments 678 is one) then process the message fully according to its type. 680 3. Otherwise: 682 1. If the message is "wholly or partially self-contained" as 683 indicated by its Fragment TLV then process the current 684 message as far as possible according to its type; 686 2. If the Fragment Set includes any messages with the same 687 originator address and content sequence number as the 688 current message, and either the same fragment number or a 689 different number of fragments, then remove these messages 690 are from the Fragment Set; 692 3. If the Fragment Set includes messages containing all the 693 remaining fragments of the same overall message as the 694 current message (i.e. if the number of messages in the 695 Fragment Set with the same originator address and content 696 sequence number as the current message is equal to the 697 current message's number of fragments, less one) then all 698 of these messages are removed from the Fragment Set and 699 processed according to their type (taking account of any 700 previous processing if any or all were wholly or 701 partially self-contained); 703 4. Otherwise, the current message is added to the Fragment 704 Set with a FG_time of FG_HOLD_TIME (possibly replacing an 705 identical and previous received instance of the same 706 fragment of the same content). 708 4.4 Message Considered for Forwarding 710 If a message is considered for forwarding then if it is either of a 711 message type defined in this document, or of an unknown message type 712 it MUST use the following algorithm. A message type not defined in 713 this document may specify the use of this, or another algorithm. 714 (Such an other algorithm MAY use the Received Set for the receiving 715 interface, it SHOULD use the Forwarded Set similarly to the following 716 algorithm.) 718 If a message is considered for forwarding according to this 719 algorithm, the following tasks MUST be performed: 721 1. If there is no symmetric link in the Link Set between the 722 receiving interface and the sending interface (as indicated by 723 the source interface of the IP datagram containing the message) 724 then the message MUST be silently discarded. 726 2. Otherwise: 728 1. If an entry exists in the Received Set for the receiving 729 interface, where: 731 + RX_type == the message type, or 0 if bit 2 of the message 732 semantics octet (in the message header) is clear, AND; 734 + RX_addr == the originator address of the received message, 735 AND; 737 + RX_seq_number == the sequence number of the received 738 message. 740 then the message MUST be silently discarded. 742 2. Otherwise: 744 1. Create an entry in the Received Set for the receiving 745 interface with: 747 - RX_type = the message type, or 0 if bit 2 of the 748 message semantics octet (in the message header) is 749 clear; 751 - RX_addr = originator address of the message; 753 - RX_seq_number = sequence number of the message; 755 - RX_time = current time + RX_HOLD_TIME. 757 2. If an entry exists in the Forwarded Set where: 759 - FW_type == the message type, or 0 if bit 2 of the 760 message semantics octet (in the message header) is 761 clear; 763 - FW_addr == the originator address of the received 764 message, AND; 766 - FW_seq_number == the sequence number of the received 767 message. 769 then the message MUST be silently discarded. 771 3. Otherwise if an entry exists in the Relay Set, where 772 RY_if_addr == source address of the message (as indicated 773 by the source interface of the IP datagram containing the 774 message): 776 1. Create an entry in the Forwarded Set with: 778 o FW_type = the message type, or 0 if bit 2 of the 779 message semantics octet (in the message header) is 780 clear; 782 o FW_addr = originator address of the message; 784 o FW_seq_number = sequence number of the message; 786 o FW_time = current time + FW_HOLD_TIME. 788 2. The message header is modified as follows: 790 o Decrement the message TTL by 1; 792 o Increment the message hop count by 1; 794 3. Transmit the message on all OLSRv2 interfaces of the 795 node. 797 Messages are retransmitted in the format specified by [4] with the 798 All-OLSRv2-Multicast address (see Section 17.1) as destination IP 799 address. 801 5. Information Repositories 803 The purpose of OLSRv2 is to determine the Routing Set, which may be 804 used to update IP's Routing Table, providing "next hop" routing 805 information for IP datagrams. In order to accomplish this, OLSRv2 806 maintains a number of protocol sets, the information repository of 807 the protocol. These sets are updated, directly or indirectly, by the 808 exchange of messages between nodes in the network. In turn the 809 contents of these messages are largely determined by the contents of 810 a part of the information repositories, the Neighbourhood Information 811 Base, which contains information about the 1- and 2- hop 812 neighbourhoods of the node. The remaining part of the information 813 repository, the Topology Information Base (including the Routing Set) 814 contains information about the network which is not constrained to 815 the node's neighbourhood. The Topology Information Base is updated 816 by the OLSRv2 messages defined in this document, it is not used to 817 define their contents. The process of information exchange which 818 leads to the population of the Neighbourhood Information Base and the 819 Topology Information Base is started using only the node's own OLSRv2 820 interface addresses and host and network associated addresses. These 821 are not affected by the exchange of the OLSRv2 messages defined in 822 this document. 824 5.1 Neighborhood Information Base 826 The neighborhood information base stores information about links 827 between local interfaces and interfaces on adjacent nodes. 829 5.1.1 Link Set 831 A node records a set of "Link Tuples": 833 (L_local_iface_addr, L_neighbor_iface_addr, 834 L_SYM_time, L_ASYM_time, L_willingness, L_time). 836 where: 838 L_local_iface_addr is the interface address of the local node; 840 L_neighbor_iface_addr is the interface address of the neighbor node; 842 L_SYM_time is the time until which the link is considered symmetric; 844 L_ASYM_time is the time until which the neighbor interface is 845 considered heard; 847 L_willingness is the nodes willingness to be selected as MPR; 849 L_time specifies when this record expires and *MUST* be removed. 851 +-------------+-------------+--------------+ 852 | L_SYM_time | L_ASYM_time | L_STATUS | 853 +-------------+-------------+--------------+ 854 | Expired | Expired | LOST | 855 | | | | 856 | Not Expired | Expired | SYMMETRIC | 857 | | | | 858 | Not Expired | Not Expired | SYMMETRIC | 859 | | | | 860 | Expired | Not Expired | ASYMMETRIC | 861 +-------------+-------------+--------------+ 863 Table 1 865 The status of the link, denoted L_STATUS, can be derived based on the 866 fields L_SYM_time and L_ASYM_time as defined in Table 1. 868 In a node, the set of Link Tuples is denoted the "Link Set". 870 5.1.2 2-Hop Neighbor Set 872 A node records a set of "2-Hop Neighbor Tuples" 874 (N2_local_iface_addr, N2_neighbor_iface_addr, N2_2hop_iface_addr, N2_time) 876 describing symmetric links between its neighbors and the symmetric 877 2-hop neighborhood. 879 N2_local_iface_addr is the address of the local interface over which 880 the information was received; 882 N2_neighbor_iface_addr is the interface address of a neighbor; 884 N2_2hop_iface_addr is the interface address of a 2-hop neighbor with 885 a symmetric link to the node with interface address 886 N_neighbor_iface_addr; 888 N2_time specifies the time at which the tuple expires and *MUST* be 889 removed. 891 In a node, the set of 2-Hop Neighbor Tuples is denoted the "2-Hop 892 Neighbor Set". 894 5.1.3 Neighborhood Address Association Set 896 A node maintains, for each 1-hop and 2-hop neighbor with multiple 897 addresses participating in the OLSRv2 network, a "Neighborhood 898 Address Association Tuple", representing that "these addresses belong 899 to the same node". 901 (NA_neighbor_addr_list, NA_time) 903 NA_neighbor_iface_addr_list is the list of interface addresses of the 904 1-hop or 2-hop neighbor node; 906 NA_time specifies the time at which the tuple expires and *MUST* be 907 removed. 909 In a node, the set of Neighborhood Address Association Tuples is 910 denoted the "Neighborhood Address Association Set". 912 5.1.4 MPR Set 914 A node maintains a set of neighbors which are selected as MPRs. 915 Their interface addresses are listed in the MPR Set. 917 5.1.5 MPR Selector Set 919 A node maintains, for each interface of an 1-hop neighbor which has 920 selected it as MPR, an "MPR Selector Tuple", representing the an 921 interface of the neighbor node which have selected it as an MPR. 923 (MS_neighbor_if_addr, MS_time) 925 MS_neighbor_if_addr specifies the interface address of a 1-hop 926 neighbor, which has selected the node as MPR; 928 MS_time specifies the time at which the tuple expires and *MUST* be 929 removed. 931 Notice that if a MPR selector node has multiple interface addresses, 932 the MPR Selector Set will contain one tuple for each interface 933 address of the MPR selector. 935 5.1.6 Advertised Neighbor Set 937 A node maintains a set of neighbor interface addresses, which are to 938 be advertised through TC messages: 940 (A_neighbor_iface_addr) 942 For this set, an Advertised Neighbor Set Sequence Number (ASSN) is 943 maintained. Each time the Advertised Neighbor Set is updated, the 944 ASSN MUST be incremented. 946 5.2 Topology Information Base 948 The Topology Information Base stores topological information 949 describing the network beyond the nodes neighborhood (i.e. beyond the 950 Neighborhood Information Base of the node). 952 5.2.1 Topology Set 954 Each node in the network maintains topology information about the 955 network. 957 For each destination in the network, at least one "Topology Tuple" 959 (T_dest_iface_addr, T_last_iface_addr, T_seq, T_time) 961 is recorded. 963 T_dest_iface_addr is the interface address of a node, which may be 964 reached in one hop from the node with the interface address 965 T_last_iface_addr; 967 T_last_iface_addr is, conversely, the last hop towards 968 T_dest_iface_addr. Typically, T_last_iface_addr is a MPR of 969 T_dest_iface_addr; 971 T_seq is a sequence number, and 973 T_time specifies the time at which this tuple expires and *MUST* be 974 removed. 976 In a node, the set of Topology Tuples are denoted the "Topology Set". 978 5.2.2 Attached Network Set 980 Each node in the network maintains information about attached 981 networks. 983 For each attached network, at least one "Attached Network Tuple" 985 (AN_net_addr, AN_prefix_lenght, AN_gw_addr, AN_seq_no, AN_time) 987 is recorded. 989 AN_net_addr is the network address (prefix) of a network, which may 990 be reached via the node with the OLSRv2 interface address 991 AN_gw_addr; 993 AN_prefix_length is the length of the prefix of the network address 994 AN_net_addr; 996 AN_gw_addr is the address of an OLSRv2 interface of a node which can 997 act as gateway to the network identified by the AD_net_addr/ 998 AD_prefix_length; 1000 AN_seq_no is a sequence number, and; 1002 AN_time specifies the time at which this tuple expires and *MUST* be 1003 removed. 1005 In a node, the set of Topology Tuples are denoted the "Topology Set". 1007 5.2.3 Routing Set 1009 A node records a set of "Routing Tuples": 1011 (R_dest_iface_addr, R_next_iface_addr, R_dist, R_iface_addr) 1013 describing the next hop and distance of the path to each destination 1014 in the network for which a route is known. 1016 R_dest_iface_addr is the interface address of the destination node; 1018 R_next_iface_addr is the interface address of the "next hop" on the 1019 path towards R_dest_iface_addr; 1021 R_dist is the number of hops on the path to R_dest_iface_addr; 1023 R_iface_addr is the address of the local interface over which a 1024 packet MUST be sent to reach R_next_iface_addr. 1026 In a node, the set of Routing Tuples is denoted the "Routing Set". 1028 6. OLSRv2 Control Message Structures 1030 Nodes using OLSRv2 exchange information through messages. One or 1031 more messages sent by a node at the same time are combined into a 1032 packet. These messages may have originated at the sending node, or 1033 have originated at another node and forwarded by the sending node. 1034 Messages with different originators may be combined in the same 1035 packet. 1037 The packet and message format used by OLSRv2 is defined in [4]. 1038 However this specification contains some options which are not used 1039 by OLSRv2. In particular (using the syntactical elements defined in 1040 the packet format specification): 1042 o All OLSRv2 packets include a . 1044 o All OLSRv2 messages, not limited to those defined in this 1045 document, include a full and hence have bits 0 and 1 1046 of cleared. 1048 o All OLSRv2 message defined in this document have all remaining 1049 bits of cleared. 1051 Other options defined in [4] may be freely used, in particular any 1052 values of consistent with its specification. An 1053 implementation of OLSRv2 MAY take full advantage of the features of 1054 the message specification in [4] allowing decisions relating to 1055 whether a message should be forwarded and/or processed to be taken 1056 parsing only the message header (plus, if a message is to be 1057 processed but may be fragmented, only the first octets of the message 1058 body). 1060 OLSRv2 messages are sent using UDP, see Appendix C. 1062 The remainder of this section defines, within the framework of [4], 1063 message types and TLVs specific to OLSRv2. 1065 6.1 General OLSRv2 Message TLVs 1067 This document specifies two message TLVs, which can be applied to any 1068 OLSRv2 control message, VALIDITY_TIME and INTERVAL_TIME, detailed in 1069 this section. 1071 6.1.1 VALIDITY_TIME TLV 1073 All OLSRv2 messages specified in this specification MUST include a 1074 VALIDITY_TIME TLV, specifying for how long a node may, upon receiving 1075 a message, consider the message content to be valid. The validity 1076 time of a message MAY be specified to depend on the distance from the 1077 originator (i.e. the field in the message header as 1078 defined in [4]). Thus, the VALIDITY_TIME TLV contains a sequence of 1079 pairs (time, hop-limit) in increasing hop-limit order, followed by a 1080 default value. 1082 Thus, an instance of a VALIDITY_TIME TLV could have the following 1083 value: 1085 ... .... 1087 Which would mean that the message, carrying this VALIDITY_TIME TLV, 1088 would have the following validity times: 1090 o in the interval from 0 (exclusive) to (inclusive) 1091 hops away from the originator; 1093 o in the interval from (exclusive) to 1094 (inclusive) hops away from the originator; and 1096 o in the interval from (exclusive) to 255> 1097 (inclusive) hops away from the originator. 1099 The VALIDITY_TIME message TLV specification is given in Table 2. 1101 VALIDITY_TIME message TLV specification overview 1103 +----------------+--------+-------------------+---------------------+ 1104 | Name | Type | Length | Value | 1105 +----------------+--------+-------------------+---------------------+ 1106 | VALIDITY_TIME | TBD | (2*n+1) * 8 bits | {