idnits 2.17.1 draft-ietf-manet-olsrv2-00.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 14. -- Found old boilerplate from RFC 3978, Section 5.5 on line 2573. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 2550. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 2557. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 2563. ** 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. ** There is 1 instance of too long lines in the document, the longest one being 2 characters in excess of 72. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 358: '...eighborhood of N MUST have a symmetric...' RFC 2119 keyword, line 448: '...ber (PSN), which MUST be be incremente...' RFC 2119 keyword, line 461: '...re address blocks. Each address SHALL...' RFC 2119 keyword, line 465: '...lock. A message MAY also contain zero...' RFC 2119 keyword, line 468: '... Message content MAY (e.g. due to size...' (102 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 652 has weird spacing: '...sisting of tw...' == Line 961 has weird spacing: '...address of th...' == Line 1041 has weird spacing: '...changed betwe...' == Line 1302 has weird spacing: '.... This allow...' -- 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 (August 2005) is 6823 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '11' on line 2487 looks like a reference -- Missing reference section? '3' on line 2459 looks like a reference -- Missing reference section? '5' on line 2466 looks like a reference -- Missing reference section? '1' on line 2450 looks like a reference -- Missing reference section? '2' on line 2454 looks like a reference -- Missing reference section? '0-7' on line 1802 looks like a reference -- Missing reference section? '9' on line 2480 looks like a reference -- Missing reference section? '4' on line 2463 looks like a reference -- Missing reference section? '6' on line 2469 looks like a reference -- Missing reference section? '7' on line 2474 looks like a reference -- Missing reference section? '8' on line 2476 looks like a reference -- Missing reference section? '10' on line 2483 looks like a reference Summary: 6 errors (**), 0 flaws (~~), 6 warnings (==), 20 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: February 2, 2006 August 2005 6 The Optimized Link-State Routing Protocol version 2 7 draft-ietf-manet-olsrv2-00 9 Status of this Memo 11 By submitting this Internet-Draft, each author represents that any 12 applicable patent or other IPR claims of which he or she is aware 13 have been or will be disclosed, and any of which he or she becomes 14 aware will be disclosed, in accordance with Section 6 of BCP 79. 16 Internet-Drafts are working documents of the Internet Engineering 17 Task Force (IETF), its areas, and its working groups. Note that 18 other groups may also distribute working documents as Internet- 19 Drafts. 21 Internet-Drafts are draft documents valid for a maximum of six months 22 and may be updated, replaced, or obsoleted by other documents at any 23 time. It is inappropriate to use Internet-Drafts as reference 24 material or to cite them other than as "work in progress." 26 The list of current Internet-Drafts can be accessed at 27 http://www.ietf.org/ietf/1id-abstracts.txt. 29 The list of Internet-Draft Shadow Directories can be accessed at 30 http://www.ietf.org/shadow.html. 32 This Internet-Draft will expire on February 2, 2006. 34 Copyright Notice 36 Copyright (C) The Internet Society (2005). 38 Abstract 40 This document describes version 2 of the Optimized Link State Routing 41 (OLSRv2) protocol for mobile ad hoc networks. The protocol is an 42 optimization of the classical link state algorithm tailored to the 43 requirements of a mobile wireless LAN. 45 The key optimization of OLSRv2 is that of multipoint relays, 46 providing an efficient mechanism for network-wide broadcast of link- 47 state information. A secondary optimization is, that OLSRv2 employs 48 partial link-state information: each node maintains information of 49 all destinations, but only a subset of links. This allows that only 50 select nodes diffuse link-state advertisements (i.e. reduces the 51 number of network-wide broadcasts) and that these advertisements 52 contain only a subset of links (i.e. reduces the size of each 53 network-wide broadcast). The partial link-state information thus 54 obtained allows each OLSRv2 node to at all times maintain optimal (in 55 terms of number of hops) routes to all destinations in the network. 57 OLSRv2 imposes minimum requirements to the network by not requiring 58 sequenced or reliable transmission of control traffic. Furthermore, 59 the only interaction between OLSRv2 and the IP stack is routing table 60 management. 62 OLSRv2 is particularly suitable for large and dense networks as the 63 technique of MPRs works well in this context. 65 Table of Contents 67 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 68 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . 6 69 1.2 Applicability Statement . . . . . . . . . . . . . . . . . 7 70 2. Protocol Overview and Functioning . . . . . . . . . . . . . . 8 71 3. OLSRv2 Signaling Framework . . . . . . . . . . . . . . . . . . 11 72 3.1 OLSRv2 Packet Format . . . . . . . . . . . . . . . . . . . 11 73 3.2 OLSR Messages . . . . . . . . . . . . . . . . . . . . . . 12 74 3.2.1 Address Blocks . . . . . . . . . . . . . . . . . . . . 13 75 3.2.2 TLVs . . . . . . . . . . . . . . . . . . . . . . . . . 14 76 3.3 Message Content Fragmentation . . . . . . . . . . . . . . 15 77 4. Packet Processing and Message Forwarding . . . . . . . . . . . 17 78 4.1 Processing and Forwarding Repositories . . . . . . . . . . 17 79 4.1.1 Received Message Set . . . . . . . . . . . . . . . . . 17 80 4.1.2 Processed Set . . . . . . . . . . . . . . . . . . . . 17 81 4.1.3 Forwarded Set . . . . . . . . . . . . . . . . . . . . 18 82 4.1.4 Relay Set . . . . . . . . . . . . . . . . . . . . . . 18 83 4.2 Fragment Set . . . . . . . . . . . . . . . . . . . . . . . 18 84 4.3 Actions when Receiving an OLSRv2-Packet . . . . . . . . . 19 85 4.4 Actions when Receiving an OLSRv2-Message . . . . . . . . . 19 86 4.5 Message Considered for Processing . . . . . . . . . . . . 20 87 4.6 Message Considered for Forwarding . . . . . . . . . . . . 21 88 5. Information Repositories . . . . . . . . . . . . . . . . . . . 23 89 5.1 Local Link Information Base . . . . . . . . . . . . . . . 23 90 5.1.1 Link Set . . . . . . . . . . . . . . . . . . . . . . . 23 91 5.1.2 2-hop Neighbor Set . . . . . . . . . . . . . . . . . . 24 92 5.1.3 Neighborhood Address Association Set . . . . . . . . . 24 93 5.1.4 MPR Set . . . . . . . . . . . . . . . . . . . . . . . 24 94 5.1.5 Advertised Neighbor Set . . . . . . . . . . . . . . . 25 95 5.2 Topology Information Base . . . . . . . . . . . . . . . . 25 96 6. OLSRv2 Control Messages . . . . . . . . . . . . . . . . . . . 26 97 6.1 HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 26 98 6.2 TC Messages . . . . . . . . . . . . . . . . . . . . . . . 26 99 6.3 MA Messages . . . . . . . . . . . . . . . . . . . . . . . 26 100 7. Populating the MPR Set . . . . . . . . . . . . . . . . . . . . 27 101 8. Populating the Advertised Neighbor Set . . . . . . . . . . . . 28 102 9. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 29 103 9.1 HELLO Message: Message TLVs . . . . . . . . . . . . . . . 29 104 9.2 HELLO Message: Address Blocks and Address TLVs . . . . . . 29 105 10. HELLO Message Processing . . . . . . . . . . . . . . . . . . 31 106 10.1 Populating the Link Set . . . . . . . . . . . . . . . . . 31 107 10.2 Populating the 2-Hop Neighbor Set . . . . . . . . . . . . 33 108 10.3 Populating the Relay Set . . . . . . . . . . . . . . . . . 34 109 10.4 Neighborhood and 2-hop Neighborhood Changes . . . . . . . 34 110 11. TC Message Generation . . . . . . . . . . . . . . . . . . . 36 111 11.1 TC Message: Message TLVs . . . . . . . . . . . . . . . . . 36 112 11.2 TC Message: Address Blocks and Address TLVs . . . . . . . 36 114 12. TC Message Processing . . . . . . . . . . . . . . . . . . . 37 115 13. MA Message Generation . . . . . . . . . . . . . . . . . . . 39 116 14. MA Message Processing . . . . . . . . . . . . . . . . . . . 40 117 15. Routing Table Calculation . . . . . . . . . . . . . . . . . 41 118 16. Proposed Values for Constants . . . . . . . . . . . . . . . 44 119 16.1 Message Types . . . . . . . . . . . . . . . . . . . . . . 44 120 16.2 Message Intervals . . . . . . . . . . . . . . . . . . . . 44 121 16.3 Holding Times . . . . . . . . . . . . . . . . . . . . . . 44 122 16.4 Willingness . . . . . . . . . . . . . . . . . . . . . . . 44 123 17. Representing Time . . . . . . . . . . . . . . . . . . . . . 45 124 18. IANA Considerations . . . . . . . . . . . . . . . . . . . . 46 125 A. Example Heuristic for Calculating MPRs . . . . . . . . . . . . 47 126 B. Example Algorithms for Generating Control Traffic . . . . . . 50 127 B.1 Example Algorithm for Generating HELLO messages . . . . . 50 128 B.2 Example Algorithm for Generating TC messages . . . . . . . 51 129 C. Protocol and Port Number . . . . . . . . . . . . . . . . . . . 53 130 D. OLSRv2 Packet and Message Layout . . . . . . . . . . . . . . . 54 131 D.1 General OLSR Packet Format . . . . . . . . . . . . . . . . 54 132 D.1.1 Message TLVs . . . . . . . . . . . . . . . . . . . . . 55 133 D.1.2 Address Block . . . . . . . . . . . . . . . . . . . . 55 134 D.1.3 Address Block TLV . . . . . . . . . . . . . . . . . . 57 135 D.2 Layout of OLSRv2 Specified Messages . . . . . . . . . . . 57 136 D.2.1 Layout of HELLO Messages . . . . . . . . . . . . . . . 58 137 D.2.2 Layout of TC messages . . . . . . . . . . . . . . . . 58 138 E. Node Configuration . . . . . . . . . . . . . . . . . . . . . . 60 139 E.1 IPv6 Specific Considerations . . . . . . . . . . . . . . . 60 140 F. Security Considerations . . . . . . . . . . . . . . . . . . . 61 141 F.1 Confidentiality . . . . . . . . . . . . . . . . . . . . . 61 142 F.2 Integrity . . . . . . . . . . . . . . . . . . . . . . . . 61 143 F.3 Interaction with External Routing Domains . . . . . . . . 62 144 F.4 Node Identity . . . . . . . . . . . . . . . . . . . . . . 63 145 G. Flow and Congestion Control . . . . . . . . . . . . . . . . . 64 146 H. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . 65 147 I. References . . . . . . . . . . . . . . . . . . . . . . . . . . 66 148 J. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 67 149 K. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 68 150 Author's Address . . . . . . . . . . . . . . . . . . . . . . . 68 151 Intellectual Property and Copyright Statements . . . . . . . . 69 153 1. Introduction 155 The Optimized Link State Routing Protocol version 2 (OLSRv2) is an 156 update to OLSRv1 as published in RFC3626 [11]. Compared to RFC3626, 157 OLSRv2 retains the same basic mechanisms and algorithms, while 158 providing an even more flexible signaling framework and some 159 simplification of the messages being exchanged. Also, OLSRv2 takes 160 care to accomodate both IPv4 and IPv6 addresses in a compact fashion. 162 OLSRv2 is developed for mobile ad hoc networks. It operates as a 163 table driven, proactive protocol, i.e., exchanges topology 164 information with other nodes of the network regularly. Each node 165 selects a set of its neighbor nodes as "multipoint relays" (MPR). In 166 OLSRv2, only nodes that are selected as such MPRs are then 167 responsible for forwarding control traffic intended for diffusion 168 into the entire network. MPRs provide an efficient mechanism for 169 flooding control traffic by reducing the number of transmissions 170 required. 172 Nodes, selected as MPRs, also have a special responsibility when 173 declaring link state information in the network. Indeed, the only 174 requirement for OLSRv2 to provide shortest path routes to all 175 destinations is that MPR nodes declare link-state information for 176 their MPR selectors. Additional available link-state information may 177 be utilized, e.g., for redundancy. 179 Nodes which have been selected as multipoint relays by some neighbor 180 node(s) announce this information periodically in their control 181 messages. Thereby a node announces to the network, that it has 182 reachability to the nodes which have selected it as an MPR. Then, 183 aside from being used to facilitate efficient flooding, MPRs are also 184 used for route calculation from any given node to any destination in 185 the network. 187 A node selects MPRs from among its one hop neighbors with 188 "symmetric", i.e., bi-directional, linkages. Therefore, selecting 189 the route through MPRs automatically avoids the problems associated 190 with data packet transfer over uni-directional links (such as the 191 problem of not getting link-layer acknowledgments for data packets at 192 each hop, for link-layers employing this technique for unicast 193 traffic). 195 OLSRv2 is developed to work independently from other protocols. 196 Likewise, OLSRv2 makes no assumptions about the underlying link- 197 layer. However, OLSRv2 may use link-layer information and 198 notifications when available and applicable. 200 OLSRv2, as OLSRv1, inherits the concept of forwarding and relaying 201 from HIPERLAN (a MAC layer protocol) which is standardized by ETSI 202 [3]. 204 1.1 Terminology 206 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 207 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 208 document are to be interpreted as described in RFC2119 [5]. 210 Additionally, this document uses the following terminology: 212 node - a MANET router which implements the Optimized Link State 213 Routing protocol as specified in this document. 215 OLSRv2 interface - A network device participating in a MANET running 216 OLSRv2. A node may have several OLSRv2 interfaces, each interface 217 assigned an unique IP address. 219 neighbor - A node X is a neighbor of node Y if node Y can hear node X 220 (i.e., a link exists from an OLSRv2 interface on node X to an 221 OLSRv2 interface on node Y). A neighbor may also be called a 222 1-hop neighbor. 224 2-hop neighbor - A node X is a 2-hop neighbor of node Y if node X is 225 a neighbor of a neighbor of node Y. 227 strict 2-hop neighbor - a 2-hop neighbor which is (i) not the node 228 itself, (ii) not a neighbor of the node, and (iii) not a 2-hop 229 neighbor only through a neighbor with willingness WILL_NEVER. 231 multipoint relay (MPR) - A node which is selected by its 1-hop 232 neighbor, node X, to "re-transmit" all the broadcast messages that 233 it receives from node X, provided that the message is not a 234 duplicate, and that the time to live field of the message is 235 greater than one. 237 multipoint relay selector (MPR selector, MS) - A node which has 238 selected its 1-hop neighbor, node X, as its multipoint relay, will 239 be called an MPR selector of node X. 241 link - A link is a pair of OLSRv2 interfaces from two different 242 nodes, where at least one interface is able to hear (i.e. receive 243 traffic from) the other. A node is said to have a link to another 244 node when one of its interfaces has a link to one of the 245 interfaces of the other node. 247 symmetric link - A link where both interfaces have verified they are 248 able to hear the other. 250 asymmetric link - A link which is not symmetric. 252 symmetric 1-hop neighborhood - The symmetric 1-hop neighborhood of 253 any node X is the set of nodes which have at least one symmetric 254 link to node X. 256 symmetric 2-hop neighborhood - The symmetric 2-hop neighborhood of 257 node X is the set of nodes, excluding node X itself, which have a 258 symmetric link to the symmetric 1-hop neighborhood of X. 260 symmetric strict 2-hop neighborhood - The symmetric strict 2-hop 261 neighborhood of node X is the set of nodes in its symmetric 2-hop 262 neighborhood that are neither in its symmetric 1-hop neighborhood 263 nor reachable only through a symmetric 1-hop neighbor of node X 264 with willingness WILL_NEVER. 266 1.2 Applicability Statement 268 OLSRv2 is a proactive routing protocol for mobile ad hoc networks 269 (MANETs) [1], [2]. It is well suited to large and dense networks of 270 mobile nodes, as the optimization achieved using the MPRs works well 271 in this context. The larger and more dense a network, the more 272 optimization can be achieved as compared to the classic link state 273 algorithm. OLSRv2 uses hop-by-hop routing, i.e., each node uses its 274 local information to route packets. 276 As OLSRv2 continuously maintains routes to all destinations in the 277 network, the protocol is beneficial for traffic patterns where the 278 traffic is random and sporadic between a large subset of nodes, and 279 where the [source, destination] pairs are changing over time: no 280 additional control traffic is generated in this situation since 281 routes are maintained for all known destinations at all times. Also, 282 since routes are maintained continously, traffic is subject to no 283 delays due to buffering/route-discovery. 285 2. Protocol Overview and Functioning 287 OLSRv2 is a proactive routing protocol for mobile ad hoc networks. 288 The protocol inherits the stability of a link state algorithm and has 289 the advantage of having routes immediately available when needed due 290 to its proactive nature. OLSRv2 is an optimization over the 291 classical link state protocol, tailored for mobile ad hoc networks. 292 The main tailoring and optimizations of OLSRv2 are: 294 o periodic, unacknowledged transmission of all control messages; 296 o optimized flooding for global link-state information diffusion; 298 o partial topology maintenance -- each node will know of all 299 destinations and a subset of links in the network. 301 More specifically, OLSRv2 consists of the following main components: 303 o A general and flexible signaling framework, allowing for 304 information exchange between OLSRv2 nodes. This framework allows 305 for both local information exchange (between neighboring nodes) 306 and global information exchange using an optimized flooding 307 mechanism denoted "MPR flooding". 309 o A specification of local signaling, denoted HELLO messages. HELLO 310 messages in OLSRv2 serve to: 312 * discover links to adjacent OLSR nodes; 314 * perform bidirectionality check on the discovered links; 316 * advertise neighbors and hence discover 2-hop neighbors; 318 * signal MPR selection. 320 HELLO messages are emitted periodically, thereby allowing nodes to 321 continuously track changes in their local neighborhoods. 323 o A specification of global signaling, denoted TC messages. TC 324 messages in OLSRv2 serve to: 326 * inject link-state information into the entire network. 328 TC messages are emitted periodically, thereby allowing nodes to 329 continuously track global changes in the network. 331 Thus, through periodic exchange of HELLO messages, a node is able to 332 acquire and maintain information about its immediate neighborhood. 334 This includes information about immediate neighbors, as well as nodes 335 which are two hops away. By HELLO messages being exchanged 336 periodically, a node learns about changes in the neighborhood (new 337 nodes emerging, old nodes disappearing) without requiring explicit 338 mechanisms for doing so. 340 Based on the local topology information, acquired through the 341 periodic exchange of HELLO messages, an OLSRv2 node is able to make 342 provisions for ensuring optimized flooding, denoted "MPR flooding", 343 as well as injection of link-state information into the network. 344 This is done through the notion of Multipoint Relays. 346 The idea of multipoint relays is to minimize the overhead of flooding 347 messages in the network by reducing redundant retransmissions in the 348 same region. Each node in the network selects a set of nodes in its 349 symmetric 1-hop neighborhood which may retransmit its messages. This 350 set of selected neighbor nodes is called the "Multipoint Relay" (MPR) 351 Set of that node. The neighbors of node N which are *NOT* in its MPR 352 set, receive and process broadcast messages but do not retransmit 353 broadcast messages received from node N. The MPR set of a node is 354 selected such that it covers (in terms of radio range) all symmetric 355 strict 2-hop nodes. The MPR set of N, denoted as MPR(N), is then an 356 arbitrary subset of the symmetric 1-hop neighborhood of N which 357 satisfies the following condition: every node in the symmetric strict 358 2-hop neighborhood of N MUST have a symmetric link towards MPR(N). 359 The smaller a MPR set, the less control traffic overhead results from 360 the routing protocol. [2] gives an analysis and example of MPR 361 selection algorithms. Notice, that as long as the condition above is 362 satisfied, any algorithm selecting MPR sets is acceptable in terms of 363 implementation interoperability. 365 Each node maintains information about the set of neighbors that have 366 selected it as MPR. This set is called the "Multipoint Relay 367 Selector set" (MPR Selector Set) of a node. A node obtains this 368 information from periodic HELLO messages received from the neighbors. 370 A broadcast message, intended to be diffused in the whole network, 371 coming from any of the MPR selectors of node N is assumed to be 372 retransmitted by node N, if N has not received it yet. This set can 373 change over time (i.e., when a node selects another MPR Set) and is 374 indicated by the selector nodes in their HELLO messages. 376 Using the MPR flooding mechanism, link-state information can be 377 injected into the network using TC messages: a node evaluates 378 periodically if it is required to generate TC messages and, if so, 379 which information is to be included in these TC messages. 381 OLSRv2 is designed to work in a completely distributed manner and 382 does not depend on any central entity. The protocol does NOT REQUIRE 383 reliable transmission of control messages: each node sends control 384 messages periodically, and can therefore sustain a reasonable loss of 385 some such messages. Such losses occur frequently in radio networks 386 due to collisions or other transmission problems. 388 Also, OLSRv2 does NOT REQUIRE sequenced delivery of messages. Each 389 control message contains a sequence number which is incremented for 390 each message. Thus the recipient of a control message can, if 391 required, easily identify which information is more recent - even if 392 messages have been re-ordered while in transmission. Furthermore, 393 OLSRv2 provides support for protocol extensions such as sleep mode 394 operation, multicast-routing etc. Such extensions may be introduced 395 as additions to the protocol without breaking backwards compatibility 396 with earlier versions. 398 OLSRv2 does NOT REQUIRE any changes to the format of IP packets. 399 Thus any existing IP stack can be used as is: OLSRv2 only interacts 400 with routing table management. 402 3. OLSRv2 Signaling Framework 404 In OLSRv2, signaling serves as a way for a node to express its 405 relationships with other nodes -- or more precisely, a control- 406 message in OLSRv2 states that "the address X has the following 407 special relationship with addresses W, Y and Z". This "special 408 relationship" may be advertisement of an adjacency between interface 409 X and interfaces WYZ, advertisement of an associated cost, 410 advertisement of selection as designated router etc. 412 In an OLSRv2 MANET, signaling may be either "local", intended only 413 for nodes adjacent to the originator of the signal or "global", 414 intended for all nodes in the OLSRv2 MANET. 416 In this section, the general mechanism employed for all OLSRv2 417 signaling is described. 419 This section provides abstract descriptions of message- and packet 420 formats. In the complementary Appendix D, a graphical representation 421 of OLSRv2 control messages and packets can be found. 423 3.1 OLSRv2 Packet Format 425 OLSRv2 messages are carried in a general packet format, allowing: 427 o piggybacking of several independent messages (originated or 428 forwarded) in a single transmission; 430 o external extensibility -- i.e. new message types can be introduced 431 for auxiliary functions, while still being delivered and forwarded 432 correctly even by nodes not capable of interpreting the message; 434 o controlled-scope diffusion of messages. 436 The packet format is inherited directly from OLSRv1 [11] and conforms 437 to the following specification: 439 packet = {}+ 441 with the usual notion of "+" indicating "one or more" occurrences of 442 the preceding element, and the elements defined thus: 444 is an 16 bit field, which specifies the length (in 445 octets) of the packet; 447 is an 16 bit field, which specifies the packet 448 sequence number (PSN), which MUST be be incremented by one each 449 time a new OLSRv2 packet is transmitted. "Wrap-around" is handled 450 as described in Appendix H. A separate Packet Sequence Number is 451 maintained for each OLSRv2 interface such that packets transmitted 452 over an interface are sequentially enumerated. 454 is the message as defined in Section 3.2. 456 3.2 OLSR Messages 458 Signals in OLSRv2 are carried through "messages". The primary 459 content of a message is a set of addresses about which the 460 originating node wishes to convey information. These addresses may 461 be divided into one or more address blocks. Each address SHALL 462 appear only once in a message. Each address block is followed by 463 zero or more TLVs, explained with more details in Section 3.2.2, 464 which convey information (e.g. cost, link-status, ...) about the 465 addresses in that address block. A message MAY also contain zero or 466 more TLVs, associated with the whole message. 468 Message content MAY (e.g. due to size limitations) be fragmented. 469 Each fragment is transmitted such that it makes up a syntactically 470 correct message (i.e. all headers are set as if each fragment is a 471 message in its own right, and each message contains all message 472 TLVs). Content fragmentation is detailed in Section 3.3. 474 A message has the following general layout 476 message = {}* 478 msg-header = 479 481 = * 483 with the usual notion of "*" indicating "zero or more" occurrences of 484 the preceding element, and the elements defined thus: 486 is a 16 bit field, which contains the total length (in 487 octets) of the immediately following TLV(s). If no TLV follows, 488 this field contains zero; 490 is a TLV, providing information regarding the entire message or 491 the address block which it follows. TLVs are specified in 492 Section 3.2.2; 494 is a block of addresses, with which the originator of 495 the message has a special relationship. Address blocks are 496 specified in Section 3.2.1; 498 is an 8 bit field, which specifies the type of message; 500 is an 8 bit field, which specifies for how long time after 501 reception a node MUST consider the information contained in the 502 message as valid, unless a more recent update to the information 503 is received. The encoding of vtime is as specified in Section 17; 505 is an 16 bit field, which specifies the size of the and the following , counted in octets; 508 is the address of an interface of the node, 509 which originated the message. Each node SHOULD select one 510 interface address and MUST utilize this address consistently as 511 "originator address" for all messages it generates; 513 is an 8 bit field, which contains the maximum number of hops a 514 message will be transmitted. Before a message is retransmitted, 515 the Time To Live MUST be decremented by 1. When a node receives a 516 message with a Time To Live equal to 0 or 1, the message MUST NOT 517 be retransmitted under any circumstances. Normally, a node would 518 not receive a message with a TTL of zero. 520 is an 8 bit field, which contains the number of hops a 521 message has attained. Before a message is retransmitted, the Hop 522 Count MUST be incremented by 1. Initially, this is set to '0' by 523 the originator of the message; 525 is a 16 bit field, which contains a unique number, 526 generated by the originator node to uniquely identify each message 527 in the network. "Wrap-around" is handled as described in 528 Appendix H. 530 TLVs associated with a message or an address block SHALL be included 531 in numerically ascending order within each TLV block. Note that this 532 means that all TLVs defined in this document appear before all other 533 TLVs in that TLV block. 535 3.2.1 Address Blocks 537 An address block represents a set of addresses in a compact form. 538 Assuming that an address can be specified as a sequence of bits of 539 the form 'head:tail', then an address-block is a set of addresses 540 sharing the same 'head' and having different 'tails'. Specifically, 541 an address block conforms to the following specification: 543 address-block = {{*}} 545 with the usual notion of "*" indicating "zero or more" occurrences of 546 the preceding element, and the elements defined thus: 548 is the number of "common leftmost bits" in a set of 549 addresses, akin to a "prefix", however with the only restriction 550 on the head-length that 0 <= head-length <= the length of the 551 address; 553 is the longest sequence of leftmost bits, which the addresses 554 in the address block have in common. Akin to a prefix; 556 is the number of tails which follows; 558 is the sequence of bits which, when concatenated to the head, 559 makes up a single, complete, unique address. 561 This representation aims at providing a flexible, yet compact, way of 562 representing sets of interface addresses. 564 3.2.2 TLVs 566 A TLV is a carrier of information, relative to a message or to 567 addresses in an address block. A TLV, associated to an address- 568 block, specifies some attribute(s), which associate with address(ses) 569 in the address-block. In order to provide the largest amount of 570 flexibility to benefit from address aggregation as described in 571 Section 3.2.1, a TLV associated to an address block can apply to: 573 o a single address in the address block; 575 o all addresses in the address block; 577 o any continuous sequence of addresses in the address block; 579 Specifically, a TLV conforms to the following specification: 581 tlv = 583 where the elements are defined thus: 585 is an 8 bit field, which specifies the type of the TLV. The 586 two most significant bits are allocated with the following 587 semantics: 589 bit 7 is the "user" bit. Types with this bit unset are defined in 590 this specification or can be allocated via standards action. 591 Types with this bit set are reserved for private/local use. 593 bit 6 is the "multivalue" bit. TLVs with types with this bit unset 594 include a single value, which applies to each of the addresses 595 defined by and . TLVs with types with 596 this bit set include separate values for each of the addresses in 597 the interval defined by and ; 599 is an 8 bit field which specifies the length, counted in 600 octets, of the data contained in . If the multivalue bit 601 is set, this MUST be an integral multiple of (-+1); 604 is an 8 bit field. For a TLV associated with an 605 address block, specifies the index of the first address in the 606 address-block (starting at zero), for which this TLV applies. For 607 a TLV associated with a message, this field SHALL be set to zero; 609 is an 8 bit field. For a TLV associated with an address 610 block, specifies the index of the last address in the address- 611 block (starting at zero) for which this TLV applies. For a TLV 612 associated with a message, this field SHALL be set to zero; 614 contains a payload, of the length specified in , 615 which is to be processed according to the specification indexed by 616 the field. If this is a TLV for an address block and the 617 multivalue bit is set, this field is divided into (- 618 +1) equal-sized fields which are applied in turn to 619 each address described by and 621 Two or more TLVs of the same type SHALL NOT apply to the same 622 address. 624 3.3 Message Content Fragmentation 626 An OLSRv2 message MAY be larger than is desirable to include, with 627 the OLSR packet and other headers (UDP, IP) in a MAC frame. In this 628 case the message SHOULD be fragmented. 630 An OLSRv2 message may be fragmented by dividing the address blocks 631 plus following TLVs among its fragments. It MAY be necessary to use 632 more address blocks than might otherwise be chosen without 633 fragmentation. Each message fragment may carry any number of these 634 address blocks plus following TLVs. 636 All message TLVs MUST be included identically in each fragment. 638 All TLVs pertaining to an address block MUST be included in the same 639 fragment as the address block. 641 When transmitting fragmented content, each message containing a 642 fragment MUST include a message TLV of type Content Sequence Number. 643 The value of this Content Sequence Number TLV is a 16 bit field 644 uniquely identifying the "version" of the content of the message. If 645 the content does not have an inherent sequence number or version 646 number, the value of the Content Sequence Number TLV SHOULD be set to 647 the message sequence number of the message containing the first 648 fragment. 650 A message containing a fragment MUST include a message TLV of type 651 Fragmentation. The value of this Fragmentation TLV is a 16 bit field 652 consisting of two 8 bit sub-fields describing the number of 653 fragments, and the fragment number (counting from zero). 655 If the same content with the same Content Sequence Number is sent 656 more than once by a node, the content MUST be fragmented and 657 transmitted identically each time it is sent. 659 4. Packet Processing and Message Forwarding 661 Upon receiving a basic packet, a node examines each of the "message 662 headers". If the "message type" is known to the node, the message is 663 processed locally according to the specifications for that message 664 type -- forwarding of known messages is considered part of the 665 message processing. Otherwise, the message is treated as "unknown", 666 and is only evaluated for forwarding. 668 4.1 Processing and Forwarding Repositories 670 The following data-structures are employed in order to ensure that a 671 message is processed at most once and is forwarded at most once per 672 interface of a node, and that fragmented content is treated 673 correctly. 675 4.1.1 Received Message Set 677 Each node maintains, for each OLSRv2 interface it possesses, a set of 678 signatures of messages received over that interface: 680 (R_addr, R_seq_number, R_time) 682 where: 684 R_addr is the originator address of the received message; 686 R_seq_number is the message sequence number of the received message; 688 R_time specifies the time at which this record expires and *MUST* be 689 removed. 691 In a node, this is denoted the "Received Message Set". 693 4.1.2 Processed Set 695 Each node maintains a set of messages, which have been processed by 696 the node: 698 (P_addr, P_seq_number, P_time) 700 where: 702 P_addr is the originator address of the received message; 703 P_seq_number is the message sequence number of the received message; 705 P_time specifies the time at which this record expires and *MUST* be 706 removed. 708 In a node, this is denoted the "Processed Set". 710 4.1.3 Forwarded Set 712 Each node maintains a set of messages, which have been retransmitted/ 713 forwarded by the node: 715 (F_addr, F_seq_number, F_time) 717 where: 719 F_addr is the originator address of the received message; 721 F_seq_number is the message sequence number of the received message; 723 F_time specifies the time at which this record expires and *MUST* be 724 removed. 726 In a node, this is denoted the "Forwarded Set". 728 4.1.4 Relay Set 730 A node maintains a set of neighbor interfaces, in the form of "relay 731 tuples", for which it is to relay flooded messages: 733 (RS_if_addr, Rs_if_time) 735 where: 737 RS_if_addr is the address of the neighbor interface, for which a node 738 SHOULD relay flooded messages; 740 RS_if_time specifies the time at which this record expires and *MUST* 741 be removed. 743 In a node, this is denoted the "Relay Set". 745 4.2 Fragment Set 747 A node stores messages containing fragmented content in form of 748 "fragment tuples" until all fragments are received and the messages 749 can be processed: 751 (F_message, F_time) 753 where: 755 F_message is the message containing a fragment; 757 F_time specifies the time at which this record expires and MUST be 758 removed. 760 In a node, this is denoted the "Fragment Set". 762 4.3 Actions when Receiving an OLSRv2-Packet 764 Upon receiving a basic packet, a node MUST perform the following 765 task: 767 1. If the packet contains no messages (i.e., the Packet Length is 768 less than or equal to the size of the packet header), the packet 769 MUST silently be discarded. 771 2. Otherwise, each encapsulated message is treated according to 772 Section 4.4. 774 4.4 Actions when Receiving an OLSRv2-Message 776 A node MUST perform the following tasks for a received OLSRv2- 777 message: 779 If for the message TTL <= 0 or if the Originator Address of the 780 message is an interface address of the receiving node, then the 781 message MUST silently be dropped. 783 If an entry exists in the received set for the receiving 784 interface, where: 786 * R_addr == the originator of the received message, AND; 788 * R_seq_number == the sequence number of the received message. 790 then the message MUST be discarded 792 Otherwise: 794 1. Create an entry in the Received Set for the receiving 795 interface with: 797 + R_addr = originator address of the received message; 799 + R_seq_number = sequence number of the received message; 801 + R_time = current time + R_HOLD_TIME. 803 2. If the message type is known to the receiving node, then: 805 1. if the message contains a message TLV of type Fragment: 807 1. if the Fragment Set contains all remaining fragments 808 necessary to reconstitute the content, the messages 809 containing these fragments MUST be removed from the 810 fragment set and received message MUST be considered 811 for processing according to Section 4.5; 813 2. otherwise, the message is added to the Fragment Set 814 with a F_time of XXXX (possibly replacing an identical 815 and previous received instance of the same fragment of 816 the same content). 818 2. Otherwise, if the message does not contain a message TLV 819 of type Fragment,the message is considered for processing 820 according to Section 4.5; 822 Otherwise, if the message type is unknown to the receiving 823 node, the message is considered for forwarding according to 824 Section 4.6. 826 Notice that known message types are not automatically considered for 827 forwarding. Forwarding of known message types MUST be specified as a 828 property of processing of that message type. 830 4.5 Message Considered for Processing 832 If a message is considered for processing, the following tasks MUST 833 be performed: 835 1. If an entry exists in the Processed Set where: 837 * P_addr == the originator address of the received message, AND; 839 * P_seq_number == the sequence number of the received message. 841 the message MUST be discarded. 843 2. Otherwise: 845 1. Create an entry in the Processed Set with: 847 + P_addr = originator address of the received message; 849 + P_seq_number = sequence number of the received message; 851 + P_time = current time + P_HOLD_TIME. 853 2. Process message locally, according to the specification for 854 the received message type. 856 3. If a message of a known message type is to be forwarded, the 857 algorithm in Section 4.6 MAY be performed. All forwardable 858 messages defined in this specification (TC, MA) do use the 859 algorithm in Section 4.6. 861 4.6 Message Considered for Forwarding 863 If a message is considered for forwarding, the following tasks MUST 864 be performed: 866 1. If an entry exists in the Forwarded Set where: 868 * F_addr == the originator address of the received message, AND; 870 * F_seq_number == the sequence number of the received message. 872 then the message MUST be discarded 874 2. Otherwise: 876 1. If an entry exists in the Relay Set, where: 878 + RS_if_addr == message source address of the received 879 message 881 2. Create an entry in the Forwarded Set with: 883 - F_addr = originator address of the received message; 885 - F_seq_number = sequence number of the received 886 message; 888 - F_time = current time + F_HOLD_TIME. 890 3. The message header is modified as follows: 892 - decrement the message TTL by 1; 894 - increment the message hop count by 1; 896 4. If the message TTL > 0: 898 - Transmit the message on all OLSRv2 interfaces of the 899 node 901 5. Information Repositories 903 The signaling of OLSRv2 populates a set of information repositories, 904 specified in this section. 906 5.1 Local Link Information Base 908 The local link information base stores information about links 909 between local interfaces and interfaces on adjacent nodes. 911 5.1.1 Link Set 913 A node records a set of "Link Tuples": 915 (L_local_iface_addr, L_neighbor_iface_addr, 916 L_SYM_time, L_ASYM_time, L_willingness, L_time). 918 where: 920 L_local_iface_addr is the interface address of the local node; 922 L_neighbor_iface_addr is the interface address of the neighbor node ; 924 L_SYM_time is the time until which the link is considered symmetric; 926 L_ASYM_time is the time until which the neighbor interface is 927 considered heard; 929 L_willingness is the nodes willingness to be selected as MPR; 931 L_time specifies when this record expires and *MUST* be removed. 933 +-------------+-------------+--------------+ 934 | L_SYM_time | L_ASYM_time | L_STATUS | 935 +-------------+-------------+--------------+ 936 | Expired | Expired | LOST | 937 | | | | 938 | Not Expired | Expired | SYMMETRIC | 939 | | | | 940 | Not Expired | Not Expired | SYMMETRIC | 941 | | | | 942 | Expired | Not Expired | ASYMMETRIC | 943 +-------------+-------------+--------------+ 945 Table 1 947 The status of the link, denoted L_STATUS, can be derived based on the 948 fields L_SYM_time and L_ASYM_time as defined in Table 1. 950 In a node, the set of Link Tuples are denoted the "Link Set". 952 5.1.2 2-hop Neighbor Set 954 A node records a set of "2-hop tuples" 956 (N_local_iface_addr, N_neighbor_iface_addr, N_2hop_iface_addr, N_time) 958 describing symmetric links between its neighbors and the symmetric 959 2-hop neighborhood. 961 N_local_iface_addr is the address of the local interface over which 962 the information was received; 964 N_neighbor_iface_addr is the interface address of a neighbor; 966 N_2hop_iface_addr is the interface address of a 2-hop neighbor with a 967 symmetric link to N_neighbor_iface_addr; 969 specifies the time at which the tuple expires and *MUST* be 970 removed. 972 In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor 973 Set". 975 5.1.3 Neighborhood Address Association Set 977 A node maintains, for each 1-hop and 2-hop neighbor with multiple 978 addresses participating in the OLSRv2 network, a "Neighborhood 979 Address Association Tuple", representing that "these n addresses 980 belong to the same node". 982 (I_neighbor_addr_list, I_time) 984 I_neighbor_iface_addr_list is the list of addresses of the 1-hop or 985 2-hop neighbor node; 987 I_time specifies the time at which the tuple expires and *MUST* be 988 removed. 990 In a node, the set of Neighborhood Address Association Tuples is 991 denoted the "Neighborhood Address Association Set". 993 5.1.4 MPR Set 995 A node maintains a set of neighbors which are selected as MPR. Their 996 interface addresses are listed in the MPR Set. 998 5.1.5 Advertised Neighbor Set 1000 A node maintains a set of neighbor interface addresses, which are to 1001 be advertised through TC messages: 1003 (A_neighbor_iface_addr) 1005 For this set, an Advertised Neighbor Set Sequence Number (ASSN) is 1006 maintained. Each time the Advertised Neighbor Set is updated, the 1007 ASSN MUST be incremented. 1009 5.2 Topology Information Base 1011 Each node in the network maintains topology information about the 1012 network. 1014 For each destination in the network, at least one "Topology Tuple" 1016 (T_dest_iface_addr, T_last_iface_addr, T_seq, T_time) 1018 is recorded. 1020 T_dest_iface_addr is the interface address of a node, which may be 1021 reached in one hop from the node with the interface address 1022 T_last_iface_addr; 1024 T_last_iface_addr is, conversely, the last hop towards 1025 T_dest_iface_addr. Typically, T_last_iface_addr is a MPR of 1026 T_dest_iface_addr; 1028 T_seq is a sequence number, and T_time specifies the time at which 1029 this tuple expires and *MUST* be removed. 1031 In a node, the set of Topology Tuples are denoted the "Topology Set". 1033 6. OLSRv2 Control Messages 1035 OLSRv2 employs two different message types for exchanging protocol 1036 information. Those are HELLO messages, which are locally scoped, and 1037 TC messages, which are globally scoped. 1039 6.1 HELLO Messages 1041 HELLO messages are, in OLSRv2, exchanged between neighbor nodes with 1042 the purpose of populating the local link information base: 1044 o Link Sensing: detecting new and lost adjacent interfaces and 1045 performing bidirectionality check of links; 1047 o 2-hop Neighbor Discovery: detecting the 2-hop symmetric 1048 neighborhood of a node; 1050 o MPR Signaling: signal MPR selection to neighbor nodes and detect 1051 selection of MPRs 1053 HELLO messages are exchanged between neighbor nodes only, i.e. they 1054 are never forwarded by any node. 1056 6.2 TC Messages 1058 TC messages are, in OLSRv2, transmitted to the entire network with 1059 the purpose of populating the topology information base: 1061 o Topology Discovery: ensure that information is present in each 1062 node describing all destinations and (at least) a sufficient 1063 subset of links in order to provide least-hop paths to all 1064 destinations. 1066 TC messages are exchanged within the entire network, i.e. they are 1067 forwarded according to the specification in section Section 4.6. 1069 6.3 MA Messages 1071 MA messages are, in OLSRv2, transmitted by nodes with more than one 1072 address participating in the OLSRv2 network with the purpose of 1073 populating the Neighborhood Address Association Set (NAAS). 1075 MA messages are exchanged within the 2-hop neighborhood of the 1076 originator - i.e. are transmitted with a TTL=2 and are forwarded 1077 according to the specification in section Section 4.6. 1079 7. Populating the MPR Set 1081 Each node MUST select, from among its one-hop neighbors, a subset of 1082 nodes as MPR. This subset MUST be selected such that a message 1083 transmitted by the node, and retransmitted by all its MPR nodes, will 1084 be received by all nodes 2 hops away. 1086 Each node selects its MPR Set individually, utilizing the information 1087 in then neighbor set. Initially, a node will have an empty neighbor- 1088 set, thus, initially the MPR set is empty. A node SHOULD recalculate 1089 its MPR set when a change is detected to the neighbor set or 2-hop 1090 neighbor set. 1092 More specifically, a node MUST calculate MPRs per interface, the 1093 union of the MPR sets of each interface make up the MPR set for the 1094 node. 1096 MPRs are used to flood control messages from a node into the network 1097 while reducing the number of retransmissions that will occur in a 1098 region. Thus, the concept of MPR is an optimization of a classical 1099 flooding mechanism. While it is not essential that the MPR set is 1100 minimal, it is essential that all strict 2-hop neighbors can be 1101 reached through the selected MPR nodes. A node MUST select an MPR 1102 set such that any strict 2-hop neighbor is covered by at least one 1103 MPR node. A node MAY select additional MPRs beyond the minimum set. 1104 Keeping the MPR set small ensures that the overhead of OLSRv2 is kept 1105 at a minimum. 1107 Appendix A contains an example heuristic for selecting MPRs. 1109 8. Populating the Advertised Neighbor Set 1111 The Advertised Neighbor Set contains the set of neighbor addresses, 1112 to which a node advertises links through TC messages. This set 1113 SHOULD at least contain the addresses of the MPR Selector Set (i.e. 1114 all addresses, associated with a MPR selector through the 1115 Neighborhood Adverticed Address Set). This set MAY contain 1116 additional neighbor addresses. 1118 Each time an address is removed from the Advertised Neighbor Set, the 1119 ASSN MUST be incremented. When an address is added to the Advertised 1120 Neighbor Set, the ASSN SHOULD be incremented. 1122 9. HELLO Message Generation 1124 An OLSRv2 HELLO message is composed as described in Section 3.2: a 1125 set of message TLVs, describing general properties of the message and 1126 the node emitting the HELLO, and a set of address blocks (with 1127 associated TLV sets), describing the links and their associated 1128 properties. 1130 OLSRv2 HELLO messages are generated and transmitted per interface, 1131 i.e. different HELLO messages are generated and transmitted per 1132 OLSRv2 interface of a node. 1134 OLSRv2 HELLO messages are generated and transmitted periodically, 1135 with a default interval between two consecutive HELLO emissions on 1136 the same interface of HELLO_INTERVAL. 1138 This section specifies the requirements, which HELLO message 1139 generation MUST fulfill. An example algorithm is proposed in 1140 Appendix B.1. 1142 9.1 HELLO Message: Message TLVs 1144 For each OLSRv2 interface a node MUST generate a HELLO message. In 1145 that HELLO message, a node MAY include a message TLV as specified in 1146 Table 2. 1148 +-------------+-------------------------------------+---------------+ 1149 | TLV Type | TLV Value | Default Value | 1150 +-------------+-------------------------------------+---------------+ 1151 | Willingness | willingness to be selected as MPR. | WILL_DEFAULT | 1152 +-------------+-------------------------------------+---------------+ 1154 Table 2 1156 If a node does not advertise a Willingness TLV in HELLO messages, the 1157 node MUST be assumed to have a willingness of WILL_DEFAULT. 1159 9.2 HELLO Message: Address Blocks and Address TLVs 1161 For each OLSRv2 interface a node MUST generate a HELLO message with 1162 address blocks and address TLVs according to Table 3. 1164 +---------------------------+---------------------------------------+ 1165 | The set of neighbor | TLV (Type = Value) | 1166 | interfaces which are.... | | 1167 +---------------------------+---------------------------------------+ 1168 | HEARD over the interface | (Link Status=HEARD); | 1169 | over which the HELLO is | (Interface=TransmittingInterface) | 1170 | being transmitted | | 1171 | | | 1172 | SYMMETRIC over the | (Link Status=SYMMETRIC); | 1173 | interface over which the | (Interface=TransmittingInterface) | 1174 | HELLO is being | | 1175 | transmitted | | 1176 | | | 1177 | LOST over the interface | (Link Status=LOST); | 1178 | over which the HELLO is | (Interface=TransmittingInterface) | 1179 | being transmitted | | 1180 | | | 1181 | SYMMETRIC over ANY | (Link Status=SYMMETRIC); | 1182 | interface of the node | (Interface=Other) | 1183 | other than the interface | | 1184 | over which the HELLO is | | 1185 | being transmitted | | 1186 | | | 1187 | selected as MPR for the | (Link Status=SYMMETRIC); | 1188 | interface over which the | (Interface=TransmittingInterface); | 1189 | HELLO is transmitted | (MPR Selection=True) | 1190 +---------------------------+---------------------------------------+ 1192 Table 3 1194 10. HELLO Message Processing 1196 Upon receiving a HELLO message, a node will update its local link 1197 information base according to the specification given in this 1198 section. 1200 For the purpose of this section, please notice the following: 1202 o the "validity time" of a message is calculated from the Vtime 1203 field of the message header as specified in Section 17; 1205 o the "originator address" refers to the address, contained in the 1206 "originator address" field of the OLSRv2 message header specified 1207 in Section 3.1; 1209 o a HELLO message MUST neither be forwarded nor be recorded in the 1210 duplicate set; 1212 o the address blocks considered exclude the originator address 1213 block, unless explicitly specified; 1215 o a HELLO message is valid when, for each address listed in the 1216 address blocks: 1218 * the address is associated with at least one TLV with Type=Link 1219 Status, AND 1221 * the address is associated with at least one TLV with 1222 Type=Interface, AND 1224 * all the TLVs with identical type, that the address is 1225 associated with, have identical values (e.g. 1226 Interface=TransmittingInterface is not compatible with 1227 Interface=Other for instance), AND 1229 * if the address is associated with one TLV "MPR Selection=True", 1230 then it MUST be associated also with one TLV "Link 1231 Status=SYMMETRIC". 1233 Invalid HELLO messages are not processed. 1235 10.1 Populating the Link Set 1237 Upon receiving a HELLO message, a node SHOULD update its Link Set 1238 with the information contained in the HELLO. Thus, for each address, 1239 listed in the HELLO message address blocks (see Section 6): 1241 1. if there exists no link tuple with 1243 * L_neighbor_iface_addr == Source Address 1245 a new tuple is created with 1247 * L_neighbor_iface_addr = Source Address; 1249 * L_local_iface_addr = Address of the interface which 1250 received the HELLO message; 1252 * L_SYM_time = current time - 1 (expired); 1254 * L_time = current time + validity time. 1256 2. The tuple (existing or new) with: 1258 * L_neighbor_iface_addr == Source Address 1260 is then modified as follows: 1262 2. if the node finds the address of the interface, which 1263 received the HELLO message, in one of the address blocks 1264 included in message, then the tuple is modified as follows: 1266 1. if the occurrence of L_local_iface_addr in the HELLO 1267 message is associated with a TLV with Type="Link Status" 1268 and value=LOST, and it is also associated with an TLV 1269 with Type="Interface" and Value="TransmittingInterface" 1270 then 1272 - L_SYM_time = current time - 1 (i.e., expired) 1274 2. else if the occurrence of L_local_iface_addr in the HELLO 1275 message is associated with a TLV with Type="Link Status" 1276 and value=SYMMETRIC or HEARD, and it is also associated 1277 with an TLV with Type="Interface" and 1278 Value="TransmittingInterface" then 1280 - L_SYM_time = current time + validity time, 1282 - L_time = L_SYM_time + NEIGHB_HOLD_TIME. 1284 3. L_ASYM_time = current time + validity time; 1286 4. L_time = max(L_time, L_ASYM_time) 1288 3. Additionally, the willingness field is updated as follows: 1290 If a TLV with Type="Willingness" is present in the message 1291 TLVs, then 1293 + L_willingness = Value of the TLV 1295 otherwise: 1297 + L_willingness = WILL_DEFAULT 1299 The rule for setting L_time is the following: a link losing its 1300 symmetry SHOULD still be advertised in HELLOs (with the remaining 1301 status as defined by Table 1) during at least the duration of the 1302 "validity time". This allows neighbors to detect the link breakage. 1304 10.2 Populating the 2-Hop Neighbor Set 1306 Upon receiving a HELLO message from a symmetric neighbor interface, a 1307 node SHOULD update its 2-hop Neighbor Set. 1309 If the Originator Address is the L_local_iface_addr from a link tuple 1310 included in the Link Set with L_STATUS equal to SYMMETRIC (in other 1311 words: if the Originator Address is a symmetric neighbor interface) 1312 then the 2-hop Neighbor Set SHOULD be updated as follows: 1314 1. for each address (henceforth: 2-hop neighbor address), listed in 1315 the HELLO message with a Link Status TLV equal to SYMMETRIC: 1317 1. if the 2-hop neighbor address is an address of the receiving 1318 node: 1320 silently discard the 2-hop neighbor address. 1322 (in other words: a node is not its own 2-hop neighbor). 1324 2. Otherwise, a 2-hop tuple is created with: 1326 + N_local_iface_addr = address of the interface over 1327 which the HELLO message was received; 1329 + N_neighbor_iface_addr = Originator Address of the message; 1331 + N_2hop_iface_addr = 2-hop neighbor address; 1333 + N_time = current time + validity time. 1335 This tuple may replace an older similar tuple with same 1336 N_local_iface_addr, N_neighbor_iface_addr and 1337 N_2hop_iface_addr values. 1339 10.3 Populating the Relay Set 1341 Upon receiving a HELLO message, if a node finds one of its own 1342 interface addresses, listed with an MPR TLV (indicating that the 1343 originator node has selected one of the receiving nodes interfaces as 1344 MPR), the Relay Set SHOULD be updated as follows: 1346 For each address in the originator address block: 1348 1. If there exists no Relay tuple with: 1350 * RS_if_addr == that address 1352 then a new tuple is created with: 1354 * RS_if_addr = that address 1356 2. The tuple (new or otherwise) with 1358 * RS_if_addr == that address 1360 is then modified as follows: 1362 * RS_time = current time + validity time. 1364 Relay tuples are removed upon expiration of RS_time, or upon link 1365 breakage as described in Section 10.4. 1367 10.4 Neighborhood and 2-hop Neighborhood Changes 1369 A change in the neighborhood is detected when: 1371 o The L_SYM_time field of a link tuple expires. This is considered 1372 as a link loss. 1374 o A new link tuple is inserted in the Link Set with a non expired 1375 L_SYM_time or a tuple with expired L_SYM_time is modified so that 1376 L_SYM_time becomes non-expired. This is considered as a link 1377 appearance if there was previously no such link tuple. 1379 A change in the 2-hop neighborhood is detected when a 2-hop neighbor 1380 tuple expires or is deleted according to section Section 10.2. 1382 The following processing occurs when changes in the neighborhood or 1383 the 2-hop neighborhood are detected: 1385 o In case of link loss, all 2-hop tuples with 1387 * N_local_iface_addr == interface address of the node where the 1388 link was lost 1390 * N_neighbor_iface_addr == interface address of the neighbor 1392 MUST be deleted. 1394 o In case of neighbor interface loss, if there exists no link left 1395 to this neighbor node, all MPR selector tuples associated with 1396 that neighbor are deleted. More precisely: 1398 * If there exists an entry in the neighbor address iface 1399 association set where 1401 + I_neighbor_iface_addr_list includes the 1402 N_neighbor_iface_addr of the lost link tuple 1404 AND such has there exists a link tuple such has 1406 + L_neighbor_iface_addr is one of the addresses in 1407 I_neighbor_iface_addr_list 1409 then a link to the neighbor interface was lost, but the 1410 neighbor node itself is still a neighbor (with another link), 1411 and the mpr selector set is not changed, 1413 * otherwise, the neighbor node is lost, and all MPR selector 1414 tuples with MS_iface_addr == interface address of the neighbor 1415 MUST be deleted, along with any interface address associated in 1416 the neighbor address iface association set. 1418 o The MPR set MUST be re-calculated when a link appearance or loss 1419 is detected, or when a change in the 2-hop neighborhood is 1420 detected. 1422 o An additional HELLO message MAY be sent when the MPR set changes. 1424 Additionally, proper update of the sets describing local topology 1425 should be made when a neighbor association address tuple has a list 1426 of addresses which is modified. 1428 11. TC Message Generation 1430 An OLSRv2 TC message is composed as described in Section 3.2: a set 1431 of message TLVs, describing general properties of the message and the 1432 node emitting the TC, and a set of address blocks (with associated 1433 TLV sets), describing the links and their associated properties. 1435 OLSRv2 TC messages are generated and transmitted per node, i.e. the 1436 same TC messages are generated and transmitted on all OLSRv2 1437 interfaces of a node. 1439 OLSRv2 TC messages are generated and transmitted periodically, with a 1440 default interval between two consecutive TC emissions by the same 1441 node of TC_INTERVAL. 1443 11.1 TC Message: Message TLVs 1445 Each OLSRv2 node, selected as MPR (i.e. a node with a non-empty MPR 1446 Selector Set) MUST generate TC messages with message TLVs according 1447 to the following table: 1449 +----------------------+----------------------+---------------------+ 1450 | TLV Type | TLV Value | Default Value | 1451 +----------------------+----------------------+---------------------+ 1452 | Content Seq. no | | | 1455 +----------------------+----------------------+---------------------+ 1457 Table 4 1459 11.2 TC Message: Address Blocks and Address TLVs 1461 Each OLSRv2 node, selected as MPR (i.e. a node with a non-empty MPR 1462 Selector Set) MUST generate TC messages with address blocks and 1463 address TLVs according to the following table: 1465 +---------------------------------+---------------------------------+ 1466 | Addresses | TLVs | 1467 +---------------------------------+---------------------------------+ 1468 | The set of neighbor interfaces, | | 1469 | which have selected the node as | | 1470 | MPR | | 1471 +---------------------------------+---------------------------------+ 1473 Table 5 1475 12. TC Message Processing 1477 Upon receiving a TC message, a node will update its topology 1478 information base according to the specification given in this 1479 section. 1481 For the purpose of this section, please notice the following: 1483 o the "validity time" of a message is calculated from the Vtime 1484 field of the message header as specified in Section 17; 1486 o the "originator address" refers to the address, contained in the 1487 "originator address" field of the OLSRv2 message header specified 1488 in Section 3.1; 1490 o the ASSN of the node, originating the TC message, is recovered as 1491 the value of the Content Seq. no message TLV in the TC message; 1493 Upon receiving a TC message, a node SHOULD update its topology set as 1494 follows: 1496 1. If the sender interface (NB: not originator) address of this 1497 message is not in the symmetric 1-hop neighborhood of this node, 1498 the message MUST be discarded; 1500 2. otherwise, if the TC message does not contain a message-TLV of 1501 type Content Seq. no., the message SHOULD be discarded; 1503 3. otherwise, if there exist some tuple in the topology set where: 1505 T_last_iface_addr == originator address in the message AND 1507 T_seq > ASSN; 1509 then the TC message SHOULD be discarded. 1511 4. The topology set is then updated in two steps: 1513 1. any topology tuple where: 1515 T_last_iface_addr == originator address in the message AND 1517 T_seq < ASSN 1519 SHOULD be removed. 1521 2. For each address, listed in the TC message: 1523 1. if there exists a tuple in the topology set where: 1525 T_dest_iface_addr == advertised neighbor address, AND 1527 T_last_iface_addr == originator address; 1529 then the tuple is updated as follows: 1531 T_time = current time + validity time. 1533 (Note that necessarily: T_seq == ASSN). 1535 2. Otherwise, a new topology tuple is created with: 1537 T_dest_iface_addr == advertised neighbor main address, 1538 AND 1540 T_last_iface_addr == originator address in the message 1541 AND 1543 T_seq == ASSN; 1545 13. MA Message Generation 1547 An OLSRv2 MA message is composed as described in Section 3.2: a set 1548 of message TLVs, describing general properties of the message and the 1549 node emitting the MA, and a set of address blocks (with associated 1550 TLV sets). These address blocks MUST list all addresses of the node 1551 which are participating in the OLSRv2 network. Other addresses of 1552 the node MAY also be included. 1554 An OLSRv2 MA message describes the set of addresses, associated to a 1555 given node. Nodes with a single address SHOULD NOT generate MA 1556 messages. Nodes with multiple addresses, participating in the OLSRv2 1557 network SHOULD generate MA messages. 1559 OLSRv2 MA messages are generated and transmitted per node, i.e. the 1560 same MA messages are generated and transmitted on all OLSRv2 1561 interfaces of a node. 1563 OLSRv2 TC messages are generated and transmitted periodically, with a 1564 default interval between two consecutive MA emissions by the same 1565 node of TC_INTERVAL. 1567 14. MA Message Processing 1569 Upon receiving a MA message the node SHOULD update its Neighborhood 1570 Address Association Set as follows: 1572 1. All neighborhood address association tuples where 1574 * I_neighbor_addr_list contains at least one address which is 1575 listed in the received MA message, 1577 SHOULD be removed, and a new neighborhood address association 1578 tuple SHOULD be created with: 1580 * I_neighbor_addr_list = list of all addresses contained in the 1581 received MA message; 1583 * I_time = current time + validity time. 1585 15. Routing Table Calculation 1587 A node records a set of "routing tuples": 1589 (R_dest_iface_addr, R_next_iface_addr, R_dist, R_iface_addr) 1591 describing the next hop and distance of the path to each destination 1592 in the network for which a route is known. 1594 R_dest_iface_addr is the interface address of the destination node; 1596 R_next_iface_addr is the interface address of the "next hop" on the 1597 path towards R_dest_iface_addr; 1599 R_dist is the number of hops on the path to R_dest_iface_addr; 1601 R_iface_addr is the address of the local interface over which a 1602 packet MUST be sent to reach R_next_iface_addr. 1604 In a node, the set of routing tuples is denoted the "routing set". 1606 The routing set is updated when a change (an entry appearing/ 1607 disappearing) is detected in: 1609 o the link set, 1611 o the neighbor address association set, 1613 o the 2-hop neighbor set, 1615 o the topology set, 1617 Updates to the routing set does not generate or trigger any messages 1618 to be transmitted. The state of the routing set SHOULD, however, be 1619 reflected in the IP routing table by adding and removing entries from 1620 the routing table as appropriate. 1622 To construct the routing set of node X, a shortest path algorithm is 1623 run on the directed graph containing the arcs X -> Y where Y is any 1624 symmetric neighbor of X (with Link Type equal to SYM), the arcs Y -> 1625 Z where Y is a neighbor node with willingness different of WILL_NEVER 1626 and there exists an entry in the 2-hop Neighbor set with Y as 1627 N_neighbor_iface_addr and Z as N_2hop_iface_addr, and the arcs U -> 1628 V, where there exists an entry in the topology set with V as 1629 T_dest_iface_addr and U as T_last_iface_addr. The graph is 1630 complemented with the arcs W0 -> W1 where W0 and W1 are two addresses 1631 of interfaces of a same neighbor (in a neighbor address association 1632 tuple). 1634 The following procedure is given as an example for (re-)calculating 1635 the routing set (with a breadth-first algorithm): 1637 1. All the tuples from the routing set are removed. 1639 2. The new routing tuples are added starting with the symmetric 1640 neighbors (h=1) as the destinations. Thus, for each tuple in the 1641 link set where: 1643 * L_STATUS = SYMMETRIC 1645 a new routing tuple is recorded in the routing set with: 1647 * R_dest_iface_addr = L_neighbor_iface_addr, of the link tuple; 1649 * R_next_iface_addr = L_neighbor_iface_addr, of the link tuple; 1651 * R_dist = 1; 1653 * R_iface_addr = L_local_iface_addr of the link tuple. 1655 3. for each neighbor address association tuple, for which two 1656 addresses A1 and A2 exist in I_neighbor_iface_addr_list where: 1658 * there exists a routing tuple with: 1660 + R_dest_iface_addr = A1 1662 * there is no routing tuple with: 1664 + R_dest_iface_addr = A2 1666 then a tuple in the routing set is created with: 1668 * R_dest_iface_addr = A2; 1670 * R_next_iface_addr = R_next_iface_addr of the route tuple of 1671 A1; 1673 * R_dist = R_dist of the route tuple of A1 (e.g. 1); 1675 * R_iface_addr = R_iface_addr of the route tuple of A1. 1677 4. for each symmetric strict 2-hop neighbor where the 1678 N_neighbor_iface_addr has a willingness different from WILL_NEVER 1679 a tuple in the routing set is created with: 1681 * R_dest_iface_addr = N_2hop_iface_addr of the 2-hop neighbor; 1683 * R_next_iface_addr = the R_next_iface_addr of the route tuple 1684 with: 1686 + R_dest_iface_addr == N_neighbor_iface_addr of the 2-hop 1687 tuple; 1689 * R_dist = 2; 1691 * R_iface_addr = the R_iface_addr of the route tuple with: 1693 + R_dest_iface_addr == N_neighbor_iface_addr of the 2-hop 1694 tuple; 1696 5. The new route tuples for the destination nodes h+1 hops away are 1697 recorded in the routing table. The following procedure MUST be 1698 executed for each value of h, starting with h=2 and incrementing 1699 by 1 for each iteration. The execution will stop if no new tuple 1700 is recorded in an iteration. 1702 1. For each topology tuple in the topology set, if its 1703 T_dest_iface_addr does not correspond to R_dest_iface_addr of 1704 any route tuple in the routing set AND its T_last_iface_addr 1705 corresponds to R_dest_iface_addr of a route tuple whose 1706 R_dist is equal to h, then a new route tuple MUST be recorded 1707 in the routing set (if it does not already exist) where: 1709 + R_dest_iface_addr = T_dest_iface_addr; 1711 + R_next_iface_addr = R_next_iface_addr of the route tuple 1712 where: 1714 - R_dest_iface_addr == T_last_iface_addr 1716 + R_dist = h+1; and 1718 + R_iface_addr = R_iface_addr of the route tuple where: 1720 - R_dest_iface_addr == T_last_iface_addr. 1722 2. Several topology tuples may be used to select a next hop 1723 R_next_iface_addr for reaching the node R_dest_iface_addr. 1724 When h=1, ties should be broken such that nodes with highest 1725 willingness and MPR selectors are preferred as next hop. 1727 16. Proposed Values for Constants 1729 This section list the values for the constants used in the 1730 description of the protocol. 1732 16.1 Message Types 1734 o HELLOv2 = 5 1736 o TCv2 = 6 1738 16.2 Message Intervals 1740 o HELLO_INTERVAL = 2 seconds 1742 o REFRESH_INTERVAL = 2 seconds 1744 o TC_INTERVAL = 5 seconds 1746 16.3 Holding Times 1748 o NEIGHB_HOLD_TIME = 3 x REFRESH_INTERVAL 1750 o TOP_HOLD_TIME = 3 x TC_INTERVAL 1752 o DUP_HOLD_TIME = 30 seconds 1754 16.4 Willingness 1756 o WILL_NEVER = 0 1758 o WILL_LOW = 1 1760 o WILL_DEFAULT = 3 1762 o WILL_HIGH = 6 1764 o WILL_ALWAYS = 7 1766 17. Representing Time 1768 In HELLO messages, the 4 highest bits of the value of the TLV with 1769 Type="Htime" (see Appendix D.2.1) represent the mantissa (a) and the 1770 four lowest bits the exponent (b), yielding that the HELLO interval 1771 is expressed thus: C*(1+a/16)*2^b [in seconds] 1773 Similarily, the validity time is represented by its mantissa (four 1774 highest bits of Vtime field) and by its exponent (four lowest bits of 1775 Vtime field). In other words: 1777 o validity time = C*(1+a/16)* 2^b [in seconds] 1779 where a is the integer represented by the four highest bits of Vtime 1780 field and b the integer represented by the four lowest bits of Vtime 1781 field. The proposed value of the scaling factor C is specified in 1782 Section 16 1784 18. IANA Considerations 1786 OLSRv2 defines a TLV "Type" field for message TLVs and address block 1787 TLVs respectively. Two new registries MUST be created for values for 1788 this TLV type field, with initial assignments as specified in Table 6 1789 and Table 7 1791 Assigned message TLV Types 1793 +--------------------+--------+-------------------------------------+ 1794 | Mnemonic | Value | Description | 1795 +--------------------+--------+-------------------------------------+ 1796 | Fragmentation | 0 | Specifies behavior in case of | 1797 | | | content fragmentation | 1798 | | | | 1799 | Content Sequence | 1 | A sequence number, associated with | 1800 | Number | | the content of the message | 1801 | | | | 1802 | Willingness | 2 | Specifies a nodes willingness [0-7] | 1803 | | | to act as a relay and to parttake | 1804 | | | in network formation | 1805 +--------------------+--------+-------------------------------------+ 1807 Table 6 1809 Assigned address block TLV Types 1811 +--------------------+--------+-------------------------------------+ 1812 | Mnemonic | Value | Description | 1813 +--------------------+--------+-------------------------------------+ 1814 | Link Status | 0 | Specifies a given link's status | 1815 | | | (asymmetric, verified | 1816 | | | bidirectional, lost) | 1817 | | | | 1818 | MPR | 1 | Specifies that a given address is | 1819 | | | selected as MPR | 1820 +--------------------+--------+-------------------------------------+ 1822 Table 7 1824 OLSRv2 message types MUST be assigned from the OLSRv2 repository 1825 (HELLOv2, TCv2) 1827 Appendix A. Example Heuristic for Calculating MPRs 1829 The following specifies a proposed heuristic for selection of MPRs. 1831 In graph theory terms, MPR computation is a "set cover" problem, 1832 which is a difficult optimization problem, but for which an easy and 1833 efficient heuristics exist: the so-called "Greedy Heuristic", a 1834 variant of which is described here. In simple terms, MPR computation 1835 constructs an MPR Set that enables a node to reach any 2-hop 1836 interfaces through relaying by one MPR node. 1838 There are several peripheral issues that the algorithm need to 1839 address. The first one is that some nodes have some willingness 1840 WILL_NEVER. The second one is that some nodes may have several 1841 interfaces. 1843 The algorithm hence need to be precised in the following way: 1845 o All neighbor nodes with willingness equal to WILL_NEVER MUST 1846 ignored in the following algorithm: they are not considered as 1847 neighbors (hence not used as MPR), nor as 2-hop neighbors (hence 1848 no attempt to cover them is made). 1850 o Because link sensing is performed by interface, the local network 1851 topology, is best described in terms of links: hence the algorithm 1852 is considering neighbor interfaces, and 2-hop neighbor interfaces 1853 (and their addresses). Additionally, asymmetric links are 1854 ignored. This is reflected in the definitions below. 1856 o MPR computation is performed on each interface of the node: on 1857 each interface I, the node MUST select some neighbor interface, so 1858 that all 2-hop interfaces are reached. 1860 >From now on, MPR calculation will be described for one interface I 1861 on the node, and the following terminology will be used in describing 1862 the heuristics: 1864 neighbor interface (of I) - An interface of a neighbor to which there 1865 exist a symmetrical link on interface I. 1867 N - the set of such neighbor interfaces 1869 2-hop neighbor interface (of I) An interface of a symmetric strict 1870 2-hop neighbor and which can be reached from a neighbor interface 1871 for I. 1873 N2 - the set of such 2-hop neighbor interfaces 1875 D(y): - the degree of a 1-hop neighbor interface y (where y is a 1876 member of N), is defined as the number of symmetric neighbor 1877 interfaces of node y which are in N2 1879 MPR set - the set of the neighbor interfaces selected as MPR. 1881 The proposed heuristic selects iteratively some interfaces from N as 1882 MPR in order to cover 2-hop neighbor interfaces from N2, as follows: 1884 1. Start with an MPR set made of all members of N with N_willingness 1885 equal to WILL_ALWAYS 1887 2. Calculate D(y), where y is a member of N, for all interfaces in 1888 N. 1890 3. Add to the MPR set those interfaces in N, which are the *only* 1891 nodes to provide reachability to an interface in N2. For 1892 example, if interface B in N2 can be reached only through a 1893 symmetric link to interface A in N, then add interface B to the 1894 MPR set. Remove the interfaces from N2 which are now covered by 1895 a interface in the MPR set. 1897 4. While there exist interfaces in N2 which are not covered by at 1898 least one interface in the MPR set: 1900 1. For each interface in N, calculate the reachability, i.e., 1901 the number of interfaces in N2 which are not yet covered by 1902 at least one node in the MPR set, and which are reachable 1903 through this neighbor interface; 1905 2. Select as a MPR the interface with highest N_willingness 1906 among the interfaces in N with non-zero reachability. In 1907 case of multiple choice select the interface which provides 1908 reachability to the maximum number of interfaces in N2. In 1909 case of multiple interfaces providing the same amount of 1910 reachability, select the interface as MPR whose D(y) is 1911 greater. Remove the interfaces from N2 which are now covered 1912 by an interface in the MPR set. 1914 Other algorithms, as well as improvements over this algorithm, are 1915 possible. For example: 1917 o Some 2-hop neighbors may have several interfaces. The described 1918 algorithm attempts to reach every such interface of the nodes. 1919 However, whenever information that several 2-hop interfaces are, 1920 in fact, interfaces of the same 2-hop neighbor, is available, it 1921 can be used: only one of the interfaces of the 2-hop neighbor 1922 needs to be covered. 1924 o Assume that in a multiple-interface scenario there exists more 1925 than one link between nodes 'a' and 'b'. If node 'a' has selected 1926 node 'b' as MPR for one of its interfaces, then node 'b' can be 1927 selected as MPR with minimal performance loss by any other 1928 interfaces on node 'a'. 1930 Appendix B. Example Algorithms for Generating Control Traffic 1932 The proposed generation of the control messages proceeds in four 1933 steps. HELLO messages, like TC messages consist essentially in a 1934 list of advertised addresses of neighbors (some part of the 1935 topology). 1937 Hence, a first step is to collect the set of relevant of addresses 1938 which are to be advertised. Because there are a number of TLVs which 1939 can be associated to each address (including mandatory ones), this 1940 steps results into a list of addresses, each associated with a 1941 certain number of TLVs. 1943 Thus, the second step is then to regroup the addresses which share 1944 exactly the same TLVs (same Type and same Value), into an address 1945 block which will be associated with a list of TLVs. 1947 The third step is to pack the message header and message TLVs into a 1948 string of octets. 1950 The fourth step consists in packing every address block obtained in 1951 the second step: by finding the longest common prefix of the 1952 addresses in the address block (the head), then, packing the list of 1953 the tail of the addresses into a string of octets, followed by the 1954 TLVs of the address block. 1956 This generation method can be used for TC generation and HELLO 1957 generation: in each case, all what need to be specified is the 1958 message headers, message TLVs, and the list of each address with its 1959 associated TLVs. 1961 The message headers are identical to RFC 3626, and should be filled 1962 in the same way. The orginator address block MUST include all the 1963 addresses of the node (including the one of chosen for originator 1964 address in the message header) 1966 Appendix B.1 Example Algorithm for Generating HELLO messages 1968 This section proposes an algorithm for generating HELLOs 1969 Periodically, on every interface I, the node generates a HELLO 1970 message different on each interface, as follows: 1972 1. First, the list of the links of the interface is collected. It 1973 is the list of the link tuples where: 1975 * L_local_iface_addr == address of the interface 1977 Each corresponding address L_neighbor_iface_addr is then 1978 advertized with the following TLVs: 1980 * Type="Link Status", Value=L_STATUS, status of the link (see 1981 Section 5.1.1) 1983 * Type="Interface" Value="TransmittingInterface" 1985 * Type="MPR Selection", Value="True", if and only of the address 1986 L_neighbor_iface_addr is one interface address in the MPR set. 1988 2. Second, if the node has several interfaces, for each address 1989 which was not previously advertised, and for which there exists a 1990 link tuple on another interface where: 1992 * L_local_iface_addr is different from address of the interface 1993 I 1995 * L_STATUS == SYMMETRIC 1997 the corresponding address L_neighbor_iface_addr is advertized 1998 with the following TLVs: 2000 * Type="Link Status", Value=L_STATUS, status of the link (see 2001 Section 5.1.1) 2003 * Type="Interface" Value="Other" 2005 3. Then a HELLO message is generated using the previous method, with 2006 the proper headers and TLVs: 2008 * a message TLV with Type="Htime" and Value=encoding of the 2009 HELLO generation interval, is added 2011 * a message TLV with Type="Willingness" and Value=the 2012 willingness of the node. If a node has a willingness of 2013 WILL_DEFAULT, a node SHOULD NOT include a TLV with 2014 type="Willingness"; 2016 * the message header including Vtime, which MUST be set to a 2017 value higher than this generation interval, typically 3 times 2018 the generation interval, to allow for message losses. 2020 Appendix B.2 Example Algorithm for Generating TC messages 2022 Periodically, the node generates TC messages, broadcast on all the 2023 interfaces of the node, as follows: 2025 1. Each A_iface_addr in the Advertised Neighbor set, will be 2026 included in the TC message. 2028 2. The TC message is generated using the previous method with the 2029 proper headers, and including the mandatory TC message TLV, 2030 Type="ASSN" Value=the current value of the ASSN of the node. 2032 Appendix C. Protocol and Port Number 2034 Packets in OLSRv2 are communicated using UDP. Port 698 has been 2035 assigned by IANA for exclusive usage by the OLSR (v1 and v2) 2036 protocol. 2038 Appendix D. OLSRv2 Packet and Message Layout 2040 This section specifies the translation from the abstract descriptions 2041 of OLSRv2 control signals, employed in the protocol specification, 2042 and the bit-layout in the control-frames actually exchanged between 2043 the nodes. 2045 Appendix D.1 General OLSR Packet Format 2047 The basic layout of any packet in OLSRv2 is as follows (omitting IP 2048 and UDP headers): 2050 0 1 2 3 2051 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2052 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2053 | Packet Length | Packet Sequence Number | 2054 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2055 | Message Type | Vtime | Message Size | 2056 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2057 | Originator Address | 2058 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2059 | Time To Live | Hop Count | Message Sequence Number | 2060 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2061 | Number of Msg TLVs | Number of Address Blocks | 2062 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2063 | Msg TLV | Msg TLV | | 2064 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 2065 | | 2066 : ... : 2067 | | 2068 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2069 | | Msg TLV | Padding | 2070 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2071 | | 2072 | Originator Address Block: Addr Block 1 | 2073 | | 2074 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2075 | | 2076 | Addr Block 2 | 2077 | | 2078 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2079 | | 2080 : : 2081 | | 2082 (etc.) 2084 The generic packet format defined in RFC3626 encapsulates messages, 2085 similarly to OLSRv1. OLSRv2 messages are defined as new message 2086 types. These messages contain the same header as OLSRv1 messages, 2087 with address blocks and TLVs, as described below. 2089 Appendix D.1.1 Message TLVs 2091 The TLV format (Type-Length-Value) is used to introduce information 2092 in a flexible way. A message TLV associates some information 2093 (depending on the type) with the node/address that originated the 2094 message. 2096 0 1 2 3 2097 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2098 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2099 | Type | Length | | 2100 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 2101 : Value ... : 2102 | | 2103 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2105 Appendix D.1.2 Address Block 2107 An address block is a way of representing addresses, as well as 2108 information associated with addresses, in a compact and flexible way. 2109 The proposed format of an address block is as follows: 2111 0 1 2 3 2112 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2113 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2114 | # addresses | Addr. length | Head length | #TLV | 2115 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2116 | | 2117 : Head : 2118 | | 2119 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2120 | Tail | Tail | | 2121 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 2122 | | 2123 : ... : 2124 | | 2125 + +-+-+-+-+-+-+-+-+-+ 2126 | | Tail | 2127 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2128 | Addr. Block TLV | Addr. Block TLV | | 2129 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 2130 | | 2131 : ... : 2132 | | 2133 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2134 | | Addr. Block TLV | Padding | 2135 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2137 # addresses - The number of addresses in the address block 2139 Addr. length - The length, in bits, of an individual address. For 2140 IPv4 addresses, this field MUST be set to 32 For IPv6 addresses, 2141 this field MUST be set to 128 2143 Prefix length - The length of the common prefix of all the addresses 2144 in the address block. 0 <= Prefix length < Addr. length A prefix 2145 length of 0 indicates, that the prefix field (following) is 2146 absent. 2148 #TLV - The number of TLV's in the address block. 2150 Prefix The longest sequence of bits which is common among all the 2151 addresses, included in the address block. This field is of a 2152 fixed length, as specified in the field "prefix length" 2154 Host The host fields specifies the unique part of all the addresses, 2155 included in the address block. Indeed, letting + denote the 2156 concatenation operator, the expression prefix+host will yield a 2157 unique address. This field os of a fixed length = "Addr. length" 2158 - "Prefix length" 2160 TLV A TLV carries the information, associated to one, or a set of, 2161 addresses in the classic type-length-value format. This format is 2162 explicitly given below. 2164 Padding A variable-length field of all-zero's, to achieve 32-bit 2165 alignment of the packet. 2167 Note that no alignments are attempted -- all alignments happen in the 2168 address block listed above. 2170 Appendix D.1.3 Address Block TLV 2172 Again, the TLV format (Type-Length-Value) is used to introduce 2173 information in a flexible way inside Address Blocks. An Address 2174 Block TLV associates some information with some address(s) listed in 2175 the Address Block. 2177 0 1 2 3 2178 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2179 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2180 | Type | Index Start | Index Stop | Length | 2181 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2182 | Value ... 2183 +-+-+-+-+-+-+-+-+ 2185 Type This field specifies the type of the TLV. 2187 Addr Start This field specifies to which address the TLV applies: the 2188 addresses listed between Index Start and Index Stop. 2190 Addr Stop This field specifies to which address the TLV applies: the 2191 addresses listed between Index Start and Index Stop. 2193 Length This field specifies the length of the data contained in 2194 "Value" 2196 Value This field is a field of the length specified in Length, which 2197 contains data -- information, which is to be interpreted according 2198 to the specification by the "Type" field, and in the context given 2199 by the "addr#" and "Offset" fields. 2201 Appendix D.2 Layout of OLSRv2 Specified Messages 2203 The message format specified for OLSRv2 allows a great deal of 2204 flexibility in how control messages are organized. For example, 2205 while it is possible to represent a sequence of addresses as an 2206 address-block, it is also possible -- although possibly less optimal 2207 -- to represent the same sequence as individual addresses in an 2208 OLSRv2 control message. 2210 This section will, therefore, give an example of how OLSRv2 HELLO and 2211 TC messages typically can be be generated. It is, however, important 2212 to keep in mind that this section presents one possible instance of 2213 HELLO and TC messages. 2215 Appendix D.2.1 Layout of HELLO Messages 2217 HELLO TLVs 2219 +-------------+---------------+------------+-------------------------+ 2220 | Type | Scope | Importance | Description | 2221 +-------------+---------------+------------+-------------------------+ 2222 | Status | Address Block | MUST | SYM, ASYM, LOST | 2223 | | | | | 2224 | MPR | Address Block | MUST | Nodes selected as MPR | 2225 | | | | | 2226 | Willingness | Message | MAY | Willingness information | 2227 | | | | | 2228 | Htime | Message | MUST | Htime information | 2229 +-------------+---------------+------------+-------------------------+ 2231 Table 8 2233 Appendix D.2.2 Layout of TC messages 2235 TC TLVs 2237 +------+-------+------------+-------------------------------------+ 2238 | Type | Scope | Importance | Description | 2239 +------+-------+------------+-------------------------------------+ 2240 | ASSN | Msg | MUST | Advertised Neighbor Sequence Number | 2241 +------+-------+------------+-------------------------------------+ 2243 Table 9 2245 0 1 2 3 2246 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2247 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2248 | TC Msg Type | Vtime | Message Size | 2249 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2250 | Originator Address | 2251 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2252 | Time To Live | Hop Count | Message Sequence Number | 2253 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2254 | Number of Msg TLVs (1) | Number of Address Blocks (1) | 2255 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2256 | ANSN (Message TLV) | 2258 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2259 |# addresses(17)|Addr lgth (32) |Prefx lgth (28)| #TLV (2) | 2261 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2262 | IP Prefix | Host1 | 2264 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2265 | Host2 | Host3 | Host4 | Host5 | Host6 | Host7 | Host8 | Host9 | 2266 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2267 | Host10| Host11| Host12| Host13| Host14| Host15| Host16| Host17| 2268 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2269 | Same Node (Addr. Block TLV) | 2271 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2273 Appendix E. Node Configuration 2275 OLSRv2 does not make any assumption about node addresses, other than 2276 that each node is assumed to have a unique and routable IP address. 2278 When applicable, a recommended way of connecting an OLSR network to 2279 an existing IP routing domain is to assign an IP prefix (under the 2280 authority of the nodes/gateways connecting the MANET with the routing 2281 domain) exclusively to the OLSR area, and to configure the gateways 2282 statically to advertise routes to that IP sequence to nodes in the 2283 existing routing domain. 2285 Appendix E.1 IPv6 Specific Considerations 2287 In the case of IPv6, a node's routable IP address can either be a 2288 global address, or a manet-local address (as described in 2289 draft-wakikawa-manet-ipv6). Typically an OLSRv2 may have several 2290 addresses, for example: a link-local address and a routable address. 2291 However the link-local address is only valid within the 1-hop 2292 neighborhood. It may be used to resolve neighbor state with the 2293 Neighbor Discovery Protocol, but routes to link-local addresses MUST 2294 NOT be advertized and MUST NOT be inserted in routing tables. Only 2295 routable addresses are stored in routing tables, and a routable 2296 address MUST be used for the originator address in HELLO messages and 2297 in TC messages. 2299 OLSRv2 uses a specific flooding address (ff02::3) called the All- 2300 OLSRv2-Multicast address. This address is similar to all nodes/ 2301 routers multicast address in IPv6 specification (i.e. ff02::1 or 2302 ff02::2). The difference is that All-OLSRv2-Multicast specifies that 2303 intended receivers are OLSRv2 nodes. Since the All-OLSRv2-Multicast 2304 address is a link-local address, the message sent to the multicast 2305 address can not reach further than 1 hop. Each OLSRv2 node MUST 2306 process flooding packets and possibly re-flood the packets to the 2307 same destination (ff02::3), if they are designated forwarders. Note 2308 that although ff02::3 is a link-local address, each flooded message 2309 MUST be transmitted with a routable address as originator address. 2311 Appendix F. Security Considerations 2313 Currently, OLSR does not specify any special security measures. As a 2314 proactive routing protocol, OLSR makes a target for various attacks. 2315 The various possible vulnerabilities are discussed in this section. 2317 Appendix F.1 Confidentiality 2319 Being a proactive protocol, OLSR periodically diffuses topological 2320 information. Hence, if used in an unprotected wireless network, the 2321 network topology is revealed to anyone who listens to OLSR control 2322 messages. 2324 In situations where the confidentiality of the network topology is of 2325 importance, regular cryptographic techniques such as exchange of OLSR 2326 control traffic messages encrypted by PGP [9] or encrypted by some 2327 shared secret key can be applied to ensure that control traffic can 2328 be read and interpreted by only those authorized to do so. 2330 Appendix F.2 Integrity 2332 In OLSR, each node is injecting topological information into the 2333 network through transmitting HELLO messages and, for some nodes, TC 2334 messages. If some nodes for some reason, malicious or malfunction, 2335 inject invalid control traffic, network integrity may be compromised. 2336 Therefore, message authentication is recommended. 2338 Different such situations may occur, for instance: 2340 1. a node generates TC messages, advertising links to non-neighbor 2341 nodes; 2343 2. a node generates TC messages, pretending to be another node; 2345 3. a node generates HELLO messages, advertising non-neighbor nodes; 2347 4. a node generates HELLO messages, pretending to be another node; 2349 5. a node forwards altered control messages; 2351 6. a node does not broadcast control messages; 2353 7. a node does not select multipoint relays correctly; 2355 8. a node forwards broadcast control messages unaltered, but does 2356 not forward unicast data traffic; 2358 9. a node "replays" previously recorded control traffic from another 2359 node. 2361 Authentication of the originator node for control messages (for 2362 situation 2, 4 and 5) and on the individual links announced in the 2363 control messages (for situation 1 and 3) may be used as a 2364 countermeasure. However to prevent nodes from repeating old (and 2365 correctly authenticated) information (situation 9) temporal 2366 information is required, allowing a node to positively identify such 2367 delayed messages. 2369 In general, digital signatures and other required security 2370 information may be transmitted as a separate OLSRv2 message type, 2371 thereby allowing that "secured" and "unsecured" nodes can coexist in 2372 the same network, if desired, or signatures and security information 2373 may be transmitted within the OLSRv2 HELLO and TC messages, using the 2374 TLV mechanism. 2376 Specifically, the authenticity of entire OLSRv2 control messages can 2377 be established through employing IPsec authentication headers, 2378 whereas authenticity of individual links (situation 1 and 3) require 2379 additional security information to be distributed. 2381 An important consideration is, that all control messages in OLSR are 2382 transmitted either to all nodes in the neighborhood (HELLO messages) 2383 or broadcast to all nodes in the network (e.g., TC messages). 2385 For example, a control message in OLSRv2 is always a point-to- 2386 multipoint transmission. It is therefore important that the 2387 authentication mechanism employed permits that any receiving node can 2388 validate the authenticity of a message. As an analogy, given a block 2389 of text, signed by a PGP private key, then anyone with the 2390 corresponding public key can verify the authenticity of the text. 2392 Appendix F.3 Interaction with External Routing Domains 2394 OLSRv2 does, through the use of TC messages, provide a basic 2395 mechanism for injecting external routing information to the OLSRv2 2396 domain. Section XXX also specifies that routing information can be 2397 extracted from the topology table or the routing table of OLSR and, 2398 potentially, injected into an external domain if the routing protocol 2399 governing that domain permits. 2401 Other than as described in the section XXX, when operating nodes, 2402 connecting OLSRv2 to an external routing domain, care MUST be taken 2403 not to allow potentially insecure and un-trustworthy information to 2404 be injected from the OLSRv2 domain to external routing domains. Care 2405 MUST be taken to validate the correctness of information prior to it 2406 being injected as to avoid polluting routing tables with invalid 2407 information. 2409 A recommended way of extending connectivity from an existing routing 2410 domain to an OLSRv2 routed MANET is to assign an IP prefix (under the 2411 authority of the nodes/gateways connecting the MANET with the exiting 2412 routing domain) exclusively to the OLSRv2 MANET area, and to 2413 configure the gateways statically to advertise routes to that IP 2414 sequence to nodes in the existing routing domain. 2416 Appendix F.4 Node Identity 2418 OLSR does not make any assumption about node addresses, other than 2419 that each node is assumed to have a unique IP address. 2421 Appendix G. Flow and Congestion Control 2423 TBD 2425 Appendix H. Sequence Numbers 2427 Sequence numbers are used in OLSR with the purpose of discarding 2428 "old" information, i.e., messages received out of order. However 2429 with a limited number of bits for representing sequence numbers, 2430 wrap-around (that the sequence number is incremented from the maximum 2431 possible value to zero) will occur. To prevent this from interfering 2432 with the operation of OLSRv2, the following MUST be observed. 2434 The term MAXVALUE designates in the following the largest possible 2435 value for a sequence number. 2437 The sequence number S1 is said to be "greater than" the sequence 2438 number S2 if: 2440 o S1 > S2 AND S1 - S2 <= MAXVALUE/2 OR 2442 o S2 > S1 AND S2 - S1 > MAXVALUE/2 2444 Thus when comparing two messages, it is possible - even in the 2445 presence of wrap-around - to determine which message contains the 2446 most recent information. 2448 Appendix I. References 2450 o [1] P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. 2451 Increasing reliability in cable free radio LANs: Low level 2452 forwarding in HIPERLAN. Wireless Personal Communications, 1996. 2454 o [2] A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An 2455 efficient technique for flooding in mobile wireless networks. 35th 2456 Annual Hawaii International Conference on System Sciences 2457 (HICSS'2001). 2459 o [3] ETSI STC-RES10 Committee. Radio equipment and systems: 2460 HIPERLAN type 1, functional specifications ETS 300-652, ETSI, June 2461 1996. 2463 o [4] P. Jacquet and L. Viennot, Overhead in Mobile Ad-hoc Network 2464 Protocols, INRIA research report RR-3965, 2000. 2466 o [5] Bradner, S., "Key words for use in RFCs to Indicate 2467 Requirement Levels", BCP 14, RFC 2119, March 1997. 2469 o [6] T. Clausen, G. Hansen, L. Christensen and G. Behrmann. The 2470 Optimized Link State Routing Protocol, Evaluation through 2471 Experiments and Simulation. IEEE Symposium on "Wireless Personal 2472 Mobile Communications", September 2001. 2474 o [7] T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, A. 2475 Qayyum and L. Viennot. Optimized Link State Routing Protocol. 2476 IEEE INMIC Pakistan 2001. [8] Narten, T. and H. Alvestrand, 2477 "Guidelines for Writing an IANA Considerations Section in RFCs", 2478 BCP 26, RFC 2434, October 1998. 2480 o [9] Atkins, D., Stallings, W. and P. Zimmermann, "PGP Message 2481 Exchange Formats", RFC 1991, August 1996. 2483 o [10] P. Jacquet, A. Laouiti, P. Minet, L. Viennot, "Performance 2484 analysis of OLSR multipoint relay flooding in two ad hoc wireless 2485 network models", INRIA research report RR-4260, 2001. 2487 o [11] T. Clausen (ed), P. Jacquet (ed), "The Optimized Link State 2488 Routing Protocol", RFC3626, October 2003 2490 Appendix J. Contributors 2492 This specification is the result of the joint efforts of the 2493 following contributers -- listed alphabetically. 2495 o Cedric Adjih, INRIA, France, 2497 o Emmanuel Baccelli, INRIA, France, 2499 o Thomas Heide Clausen, PCRI, France 2501 o Justin Dean, NRL, USA 2503 o Christopher Dearlove, BAE Systems, UK, 2504 2506 o Satoh Hiroki, Hitachi SDL, Japan, 2508 o Philippe Jacquet, INRIA, France, 2510 o Monden Kazuya, Hitachi SDL, Japan, 2512 o Kenichi Mase, University, Japan, 2514 o Ryuji Wakikawa, KEIO University, Japan, 2516 Appendix K. Acknowledgements 2518 The authors would like to acknowledge the team behind OLSRv1, 2519 specified in RFC3626, including Paul Muhlethaler, Anis Laouiti, 2520 Pascale Minet, Laurent Viennot (all at INRIA, France), and Amir 2521 Qayuum (Center for Advanced Research in Engineering) for their 2522 contributions. 2524 The authors would like to gratefully acknowledge the following people 2525 for intense technical discussions, early reviews and comments on the 2526 specification and its components: Kenichi Mase (Niigata University), 2527 Li Li (CRC), Louise Lamont (CRC), Joe Macker (NRL), Alan Cullen (BAE 2528 Systems), Philippe Jacquet (INRIA), Khaldoun Al Agha (LRI), Richard 2529 Ogier (?), Song-Yean Cho (Samsung Software Center), Shubhranshu Singh 2530 (Samsung AIT) and the entire IETF MANET working group. 2532 Author's Address 2534 Thomas Heide Clausen 2535 LIX, Ecole Polytechnique, France 2537 Phone: +33 6 6058 9349 2538 Email: T.Clausen@computer.org 2539 URI: http://www.lix.polytechnique.fr/Labo/Thomas.Clausen/ 2541 Intellectual Property Statement 2543 The IETF takes no position regarding the validity or scope of any 2544 Intellectual Property Rights or other rights that might be claimed to 2545 pertain to the implementation or use of the technology described in 2546 this document or the extent to which any license under such rights 2547 might or might not be available; nor does it represent that it has 2548 made any independent effort to identify any such rights. Information 2549 on the procedures with respect to rights in RFC documents can be 2550 found in BCP 78 and BCP 79. 2552 Copies of IPR disclosures made to the IETF Secretariat and any 2553 assurances of licenses to be made available, or the result of an 2554 attempt made to obtain a general license or permission for the use of 2555 such proprietary rights by implementers or users of this 2556 specification can be obtained from the IETF on-line IPR repository at 2557 http://www.ietf.org/ipr. 2559 The IETF invites any interested party to bring to its attention any 2560 copyrights, patents or patent applications, or other proprietary 2561 rights that may cover technology that may be required to implement 2562 this standard. Please address the information to the IETF at 2563 ietf-ipr@ietf.org. 2565 Disclaimer of Validity 2567 This document and the information contained herein are provided on an 2568 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 2569 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 2570 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 2571 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 2572 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 2573 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 2575 Copyright Statement 2577 Copyright (C) The Internet Society (2005). This document is subject 2578 to the rights, licenses and restrictions contained in BCP 78, and 2579 except as set forth therein, the authors retain all their rights. 2581 Acknowledgment 2583 Funding for the RFC Editor function is currently provided by the 2584 Internet Society.