idnits 2.17.1 draft-ietf-manet-olsrv2-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 21. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 2737. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 2748. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 2755. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 2761. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust Copyright Line does not match the current year == Line 418 has weird spacing: '...et_addr is th...' == Line 421 has weird spacing: '...AL_dist is th...' == Line 455 has weird spacing: '...RX_type is th...' == Line 458 has weird spacing: '...ig_addr is th...' == Line 460 has weird spacing: '..._number is th...' == (29 more instances...) == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (February 2007) is 6280 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Downref: Normative reference to an Experimental RFC: RFC 3626 (ref. '1') == Outdated reference: A later version (-17) exists of draft-ietf-manet-packetbb-03 == Outdated reference: A later version (-15) exists of draft-ietf-manet-nhdp-01 -- Obsolete informational reference (is this intentional?): RFC 1991 (ref. '5') (Obsoleted by RFC 4880) Summary: 3 errors (**), 0 flaws (~~), 11 warnings (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Mobile Ad hoc Networking (MANET) T. Clausen 3 Internet-Draft LIX, Ecole Polytechnique, France 4 Expires: August 5, 2007 C. Dearlove 5 BAE Systems Advanced Technology 6 Centre 7 P. Jacquet 8 Project Hipercom, INRIA 9 The OLSRv2 Design Team 10 MANET Working Group 11 February 2007 13 The Optimized Link State Routing Protocol version 2 14 draft-ietf-manet-olsrv2-03 16 Status of this Memo 18 By submitting this Internet-Draft, each author represents that any 19 applicable patent or other IPR claims of which he or she is aware 20 have been or will be disclosed, and any of which he or she becomes 21 aware will be disclosed, in accordance with Section 6 of BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF), its areas, and its working groups. Note that 25 other groups may also distribute working documents as Internet- 26 Drafts. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 The list of current Internet-Drafts can be accessed at 34 http://www.ietf.org/ietf/1id-abstracts.txt. 36 The list of Internet-Draft Shadow Directories can be accessed at 37 http://www.ietf.org/shadow.html. 39 This Internet-Draft will expire on August 5, 2007. 41 Copyright Notice 43 Copyright (C) The IETF Trust (2007). 45 Abstract 47 This document describes version 2 of the Optimized Link State Routing 48 (OLSRv2) protocol for mobile ad hoc networks. The protocol embodies 49 an optimization of the classical link state algorithm tailored to the 50 requirements of a mobile ad hoc network (MANET). 52 The key optimization of OLSRv2 is that of multipoint relays, 53 providing an efficient mechanism for network-wide broadcast of link 54 state information (i.e. reducing the cost of performing a network- 55 wide link state broadcast). A secondary optimization is that OLSRv2 56 employs partial link state information: each node maintains 57 information about all destinations, but only a subset of links. 58 Consequently, only selected nodes diffuse link state advertisements 59 (thus reducing the number of network-wide link state broadcasts) and 60 these advertisements contain only a subset of links (thus reducing 61 the size of network-wide link state broadcasts). The partial link 62 state information thus obtained still allows each OLSRv2 node to at 63 all times maintain optimal (in terms of number of hops) routes to all 64 destinations in the network. 66 OLSRv2 imposes minimum requirements on the network by not requiring 67 sequenced or reliable transmission of control traffic. Furthermore, 68 the only interaction between OLSRv2 and the IP stack is routing table 69 management. 71 OLSRv2 is particularly suitable for large and dense networks as the 72 technique of MPRs works well in this context. 74 Table of Contents 76 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 6 77 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 7 78 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 8 79 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 9 80 5. Local Information Base . . . . . . . . . . . . . . . . . . . . 11 81 5.1. Local Attached Network Set . . . . . . . . . . . . . . . . 11 82 6. Processing and Forwarding Repositories . . . . . . . . . . . . 12 83 6.1. Received Set . . . . . . . . . . . . . . . . . . . . . . . 12 84 6.2. Processed Set . . . . . . . . . . . . . . . . . . . . . . 12 85 6.3. Forwarded Set . . . . . . . . . . . . . . . . . . . . . . 13 86 6.4. Relay Set . . . . . . . . . . . . . . . . . . . . . . . . 13 87 7. Packet Processing and Message Forwarding . . . . . . . . . . . 14 88 7.1. Actions when Receiving an OLSRv2 Packet . . . . . . . . . 14 89 7.2. Actions when Receiving an OLSRv2 Message . . . . . . . . . 14 90 7.3. Message Considered for Processing . . . . . . . . . . . . 15 91 7.4. Message Considered for Forwarding . . . . . . . . . . . . 15 92 8. Information Repositories . . . . . . . . . . . . . . . . . . . 18 93 8.1. Neighborhood Information Base . . . . . . . . . . . . . . 18 94 8.1.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . 18 95 8.1.2. MPR Set . . . . . . . . . . . . . . . . . . . . . . . 18 96 8.1.3. MPR Selector Set . . . . . . . . . . . . . . . . . . . 19 97 8.2. Topology Information Base . . . . . . . . . . . . . . . . 19 98 8.2.1. Advertised Neighbor Set . . . . . . . . . . . . . . . 19 99 8.2.2. ANSN History Set . . . . . . . . . . . . . . . . . . . 20 100 8.2.3. Topology Set . . . . . . . . . . . . . . . . . . . . . 20 101 8.2.4. Attached Network Set . . . . . . . . . . . . . . . . . 20 102 8.2.5. Routing Set . . . . . . . . . . . . . . . . . . . . . 21 103 9. Control Message Structures . . . . . . . . . . . . . . . . . . 22 104 9.1. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 22 105 9.1.1. HELLO Message TLVs . . . . . . . . . . . . . . . . . . 23 106 9.1.2. HELLO Message Address Block TLVs . . . . . . . . . . . 23 107 9.2. TC Messages . . . . . . . . . . . . . . . . . . . . . . . 24 108 9.2.1. TC Message TLVs . . . . . . . . . . . . . . . . . . . 24 109 9.2.2. TC Message Address Block TLVs . . . . . . . . . . . . 25 110 10. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 26 111 10.1. HELLO Message: Transmission . . . . . . . . . . . . . . . 26 112 11. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 27 113 11.1. Populating the MPR Selector Set . . . . . . . . . . . . . 27 114 11.2. Symmetric Neighborhood and 2-Hop Neighborhood Changes . . 28 115 12. TC Message Generation . . . . . . . . . . . . . . . . . . . . 29 116 12.1. TC Message: Transmission . . . . . . . . . . . . . . . . . 30 117 13. TC Message Processing . . . . . . . . . . . . . . . . . . . . 32 118 13.1. Initial TC Message Processing . . . . . . . . . . . . . . 32 119 13.1.1. Populating the ANSN History Set . . . . . . . . . . . 32 120 13.1.2. Populating the Topology Set . . . . . . . . . . . . . 33 121 13.1.3. Populating the Attached Network Set . . . . . . . . . 34 123 13.2. Completing TC Message Processing . . . . . . . . . . . . . 34 124 13.2.1. Purging the Topology Set . . . . . . . . . . . . . . . 35 125 13.2.2. Purging the Attached Network Set . . . . . . . . . . . 35 126 14. Populating the MPR Set . . . . . . . . . . . . . . . . . . . . 36 127 15. Populating Derived Sets . . . . . . . . . . . . . . . . . . . 37 128 15.1. Populating the Relay Set . . . . . . . . . . . . . . . . . 37 129 15.2. Populating the Advertised Neighbor Set . . . . . . . . . . 37 130 16. Routing Table Calculation . . . . . . . . . . . . . . . . . . 38 131 17. Proposed Values for Constants . . . . . . . . . . . . . . . . 42 132 17.1. Neighborhood Discovery Constants . . . . . . . . . . . . . 42 133 17.2. Message Intervals . . . . . . . . . . . . . . . . . . . . 42 134 17.3. Holding Times . . . . . . . . . . . . . . . . . . . . . . 42 135 17.4. Jitter Times . . . . . . . . . . . . . . . . . . . . . . . 42 136 17.5. Willingness . . . . . . . . . . . . . . . . . . . . . . . 42 137 18. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . 43 138 19. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 44 139 19.1. Message Types . . . . . . . . . . . . . . . . . . . . . . 44 140 19.2. TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 44 141 20. References . . . . . . . . . . . . . . . . . . . . . . . . . . 46 142 20.1. Normative References . . . . . . . . . . . . . . . . . . . 46 143 20.2. Informative References . . . . . . . . . . . . . . . . . . 46 144 Appendix A. Node Configuration . . . . . . . . . . . . . . . . . 47 145 Appendix B. Protocol and Port Number . . . . . . . . . . . . . . 48 146 Appendix C. Example Heuristic for Calculating MPRs . . . . . . . 49 147 Appendix D. Packet and Message Layout . . . . . . . . . . . . . 52 148 Appendix D.1. Packet and Message Options . . . . . . . . . . . . . 52 149 Appendix D.2. Example HELLO Message . . . . . . . . . . . . . . . 54 150 Appendix D.3. Example TC Message . . . . . . . . . . . . . . . . . 55 151 Appendix E. Time TLVs . . . . . . . . . . . . . . . . . . . . . 58 152 E.1. Representing Time . . . . . . . . . . . . . . . . . . . . 58 153 E.2. General Time TLV Structure . . . . . . . . . . . . . . . . 58 154 E.3. Message TLVs . . . . . . . . . . . . . . . . . . . . . . . 60 155 E.3.1. VALIDITY_TIME TLV . . . . . . . . . . . . . . . . . . 60 156 E.3.2. INTERVAL_TIME TLV . . . . . . . . . . . . . . . . . . 60 157 Appendix F. Message Jitter . . . . . . . . . . . . . . . . . . . 61 158 F.1. Jitter . . . . . . . . . . . . . . . . . . . . . . . . . . 61 159 F.1.1. Periodic message generation . . . . . . . . . . . . . 61 160 F.1.2. Externally triggered message generation . . . . . . . 62 161 F.1.3. Message forwarding . . . . . . . . . . . . . . . . . . 63 162 F.1.4. Maximum Jitter Determination . . . . . . . . . . . . . 64 163 Appendix G. Security Considerations . . . . . . . . . . . . . . 65 164 Appendix G.1. Confidentiality . . . . . . . . . . . . . . . . . . 65 165 Appendix G.2. Integrity . . . . . . . . . . . . . . . . . . . . . 65 166 Appendix G.3. Interaction with External Routing Domains . . . . . 66 167 Appendix G.4. Node Identity . . . . . . . . . . . . . . . . . . . 67 168 Appendix H. Flow and Congestion Control . . . . . . . . . . . . 68 169 Appendix I. Contributors . . . . . . . . . . . . . . . . . . . . 69 170 Appendix J. Acknowledgements . . . . . . . . . . . . . . . . . . 70 171 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 71 172 Intellectual Property and Copyright Statements . . . . . . . . . . 72 174 1. Introduction 176 The Optimized Link State Routing protocol version 2 (OLSRv2) is an 177 update to OLSRv1 as published in RFC3626 [1]. Compared to RFC3626, 178 OLSRv2 retains the same basic mechanisms and algorithms, while 179 providing a more flexible signaling framework and some simplification 180 of the messages being exchanged. Also, OLSRv2 accommodates both IPv4 181 and IPv6 addresses in a compact manner. 183 OLSRv2 is developed for mobile ad hoc networks. It operates as a 184 table driven, proactive protocol, i.e. it exchanges topology 185 information with other nodes in the network regularly. Each node 186 selects a set of its neighbor nodes as "MultiPoint Relays" (MPRs). 187 Control traffic may be diffused through the network using hop by hop 188 forwarding; a node only needs to forward control traffic directly 189 received from its MPR selectors (nodes which have selected it as an 190 MPR). MPRs thus provide an efficient mechanism for diffusing control 191 traffic by reducing the number of transmissions required. 193 Nodes selected as MPRs also have a special responsibility when 194 declaring link state information in the network. A sufficient 195 requirement for OLSRv2 to provide shortest path routes to all 196 destinations is that nodes declare link state information for their 197 MPR selectors, if any. Additional available link state information 198 may be transmitted, e.g. for redundancy. Thus, as well as being used 199 to facilitate efficient flooding, MPRs are also allow the reduction 200 of the number and size of link state messages. MPRs are also thus 201 used as intermediate nodes in multi-hop route calculations. 203 A node selects MPRs from among its one hop neighbors connected by 204 "symmetric", i.e. bi-directional, links. Therefore, selecting routes 205 through MPRs automatically avoids the problems associated with data 206 packet transfer over uni-directional links (such as the problem of 207 not getting link layer acknowledgments at each hop, for link layers 208 employing this technique). 210 OLSRv2 is developed to work independently from other protocols. 211 (Parts of OLSRv2 have been published separately as [3] and [4] for 212 wider use.) Likewise, OLSRv2 makes no assumptions about the 213 underlying link layer. However, OLSRv2 may use link layer 214 information and notifications when available and applicable, as 215 described in [4]. 217 OLSRv2, as OLSRv1, inherits its concept of forwarding and relaying 218 from HIPERLAN (a MAC layer protocol) which is standardized by ETSI 219 [6], [7]. 221 2. Terminology 223 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 224 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 225 document are to be interpreted as described in RFC2119 [2]. 227 MANET specific terminology is to be interpreted as described in [3] 228 and [4]. 230 Additionally, this document uses the following terminology: 232 Node - A MANET router which implements the Optimized Link State 233 Routing protocol version 2 as specified in this document. 235 OLSRv2 interface - A MANET interface, running OLSRv2. 237 Symmetric strict 2-hop neighbor - A symmetric 2-hop neighbor which 238 is not a symmetric 1-hop neighbor and is not a 2-hop neighbor only 239 through a symmetric 1-hop neighbor with willingness WILL_NEVER. 241 Symmetric strict 2-hop neighborhood - The set of the symmetric 242 strict 2-hop neighbors of a node. 244 Multipoint relay (MPR) - A node which is selected by its symmetric 245 1-hop neighbor, node X, to "re-transmit" all the broadcast 246 messages that it receives from node X, provided that the message 247 is not a duplicate, and that the hop limit field of the message is 248 greater than one. 250 MPR selector - A node which has selected its symmetric 1-hop 251 neighbor, node X, as one of its MPRs is an MPR selector of node X. 253 3. Applicability Statement 255 OLSRv2 is a proactive routing protocol for mobile ad hoc networks 256 (MANETs). The larger and more dense a network, the more optimization 257 can be achieved by using MPRs compared to the classic link state 258 algorithm. OLSRv2 enables hop-by-hop routing, i.e. each node using 259 its local information provided by OLSRv2 to route packets. 261 As OLSRv2 continuously maintains routes to all destinations in the 262 network, the protocol is beneficial for traffic patterns where the 263 traffic is random and sporadic between a large subset of nodes, and 264 where the [source, destination] pairs are changing over time: no 265 additional control traffic need be generated in this situation since 266 routes are maintained for all known destinations at all times. Also, 267 since routes are maintained continuously, traffic is subject to no 268 delays due to buffering or to route discovery. 270 OLSRv2 supports nodes which have multiple interfaces which 271 participate in the MANET using OLSRv2. As described in [4], each 272 OLSRv2 interface may have one or more network addresses (which may 273 have prefix lengths). OLSRv2, additionally, supports nodes which 274 have non-OLSRv2 interfaces which can serve as gateways towards other 275 networks. 277 OLSRv2 uses the format specified in [3] for all messages and packets. 278 OLSRv2 is thereby able to allow for extensions via "external" and 279 "internal" extensibility. External extensibility allows a protocol 280 extension to specify and exchange new message types, which can be 281 forwarded and delivered correctly even by nodes which do not support 282 that extension. Internal extensibility allows a protocol extension 283 to define additional attributes to be carried embedded in the 284 standard OLSRv2 control messages detailed in this specification (or 285 any new message types defined by other protocol extensions) using the 286 TLV mechanism specified in [3], while still allowing nodes not 287 supporting that extension to forward messages including the extension 288 and process messages ignoring the extension. 290 The OLSRv2 neighborhood discovery protocol using HELLO messages is 291 specified in [4]; note that all references to MANET interfaces in [4] 292 refer to OLSRv2 interfaces when using [4] as part of OLSRv2. This 293 neighborhood discovery protocol serves to ensure that each OLSRv2 294 node has available continuously updated information repositories 295 describing the node's 1-hop and symmetric 2-hop neighbors. This 296 neighborhood discovery protocol, which also uses [3], is extended in 297 this document by the addition of MPR information. 299 4. Protocol Overview and Functioning 301 OLSRv2 is a proactive routing protocol for mobile ad hoc networks. 302 The protocol inherits the stability of a link state algorithm and has 303 the advantage of having routes immediately available when needed due 304 to its proactive nature. OLSRv2 is an optimization of the classical 305 link state protocol, tailored for mobile ad hoc networks. The main 306 tailoring and optimizations of OLSRv2 are: 308 o periodic, unacknowledged transmission of all control messages; 310 o optimized flooding for global link state information diffusion; 312 o partial topology maintenance - each node knows only a subset of 313 the links in the network, sufficient for a minimum hop route to 314 all destinations. 316 The optimized flooding and partial topology maintenance are based on 317 the concept on MultiPoint Relays (MPRs), selected independently by 318 nodes based on the symmetric 1-hop and 2-hop neighbor information 319 maintained using [4]. 321 Using the message exchange format [3] and the neighborhood discovery 322 protocol [4], OLSRv2 also contains the following main components: 324 o A TLV, to be included within the HELLO messages of [4], allowing a 325 node to signal MPR selection. 327 o An optimized flooding mechanism for global information exchange, 328 denoted "MPR flooding". 330 o A specification of global signaling, denoted TC (Topology Control) 331 messages. TC messages in OLSRv2 serve to: 333 * inject link state information into the entire network; 335 * inject addresses of hosts and networks for which they may serve 336 as a gateway into the entire network. 338 TC messages are emitted periodically, thereby allowing nodes to 339 continuously track global changes in the network. Incomplete TC 340 messages may be used to report additions to advertised information 341 without repeating unchanged information. Some TC messages may be 342 flooded over only part of the network, allowing a node to ensure 343 that nearer nodes are kept more up to date than distant nodes. 345 Each node in the network selects an MPR Set. The MPR Set of a node X 346 may be any subset of its symmetric 1-hop neighborhood such that every 347 node in the symmetric strict 2-hop neighborhood of node X has a 348 symmetric link to a node in the MPR Set of node X. The MPR Set of a 349 node may thus be said to "cover" the node's symmetric strict 2-hop 350 neighborhood. Each node also maintains information about the set of 351 symmetric 1-hop neighbors that have selected it as MPR. This set is 352 called the MPR Selector Set of the node. 354 Note that as long as the condition above is satisfied, any algorithm 355 selecting MPR Sets is acceptable in terms of implementation 356 interoperability. However if smaller MPR Sets are selected then the 357 greater the efficiency gains that are possible. Note that [8] gives 358 an analysis and example of MPR selection algorithms. 360 In OLSRv2, actual efficiency gains are based on the sizes of each 361 node's Relay Set, the set of symmetric 1-hop neighbors for which it 362 is to relay broadcast traffic, and its Advertised Neighbor Set, the 363 set of symmetric 1-hop neighbors for which it is to advertise link 364 state information into the network in TC messages. Each of these 365 sets MUST contain all the nodes in the MPR Selector Set and MAY 366 contain additional nodes. If the Advertised Neighbor Set is empty, 367 TC messages are not generated by that node, unless needed for gateway 368 reporting, or for a short period to accelerate the removal of 369 unwanted links. 371 OLSRv2 is designed to work in a completely distributed manner and 372 does not depend on any central entity. The protocol does not require 373 reliable transmission of control messages: each node sends control 374 messages periodically, and can therefore sustain a reasonable loss of 375 some such messages. Such losses may occur frequently in radio 376 networks due to collisions or other transmission problems. OLSRv2 377 may use "jitter", randomized adjustments to message transmission 378 times, to reduce the incidence of collisions. 380 OLSRv2 does not require sequenced delivery of messages. Each control 381 message contains a sequence number which is incremented for each 382 message. Thus the recipient of a control message can, if required, 383 easily identify which information is more recent - even if messages 384 have been re-ordered while in transmission. 386 OLSRv2 does not require any changes to the format of IP packets, any 387 existing IP stack can be used as is: OLSRv2 only interacts with 388 routing table management. OLSR sends its control messages using UDP. 390 5. Local Information Base 392 A node maintains a Local Information Base that records information 393 about its OLSRv2 interfaces, and its non-OLSRv2 interfaces that can 394 serve as gateways to other networks. The former is maintained using 395 a Local Interface Set, as described in [4]. The latter is maintained 396 using a Local Attached Network Set. All addresses in the Local 397 Information Base have an associated prefix length; if an address 398 otherwise does not have a prefix length then it is set equal to the 399 address length. Two addresses are considered equal if and only if 400 their associated prefix lengths are also equal. 402 The Local Information Base is not modified by this protocol. This 403 protocol may respond to changes of this Local Information Base which 404 MUST reflect corresponding changes in the node's status. It is not 405 the responsibility of OLSRv2 to maintain routes to networks recorded 406 in the Local Attached Network Set in that node. 408 5.1. Local Attached Network Set 410 A node's Local Attached Network Set records its local non-OLSRv2 411 interfaces. that can act as gateways to other networks. It consists 412 of Local Attached Network Tuples: 414 (AL_net_addr, AL_dist) 416 where: 418 AL_net_addr is the network address of an attached network which can 419 be reached via this node. 421 AL_dist is the number of hops to the network with address 422 AL_net_addr from this node. 424 Attached networks with AL_dist == 0 MUST be local to this node and 425 MUST NOT be attached to any other node. Attached networks with 426 AL_dist > 0 MAY be attached to other nodes. 428 Attached networks with AL_dist > 0 MUST be advertised in TC messages 429 generated by this node, this may result in the node originating TC 430 messages when it has no other reason to do so. Attached networks 431 with AL_dist == 0 MAY be advertised in HELLO messages (which causes 432 the MPRs of this node to advertise them in their TC messages) or MAY 433 be advertised in TC messages; they MUST be advertised in one type of 434 message and SHOULD NOT be advertised in both. If a node is sending 435 TC messages for any other reason, then advertising attached networks 436 in TC messages is more efficient. A node MAY decide which form of 437 advertisement to use depending on its circumstances. 439 6. Processing and Forwarding Repositories 441 The following data structures are employed in order to ensure that a 442 message is processed at most once and is forwarded at most once per 443 interface of a node. 445 6.1. Received Set 447 A node's Received Sets, one per OLSRv2 interface, each record the 448 signatures of messages which have been received over that interface. 449 Each consists of Received Tuples: 451 (RX_type, RX_orig_addr, RX_seq_number, RX_time) 453 where: 455 RX_type is the received message type, or zero if the received 456 message sequence number is not type-specific; 458 RX_orig_addr is the originator address of the received message; 460 RX_seq_number is the message sequence number of the received 461 message; 463 RX_time specifies the time at which this Tuple expires and MUST be 464 removed. 466 6.2. Processed Set 468 A node's Processed Set records signatures of messages which have been 469 processed by the node. It consists of Processed Tuples: 471 (P_type, P_orig_addr, P_seq_number, P_time) 473 where: 475 P_type is the processed message type, or zero if the processed 476 message sequence number is not type-specific; 478 P_orig_addr is the originator address of the processed message; 480 P_seq_number is the message sequence number of the processed 481 message; 483 P_time specifies the time at which this Tuple expires and MUST be 484 removed. 486 6.3. Forwarded Set 488 A node's Forwarded Set records signatures of messages which have been 489 processed by the node. It consists of Forwarded Tuples: 491 (F_type, F_orig_addr, F_seq_number, F_time) 493 where: 495 F_type is the forwarded message type, or zero if the forwarded 496 message sequence number is not type-specific; 498 F_orig_addr is the originator address of the forwarded message; 500 F_seq_number is the message sequence number of the forwarded 501 message; 503 F_time specifies the time at which this Tuple expires and MUST be 504 removed. 506 6.4. Relay Set 508 A node's Relay Set records the neighbor interface addresses for which 509 it is to relay flooded messages. It consists of Relay Tuples: 511 (RY_iface_addr) 513 where: 515 RY_iface_addr is the address of a neighbor interface for which the 516 node SHOULD relay flooded messages. This MUST include a prefix 517 length. 519 7. Packet Processing and Message Forwarding 521 On receiving a packet, as defined in [3], a node examines the packet 522 header and each of the message headers. If the message type is known 523 to the node, the message is processed locally according to the 524 specifications for that message type. The message is also 525 independently evaluated for forwarding. 527 7.1. Actions when Receiving an OLSRv2 Packet 529 On receiving a packet, a node MUST perform the following tasks: 531 1. The packet MAY be fully parsed on reception, or the packet and 532 its messages MAY be parsed only as required. (It is possible to 533 parse the packet header, or determine its absence, without 534 parsing any messages. It is possible to divide the packet into 535 messages without even fully parsing their headers. It is 536 possible to determine whether a message is to be forwarded, and 537 to forward it, without parsing its body. It is possible to 538 determine whether a message is to be processed without parsing 539 its body.) 541 2. If parsing fails at any point the relevant entity (packet or 542 message) MUST be silently discarded, other parts of the packet 543 (up to the whole packet) MAY be silently discarded; 545 3. Otherwise if the packet header is present and it contains a 546 packet TLV block, then each TLV in it is processed according to 547 its type if recognized, otherwise the TLV is ignored; 549 4. Otherwise each message in the packet, if any, is treated 550 according to Section 7.2. 552 7.2. Actions when Receiving an OLSRv2 Message 554 A node MUST perform the following tasks for each received OLSRv2 555 message: 557 1. If the received OLSRv2 message header cannot be correctly parsed 558 according to the specification in [3], or if the node recognizes 559 from the originator address of the message that the message is 560 one which the receiving node itself originated, then the message 561 MUST be silently discarded; 563 2. Otherwise: 565 1. If the received message is of a known type then the message 566 is considered for processing according to Section 7.3, AND; 568 2. If for the received message ( + ) > 1, 569 then the message is considered for forwarding according to 570 Section 7.4. 572 7.3. Message Considered for Processing 574 If a message (the "current message") is considered for processing, 575 the following tasks MUST be performed: 577 1. If an entry exists in the Processed Set where: 579 * P_type == the message type of the current message, or 0 if the 580 typedep bit in the message semantics octet (in the message 581 header) of the current message is cleared ('0'), AND; 583 * P_orig_addr == the originator address of the current message, 584 AND; 586 * P_seq_number == the message sequence number of the current 587 message. 589 then the current message MUST NOT be processed. 591 2. Otherwise: 593 1. Create an entry in the Processed Set with: 595 + P_type = the message type of the current message, or 0 if 596 the typedep bit in the message semantics octet (in the 597 message header) of the current message is cleared ('0'); 599 + P_orig_addr = originator address of the current message; 601 + P_seq_number = sequence number of the current message; 603 + P_time = current time + P_HOLD_TIME. 605 2. Process the message according to its type. 607 7.4. Message Considered for Forwarding 609 If a message is considered for forwarding, and it is either of a 610 message type defined in this document or of an unknown message type, 611 then it MUST use the following algorithm. A message type not defined 612 in this document MAY specify the use of this, or another algorithm. 613 (Such an other algorithm MAY use the Received Set for the receiving 614 interface, it SHOULD use the Forwarded Set similarly to the following 615 algorithm.) 616 If a message is considered for forwarding according to this 617 algorithm, the following tasks MUST be performed: 619 1. If the sending interface (as indicated by the source interface of 620 the IP datagram containing the message) does not match (taking 621 into account any address prefix of) any N_neighbor_iface_addr in 622 any Symmetric Neighbor Tuple, then the message MUST be silently 623 discarded. 625 2. Otherwise: 627 1. If an entry exists in the Received Set for the receiving 628 interface, where: 630 + RX_type == the message type, or 0 if the typedep bit in 631 the message semantics octet (in the message header) is 632 cleared ('0'), AND; 634 + RX_orig_addr == the originator address of the received 635 message, AND; 637 + RX_seq_number == the sequence number of the received 638 message. 640 then the message MUST be silently discarded. 642 2. Otherwise: 644 1. Create an entry in the Received Set for the receiving 645 interface with: 647 - RX_type = the message type, or 0 if the typedep bit in 648 the message semantics octet (in the message header) is 649 cleared ('0'); 651 - RX_orig_addr = originator address of the message; 653 - RX_seq_number = sequence number of the message; 655 - RX_time = current time + RX_HOLD_TIME. 657 2. If an entry exists in the Forwarded Set where: 659 - F_type == the message type, or 0 if the typedep bit in 660 the message semantics octet (in the message header) is 661 cleared ('0'); 663 - F_orig_addr == the originator address of the received 664 message, AND; 666 - F_seq_number == the sequence number of the received 667 message. 669 then the message MUST be silently discarded. 671 3. Otherwise if a Relay Tuple exists whose RY_iface_addr 672 matches (taking into account any address prefix) the 673 sending interface (as indicated by the source interface 674 of the IP datagram containing the message): 676 1. Create an entry in the Forwarded Set with: 678 o F_type = the message type, or 0 if the typedep bit 679 in the message semantics octet (in the message 680 header) is cleared ('0'); 682 o F_orig_addr = originator address of the message; 684 o F_seq_number = sequence number of the message; 686 o F_time = current time + F_HOLD_TIME. 688 2. The message header is modified as follows: 690 o Decrement in the message header by 1; 692 o Increment in the message header by 1; 694 3. Transmit the message on all OLSRv2 interfaces of the 695 node. 697 Messages are retransmitted in the format specified by [3] with the 698 ALL-MANET-NEIGHBORS address (see [4]) as destination IP address. 700 8. Information Repositories 702 The purpose of OLSRv2 is to determine the Routing Set, which may be 703 used to update IP's Routing Table, providing "next hop" routing 704 information for IP datagrams. In order to accomplish this, OLSRv2 705 uses a number of protocol sets: the Neighborhood Information Base, 706 provided by [4], is in OLSRv2 augmented by information allowing MPR 707 selection and signaling. Additionally, OLSRv2 specifies a Topology 708 Information Base, which describes the information used for and 709 acquired through TC message exchange - in other words: the Topology 710 Information Base represents the network topology graph as seen from 711 each node. 713 Addresses (other than originator addresses) recorded in the 714 Neighborhood Information Base and the Topology Information Base MUST 715 all be recorded with prefix lengths, in order to allow comparison 716 with addresses received in HELLO and TC messages. 718 8.1. Neighborhood Information Base 720 The Neighborhood Information Base stores information about links 721 between local interfaces and interfaces on adjacent nodes. In 722 addition to the sets described in [4], OLSRv2 adds an element to each 723 Link Tuple to allow a node to record the willingness of a 1-hop 724 neighbor node to be selected as an MPR. Also, OLSRv2 adds an MPR Set 725 and an MPR Selector Set to the Neighborhood Information Base. The 726 MPR Set is used by a node to record which of its symmetric 1-hop 727 neighbors are selected as MPRs, and the MPR Selector Set is used by a 728 node to record which of its symmetric 1-hop neighbors have selected 729 it as MPR. Thus, in addition to what is specified in [4], the MPR 730 Set is used when generating HELLO messages, and the MPR Selector Set 731 is populated when processing HELLO messages. 733 8.1.1. Link Set 735 Link Tuples are as specified in [4], augmented with: 737 L_willingness is the node's willingness to be selected as an MPR; 739 8.1.2. MPR Set 741 A node's MPR Set contains OLSRv2 interface addresses with which the 742 node has a symmetric link and which are of 1-hop symmetric neighbors 743 which the node has selected as MPRs: 745 (MP_neighbor_iface_addr) 747 8.1.3. MPR Selector Set 749 A node's MPR Selector Set records the nodes which have selected this 750 node as an MPR. It consists of MPR Selector Tuples: 752 (MS_neighbor_iface_addr, MS_time) 754 where: 756 MS_neighbor_iface_addr is an OLSRv2 interface address with which 757 this node has a symmetric link and which is of a 1-hop symmetric 758 neighbor which has selected this node as an MPR; 760 MS_time specifies the time at which this Tuple expires and MUST be 761 removed. 763 8.2. Topology Information Base 765 The Topology Information Base stores information, required for the 766 generation and processing of TC messages. The Advertised Neighbor 767 Set contains OLSRv2 interface addresses of symmetric 1-hop neighbors 768 which are to be reported in TC messages. The Topology Set and 769 Attached Network Set both record information received through TC 770 messages. Thus the Advertised Neighbor Set is used for generating TC 771 messages, while the Topology Set and Attached Network Set are 772 populated when processing TC messages. 774 Additionally, a Routing Set is maintained, derived from the 775 information recorded in the Neighborhood Information Base, Topology 776 Set and Attached Network Set. 778 8.2.1. Advertised Neighbor Set 780 A node's Advertised Neighbor Set contains OLSRv2 interface addresses 781 of symmetric 1-hop neighbors which are to be advertised through TC 782 messages: 784 (A_neighbor_iface_addr) 786 In addition, an Advertised Neighbor Set Sequence Number (ANSN) is 787 maintained. Each time the Advertised Neighbor Set is updated, the 788 ANSN MUST be incremented. The ANSN MUST also be incremented if there 789 is a change to the set of Local Attached Network Tuples that are to 790 be advertised in the node's TC messages. 792 8.2.2. ANSN History Set 794 A node's ANSN History Set records information about the freshness of 795 the topology information received from each other node. It consists 796 of ANSN History Tuples: 798 (AH_orig_addr, AH_seq_number, AH_time) 800 where: 802 AH_orig_addr is the originator address of a received TC message, 803 note that this does not include a prefix length; 805 AH_seq_number is the highest ANSN in any TC message received which 806 originated from AH_orig_addr; 808 AH_time is the time at which this Tuple expires and MUST be removed. 810 8.2.3. Topology Set 812 A node's Topology Set records topology information about the network. 813 It consists of Topology Tuples: 815 (T_dest_iface_addr, T_last_iface_addr, T_seq_number, T_time) 817 where: 819 T_dest_iface_addr is an OLSRv2 interface address of a destination 820 node, which may be reached in one hop from the node with the 821 OLSRv2 interface address T_last_iface_addr; 823 T_last_iface_addr is, conversely, an OLSRv2 interface address of a 824 node which is the last hop on a path towards the node with OLSRv2 825 interface address T_dest_iface_addr. 827 T_seq_number is the highest received ANSN associated with the 828 information contained in this Topology Tuple; 830 T_time specifies the time at which this Tuple expires and MUST be 831 removed. 833 8.2.4. Attached Network Set 835 A node's Attached Network Set records information about networks 836 attached to other nodes. It consists of Attached Network Tuples: 838 (AN_net_addr, AN_gw_iface_addr, AN_dist, AN_seq_number, AN_time) 840 where: 842 AN_net_addr is the network address of an attached network, which may 843 be reached via the node with the OLSRv2 interface address 844 AN_gw_iface_addr; 846 AN_gw_iface_addr is the address of an OLSRv2 interface of a node 847 which can act as gateway to the network with address AN_net_addr; 849 AN_dist is the number of hops to the network with address 850 AL_net_addr from the node with address AN_gw_iface_addr. 852 AN_seq_number is the highest received ANSN associated with the 853 information contained in this Attached Network Tuple; 855 AN_time specifies the time at which this Tuple expires and MUST be 856 removed. 858 8.2.5. Routing Set 860 A node's Routing Set records the selected path to each destination 861 for which a route is known. It consists of Routing Tuples: 863 (R_dest_addr, R_next_iface_addr, R_dist, R_local_iface_addr) 865 where: 867 R_dest_addr is the address of the destination, either the address of 868 an OLSRv2 interface of a destination node, or the network address 869 of an attached network; 871 R_next_iface_addr is the OLSRv2 interface address of the "next hop" 872 on the selected path to the destination; 874 R_dist is the number of hops on the selected path to the 875 destination; 877 R_local_iface_addr is the address of the local interface over which 878 a packet MUST be sent to reach the destination. 880 9. Control Message Structures 882 Nodes using OLSRv2 exchange information through messages. One or 883 more messages sent by a node at the same time SHOULD be combined into 884 a single packet. These messages may have originated at the sending 885 node, or have originated at another node and are forwarded by the 886 sending node. Messages with different originators may be combined in 887 the same packet. 889 The packet and message format used by OLSRv2 is defined in [3]. 890 However this specification contains some options which are not used 891 by OLSRv2. In particular (using the syntactical entities defined in 892 [3]): 894 o All OLSRv2 packets, not limited to those defined in this document, 895 include a . 897 o All OLSRv2 packets, not limited to those defined in this document, 898 have the pseqnum bit of cleared ('0'), i.e. 899 they include a packet sequence number. 901 o OLSRv2 packets MAY include packet TLVs, however OLSRv2 itself does 902 not specify any packet TLVs. 904 o All OLSRv2 messages, not limited to those defined in this 905 document, include a full and hence have the noorig 906 and nohops bits of cleared ('0'). 908 o All OLSRv2 message defined in this document have the typedep bit 909 of cleared ('0'). 911 Other options defined in [3] may be freely used, in particular any 912 other values of , or consistent with its specification. 915 The remainder of this section defines, within the framework of [3], 916 message types and TLVs specific to OLSRv2. 918 9.1. HELLO Messages 920 A HELLO message in OLSRv2 is generated as specified in [4]. 921 Additionally, an OLSRv2 node: 923 o MUST include TLV(s) with Type == MPR associated with all OLSRv2 924 interface addresses included in the HELLO message with a TLV with 925 Type == LINK_STATUS and Value == SYMMETRIC if that address is also 926 included in the node's MPR Set (if there is more than one copy of 927 the address, this applies to the specific copy of the address to 928 which the LINK_STATUS TLV is associated); 930 o MUST NOT include any TLVs with Type == MPR associated with any 931 other addresses; 933 o MAY include a message TLV with Type == WILLINGNESS, indicating the 934 node's willingness to be selected as an MPR. 936 9.1.1. HELLO Message TLVs 938 In a HELLO message, a node MAY include a WILLINGNESS message TLV as 939 specified in Table 1. 941 +----------------+------+-------------------+-----------------------+ 942 | Name | Type | Length | Value | 943 +----------------+------+-------------------+-----------------------+ 944 | WILLINGNESS | TBD | 8 bits | The node's | 945 | | | | willingness to be | 946 | | | | selected as MPR; | 947 | | | | unused bits (based on | 948 | | | | the maximum | 949 | | | | willingness value | 950 | | | | WILL_ALWAYS) are | 951 | | | | RESERVED and SHOULD | 952 | | | | be set to zero | 953 +----------------+------+-------------------+-----------------------+ 955 Table 1 957 A node's willingness to be selected as MPR ranges from WILL_NEVER 958 (indicating that a node MUST NOT be selected as MPR by any node) to 959 WILL_ALWAYS (indicating that a node MUST always be selected as MPR). 961 If a node does not advertise a Willingness TLV in HELLO messages, the 962 node MUST be assumed to have a willingness of WILL_DEFAULT. 964 9.1.2. HELLO Message Address Block TLVs 966 In a HELLO message, a node MAY include MPR address block TLV(s) as 967 specified in Table 2. 969 +----------------+------+-------------------+----------------------+ 970 | Name | Type | Length | Value | 971 +----------------+------+-------------------+----------------------+ 972 | MPR | TBD | 0 bits | None | 973 +----------------+------+-------------------+----------------------+ 975 Table 2 977 9.2. TC Messages 979 A TC message MUST contain: 981 o A message TLV with Type == CONT_SEQ_NUM, as specified in 982 Section 9.2.1. 984 o A message TLV with Type == VALIDITY_TIME, as specified in 985 Appendix E. 987 o A first address block containing all of the node's OLSRv2 988 interface addresses. This is similar to the Local Interface Block 989 included in HELLO messages as specified in [4], however in a TC 990 message these addresses MUST be included in the same order in all 991 copies of a given TC message, regardless of which OLSRv2 interface 992 it is transmitted on, and no OTHER_IF address block TLVs are 993 required. 995 o Additional address block(s) containing all addresses in the 996 Advertised Address Set and selected addresses in the Local 997 Attached Network Set, the latter (only) with associated GATEWAY 998 address block TLV(s), as specified in Section 9.2.2. 1000 A TC message MAY contain: 1002 o A message TLV with Type == INTERVAL_TIME, as specified in 1003 Appendix E. 1005 o A message TLV with Type == INCOMPLETE, as specified in 1006 Section 9.2.1. 1008 9.2.1. TC Message TLVs 1010 In a TC message, a node MUST include a CONT_SEQ_NUM message TLV, and 1011 MAY contain an INCOMPLETE message TLV, as specified in Table 3. 1013 +----------------+------+-------------------+-----------------------+ 1014 | Name | Type | Length | Value | 1015 +----------------+------+-------------------+-----------------------+ 1016 | CONT_SEQ_NUM | TBD | 8 bits | The ANSN contained in | 1017 | | | | the Advertised | 1018 | | | | Neighbor Set | 1019 | | | | | 1020 | INCOMPLETE | TBD | 0 bits | None | 1021 +----------------+------+-------------------+-----------------------+ 1023 Table 3 1025 9.2.2. TC Message Address Block TLVs 1027 In a TC message, a node MAY include GATEWAY address block TLV(s) as 1028 specified in Table 4. 1030 +----------------+------+-------------------+-----------------------+ 1031 | Name | Type | Length | Value | 1032 +----------------+------+-------------------+-----------------------+ 1033 | GATEWAY | TBD | 8 bits | Number of hops to | 1034 | | | | attached network | 1035 +----------------+------+-------------------+-----------------------+ 1037 Table 4 1039 10. HELLO Message Generation 1041 An OLSRv2 HELLO message is composed as defined in [4], with the 1042 following additions: 1044 o A message TLV with Type == WILLINGNESS and Value == the node's 1045 willingness to act as an MPR, MAY be included. 1047 o For each address which is included in the message with an 1048 associated TLV with Type == LINK_STATUS, and is of an MPR (i.e. is 1049 an MP_neighbor_iface_addr), an address TLV with Type == MPR MUST 1050 be included; this TLV MUST be associated with the same copy of the 1051 address as is the TLV with Type == LINK_STATUS. 1053 o For address which is included in the message and is not of an MPR 1054 (i.e. is not an MP_neighbor_iface_addr) or is not associated with 1055 a TLV with Type == LINK_STATUS, an address TLV with Type == MPR 1056 MUST NOT be included. 1058 o For each Local Attached Tuple with AL_dist == 0, a node MAY 1059 include AL_net_addr in the Local Interface Block of the message, 1060 with an associated TLV with Type == OTHER_IF. 1062 10.1. HELLO Message: Transmission 1064 HELLO messages are included in packets as specified in [3]. These 1065 packets may contain other messages, including TC messages. 1067 11. HELLO Message Processing 1069 Subsequent to the processing of HELLO messages, as specified in [4], 1070 the node MUST: 1072 1. Determine the willingness of the originating node to be an MPR 1073 by: 1075 * if the HELLO message contains a message TLV with Type == 1076 WILLINGNESS then the willingness is the value of that TLV, 1077 ignoring the reserved bits in that field; 1079 * otherwise the willingness is WILL_DEFAULT. 1081 2. Update each Link Tuple for which any address in its 1082 L_neighbor_iface_addr_list is present in the Local Interface 1083 Block of the HELLO message, with: 1085 * L_willingness = the willingness of the originating node. 1087 3. Update its MPR Selector Set, according to Section 11.1. 1089 11.1. Populating the MPR Selector Set 1091 On receiving a HELLO message: 1093 1. If a node finds one of its OLSRv2 interface addresses with an 1094 associated TLV with Type == MPR in the HELLO message (indicating 1095 that the originator node has selected the receiving node as an 1096 MPR), the MPR Selector Set MUST be updated as follows: 1098 1. For each address, henceforth neighbor address, in the Local 1099 Interface Block of the received HELLO message, where the 1100 neighbor address is present as an N_neighbor_iface_addr in a 1101 Symmetric Neighbor Tuple with N_STATUS == SYMMETRIC: 1103 1. If there exists no MPR Selector Tuple with: 1105 - MS_neighbor_iface_addr == neighbor address 1107 then a new MPR Selector Tuple is created with: 1109 - MS_neighbor_iface_addr = neighbor address 1111 2. The MPR Selector Tuple (new or otherwise) with: 1113 - MS_neighbor_iface_addr == neighbor address 1114 is then modified as follows: 1116 - MS_time = current time + validity time 1118 2. Otherwise if a node finds one of its own interface addresses with 1119 an associated TLV with Type == LINK_STATUS and Value == SYMMETRIC 1120 in the HELLO message, the MPR Selector Set MUST be updated as 1121 follows: 1123 1. All MPR Selector Tuples whose MS_neighbor_iface_addr is in 1124 the Local Interface Block of the HELLO message are removed. 1126 MPR Selector Tuples are also removed upon expiration of MS_time, or 1127 upon symmetric link breakage as described in Section 11.2. 1129 11.2. Symmetric Neighborhood and 2-Hop Neighborhood Changes 1131 A node MUST also perform the following: 1133 1. If a Link Tuple with L_STATUS == SYMMETRIC is removed, or its 1134 L_STATUS changes from SYMMETRIC to HEARD or LOST, and for each 1135 address in that Link Tuple's L_neighbor_iface_addr_list, if it is 1136 an MS_neighbor_iface_addr of an MPR Selector Tuple, then that MPR 1137 Selector Tuple MUST be removed. 1139 2. If any of: 1141 * a Link Tuple is added with L_STATUS == SYMMETRIC, OR; 1143 * a Link Tuple with L_STATUS == SYMMETRIC is removed, or its 1144 L_STATUS changes from SYMMETRIC to HEARD or LOST, or vice 1145 versa, OR; 1147 * a 2-Hop Neighbor Tuple is added or removed, OR; 1149 * the Neighbor Address Association Set is changed such that the 1150 subset of any NA_neighbor_iface_addr_list consisting of those 1151 addresses which are in the L_neighbor_iface_addr_list of a 1152 Link Tuple with L_STATUS == SYMMETRIC is changed, including 1153 the cases of removal or addition of a Neighbor Address 1154 Association Tuple containing any such addresses; 1156 then the MPR Set MUST be recalculated. 1158 An additional HELLO message MAY be sent when the MPR Set changes, in 1159 addition to the cases specified in [4], and subject to the same 1160 constraints. 1162 12. TC Message Generation 1164 A node with one or more OLSRv2 interfaces, and with a non-empty 1165 Advertised Neighbor Set or which acts as a gateway to an associated 1166 network which is to be advertised in the MANET, MUST generate TC 1167 messages. A node with an empty Advertised Neighbor Set and which is 1168 not acting as such a gateway SHOULD also generate "empty" TC messages 1169 for a period A_HOLD_TIME after it last generated a non-empty TC 1170 message. TC messages (non-empty and empty) are generated according 1171 to the following: 1173 1. The message hop count MUST be set to zero. 1175 2. The message hop limit MAY be set to any positive value, this 1176 SHOULD be at least two. A node MAY: 1178 * use the same hop limit in all TC messages, this MUST be at 1179 least equal to the network diameter in hops, a value of 255 is 1180 RECOMMENDED in this case; OR 1182 * use different hop limits in TC messages, this MUST regularly 1183 include messages with hop limit at least equal to the network 1184 diameter, a value of 255 is RECOMMENDED for these messages; 1185 other hop limits SHOULD use a regular pattern with a regular 1186 interval at any given number of hops distance. 1188 3. The message MUST contain a message TLV with Type == CONT_SEQ_NUM 1189 and Value == ANSN from the Advertised Neighbor Set. 1191 4. The message MUST contain a message TLV with Type == 1192 VALIDITY_TIME, as specified in Appendix E.2. If all TC messages 1193 are sent with the same hop limit (usually 255) then this TLV MUST 1194 have Value == T_HOLD_TIME. If TC messages are sent with 1195 different hop limits, then this TLV MUST specify times which vary 1196 with the number of hops distance appropriate to the chosen 1197 pattern of TC message hop limits, these times SHOULD be 1198 appropriate multiples of T_HOLD_TIME. 1200 5. The message MAY contain a message TLV with Type == INTERVAL_TIME, 1201 as specified in Appendix E.2. If all TC messages are sent with 1202 the same hop limit (usually 255) then this TLV MUST have Value == 1203 TC_INTERVAL. If TC messages are sent with different hop limits, 1204 then this TLV MUST specify times which vary with the number of 1205 hops distance appropriate to the chosen pattern of TC message hop 1206 limits, these times SHOULD be appropriate multiples of 1207 TC_INTERVAL. 1209 6. The message MUST contain the addresses of all of its OLSRv2 1210 interfaces in its first address block, note that the TC message 1211 generated on all OLSRv2 interfaces MUST be identical (including 1212 having identical message sequence number) and hence these 1213 addresses are not ordered or otherwise identified according to 1214 the interface on which the TC message is transmitted. 1216 7. The message MUST contain, in address blocks other than its first: 1218 1. A_neighbor_iface_addr from each Advertised Neighbor Tuple; 1220 2. AL_net_addr from each Local Attached Neighbor Tuple with 1221 AL_dist > 0, each associated with a TLV with Type == GATEWAY 1222 and Value == AL_dist. 1224 8. The message MAY contain, in address blocks other than its first: 1226 1. AL_net_addr from each Local Attached Neighbor Tuple with 1227 AL_dist == 0, each associated with a TLV with Type == GATEWAY 1228 and Value == 0. 1230 12.1. TC Message: Transmission 1232 TC messages are generated and transmitted periodically on all OLSRv2 1233 interfaces, with a default interval between two consecutive TC 1234 emissions by the same node of TC_INTERVAL. 1236 TC messages MAY be generated in response to a change of contents, 1237 indicated by a change in ANSN. In this case a node MAY send a 1238 complete TC message, and if so MAY re-start its TC message schedule. 1239 Alternatively a node MAY send only new content in its address blocks 1240 (with appropriate associated TLVs) in which case it MUST include a 1241 message TLV with Type == INCOMPLETE, and MUST NOT re-start its TC 1242 message schedule. This TC message MUST include its usual message 1243 TLVs. Note that a node cannot report removal of advertised content 1244 using an incomplete TC message. 1246 When sending a TC message in response to a change of contents, a node 1247 must respect a minimum interval of TC_MIN_INTERVAL between generated 1248 TC messages. Sending an incomplete TC message MUST NOT cause the 1249 interval between complete TC messages to be increased, and thus a 1250 node MUST NOT send an incomplete TC message if within TC_MIN_INTERVAL 1251 of the next scheduled complete TC message. 1253 The generation of TC messages, whether scheduled or triggered by a 1254 change of contents, and the forwarding of TC messages, MAY be 1255 jittered as described in Appendix F. The values of MAXJITTER used 1256 SHOULD be: 1258 o TP_MAXJITTER for periodic TC message generation; 1260 o TT_MAXJITTER for triggered TC message generation; 1262 o TF_MAXJITTER for TC message forwarding; 1264 TC messages are included in packets as specified in [3]. These 1265 packets may contain other messages, including HELLO messages and TC 1266 messages with different originator addresses. TC messages are 1267 forwarded according to the specification in Section 7.4. 1269 13. TC Message Processing 1271 When according to Section 7.3 a TC message is to be processed 1272 according to its type, this means that: 1274 o if the message does not contain a message TLV with Type == 1275 INCOMPLETE, then processing according to Section 13.1 and then 1276 according to Section 13.2 is carried out; 1278 o if the message contains a message TLV with Type == INCOMPLETE, 1279 then only processing according to Section 13.1 is carried out. 1281 For all processing purposes, "ANSN" is defined as being the value of 1282 the message TLV with Type == CONT_SEQ_NUM in the TC message. If a TC 1283 message has no such TLV then it MUST NOT be processed. 1285 13.1. Initial TC Message Processing 1287 For the purposes of this section, note the following: 1289 o "validity time" is calculated from the VALIDITY_TIME message TLV 1290 in the TC message according to the specification in Appendix E.2; 1292 o "originator address" refers to the originator address in the TC 1293 message header; 1295 o comparisons of sequence numbers are carried out as specified in 1296 Section 18. 1298 The TC message is processed as follows: 1300 1. the ANSN History Set is updated according to Section 13.1.1; if 1301 the TC message is indicated as discarded in that processing then 1302 the following steps are not carried out; 1304 2. the Topology Set is updated according to Section 13.1.2; 1306 3. the Attached Network Set is updated according to Section 13.1.3. 1308 13.1.1. Populating the ANSN History Set 1310 The node MUST update its ANSN History Set as follows: 1312 1. If there is an ANSN History Tuple with: 1314 * AH_orig_addr == originator address; AND 1315 * AH_seq_number > ANSN 1317 then the TC message MUST be discarded. 1319 2. Otherwise 1321 1. If there is no ANSN History Tuple such that: 1323 + AH_orig_addr == originator address; 1325 then create a new ANSN History Tuple with: 1327 + AH_orig_addr = originator address. 1329 2. This ANSN History Tuple (existing or new) is then modified as 1330 follows: 1332 + AH_seq_number = ANSN; 1334 + AH_time = current time + validity time. 1336 13.1.2. Populating the Topology Set 1338 The node MUST update its Topology Set as follows: 1340 1. For each address, henceforth local address, in the first address 1341 block in the TC message: 1343 1. For each address, henceforth advertised address, in an 1344 address block other than the first in the TC message, and 1345 which does not have an associated TLV with Type == GATEWAY: 1347 1. If there is no Topology Tuple such that: 1349 - T_dest_iface_addr == advertised address; AND 1351 - T_last_iface_addr == local address 1353 then create a new Topology Tuple with: 1355 - T_dest_iface_addr = advertised address; 1357 - T_last_iface_addr = local address. 1359 2. This Topology Tuple (existing or new) is then modified as 1360 follows: 1362 - T_seq_number = ANSN; 1364 - T_time = current time + validity time. 1366 13.1.3. Populating the Attached Network Set 1368 The node MUST update its Attached Network Set as follows: 1370 1. For each address, henceforth gateway address, in the first 1371 address block in the TC message: 1373 1. For each address, henceforth network address, in an address 1374 block other than the first in the TC message, and which has 1375 an associated TLV with Type == GATEWAY: 1377 1. If there is no Attached Network Tuple such that: 1379 - AN_net_addr == network address; AND 1381 - AN_gw_iface_addr == gateway address 1383 then create a new Attached Network Tuple with: 1385 - AN_net_addr = network address; 1387 - AN_gw_iface_addr = gateway address. 1389 2. This Attached Network Tuple (existing or new) is then 1390 modified as follows: 1392 - AN_dist = the value of the associated GATEWAY TLV; 1394 - AN_seq_number = ANSN; 1396 - AN_time = current time + validity time. 1398 13.2. Completing TC Message Processing 1400 The TC message is processed as follows: 1402 1. the Topology Set is updated according to Section 13.2.1; 1404 2. the Attached Network Set is updated according to Section 13.2.2. 1406 13.2.1. Purging the Topology Set 1408 The Topology Set MUST be updated as follows: 1410 1. for each address, henceforth local address, in the first address 1411 block of the TC message, all Topology Tuples with: 1413 * T_last_iface_addr == local address; AND 1415 * T_seq_number < ANSN 1417 MUST be removed. 1419 13.2.2. Purging the Attached Network Set 1421 The Attached Network Set MUST be updated as follows: 1423 1. for each address, henceforth local address, in the first address 1424 block of the TC message, all Attached Network Tuples with: 1426 * AN_gw_iface_addr == local address; AND 1428 * AN_seq_number < ANSN 1430 MUST be removed. 1432 14. Populating the MPR Set 1434 Each node MUST select, from among its symmetric 1-hop neighbors, a 1435 subset of nodes as MPRs. This subset MUST be selected such that a 1436 message transmitted by the node, and retransmitted by all its MPRs, 1437 will be received by all of its symmetric strict 2-hop neighbors. 1439 Each node selects its MPR Set individually, utilizing the information 1440 in the Symmetric Neighbor Set, the 2-Hop Neighbor Set and the 1441 Neighborhood Address Association Set. Initially these sets will be 1442 empty, as will be the MPR Set. A node SHOULD recalculate its MPR Set 1443 when a relevant change is made to the Symmetric Neighbor Set, the 1444 2-Hop Neighbor Set or the Neighborhood Address Association Set. 1446 More specifically, a node MUST calculate MPRs per interface, the 1447 union of the MPR Sets of each interface make up the MPR Set for the 1448 node. All OLSRv2 interfaces of nodes selected as MPRs with which the 1449 node has a symmetric link MUST be added to the MPR Set. Also 1450 symmetric 1-hop neighbor nodes with willingness WILL_NEVER (as 1451 recorded in the Link Set) MUST NOT be considered as MPRs. 1453 MPRs are used to flood control messages from a node into the network 1454 while reducing the number of retransmissions that will occur in a 1455 region. Thus, the concept of MPR is an optimization of a classical 1456 flooding mechanism. While it is not essential that the MPR Set is 1457 minimal, it is essential that all symmetric strict 2-hop neighbors 1458 can be reached through the selected MPR nodes. A node MUST select an 1459 MPR Set such that any strict 2-hop neighbor is "covered" by at least 1460 one MPR node. A node MAY select additional MPRs beyond the minimum 1461 set. Keeping the MPR Set small ensures that the overhead of OLSRv2 1462 is kept at a minimum. 1464 Appendix C contains an example heuristic for selecting MPRs. 1466 15. Populating Derived Sets 1468 The Relay Set and the Advertised Neighbor Set of OLSRv2 are denoted 1469 derived sets, since updates to these sets are not directly a function 1470 of message exchanges, but rather are derived from updates to other 1471 sets, in particular the MPR Selector Set. 1473 15.1. Populating the Relay Set 1475 The Relay Set contains the set of OLSRv2 interface addresses of those 1476 symmetric 1-hop neighbors for which a node is supposed to relay 1477 broadcast traffic. This set MUST at least contain all addresses in 1478 the MPR Selector Set (i.e. all MS_neighbor_iface_addr). This set MAY 1479 contain additional symmetric 1-hop neighbor OLSRv2 interface 1480 addresses. 1482 15.2. Populating the Advertised Neighbor Set 1484 The Advertised Neighbor Set contains the set of OLSRv2 interface 1485 addresses of those 1-hop neighbors to which a node advertises a 1486 symmetric link in TC messages. This set MUST at least contain all 1487 addresses in the MPR Selector Set (i.e. all MS_neighbor_iface_addr). 1488 This set MAY contain additional symmetric 1-hop neighbor OLSRv2 1489 interface addresses. 1491 Whenever an address is added to or removed from the Advertised 1492 Neighbor Set, the ANSN MUST be incremented. 1494 16. Routing Table Calculation 1496 The Routing Set is updated when a change (an entry appearing or 1497 disappearing, or changing between SYMMETRIC and LOST) is detected in: 1499 o the Link Set, OR; 1501 o the Neighbor Address Association Set, OR; 1503 o the 2-Hop Neighbor Set, OR; 1505 o the Topology Set, OR; 1507 o the Attached Network Set. 1509 Note that some changes to these sets do not necessitate a change to 1510 the Routing Set, in particular changes to the Link Set which do not 1511 involve Link Tuples with L_STATUS == SYMMETRIC (either before or 1512 after the change), and similar changes to the Neighbor Address 1513 Association Set. A node MAY avoid updating the Routing Set in such 1514 cases. 1516 Updates to the Routing Set do not generate or trigger any messages to 1517 be transmitted. The state of the Routing Set SHOULD, however, be 1518 reflected in the IP routing table by adding and removing entries from 1519 the routing table as appropriate. 1521 To construct the Routing Set of node X, a shortest path algorithm is 1522 run on the directed graph containing 1524 o the arcs X -> Y where there exists a Link Tuple with Y in the 1525 L_neighbor_iface_addr_list and L_STATUS == SYMMETRIC (i.e. Y is a 1526 symmetric 1-hop neighbor of X), AND; 1528 o the arcs Y -> Z where Y is added as above and the Link Tuple with 1529 Y in its L_neighbor_iface_addr_list has L_willingness not equal to 1530 WILL_NEVER, and there exists a 2-Hop Neighbor Tuple with Y as 1531 N2_neighbor_iface_addr and Z as N2_2hop_iface_addr (i.e. Z is a 1532 symmetric 2-hop neighbor of Z through Y, which does not have 1533 willingness WILL_NEVER), AND; 1535 o the arcs U -> V, where there exists a Topology Tuple with U as 1536 T_last_iface_addr and V as T_dest_iface_addr (i.e. this is an 1537 advertised link in the network). 1539 The graph is complemented with: 1541 o arcs Y -> W where there exists a Link Tuple with Y in its 1542 L_neighbor_iface_addr_list and L_STATUS == SYMMETRIC and a 1543 Neighborhood Address Association Tuple with Y and W both contained 1544 in its NA_neighbor_iface_addr_list (i.e. Y and W are both 1545 addresses of the same symmetric 1-hop neighbor), AND; 1547 o arcs U -> T where there exists an Attached Network Tuple with U as 1548 AN_net_addr and T as AN_gw_iface_addr (i.e. U is a gateway to 1549 network T). 1551 The following procedure is given as an example for calculating the 1552 Routing Set using a variation of Dijkstra's algorithm. Thus: 1554 1. All Routing Tuples are removed. 1556 2. For each Link Tuple with L_STATUS == SYMMETRIC, and for each 1557 address (henceforth neighbor address) in that Link Tuple's 1558 L_neighbor_iface_addr_list, a new Routing Tuple is added with: 1560 * R_dest_addr = neighbor address; 1562 * R_next_iface_addr = neighbor address; 1564 * R_dist = 1; 1566 * R_local_iface_addr = neighbor address. 1568 3. For each Neighbor Address Association Tuple, for which two 1569 addresses A1 and A2 are in NA_neighbor_iface_addr_list where: 1571 * there is a Routing Tuple with: 1573 + R_dest_addr == A1 1575 * and there is no Routing Tuple with: 1577 + R_dest_addr == A2 1579 then a Routing Tuple is added with: 1581 * R_dest_addr = A2; 1583 * R_next_iface_addr = R_next_iface_addr of the Routing Tuple in 1584 which R_dest_addr == A1; 1586 * R_dist = 1; 1587 * R_local_iface_addr = R_local_iface_addr of the Routing Tuple 1588 in which R_dest_addr == A1. 1590 4. The following procedure, which adds Routing Tuples for 1591 destination nodes h+1 hops away, MUST be executed for each value 1592 of h, starting with h=2 and incrementing by 1 for each iteration. 1593 The execution MUST stop if no new Routing Tuples are added in an 1594 iteration. 1596 1. For each Topology Tuple, if 1598 + T_dest_iface_addr is not equal to R_dest_addr of any 1599 Routing Tuple, AND; 1601 + T_last_iface_addr is equal to R_dest_addr of a Routing 1602 Tuple whose R_dist == h; 1604 then a new Routing Tuple MUST be added, with: 1606 + R_dest_addr = T_dest_iface_addr; 1608 + R_next_iface_addr = R_next_iface_addr of the Routing Tuple 1609 whose R_dest_addr == T_last_iface_addr; 1611 + R_dist = h+1; 1613 + R_local_iface_addr = R_local_iface_addr of the Routing 1614 Tuple whose R_dest_addr == T_last_iface_addr. 1616 Several Topology Tuples may be used to select a next hop 1617 R_next_iface_addr for reaching the address R_dest_addr. When 1618 h == 1, ties should be broken such that nodes with highest 1619 willingness are preferred, and between nodes of equal 1620 willingness, MPR selectors are preferred over non-MPR 1621 selectors. 1623 2. After the above iteration has completed, if h == 1, for each 1624 2-Hop Neighbor Tuple where: 1626 + N2_2hop_iface_addr is not equal to R_dest_addr of any 1627 Routing Tuple, AND; 1629 + N2_neighbor_iface_addr has a willingness (i.e. the 1630 L_willingness of the Link Tuple whose 1631 L_neighbor_iface_addr_list contains 1632 N2_neighbor_iface_addr) which is not equal to WILL_NEVER; 1634 a Routing Tuple is added with: 1636 + R_dest_addr = N2_2hop_iface_addr of the 2-Hop Neighbor 1637 Tuple; 1639 + R_next_iface_addr = R_next_iface_addr of the Routing Tuple 1640 in which R_dest_addr == N2_neighbor_iface_addr; 1642 + R_dist = 2; 1644 + R_local_iface_addr = R_local_iface_addr of the Routing 1645 Tuple in which R_dest_addr == N2_neighbor_iface_addr. 1647 5. For each Attached Network Tuple, if 1649 * AN_net_addr is not equal to R_dest_addr of any Routing Tuple, 1650 AND; 1652 * AN_gw_iface_addr is equal to R_dest_addr of a Routing Tuple; 1654 then a new Routing Tuple MUST be added, with: 1656 * R_dest_addr = AN_net_addr; 1658 * R_next_iface_addr = R_next_iface_addr of the Routing Tuple 1659 whose R_dest_addr == AN_gw_iface_addr; 1661 * R_dist = (R_dist of the Routing Tuple whose R_dest_addr == 1662 AN_gw_iface_addr) + AN_dist; 1664 * R_local_iface_addr = R_local_iface_addr of the Routing Tuple 1665 whose R_dest_addr == AN_gw_iface_addr. 1667 If more than one Attached Network Tuple has the same AN_net_addr, 1668 then more than one Routing Tuple MUST NOT be added, and the added 1669 Routing Tuple MUST have minimum R_dist. 1671 17. Proposed Values for Constants 1673 This section list the values for the constants used in the 1674 description of the protocol. These proposed values are appropriate 1675 to the case where all TC messages are sent with the same hop limit 1676 (usually 255). 1678 17.1. Neighborhood Discovery Constants 1680 The constants HELLO_INTERVAL, REFRESH_INTERVAL, HELLO_MIN_INTERVAL, 1681 H_HOLD_TIME, L_HOLD_TIME, N_HOLD_TIME, HP_MAXJITTER, HT_MAXJITTER and 1682 C are used as in [4]. 1684 17.2. Message Intervals 1686 o TC_INTERVAL = 5 seconds 1688 o TC_MIN_INTERVAL = TC_INTERVAL/4 1690 17.3. Holding Times 1692 o T_HOLD_TIME = 3 x TC_INTERVAL 1694 o A_HOLD_TIME = T_HOLD_TIME 1696 o P_HOLD_TIME = 30 seconds 1698 o RX_HOLD_TIME = 30 seconds 1700 o F_HOLD_TIME = 30 seconds 1702 17.4. Jitter Times 1704 o TP_MAXJITTER = HP_MAXJITTER 1706 o TT_MAXJITTER = HT_MAXJITTER 1708 o TF_MAXJITTER = TT_MAXJITTER 1710 17.5. Willingness 1712 o WILL_NEVER = 0 1714 o WILL_DEFAULT = 3 1716 o WILL_ALWAYS = 7 1718 18. Sequence Numbers 1720 Sequence numbers are used in OLSRv2 with the purpose of discarding 1721 "old" information, i.e. messages received out of order. However with 1722 a limited number of bits for representing sequence numbers, wrap- 1723 around (that the sequence number is incremented from the maximum 1724 possible value to zero) will occur. To prevent this from interfering 1725 with the operation of OLSRv2, the following MUST be observed when 1726 determining the ordering of sequence numbers. 1728 The term MAXVALUE designates in the following one more than the 1729 largest possible value for a sequence number. For a 16 bit sequence 1730 number (as are those defined in this specification) MAXVALUE is 1731 65536. 1733 The sequence number S1 is said to be "greater than" the sequence 1734 number S2 if: 1736 o S1 > S2 AND S1 - S2 < MAXVALUE/2 OR 1738 o S2 > S1 AND S2 - S1 > MAXVALUE/2 1740 When sequence numbers S1 and S2 differ by MAXVALUE/2 their ordering 1741 cannot be determined. In this case, which should not occur, either 1742 ordering may be assumed. 1744 Thus when comparing two messages, it is possible - even in the 1745 presence of wrap-around - to determine which message contains the 1746 most recent information. 1748 19. IANA Considerations 1750 19.1. Message Types 1752 OLSRv2 defines one message type, which must be allocated from the 1753 "Assigned Message Types" repository of [3]. 1755 +--------------------+-------+--------------------------------------+ 1756 | Mnemonic | Value | Description | 1757 +--------------------+-------+--------------------------------------+ 1758 | TC | TBD | Topology Control (global signaling) | 1759 +--------------------+-------+--------------------------------------+ 1761 Table 5 1763 19.2. TLV Types 1765 OLSRv2 defines three message TLV types, which must be allocated from 1766 the "Assigned message TLV Types" repository of [3]. 1768 +--------------------+-------+--------------------------------------+ 1769 | Mnemonic | Value | Description | 1770 +--------------------+-------+--------------------------------------+ 1771 | WILLINGNESS | TBD | Specifies the originating node's | 1772 | | | willingness to act as a relay and to | 1773 | | | partake in network formation | 1774 | | | | 1775 | CONT_SEQ_NUM | TBD | Specifies a content sequence number | 1776 | | | for this message | 1777 | | | | 1778 | INCOMPLETE | TBD | Specifies that this message is | 1779 | | | incomplete | 1780 +--------------------+-------+--------------------------------------+ 1782 Table 6 1784 OLSRv2 defines two Address Block TLV types, which must be allocated 1785 from the "Assigned address block TLV Types" repository of [3]. 1787 +--------------------+-------+--------------------------------------+ 1788 | Mnemonic | Value | Description | 1789 +--------------------+-------+--------------------------------------+ 1790 | MPR | TBD | Specifies that a given address is | 1791 | | | selected as MPR | 1792 | | | | 1793 | GATEWAY | TBD | Specifies that a given address is | 1794 | | | reached via a gateway on the | 1795 | | | originating node | 1796 +--------------------+-------+--------------------------------------+ 1798 Table 7 1800 20. References 1802 20.1. Normative References 1804 [1] Clausen, T. and P. Jacquet, "The Optimized Link State Routing 1805 Protocol", RFC 3626, October 2003. 1807 [2] Bradner, S., "Key words for use in RFCs to Indicate Requirement 1808 Levels", RFC 2119, BCP 14, March 1997. 1810 [3] Clausen, T., Dean, J., Dearlove, C., and C. Adjih, "Generalized 1811 MANET Packet/Message Format", work in 1812 progress draft-ietf-manet-packetbb-03.txt, January 2007. 1814 [4] Clausen, T., Dean, J., and C. Dearlove, "MANET Neighborhood 1815 Discovery Protocol (NHDP)", work in 1816 progress draft-ietf-manet-nhdp-01.txt, February 2007. 1818 20.2. Informative References 1820 [5] Atkins, D., Stallings, W., and P. Zimmermann, "PGP Message 1821 Exchange Formats", RFC 1991, August 1996. 1823 [6] ETSI, "ETSI STC-RES10 Committee. Radio equipment and systems: 1824 HIPERLAN type 1, functional specifications ETS 300-652", 1825 June 1996. 1827 [7] Jacquet, P., Minet, P., Muhlethaler, P., and N. Rivierre, 1828 "Increasing reliability in cable free radio LANs: Low level 1829 forwarding in HIPERLAN.", 1996. 1831 [8] Qayyum, A., Viennot, L., and A. Laouiti, "Multipoint relaying: 1832 An efficient technique for flooding in mobile wireless 1833 networks.", 2001. 1835 Appendix A. Node Configuration 1837 OLSRv2 does not make any assumption about node addresses, other than 1838 that each node is assumed to have at least one unique and routable IP 1839 address for each interface that it has which participates in the 1840 MANET. 1842 When applicable, a recommended way of connecting an OLSRv2 network to 1843 an existing IP routing domain is to assign an IP prefix (under the 1844 authority of the nodes/gateways connecting the MANET with the routing 1845 domain) exclusively to the OLSRv2 area, and to configure the gateways 1846 statically to advertise routes to that IP sequence to nodes in the 1847 existing routing domain. 1849 Appendix B. Protocol and Port Number 1851 Packets in OLSRv2 are communicated using UDP. Port 698 has been 1852 assigned by IANA for exclusive usage by the OLSR (v1 and v2) 1853 protocol. 1855 Appendix C. Example Heuristic for Calculating MPRs 1857 The following specifies a proposed heuristic for selection of MPRs. 1859 In graph theory terms, MPR computation is a "set cover" problem, 1860 which is a difficult optimization problem, but for which an easy and 1861 efficient heuristics exist: the so-called "Greedy Heuristic", a 1862 variant of which is described here. In simple terms, MPR computation 1863 constructs an MPR Set that enables a node to reach any symmetric 1864 2-hop neighbors by relaying through an MPR node. 1866 There are several peripheral issues that the algorithm needs to 1867 address. The first one is that some nodes have some willingness 1868 WILL_NEVER. The second one is that some nodes may have several 1869 interfaces. 1871 The algorithm hence can be summarized by: 1873 o All 1-hop neighbor nodes with willingness equal to WILL_NEVER MUST 1874 ignored in the following algorithm: they are not considered as 1875 1-hop neighbors (hence not used as MPRs). 1877 o Because link sensing is performed by interface, the local network 1878 topology is best described in terms of links: hence the algorithm 1879 is considering 1-hop neighbor OLSRv2 interfaces, and 2-hop 1880 neighbor OLSRv2 interfaces (and their addresses). Additionally, 1881 asymmetric links are ignored. This is reflected in the 1882 definitions below. 1884 o MPR computation is performed on each interface of the node: on 1885 each interface I, the node MUST select some neighbor interfaces, 1886 so that all 2-hop neighbor interfaces are reached. 1888 From now on, MPR calculation will be described for one interface I on 1889 the node, and the following terminology will be used in describing 1890 the heuristics: 1892 neighbor interface (of I) - An OLSRv2 interface of a 1-hop neighbor 1893 to which there exist a symmetric link using interface I. 1895 N - the set of such neighbor interfaces 1897 2-hop neighbor interface (of I) An interface of a symmetric strict 1898 2-hop neighbor which can be reached from a neighbor interface for 1899 I. 1901 N2 - the set of such 2-hop neighbor interfaces 1903 D(y): - the degree of a 1-hop neighbor interface y (where y is a 1904 member of N), is defined as the number of symmetric neighbor 1905 interfaces of node y which are in N2 1907 MPR Set - the set of the neighbor interfaces selected as MPRs. 1909 The proposed heuristic selects iteratively some interfaces from N as 1910 MPRs in order to cover 2-hop neighbor interfaces from N2, as follows: 1912 1. Start with an MPR Set made of all members of N with L_willingness 1913 equal to WILL_ALWAYS 1915 2. Calculate D(y), where y is a member of N, for all interfaces in 1916 N. 1918 3. Add to the MPR Set those interfaces in N, which are the *only* 1919 nodes to provide reachability to an interface in N2. For 1920 example, if interface B in N2 can be reached only through a 1921 symmetric link to interface A in N, then add interface B to the 1922 MPR Set. Remove the interfaces from N2 which are now covered by a 1923 interface in the MPR Set. 1925 4. While there exist interfaces in N2 which are not covered by at 1926 least one interface in the MPR Set: 1928 1. For each interface in N, calculate the reachability, i.e., 1929 the number of interfaces in N2 which are not yet covered by 1930 at least one node in the MPR Set, and which are reachable 1931 through this neighbor interface; 1933 2. Select as an MPR the interface with highest L_willingness 1934 among the interfaces in N with non-zero reachability. In 1935 case of multiple choice select the interface which provides 1936 reachability to the maximum number of interfaces in N2. In 1937 case of multiple interfaces providing the same amount of 1938 reachability, select the interface as MPR whose D(y) is 1939 greater. Remove the interfaces from N2 which are now covered 1940 by an interface in the MPR Set. 1942 Other algorithms, as well as improvements over this algorithm, are 1943 possible. For example: 1945 o Assume that in a multiple interface scenario there exists more 1946 than one link between nodes 'a' and 'b'. If node 'a' has selected 1947 node 'b' as MPR for one of its interfaces, then node 'b' can be 1948 selected as MPR with minimal performance loss by any other 1949 interfaces on node 'a'. 1951 o In a multiple interface scenario MPRs are selected for each 1952 interface of the selecting node, providing full coverage of all 1953 2-hop nodes accessible through that interface. The overall MPR 1954 Set is then the union of these sets. These sets do not however 1955 have to be selected independently, if a node is selected as an MPR 1956 for one interface it may be automatically added to the MPR 1957 selection for other interfaces. 1959 Appendix D. Packet and Message Layout 1961 This appendix illustrates the translation from the abstract 1962 descriptions of packets employed in the protocol specification, and 1963 the bit-layout packets actually exchanged between the nodes. 1965 Appendix D.1. Packet and Message Options 1967 The basic layout of an OLSRv2 packet is as described in [3]. However 1968 the following points should be noted. 1970 In the following figures, reserved bits marked Reserved or Resv MUST 1971 be cleared ('0'). Octets indicated as Padding are optional and MAY 1972 be omitted; if not omitted they SHOULD be used to pad to a 32 bit 1973 boundary and MUST all be zero. 1975 OLSRv2 uses only packets with a packet header including a packet 1976 sequence number, either with or without a packet TLV block. Thus all 1977 OLSRv2 packets have the layout of either 1979 0 1 2 3 1980 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 1981 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1982 |0 0 0 0 0 0 0 0| Reserved |0|0| Packet Sequence Number | 1983 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1984 | | 1985 | Message + Padding | 1986 | | 1987 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1988 | | 1989 : ... : 1990 | | 1991 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1992 | | 1993 | Message + Padding | 1994 | | 1995 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1997 or 1998 0 1 2 3 1999 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 2000 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2001 |0 0 0 0 0 0 0 0| Reserved |1|0| Packet Sequence Number | 2002 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2003 | | 2004 | Packet TLV Block | 2005 | | 2006 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2007 | | Padding | 2008 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2009 | | 2010 | Message + Padding | 2011 | | 2012 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2013 | | 2014 : ... : 2015 | | 2016 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2017 | | 2018 | Message + Padding | 2019 | | 2020 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2022 OLSRv2 uses only messages with a complete message header. Thus all 2023 OLSRv2 messages, plus padding if any, have the following layout. 2025 0 1 2 3 2026 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 2027 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2028 | Message Type | Resv |N|0|0| Message Size | 2029 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2030 | Originator Address | 2031 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2032 | Hop Limit | Hop Count | Message Sequence Number | 2033 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2034 | | 2035 | Message Body | 2036 | | 2037 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2038 | | Padding | 2039 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2041 In standard OLSRv2 messages (HELLO and TC) the type dependent 2042 sequence number bit marked N MUST be cleared ('0'). 2044 The layouts of the message body, address block, TLV block and TLV are 2045 as in [3], allowing all options. Standard (HELLO and TC) messages 2046 contain a first address block which contains local interface address 2047 information, all other address blocks contain neighbor interface 2048 address information (or for a TC message address information for 2049 which it is a gateway) specific to the message type. 2051 Appendix D.2. Example HELLO Message 2053 An example HELLO message, using IPv4 (four octet) addresses is as 2054 follows. The overall message length is 58 octets. The message has a 2055 hop limit of 1 and a hop count of 0, as sent by its originator. 2057 The message has a message TLV block with content length 12 octets 2058 containing three message TLVs. These TLVs represent message validity 2059 time, message interval time and willingness. Each uses a TLV with 2060 semantics value 4, indicating no start and stop indexes are included, 2061 and each has a value length of 1 octet. 2063 The first address block contains 1 local interface address. The 2064 semantics octet 2 indicates it has no tail section. It has head 2065 length 4, this is equal to the address length, it thus has no mid 2066 section. This address block has no TLVs (TLV block content length is 2067 0 octets). 2069 The second, and last, address block includes 4 neighbor interface 2070 addresses. The semantics octet 2 indicates they have no tail 2071 section. The addresses have head length 3 octets, thus each mid 2072 section is of length one octet. The following address TLV block 2073 (content length 11 octets) includes two TLVs. 2075 The first of these TLVs reports the link status of all four neighbors 2076 in a single multivalue TLV, the first two addresses are HEARD, the 2077 last two addresses are SYMMETRIC. The TLV semantics octet value of 2078 20 indicates, in addition to that this is a multivalue TLV, that no 2079 start index and stop index are included, hence values for all 2080 addresses are included. The TLV value length of 4 octets indicates 2081 one octet per value per address. 2083 The second of these TLVs indicates that the last address (start index 2084 3, stop index 3) is an MPR. This TLV has no value, or value length, 2085 fields, as indicated by its semantics octet being equal to 2. 2087 0 1 2 3 2088 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 2089 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2090 | HELLO |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0| 2091 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2092 | Originator Address | 2093 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2094 |0 0 0 0 0 0 0 1|0 0 0 0 0 0 0 0| Message Sequence Number | 2095 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2096 |0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0| VALIDITY_TIME |0 0 0 0 0 1 0 0| 2097 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2098 |0 0 0 0 0 0 0 1| Value | INTERVAL_TIME |0 0 0 0 0 1 0 0| 2099 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2100 |0 0 0 0 0 0 0 1| Value | WILLINGNESS |0 0 0 0 0 1 0 0| 2101 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2102 |0 0 0 0 0 0 0 1| Value |0 0 0 0 0 0 0 1|0 0 0 0 0 0 1 0| 2103 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2104 |0 0 0 0 0 1 0 0| Head | 2105 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2106 | Head (cont) |0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 1 0 0| 2107 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2108 |0 0 0 0 0 0 1 0|0 0 0 0 0 0 1 1| Head | 2109 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2110 | Head (cont) | Mid | Mid | Mid | 2111 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2112 | Mid |0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1| LINK_STATUS | 2113 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2114 |0 0 0 1 0 1 0 0|0 0 0 0 0 1 0 0| HEARD | HEARD | 2115 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2116 | SYMMETRIC | SYMMETRIC | MPR |0 0 0 0 0 0 1 0| 2117 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2118 |0 0 0 0 0 0 1 1|0 0 0 0 0 0 1 1| 2119 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2121 Appendix D.3. Example TC Message 2123 An example TC message, using IPv4 (four octet) addresses, is as 2124 follows. The overall message length is 67 octets. 2126 The message has a message TLV block with content length 13 octets 2127 containing three TLVs. The first two TLVs are validity and interval 2128 times as for the HELLO message above. The third TLV is a content 2129 sequence number TLV used to carry the 2 octet ANSN. The semantics 2130 value is also 4. 2132 The message has three address blocks. The first address block 2133 contains 3 local interface addresses (with semantics octet 2, hence 2134 no tail section, head length 2 octets, and hence mid sections with 2135 length two octets) and has no TLVs (TLV block content length 0 2136 octets). 2138 The other two address blocks contain neighbor interface addresses. 2139 The first contains 3 addresses (semantics octet 2, no tail section, 2140 head length 2 octets, hence mid sections length two octets) and has 2141 no TLVs (TLV block content length 0 octets). The second contains 1 2142 address, with semantics octet 4 indicating that the tail section, 2143 length 2 octets, consists of zero valued octets (not included). The 2144 following TLV block (content length 6 octets) includes two TLVs, the 2145 first (semantics value 4 indicating no indexes are needed) indicates 2146 that the address has a netmask, with length given by the value (of 2147 length 1 octet) of 16. Thus this address is Head.0.0/16. The second 2148 TLV indicates that the originating node is a gateway to this network, 2149 at a given number of hops distance. The TLV semantics value of 4 2150 indicates that no indexes are needed. 2152 0 1 2 3 2153 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 2154 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2155 | TC |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0| 2156 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2157 | Originator Address | 2158 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2159 | Hop Limit | Hop Count | Message Sequence Number | 2160 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2161 |0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1| VALIDITY_TIME |0 0 0 0 0 1 0 0| 2162 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2163 |0 0 0 0 0 0 0 1| Value | INTERVAL_TIME |0 0 0 0 0 1 0 0| 2164 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2165 |0 0 0 0 0 0 0 1| Value | CONT_SEQ_NUM |0 0 0 0 0 1 0 0| 2166 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2167 |0 0 0 0 0 0 1 0| Value (ANSN) |0 0 0 0 0 0 1 1| 2168 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2169 | 0x02 |0 0 0 0 0 0 1 0| Head | 2170 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2171 | Mid | Mid | 2172 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2173 | Mid |0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0| 2174 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2175 |0 0 0 0 0 0 1 1| 0x02 |0 0 0 0 0 0 1 0| Head | 2176 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2177 | Head (cont) | Mid | Mid | 2178 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2179 | Mid (cont) | Mid |0 0 0 0 0 0 0 0| 2180 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2181 |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 1|0 0 0 0 0 1 0 0|0 0 0 0 0 0 1 0| 2182 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2183 | Head |0 0 0 0 0 0 1 0|0 0 0 0 0 0 0 0| 2184 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2185 |0 0 0 0 0 1 1 1| PREFIX_LENGTH |0 0 0 0 0 1 0 0|0 0 0 0 0 0 0 1| 2186 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2187 |0 0 0 1 0 0 0 0| GATEWAY |0 0 0 0 0 1 0 0| Number Hops | 2188 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2190 Appendix E. Time TLVs 2192 This appendix specifies a general time TLV structure for expressing 2193 either single time values or a set of time values with each value 2194 associated with a range of distances. Furthermore, using this 2195 general time TLV structure, this document specifies the INTERVAL_TIME 2196 and VALIDITY_TIME TLVs, which are used by OLSRv2. 2198 E.1. Representing Time 2200 This document specifies a TLV structure in which time values are each 2201 represented in an 8 bit time code, one or more of which may be used 2202 in a TLV's value field. Of these 8 bits, the least significant four 2203 bits represent the mantissa (a), and the most significant four bits 2204 represent the exponent (b), so that: 2206 o time value = (1 + a/16) * 2^b * C 2208 o time code = 16 * b + a 2210 All nodes in the network MUST use the same value of C, which will be 2211 specified in seconds, hence so will be all time values. Note that 2212 ascending values of the time code represent ascending time values, 2213 time values may thus be compared by comparison of time codes. 2215 An algorithm for computing the time code representing the smallest 2216 representable time value not less than the time value t is: 2218 1. find the largest integer b such that t/C >= 2^b; 2220 2. set a = 16 * (t / (C * 2^b) - 1), rounded up to the nearest 2221 integer; 2223 3. if a == 16 then set b = b + 1 and set a = 0; 2225 4. if a and b are in the range 0 and 15 then the required time value 2226 can be represented by the time code 16 * b + a, otherwise it can 2227 not. 2229 The minimum time value that can be represented in this manner is C. 2230 The maximum time value that can be represented in this manner is 2231 63488 * C. 2233 E.2. General Time TLV Structure 2235 A Time TLV may be a packet, message or address block TLV. If it is a 2236 packet or message TLV then it must be a single value TLV as defined 2237 in [3]; if it is an address block TLV then it may be single value or 2238 multivalue TLV. The specific Time TLVs specified in this document, 2239 in Appendix E.3 are message, and hence single value, TLVs. Note that 2240 even a single value Time TLV may contain a multiple octet 2241 field. 2243 The purpose of a single value Time TLV is to allow a single time 2244 value to be determined by a node receiving an entity containing the 2245 Time TLV, based on its distance from the entity's originator. The 2246 Time TLV may contain information that allows that time value to be a 2247 function of distance, and thus different receiving nodes may 2248 determine different time values. If a receiving node will not be 2249 able to determine its distance from the originating node, then the 2250 form of this Time TLV with a single time code in a field (or 2251 single value subfield) SHOULD be used. 2253 The field of a single value Time TLV is specified, using the 2254 regular expression syntax of [3], by: 2256 = {