idnits 2.17.1 draft-ietf-manet-olsrv2-02.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 21. -- Found old boilerplate from RFC 3978, Section 5.5 on line 2613. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 2590. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 2597. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 2603. ** 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. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == 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 (June 26, 2006) is 6513 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) ** Downref: Normative reference to an Experimental RFC: RFC 3626 (ref. '1') == Outdated reference: A later version (-17) exists of draft-ietf-manet-packetbb-01 == Outdated reference: A later version (-15) exists of draft-ietf-manet-nhdp-00 -- Obsolete informational reference (is this intentional?): RFC 1991 (ref. '5') (Obsoleted by RFC 4880) Summary: 5 errors (**), 0 flaws (~~), 5 warnings (==), 8 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: December 28, 2006 C. Dearlove 5 BAE Systems Advanced Technology 6 Centre 7 P. Jacquet 8 Project Hipercom, INRIA 9 The OLSRv2 Design Team 10 MANET Working Group 11 June 26, 2006 13 The Optimized Link-State Routing Protocol version 2 14 draft-ietf-manet-olsrv2-02 16 Status of this Memo 18 By submitting this Internet-Draft, each author represents that any 19 applicable patent or other IPR claims of which he or she is aware 20 have been or will be disclosed, and any of which he or she becomes 21 aware will be disclosed, in accordance with Section 6 of BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF), its areas, and its working groups. Note that 25 other groups may also distribute working documents as Internet- 26 Drafts. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 The list of current Internet-Drafts can be accessed at 34 http://www.ietf.org/ietf/1id-abstracts.txt. 36 The list of Internet-Draft Shadow Directories can be accessed at 37 http://www.ietf.org/shadow.html. 39 This Internet-Draft will expire on December 28, 2006. 41 Copyright Notice 43 Copyright (C) The Internet Society (2006). 45 Abstract 47 This document describes version 2 of the Optimized Link State Routing 48 (OLSRv2) protocol for mobile ad hoc networks. The protocol embodies 49 an optimization of the classical link state algorithm tailored to the 50 requirements of a mobile wireless LAN. 52 The key optimization of OLSRv2 is that of multipoint relays, 53 providing an efficient mechanism for network-wide broadcast of link- 54 state information (i.e. reducing the cost of performing a network- 55 wide link-state broadcast). A secondary optimization is that OLSRv2 56 employs partial link-state information: each node maintains 57 information about all destinations, but only a subset of links. This 58 allows that only select nodes diffuse link-state advertisements (i.e. 59 reduces the number of network-wide link-state broadcasts) and that 60 these advertisements contain only a subset of links (i.e. reduces the 61 size of each network-wide link-state broadcast). The partial link- 62 state information thus obtained still allows each OLSRv2 node to at 63 all times maintain optimal (in terms of number of hops) routes to all 64 destinations in the network. 66 OLSRv2 imposes minimum requirements to the network by not requiring 67 sequenced or reliable transmission of control traffic. Furthermore, 68 the only interaction between OLSRv2 and the IP stack is routing table 69 management. 71 OLSRv2 is particularly suitable for large and dense networks as the 72 technique of MPRs works well in this context. 74 Table of Contents 76 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 77 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 6 78 1.2. Applicability Statement . . . . . . . . . . . . . . . . . 6 79 2. Protocol Overview and Functioning . . . . . . . . . . . . . . 8 80 2.1. Protocol Extensibility . . . . . . . . . . . . . . . . . . 10 81 3. Processing and Forwarding Repositories . . . . . . . . . . . . 11 82 3.1. Received Set . . . . . . . . . . . . . . . . . . . . . . . 11 83 3.2. Fragment Set . . . . . . . . . . . . . . . . . . . . . . . 11 84 3.3. Processed Set . . . . . . . . . . . . . . . . . . . . . . 12 85 3.4. Forwarded Set . . . . . . . . . . . . . . . . . . . . . . 12 86 3.5. Relay Set . . . . . . . . . . . . . . . . . . . . . . . . 12 87 4. Packet Processing and Message Forwarding . . . . . . . . . . . 14 88 4.1. Actions when Receiving an OLSRv2 Packet . . . . . . . . . 14 89 4.2. Actions when Receiving an OLSRv2 Message . . . . . . . . . 14 90 4.3. Message Considered for Processing . . . . . . . . . . . . 15 91 4.4. Message Considered for Forwarding . . . . . . . . . . . . 17 92 5. Information Repositories . . . . . . . . . . . . . . . . . . . 20 93 5.1. Neighborhood Information Base . . . . . . . . . . . . . . 20 94 5.1.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . 20 95 5.1.2. MPR Set . . . . . . . . . . . . . . . . . . . . . . . 21 96 5.1.3. MPR Selector Set . . . . . . . . . . . . . . . . . . . 21 97 5.2. Topology Information Base . . . . . . . . . . . . . . . . 21 98 5.2.1. Advertised Neighbor Set . . . . . . . . . . . . . . . 21 99 5.2.2. ANSN History Set . . . . . . . . . . . . . . . . . . . 22 100 5.2.3. Topology Set . . . . . . . . . . . . . . . . . . . . . 22 101 5.2.4. Attached Network Set . . . . . . . . . . . . . . . . . 23 102 5.2.5. Routing Set . . . . . . . . . . . . . . . . . . . . . 23 103 6. OLSRv2 Control Message Structures . . . . . . . . . . . . . . 24 104 6.1. General OLSRv2 Message TLVs . . . . . . . . . . . . . . . 24 105 6.1.1. VALIDITY_TIME TLV . . . . . . . . . . . . . . . . . . 24 106 6.2. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 25 107 6.2.1. HELLO Message OLSRv2 Message TLVs . . . . . . . . . . 26 108 6.2.2. HELLO Message OLSRv2 Address Block TLVs . . . . . . . 26 109 6.3. TC Messages . . . . . . . . . . . . . . . . . . . . . . . 27 110 6.4. TC Message: OLSRv2 Address Block TLVs . . . . . . . . . . 27 111 7. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 29 112 7.1. HELLO Message: Transmission . . . . . . . . . . . . . . . 29 113 8. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 30 114 8.1. Populating the MPR Selector Set . . . . . . . . . . . . . 30 115 8.2. Symmetric Neighborhood and 2-Hop Neighborhood Changes . . 31 116 9. TC Message Generation . . . . . . . . . . . . . . . . . . . . 32 117 9.1. TC Message: Transmission . . . . . . . . . . . . . . . . . 33 118 10. TC Message Processing . . . . . . . . . . . . . . . . . . . . 34 119 10.1. Single TC Message Processing . . . . . . . . . . . . . . . 34 120 10.1.1. Populating the ANSN History Set . . . . . . . . . . . 35 121 10.1.2. Populating the Topology Set . . . . . . . . . . . . . 35 122 10.1.3. Populating the Attached Network Set . . . . . . . . . 36 123 10.2. Completed TC Message Processing . . . . . . . . . . . . . 37 124 10.2.1. Purging the Topology Set . . . . . . . . . . . . . . . 37 125 10.2.2. Purging the Attached Network Set . . . . . . . . . . . 37 126 11. Populating the MPR Set . . . . . . . . . . . . . . . . . . . . 38 127 12. Populating Derived Sets . . . . . . . . . . . . . . . . . . . 39 128 12.1. Populating the Relay Set . . . . . . . . . . . . . . . . . 39 129 12.2. Populating the Advertised Neighbor Set . . . . . . . . . . 39 130 13. Routing Table Calculation . . . . . . . . . . . . . . . . . . 40 131 14. Proposed Values for Constants . . . . . . . . . . . . . . . . 44 132 14.1. Neighborhood Discovery Constants . . . . . . . . . . . . . 44 133 14.2. Message Intervals . . . . . . . . . . . . . . . . . . . . 44 134 14.3. Holding Times . . . . . . . . . . . . . . . . . . . . . . 44 135 14.4. Willingness . . . . . . . . . . . . . . . . . . . . . . . 44 136 15. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . 45 137 16. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 46 138 16.1. Multicast Addresses . . . . . . . . . . . . . . . . . . . 46 139 16.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 46 140 16.3. TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 46 141 17. References . . . . . . . . . . . . . . . . . . . . . . . . . . 48 142 17.1. Normative References . . . . . . . . . . . . . . . . . . . 48 143 17.2. Informative References . . . . . . . . . . . . . . . . . . 48 144 Appendix A. Example Heuristic for Calculating MPRs . . . . . . . 49 145 Appendix B. Heuristics for Generating Control Traffic . . . . . 52 146 Appendix C. Protocol and Port Number . . . . . . . . . . . . . . 53 147 Appendix D. Packet and Message Layout . . . . . . . . . . . . . 54 148 Appendix D.1. OLSRv2 Packet Format . . . . . . . . . . . . . . . . 54 149 Appendix E. Node Configuration . . . . . . . . . . . . . . . . . 59 150 Appendix F. Jitter . . . . . . . . . . . . . . . . . . . . . . . 60 151 Appendix G. Security Considerations . . . . . . . . . . . . . . 63 152 Appendix G.1. Confidentiality . . . . . . . . . . . . . . . . . . 63 153 Appendix G.2. Integrity . . . . . . . . . . . . . . . . . . . . . 63 154 Appendix G.3. Interaction with External Routing Domains . . . . . 64 155 Appendix G.4. Node Identity . . . . . . . . . . . . . . . . . . . 65 156 Appendix H. Flow and Congestion Control . . . . . . . . . . . . 66 157 Appendix I. Contributors . . . . . . . . . . . . . . . . . . . . 67 158 Appendix J. Acknowledgements . . . . . . . . . . . . . . . . . . 68 159 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 69 160 Intellectual Property and Copyright Statements . . . . . . . . . . 70 162 1. Introduction 164 The Optimized Link State Routing protocol version 2 (OLSRv2) is an 165 update to OLSRv1 as published in RFC3626 [1]. Compared to RFC3626, 166 OLSRv2 retains the same basic mechanisms and algorithms, while 167 providing an even more flexible signaling framework and some 168 simplification of the messages being exchanged. Also, OLSRv2 takes 169 care to accommodate both IPv4 and IPv6 addresses in a compact 170 fashion. 172 OLSRv2 is developed for mobile ad hoc networks. It operates as a 173 table driven, proactive protocol, i.e. it exchanges topology 174 information with other nodes of the network regularly. Each node 175 selects a set of its neighbor nodes as "MultiPoint Relays" (MPRs). 176 Only nodes that are selected as such MPRs are then responsible for 177 forwarding control traffic intended for diffusion into the entire 178 network. MPRs provide an efficient mechanism for flooding control 179 traffic by reducing the number of transmissions required. 181 Nodes selected as MPRs also have a special responsibility when 182 declaring link state information in the network. Indeed, the only 183 requirement for OLSRv2 to provide shortest path routes to all 184 destinations is that MPR nodes declare link-state information for 185 their MPR selectors. Additional available link-state information may 186 be utilized, e.g. for redundancy. 188 Nodes which have been selected as multipoint relays by some neighbor 189 node(s) announce this information periodically in their control 190 messages. Thereby a node announces to the network that it has 191 reachability to the nodes which have selected it as an MPR. Thus, as 192 well as being used to facilitate efficient flooding, MPRs are also 193 used for route calculation from any given node to any destination in 194 the network. 196 A node selects MPRs from among its one hop neighbors with 197 "symmetric", i.e. bi-directional, linkages. Therefore, selecting 198 routes through MPRs automatically avoids the problems associated with 199 data packet transfer over uni-directional links (such as the problem 200 of not getting link-layer acknowledgments for data packets at each 201 hop, for link-layers employing this technique for unicast traffic). 203 OLSRv2 is developed to work independently from other protocols. 204 Likewise, OLSRv2 makes no assumptions about the underlying link- 205 layer. However, OLSRv2 may use link-layer information and 206 notifications when available and applicable. 208 OLSRv2, as OLSRv1, inherits the concept of forwarding and relaying 209 from HIPERLAN (a MAC layer protocol) which is standardized by ETSI 211 [6]. 213 1.1. Terminology 215 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 216 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 217 document are to be interpreted as described in RFC2119 [2]. 219 MANET specific terminology is to be interpreted as described in [3] 220 and [4]. 222 Additionally, this document uses the following terminology: 224 node - A MANET router which implements the Optimized Link State 225 Routing protocol version 2 as specified in this document. 227 OLSRv2 interface - A MANET interface, running OLSRv2. 229 symmetric strict 2-hop neighbor - A symmetric 2-hop neighbor which is 230 not a symmetric 1-hop neighbor and is not a 2-hop neighbor only 231 through a symmetric 1-hop neighbor with willingness WILL_NEVER. 232 (If node Z is a symmetric 2-hop neighbor of node X then there is a 233 node Y such that node Z is a symmetric 1-hop neighbor of node Y 234 and node Y is a symmetric 1-hop neighbor of node X. If node Z is a 235 symmetric strict 2-hop neighbor of node X then there is such a 236 node Y with willingness which is not WILL_NEVER.) 238 symmetric strict 2-hop neighborhood - The set of the symmetric strict 239 2-hop neighbors of node X. 241 multipoint relay (MPR) - A node which is selected by its symmetric 242 1-hop neighbor, node X, to "re-transmit" all the broadcast 243 messages that it receives from node X, provided that the message 244 is not a duplicate, and that the hop limit field of the message is 245 greater than one. 247 MPR selector - A node which has selected its symmetric 1-hop 248 neighbor, node X, as one of its MPRs is an MPR selector of node X. 250 1.2. Applicability Statement 252 OLSRv2 is a proactive routing protocol for mobile ad hoc networks 253 (MANETs) [7], [8]. It is well suited to large and dense networks of 254 mobile nodes, as the optimization achieved using the MPRs works well 255 in this context. The larger and more dense a network, the more 256 optimization can be achieved as compared to the classic link state 257 algorithm. OLSRv2 uses hop-by-hop routing, i.e. each node uses its 258 local information to route packets. 260 As OLSRv2 continuously maintains routes to all destinations in the 261 network, the protocol is beneficial for traffic patterns where the 262 traffic is random and sporadic between a large subset of nodes, and 263 where the [source, destination] pairs are changing over time: no 264 additional control traffic need be generated in this situation since 265 routes are maintained for all known destinations at all times. Also, 266 since routes are maintained continuously, traffic is subject to no 267 delays due to buffering/route-discovery. This continued route 268 maintenance may be done using periodic message exchange, as detailed 269 in this specification, or triggered by external events if available. 271 OLSRv2 supports nodes which have multiple interfaces which 272 participate in the MANET. OLSRv2, additionally, supports nodes which 273 have non-MANET interfaces which can serve as (if configured to do so) 274 gateways towards other networks. 276 The message exchange format, contained in previous versions of this 277 specification, has been factored out to an independent specification 278 [3], which is used for carrying OLSRv2 control signals. OLSRv2 is 279 thereby able to allow for extensions via "external" and "internal" 280 extensibility. External extensibility implies that a protocol 281 extension may specify and exchange new message types, formatted 282 according to [3], which can be forwarded and delivered correctly. 283 Internal extensibility implies that a protocol extension may define 284 additional attributes to be carried embedded in the standard OLSRv2 285 control messages detailed in this specification, using the TLV 286 mechanism specified in [3], while OLSRv2 control messages with 287 additional attributes can still be correctly understood by all OLSRv2 288 nodes. 290 The OLSRv2 neighborhood discovery protocol using HELLO messages has 291 likewise been factored out to an independent specification [4]. This 292 neighborhood discovery protocol serves to ensure that each OLSRv2 293 node has available continuously updated information repositories 294 describing the node's 1-hop and 2-hop neighbors. [4] uses the message 295 format specified in [3], and hence is extensible as described above. 297 2. Protocol Overview and Functioning 299 OLSRv2 is a proactive routing protocol for mobile ad hoc networks. 300 The protocol inherits the stability of a link state algorithm and has 301 the advantage of having routes immediately available when needed due 302 to its proactive nature. OLSRv2 is an optimization over the 303 classical link state protocol, tailored for mobile ad hoc networks. 304 The main tailoring and optimizations of OLSRv2 are: 306 o periodic, unacknowledged transmission of all control messages; 308 o optimized flooding for global link-state information diffusion; 310 o partial topology maintenance - each node knows only a subset of 311 the links in the network, sufficient for a minimum hop route to 312 all destinations. 314 Using the message exchange format [3] and the neighborhood discovery 315 protocol [4], OLSRv2 also contains the following main components: 317 o a TLV, to be included within the HELLO messages of [4], allowing a 318 node to signal MPR selection; 320 o an optimized flooding mechanism for global information exchange, 321 denoted "MPR flooding"; 323 o a specification of global signaling, denoted TC (Topology Control) 324 messages. TC messages in OLSRv2 serve to: 326 * inject link-state information into the entire network; 328 * inject addresses of hosts and networks for which they may serve 329 as a gateway into the entire network. 331 TC messages are emitted periodically, thereby allowing nodes to 332 continuously track global changes in the network. 334 The use of [4] allows a node to continuously track changes to its 335 local topology up to two hops away. This allows a node to make 336 provisions for ensuring optimized flooding, denoted "MPR flooding", 337 as well as injection of link-state information into the network. 338 This is done through the notion of MultiPoint Relays (MPRs). 340 The idea of MPRs is to minimize the overhead of flooding messages in 341 the network by reducing redundant retransmissions of messages in the 342 same region. Each node in the network selects an MPR Set, a set of 343 nodes in its symmetric 1-hop neighborhood which may retransmit its 344 messages. The 1-hop neighbors of a node which are not in its MPR set 345 receive and process broadcast messages, but do not retransmit 346 broadcast messages received from that node. The MPR Set of a node X 347 may be any subset of its symmetric 1-hop neighborhood such that every 348 node in its symmetric strict 2-hop neighborhood has a symmetric link 349 to a node in the MPR Set of node X. The MPR Set of a node may thus be 350 said to "cover" the node's symmetric strict 2-hop neighborhood. The 351 smaller a MPR Set, the fewer times messages are forwarded and the 352 less resulting control traffic overhead. [8] gives an analysis and 353 example of MPR selection algorithms. Note that as long as the 354 condition above is satisfied, any algorithm selecting MPR Sets is 355 acceptable in terms of implementation interoperability. 357 Each node maintains information about the set of symmetric 1-hop 358 neighbors that have selected it as MPR. This set is called the MPR 359 Selector Set of the node. A node obtains this information from an 360 MPR TLV which is inserted into the HELLO message exchange of [4]. 362 Each node also maintains a Relay Set, which is the set of nodes for 363 which a node is to relay broadcast traffic. The Relay Set is derived 364 from the MPR Selector Set in that the Relay Set MUST contain all the 365 nodes in the MPR Selector set and MAY contain additional nodes. 367 Using the MPR flooding mechanism, link-state information can be 368 injected into the network. For this purpose, a node maintains an 369 Advertised Neighbor Set which MUST contain all the nodes in the MPR 370 selector set and MAY contain additional nodes. If the Advertised 371 Neighbor Set of a node is non-empty, it is reported in TC messages 372 generated by that node. If the Advertised Neighbor Set is empty, TC 373 messages are not generated by that node, unless needed for gateway 374 reporting, or for a short period to accelerate the removal of 375 unwanted links. 377 OLSRv2 is designed to work in a completely distributed manner and 378 does not depend on any central entity. The protocol does not require 379 reliable transmission of control messages: each node sends control 380 messages periodically, and can therefore sustain a reasonable loss of 381 some such messages. Such losses may occur frequently in radio 382 networks due to collisions or other transmission problems. 384 OLSRv2 does not require sequenced delivery of messages. Each control 385 message contains a sequence number which is incremented for each 386 message. Thus the recipient of a control message can, if required, 387 easily identify which information is more recent - even if messages 388 have been re-ordered while in transmission. 390 OLSRv2 does not require any changes to the format of IP packets, any 391 existing IP stack can be used as is: OLSRv2 only interacts with 392 routing table management. OLSR sends its control messages using UDP. 394 2.1. Protocol Extensibility 396 OLSRv2 uses the neighborhood discovery mechanism of [4], and 397 specifies additionally one message type, TC, and a number of TLVs. 398 All messages exchanged by [4] and by OLSRv2 use and comply with the 399 extensible message exchange format of [3], thus OLSR provides both 400 "external" extensibility (addition of new message types as in OLSRv1 401 [1]) and "internal" extensibility (addition of information to 402 existing messages through TLVs) as described in [3]. 404 Those nodes which do not recognize a new message type ("external 405 extensibility") will ignore this message type for processing, but 406 will correctly forward the message, if specified in the message 407 header. Those nodes which do not recognize a newly defined TLV type 408 ignore the added TLV, but process (if the message type is recognized) 409 the message correctly, as well as forwards the message, if specified 410 in the message header. 412 3. Processing and Forwarding Repositories 414 The following data structures are employed in order to ensure that a 415 message is processed at most once and is forwarded at most once per 416 interface of a node, and that fragmented content is treated 417 correctly. 419 3.1. Received Set 421 Each node maintains, for each OLSRv2 interface, a set of signatures 422 of messages, which have been received over that interface, in the 423 form of "Received Tuples": 425 (RX_type, RX_orig_addr, RX_seq_number, RX_time) 427 where: 429 RX_type is the received message type, or zero if the received message 430 sequence number is not type-specific; 432 RX_orig_addr is the originator address of the received message; 434 RX_seq_number is the message sequence number of the received message; 436 RX_time specifies the time at which this Received Tuple expires and 437 *MUST* be removed. 439 In a node, this is denoted the "Received Set" for that interface. 441 3.2. Fragment Set 443 Each node stores messages containing fragmented content until all 444 fragments are received and the message processing can be completed, 445 in the form of "Fragment Tuples": 447 (FG_message, FG_time) 449 where: 451 FG_message is the message containing fragmented content; 453 FG_time specifies the time at which this Fragment Tuple expires and 454 MUST be removed. 456 In a node, this is denoted the "Fragment Set". 458 3.3. Processed Set 460 Each node maintains a set of signatures of messages which have been 461 processed by the node, in the form of "Processed Tuples": 463 (P_type, P_orig_addr, P_seq_number, P_time) 465 where: 467 P_type is the processed message type, or zero if the processed 468 message sequence number is not type-specific; 470 P_orig_addr is the originator address of the processed message; 472 P_seq_number is the message sequence number of the processed message; 474 P_time specifies the time at which this Processed Tuple expires and 475 *MUST* be removed. 477 In a node, this is denoted the "Processed Set". 479 3.4. Forwarded Set 481 Each node maintains a set of signatures of messages which have been 482 retransmitted/forwarded by the node, in the form of "Forwarded 483 Tuples": 485 (FW_type, FW_orig_addr, FW_seq_number, FW_time) 487 where: 489 FW_type is the forwarded message type, or zero if the forwarded 490 message sequence number is not type-specific; 492 FW_orig_addr is the originator address of the forwarded message; 494 FW_seq_number is the message sequence number of the forwarded 495 message; 497 FW_time specifies the time at which this Forward Tuple expires and 498 *MUST* be removed. 500 In a node, this is denoted the "Forwarded Set". 502 3.5. Relay Set 504 Each node maintains a set of neighbor interface addresses for which 505 it is to relay flooded messages, in the form of "Relay Tuples": 507 (RY_iface_addr) 509 where: 511 RY_iface_addr is the address of a neighbor interface for which the 512 node SHOULD relay flooded messages. This MUST include a prefix 513 length. 515 In a node, this is denoted the "Relay Set". 517 4. Packet Processing and Message Forwarding 519 On receiving a basic packet, as defined in [3], a node examines each 520 of the message headers. If the message type is known to the node, 521 the message is processed locally according to the specifications for 522 that message type. The message is also independently evaluated for 523 forwarding. 525 4.1. Actions when Receiving an OLSRv2 Packet 527 On receiving a packet, a node MUST perform the following tasks: 529 1. The packet may be fully parsed on reception, or the packet and 530 its messages may be parsed only as required. (It is possible to 531 parse the packet header, or determine its absence, without 532 parsing any messages. It is possible to divide the packet into 533 messages without even fully parsing their headers. It is 534 possible to determine whether a message is to be forwarded, and 535 to forward it, without parsing its body. It is possible to 536 determine whether a message is to be processed without parsing 537 its body. It is possible to determine if that processing may be 538 delayed because the message is a fragment by inspecting the first 539 few octets of the message body without fully parsing it.) 541 2. If parsing fails at any point the relevant entity (packet or 542 message) MUST be silently discarded, other parts of the packet 543 (up to the whole packet) MAY be silently discarded; 545 3. Otherwise if the packet header is present and it contains a 546 packet TLV block, then each TLV in it is processed according to 547 its type; 549 4. Otherwise each message in the packet, if any, is treated 550 according to Section 4.2. 552 4.2. Actions when Receiving an OLSRv2 Message 554 A node MUST perform the following tasks for each received OLSRv2 555 message: 557 1. If the received OLSRv2 message header cannot be correctly parsed 558 according to the specification in [3], or if the node recognizes 559 from the originator address of the message that the message is 560 one which the receiving node itself originated, then the message 561 MUST be silently discarded; 563 2. Otherwise: 565 1. If the received message is of a known type then the message 566 is considered for processing according to Section 4.3, AND; 568 2. If for the received message ( + ) > 1, 569 then the message is considered for forwarding according to 570 Section 4.4. 572 4.3. Message Considered for Processing 574 If a message (the "current message") is considered for processing, 575 the following tasks MUST be performed: 577 1. If an entry exists in the Processed Set where: 579 * P_type == the message type of the current message, or 0 if the 580 typedep bit in the message semantics octet (in the message 581 header) of the current message is cleared ('0'), AND; 583 * P_orig_addr == the originator address of the current message, 584 AND; 586 * P_seq_number == the message sequence number of the current 587 message. 589 then the current message MUST NOT be processed. 591 2. Otherwise: 593 1. Create an entry in the Processed Set with: 595 + P_type = the message type of the current message, or 0 if 596 the typedep bit in the message semantics octet (in the 597 message header) of the current message is cleared ('0'); 599 + P_orig_addr = originator address of the current message; 601 + P_seq_number = sequence number of the current message; 603 + P_time = current time + P_HOLD_TIME. 605 2. If the current message does not contain a valid message TLV 606 with Type == FRAGMENTATION (or if it does and the indicated 607 number of fragments is one) then process the message fully 608 according to its type. 610 3. Otherwise: 612 1. If the current message does not contain a valid message 613 TLV with Type == CONT_SEQ_NUM then the current message 614 MUST be silently discarded; 616 2. Otherwise if the current message is "partially or wholly 617 self-contained", as indicated by the notselfcont bit in 618 the Value field of the TLV with Type == FRAGMENTATION 619 being cleared ('0'), then process the current message as 620 far as possible according to its type; 622 3. If the Fragment Set includes any Fragment Tuples with: 624 - either the typedepseq bit in the Value field of the 625 TLV with Type == FRAGMENTATION in the current message 626 is cleared ('0') OR message type of FG_message == 627 message type of current message, AND; 629 - originator address of FG_message == originator address 630 of current message, AND; 632 - content sequence number (the Value field of the 633 message TLV with Type == CONT_SEQ_NUM) of FG_message 634 == content sequence number of current message; AND 636 - either fragment number (from the Value field of the 637 TLV with Type == FRAGMENTATION) in FG_message == 638 fragment number of current message OR number of 639 fragments (from the Value field of the TLV with Type 640 == FRAGMENTATION) of FG_message != number of fragments 641 of current message; 643 then remove these Fragment Tuples from the Fragment Set; 645 4. If the Fragment Set includes Fragment Tuples containing 646 all the remaining fragments of the same overall message 647 as the current message, i.e. if the number of Fragment 648 Tuples such that: 650 - either the typedepseq bit in the Value field of the 651 TLV with Type == FRAGMENTATION in the current message 652 is cleared ('0') OR message type of FG_message == 653 message type of current message, AND; 655 - originator address of FG_message == originator address 656 of current message, AND; 658 - content sequence number (the Value field of the 659 message TLV with Type == CONT_SEQ_NUM) of FG_message 660 == content sequence number of current message 662 is equal to (number of fragments of current message, less 663 one) then all of these Fragment Tuples are removed from 664 the Fragment Set and their messages processed according 665 to their type (taking account of any previous processing 666 of any which are partially or wholly self-contained); 668 5. Otherwise, a Fragment Tuple is added to the Fragment Set 669 with 671 - FG_message = current message; 673 - FG_time = current time + FG_HOLD_TIME; 675 possibly replacing a previously received instance of the 676 same fragment. 678 4.4. Message Considered for Forwarding 680 If a message is considered for forwarding, and it is either of a 681 message type defined in this document or of an unknown message type, 682 then it MUST use the following algorithm. A message type not defined 683 in this document MAY specify the use of this, or another algorithm. 684 (Such an other algorithm MAY use the Received Set for the receiving 685 interface, it SHOULD use the Forwarded Set similarly to the following 686 algorithm.) 688 If a message is considered for forwarding according to this 689 algorithm, the following tasks MUST be performed: 691 1. If the sending interface (as indicated by the source interface of 692 the IP datagram containing the message) does not match (taking 693 into account any address prefix of) any N_neighbor_iface_addr in 694 any Symmetric Neighbor Tuple, then the message MUST be silently 695 discarded. 697 2. Otherwise: 699 1. If an entry exists in the Received Set for the receiving 700 interface, where: 702 + RX_type == the message type, or 0 if the typedep bit in 703 the message semantics octet (in the message header) is 704 cleared ('0'), AND; 706 + RX_orig_addr == the originator address of the received 707 message, AND; 709 + RX_seq_number == the sequence number of the received 710 message. 712 then the message MUST be silently discarded. 714 2. Otherwise: 716 1. Create an entry in the Received Set for the receiving 717 interface with: 719 - RX_type = the message type, or 0 if the typedep bit in 720 the message semantics octet (in the message header) is 721 cleared ('0'); 723 - RX_orig_addr = originator address of the message; 725 - RX_seq_number = sequence number of the message; 727 - RX_time = current time + RX_HOLD_TIME. 729 2. If an entry exists in the Forwarded Set where: 731 - FW_type == the message type, or 0 if the typedep bit 732 in the message semantics octet (in the message header) 733 is cleared ('0'); 735 - FW_orig_addr == the originator address of the received 736 message, AND; 738 - FW_seq_number == the sequence number of the received 739 message. 741 then the message MUST be silently discarded. 743 3. Otherwise if a Relay Tuple exists whose RY_iface_addr 744 matches (taking into account any address prefix) the 745 sending interface (as indicated by the source interface 746 of the IP datagram containing the message): 748 1. Create an entry in the Forwarded Set with: 750 o FW_type = the message type, or 0 if the typedep 751 bit in the message semantics octet (in the message 752 header) is cleared ('0'); 754 o FW_orig_addr = originator address of the message; 755 o FW_seq_number = sequence number of the message; 757 o FW_time = current time + FW_HOLD_TIME. 759 2. The message header is modified as follows: 761 o Decrement in the message header by 1; 763 o Increment in the message header by 1; 765 3. Transmit the message on all OLSRv2 interfaces of the 766 node. 768 Messages are retransmitted in the format specified by [3] with the 769 ALL-MANET-NEIGHBORS address (see Section 16.1) as destination IP 770 address. 772 5. Information Repositories 774 The purpose of OLSRv2 is to determine the Routing Set, which may be 775 used to update IP's Routing Table, providing "next hop" routing 776 information for IP datagrams. In order to accomplish this, OLSRv2 777 uses a number of protocol sets: the Neighborhood Information Base, 778 provided by [4], is in OLSRv2 augmented by information allowing MPR 779 selection and signaling. Additionally, OLSRv2 specifies a Topology 780 Information Base, which describes the information used for and 781 acquired through TC message exchange - in other words: the topology 782 base represents the network topology graph as seen from each node. 784 Addresses (other than originator addresses) recorded in the 785 Neighborhood Information Base and the Topology Information Base MUST 786 all be recorded with prefix lengths, in order to allow comparison 787 with addresses received in HELLO and TC messages. For the Topology 788 Information Base this applies to A_neighbor_iface_addr, 789 T_dest_iface_addr, T_last_iface_addr, AN_net_addr, AN_gw_iface_addr, 790 R_dest_addr, R_dest_addr, R_next_iface_addr and R_local_iface_addr, 791 but not AH_orig_addr. For the Neighborhood Information Base see [4]. 793 5.1. Neighborhood Information Base 795 The neighborhood information base stores information about links 796 between local interfaces and interfaces on adjacent nodes. In 797 addition to the sets described in [4], OLSRv2 adds an element to each 798 Link Tuple to allow a node to record the willingness of a 1-hop 799 neighbor node to be selected as an MPR. Also, OLSRv2 adds an MPR Set 800 and an MPR Selector Set to the Neighborhood Information Base. The 801 MPR Set is used by a node to record which of its symmetric 1-hop 802 neighbors are selected as MPRs, and the MPR Selector Set is used by a 803 node to record which of its symmetric 1-hop neighbors have selected 804 it as MPR. Thus the MPR Set is used, in addition to what is 805 specified in [4], when generating HELLO messages, and the MPR 806 Selector Set is populated, in addition to what is specified in [4] 807 when processing HELLO messages. 809 5.1.1. Link Set 811 The Link Tuples, specified in [4] are augmented by an element, 812 L_willingness: 814 L_willingness is the node's willingness to be selected as an MPR; 816 The remaining elements of the Link Tuples are as specified in [4]. 818 5.1.2. MPR Set 820 A node maintains a set of all of the OLSRv2 interface addresses with 821 which the node has a symmetric link and which are of 1-hop symmetric 822 neighbors which the node has selected as MPRs. This is denoted the 823 "MPR Set". 825 5.1.3. MPR Selector Set 827 A node maintains a set of "MPR Selector Tuples" containing all of the 828 OLSRv2 interface addresses with which the node has a symmetric link 829 and which are of 1-hop symmetric neighbors which have selected the 830 node as an MPR. 832 (MS_neighbor_iface_addr, MS_time) 834 MS_neighbor_iface_addr specifies an OLSRv2 interface address with 835 which the node has a symmetric link and which is of a 1-hop 836 symmetric neighbor which has selected the node as an MPR; 838 MS_time specifies the time at which this MPR Selector Tuple expires 839 and *MUST* be removed. 841 In a node, the set of MPR Selector Tuples is denoted the "MPR 842 Selector Set". 844 5.2. Topology Information Base 846 The Topology Information Base stores information, required for the 847 generation and processing of TC messages. The Advertised Neighbor 848 Set contains OLSRv2 interface addresses of symmetric 1-hop neighbors 849 which are to be reported in TC messages. The Topology Set and 850 Attached Network Set both record information received through TC 851 messages. Thus the Advertised Neighbor Set is used for generating TC 852 messages, while the Topology Set and Attached Network Set are 853 populated when processing TC messages. 855 Additionally, a Routing Set is maintained, derived from the 856 information recorded in the Neighborhood Information Base, Topology 857 Set and Attached Network Set. 859 5.2.1. Advertised Neighbor Set 861 A node maintains a set of OLSRv2 interface addresses of symmetric 862 1-hop neighbors, which are to be advertised through TC messages: 864 (A_neighbor_iface_addr) 866 For this set, an Advertised Neighbor Set Sequence Number (ANSN) is 867 maintained. Each time the Advertised Neighbor Set is updated, the 868 ANSN MUST be incremented. The ANSN MUST also be incremented if any 869 locally advertised attached networks are added or removed. 871 5.2.2. ANSN History Set 873 A node records a set of "ANSN History Tuples", recording information 874 about the freshness of the topology information received from each 875 other node: 877 (AH_orig_addr, AH_seq_number, AH_time) 879 AH_orig_addr is the originator address of a received TC message; 881 AH_seq_number is the highest ANSN in any TC message received which 882 originated from AH_orig_addr; 884 AH_time is the time at which this ANSN History Tuple expires and 885 *MUST* be removed. 887 In a node, the set of ANSN History Tuples is denoted the "ANSN 888 History Set". 890 5.2.3. Topology Set 892 Each node in the network maintains topology information about the 893 network in the form of "Topology Tuples": 895 (T_dest_iface_addr, T_last_iface_addr, T_seq_number, T_time) 897 T_dest_iface_addr is an OLSRv2 interface address of a destination 898 node, which may be reached in one hop from the node with the 899 OLSRv2 interface address T_last_iface_addr; 901 T_last_iface_addr is, conversely, an OLSRv2 interface address of a 902 node which is the last hop on a path towards the node with OLSRv2 903 interface address T_dest_iface_addr. Typically, the node with 904 OLSRv2 interface address T_last_iface_addr is a MPR of the node 905 with OLSRv2 interface address T_dest_iface_addr; 907 T_seq_number is the highest received ANSN associated with the 908 information contained in this Topology Tuple; 910 T_time specifies the time at which this Topology Tuple expires and 911 *MUST* be removed. 913 In a node, the set of Topology Tuples is denoted the "Topology Set". 915 5.2.4. Attached Network Set 917 Each node in the network maintains information about attached 918 networks in the form of "Attached Network Tuples": 920 (AN_net_addr, AN_gw_iface_addr, AN_seq_number, AN_time) 922 AN_net_addr is the network address (including prefix length) of an 923 attached network, which may be reached via the node with the 924 OLSRv2 interface address AN_gw_iface_addr; 926 AN_gw_iface_addr is the address of an OLSRv2 interface of a node 927 which can act as gateway to the network identified by AN_net_addr; 929 AN_seq_number is the highest received ANSN associated with the 930 information contained in this Attached Network Tuple; 932 AN_time specifies the time at which this Attached Network Tuple 933 expires and *MUST* be removed. 935 In a node, the set of Attached Network Tuples is denoted the 936 "Attached Network Set". 938 5.2.5. Routing Set 940 A node records a set of "Routing Tuples" describing the selected path 941 to each destination in the network for which a route is known: 943 (R_dest_addr, R_next_iface_addr, R_dist, R_local_iface_addr) 945 R_dest_addr is the address of the destination, either the address of 946 an OLSRv2 interface of a destination node, or the network address 947 of an attached network; 949 R_next_iface_addr is the OLSRv2 interface address of the "next hop" 950 on the selected path to the destination; 952 R_dist is the number of hops on the selected path to the destination; 954 R_local_iface_addr is the address of the local interface over which a 955 packet MUST be sent to reach the destination. 957 In a node, the set of Routing Tuples is denoted the "Routing Set". 959 6. OLSRv2 Control Message Structures 961 Nodes using OLSRv2 exchange information through messages. One or 962 more messages sent by a node at the same time are combined into a 963 packet. These messages may have originated at the sending node, or 964 have originated at another node and forwarded by the sending node. 965 Messages with different originators may be combined in the same 966 packet. 968 The packet and message format used by OLSRv2 is defined in [3]. 969 However this specification contains some options which are not used 970 by OLSRv2. In particular (using the syntactical elements defined in 971 the packet format specification): 973 o All OLSRv2 packets, not limited to those defined in this document, 974 include a . 976 o All OLSRv2 packets, not limited to those defined in this document, 977 have the pseqnum bit of cleared ('0'), i.e. 978 they include a packet sequence number. 980 o OLSRv2 packets MAY include packet TLVs, however OLSRv2 itself does 981 not specify any packet TLVs. 983 o All OLSRv2 messages, not limited to those defined in this 984 document, include a full and hence have the noorig 985 and nohops bits of cleared ('0'). 987 o All OLSRv2 message defined in this document have the typedep bit, 988 and all reserved bits of cleared ('0'). 990 Other options defined in [3] may be freely used, in particular any 991 other values of or consistent with 992 its specification. 994 OLSRv2 messages are sent using UDP, see Appendix C. 996 The remainder of this section defines, within the framework of [3], 997 message types and TLVs specific to OLSRv2. 999 6.1. General OLSRv2 Message TLVs 1001 This document specifies two message TLVs, which can be applied to any 1002 OLSRv2 control messages, VALIDITY_TIME and INTERVAL_TIME. 1004 6.1.1. VALIDITY_TIME TLV 1006 All OLSRv2 messages specified in this document MUST include a 1007 VALIDITY_TIME TLV, specifying a period following receipt of a 1008 message, after which the receiving node MUST consider the message 1009 content to no longer be valid (unless repeated in a later message). 1010 The validity time of a message MAY be specified to depend on the 1011 distance from the originator (i.e. the field in the 1012 message header as defined in [3]). Thus, a VALIDITY_TIME TLV's value 1013 field MAY contain a sequence of pairs (time, hop limit) in increasing 1014 hop limit order; it MUST contain a final default value. 1016 This is an extended, and compatible, version of the VALIDITY_TIME TLV 1017 defined in [4]. 1019 Thus, an instance of a VALIDITY_TIME TLV MAY have the following value 1020 field: 1022 ... .... 1024 Which would mean that the message carrying this VALIDITY_TIME TLV 1025 would have the following validity times: 1027 o in the interval from 0 (exclusive) to (inclusive) 1028 hops away from the originator; 1030 o in the interval from (exclusive) to 1031 (inclusive) hops away from the originator; 1033 o in the interval from (exclusive) to 255 1034 (inclusive) hops away from the originator. 1036 The VALIDITY_TIME message TLV specification is given in Table 1. 1038 +----------------+------+-------------------+-----------------------+ 1039 | Name | Type | Length | Value | 1040 +----------------+------+-------------------+-----------------------+ 1041 | VALIDITY_TIME | TBD | (2*n+1) * 8 bits | {