idnits 2.17.1 draft-ietf-ospf-manet-or-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 15. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 1527. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1538. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1545. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1551. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- == There are 2 instances of lines with non-RFC3849-compliant IPv6 addresses in the document. If these are example addresses, they should be changed. -- The document has examples using IPv4 documentation addresses according to RFC6890, but does not use any IPv6 documentation addresses. Maybe there should be IPv6 examples, too? Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust Copyright Line does not match the current year == The document seems to use 'NOT RECOMMENDED' as an RFC 2119 keyword, but does not include the phrase in its RFC 2119 key words list. -- 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 2008) is 5914 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Obsolete normative reference: RFC 2740 (ref. 'OSPFv3') (Obsoleted by RFC 5340) ** Obsolete normative reference: RFC 2434 (ref. 'IANA') (Obsoleted by RFC 5226) == Outdated reference: A later version (-08) exists of draft-ietf-ospf-lls-03 Summary: 3 errors (**), 0 flaws (~~), 4 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group M. Chandra (Editor) 3 Internet-Draft A. Roy (Editor) 4 Intended status: Standards Track Cisco Systems 5 Expires: August 2008 February 2008 7 Extensions to OSPF to Support Mobile Ad Hoc Networking 8 draft-ietf-ospf-manet-or-00 10 Status of this Memo 12 By submitting this Internet-Draft, each author represents that any 13 applicable patent or other IPR claims of which he or she is aware 14 have been or will be disclosed, and any of which he or she becomes 15 aware will be disclosed, in accordance with Section 6 of BCP 79. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that 19 other groups may also distribute working documents as Internet- 20 Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt. 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 Copyright Notice 35 Copyright (C) The IETF Trust (2008). 37 Abstract 39 This document describes extensions to OSPF to support mobile ad hoc 40 networking. Specifically, the document specifies a mechanism for 41 link-local signaling, a OSPF-MANET interface, a simple technique to 42 reduce the size of Hello packets by only transmitting incremental 43 state changes, and a method for optimized flooding of routing 44 updates. 46 Table of Contents 48 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 49 1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . 3 50 1.2 Motivation for extending OSPF to support MANETs . . . . . 4 51 2. Specification of Requirements . . . . . . . . . . . . . . . 4 52 3. Proposed Enhancements . . . . . . . . . . . . . . . . . . . 4 53 3.1 OSPF-MANET Interface . . . . . . . . . . . . . . . . . . . 5 54 3.1.1 Interface Operation . . . . . . . . . . . . . . . . . 6 55 3.1.2 LSA Formats and Examples . . . . . . . . . . . . . . . 6 56 3.2 Incremental OSPF-MANET Hellos . . . . . . . . . . . . . . 10 57 3.2.1 The I Option Bit . . . . . . . . . . . . . . . . . . . 10 58 3.2.2 State Check Sequence TLV . . . . . . . . . . . . . . . 11 59 3.2.3 Neighbor Drop TLV . . . . . . . . . . . . . . . . . . 12 60 3.2.4 'Request From' TLV (RF-TLV) . . . . . . . . . . . . . 12 61 3.2.5 Full State For TLV (FSF-TLV) . . . . . . . . . . . . . 12 62 3.2.6 Neighbor Adjacencies . . . . . . . . . . . . . . . . . 13 63 3.2.7 Sending Hellos . . . . . . . . . . . . . . . . . . . . 14 64 3.2.8 Receiving Hellos . . . . . . . . . . . . . . . . . . . 15 65 3.2.9 Interoperability . . . . . . . . . . . . . . . . . . . 17 66 3.2.10 Support for OSPF Graceful Restart . . . . . . . . . 17 67 3.3 Optimized Flooding (Overlapping Relays) . . . . . . . . . 17 68 3.3.1 Operation Overview . . . . . . . . . . . . . . . . . . 18 69 3.3.2 Determination of Overlapping Relays . . . . . . . . . 18 70 3.3.3 Terminology . . . . . . . . . . . . . . . . . . . . . 19 71 3.3.4 Overlapping Relay Discovery Process . . . . . . . . . 19 72 3.3.5 The F Option Bit . . . . . . . . . . . . . . . . . . . 20 73 3.3.6 Active Overlapping Relay Extension . . . . . . . . . . 20 74 3.3.7 Willingness TLV . . . . . . . . . . . . . . . . . . . 22 75 3.3.8 Flooding and Relay Decisions . . . . . . . . . . . . . 22 76 3.3.9 Intelligent Transmission of Link State 77 Acknowledgements . . . . . . . . . . . . . . . . . . . 24 78 3.3.10 Important Timers . . . . . . . . . . . . . . . . . . 24 79 3.3.11 Miscellaneous Protocol Considerations . . . . . . . 25 80 3.3.12 Interoperability . . . . . . . . . . . . . . . . . . 26 81 3.4 New Bits in OSPFv3 Option Field . . . . . . . . . . . . . 26 82 3.5 Smart Peering . . . . . . . . . . . . . . . . . . . . . . . 26 83 3.5.1 Introduction . . . . . . . . . . . .. . . . . . . . . . . 26 84 3.5.2 Previous Related Work . . . . . . .. . . . . . . . . . . 27 85 3.5.3 Proposed Solution . . . . . . . . .. . . . . . . . . . . 27 86 4. Security Considerations . . . . . . . . . . . . . . . . . . 30 87 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . 31 88 6. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 31 89 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 32 90 References . . . . . . . . . . . . . . . . . . . . . . . . . 32 91 Normative References . . . . . . . . . . . . . . . . . . 32 92 Informative References . . . . . . . . . . . . . . . . . 33 93 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 33 94 Intellectual Property and Copyright Statements . . . . . . . 34 96 1. Introduction 98 Mobile Ad Hoc Networks have been an area of study for some time, 99 within various working groups and areas within the IETF, various 100 Military branches, and various government agencies. Recently, 101 networks with mobile ad hoc requirements are being proposed and 102 seriously considered for deployment in the near term, which means the 103 concepts and research now needs to be applied to deployed networks. 104 Towards that end, this draft applies many of the principles and 105 concepts learned through prior work to [OSPFv3], along with new 106 concepts based on current requirements. 108 1.1 Problem Statement 110 MANETs are synonymous with packet radio networks, which have been 111 around since the 1960s in a limited military capacity. With the boom 112 of mobile devices and wireless communications, MANETs are finding 113 scope in commercial and military environments. The aim of these 114 networks is to support robust and efficient communication in a mobile 115 wireless network by incorporating routing functionality into mobile 116 nodes. 118 A MANET is an autonomous set of nodes distributed over a wide 119 geographical area that communicate over bandwidth-constrained 120 wireless links. Each node may represent a transmitter, receiver, or 121 relay station with varying physical capabilities. Packets may 122 traverse through several intermediate (relay) nodes before reaching 123 their destination. These networks typically lack infrastructure: 124 nodes are mobile, there is no central hub or controller, and thus 125 there is no fixed network topology. Moreover, MANETs must contend 126 with a difficult and variable communication environment. Packet 127 transmissions are plagued by the usual problems of radio 128 communication, which include propagation path loss, signal multipath 129 and fading, and thermal noise. These effects vary with terminal 130 movement, which also induces Doppler spreading in the frequency of 131 the transmitted signal. Finally, transmissions from neighboring 132 terminals, known as multi-access interference, hostile jammers, and 133 impulsive interference, e.g., ignition systems, generators, and other 134 non-similar in-band communications, may contribute additional 135 interference. 137 Given this nature of MANETs, the existence of a communication link 138 between a pair of nodes is a function of their variable link quality, 139 including signal strength and bandwidth. Thus, routing paths vary 140 based on environment, and the resulting network topology. In such 141 networks, the topology may be stable for periods of time, and then 142 suddenly become unpredictable. Since MANETs are typically 143 decentralized systems, there are no central controllers or specially 145 designated routers to determine the routing paths as the topology 146 changes. All of the routing decisions and forwarding (relaying) of 147 packets must be done by the nodes themselves, and communication is on 148 a peer-to-peer basis. 150 1.2 Motivation for extending OSPF to support MANETs 152 The motivation to extend a standard protocol, OSPF (described in 153 [OSPF] and [OSPFv3]) to operate on MANET networks is twofold. The 154 primary reason is for interoperability--MANET devices need to be able 155 to work when plugged into a wireline network in as many cases as 156 possible. The junction point between a MANET and wire-line network 157 should also be as fluid as possible, allowing a MANET network to 158 "plug in" to just about any location within a wire-line network, and 159 find connectivity, etc., as needed. 161 While routes could be redistributed between two routing protocols, 162 one designed just for wire-line networks, and the other just for 163 MANET networks, this adds complexity and overhead to the MANET/ 164 wireline interface, increases the odds of an error being introduced 165 between the two domains, and decreases flexibility. 167 The second motivation is that OSPF is a well understand and widely 168 deployed routing protocol. This provides a strong basis of 169 experience and skills from which to work. A protocol which is known 170 to work can be extended, rather than developing a new protocol, which 171 must then be completely troubleshoot, tested, and modified over a 172 number of years. Working with a well known protocol allows 173 development effort to be placed in a narrowly focused area, rather 174 than rebuilding, from scratch, many things which are already known to 175 work. 177 2. Requirements notation 179 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 180 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 181 document are to be interpreted as described in [KEY]. 183 3. Proposed Enhancements 185 This document proposes modifications to [OSPFv3] to support mobile ad 186 hoc networks (MANETs). Note that it is possible to use the mechanism 187 defined in Section "Incremental OSPF-MANET Hellos" and the mechanism 188 defined in Section "Optimized Flooding (Overlapping Relays)" 189 independently of one another. 191 The challenges with deploying standard [OSPFv3] in a MANET 192 environment fit into two categories. First, traditional link-state 193 routing protocols are designed for a statically configured 194 environment. As a result, most of the configuration is done manually 195 when a new router is placed in the network. Thus, OSPF will not 196 function in an environment where routers interconnect and disconnect 197 in somewhat random topologies and combinations. There are 198 modifications that must be made in order for routers running the same 199 protocol to communicate in a heterogeneous and dynamic environment. 200 Second, a MANET network must transmit more state information to 201 maintain reachability. Therefore, OSPF will need scalability 202 enhancements to support MANETs. 204 Currently there is no defined interface type that describes a 205 wireless network. Wireless links have characteristics of both multi- 206 access and point-to-multipoint links. Treating wireless links as 207 multi-access does not take into account that not all nodes on the 208 same Layer 2 link have bi-directional connectivity. However, any 209 transmission on a link will reach nodes that are within transmission 210 range. In this way, the link is multi-access due to the fact that 211 two simultaneous transmissions may collide. A new interface type 212 needs to be defined in order to accurately describe this behavior. 214 The second category of challenges fall into is scalability. While 215 some flooding optimizations are present in OSPF, such as designated 216 router (DR) election, many of these were built under the assumption 217 of a true multi-access network. Wireless networks are not true 218 multi-access because it cannot be assumed that there is two-way 219 connectivity between everyone on the same Layer 2 link. Therefore, 220 optimizations such as DR election will not perform correctly in MANET 221 networks. Without any further optimizations in link-state flooding, 222 current OSPF would not be able to operate in a highly dynamic 223 environment in which links are constantly being formed and broken. 224 The amount of information that would need to be flooded would 225 overload the network. 227 Another scalability issue is the periodic transmission of Hello 228 messages. Currently, even if there are no changes in a router's 229 neighbor list, the Hello messages still list all the neighbors on a 230 particular link. For a MANET router, where saving bandwidth and 231 transmission power is a critical issue, the transmission of 232 potentially large Hello messages is particularly wasteful. 234 Finally, current routing protocols will form a neighbor relationship 235 with any router on a Layer 2 link that is correctly configured. For 236 MANET routers in a wireless network, this may lead to an excessive 237 number of parallel links between two routers if communication is 238 achieved via multiple interfaces. In a statically configured 239 network, this is not a problem, since the physical topology can be 240 built to prevent excessive redundancy. However, in a dynamic 241 network, there must exist additional mechanisms to prevent too many 242 redundant links. (Note that links between two nodes on different 243 radio types, different antenna, different channels, etc., are 244 considered different links and not redundant links.) In scalability 245 tests, it has been demonstrated that the presence of too many 246 redundant links will increase both the size of routing updates and 247 cause extra flooding resulting in even relatively small networks not 248 converging. 250 3.1 OSPF-MANET Interface 252 Interfaces are defined as the connection between a router and one of 253 its attached networks [OSPF]. Four types of interfaces have been 254 defined and supported in [OSPF] and [OSPFv3]: broadcast, NBMA, point- 255 to-point, and point-to-multipoint. 257 Point-to-multipoint model has been chosen to represent MANET 258 interfaces. (The features designed in this document MAY be included 259 on other interface types as appropriate.) The MANET interface allows 260 the following: 262 o OSPF treats all router-to-router connections over the MANET 263 interface as if they were point-to-point links. 264 o Link metric can be set on a per neighbor basis. 265 o Broadcast and multicast can be accomplished through Layer-2 266 broadcast or Layer-2 pseudo-broadcast. 267 * The MANET interface supports Layer-2 broadcast if it is able to 268 address a single physical message to all of the attached 269 neighbors. One such example is 802.11. 270 * The MANET interface supports Layer-2 pseudo-broadcast if it is 271 able to pick up a packet from the broadcast queue, replicate 272 the packet, and send a copy over each point-to-point link. One 273 such example is Frame Relay. 274 o An API must be provided for Layer-3 to determine the layer-2 275 broadcast capability. Based on the return of the API, OSPF 276 classifies the MANET interfaces into the following three types: 277 MANET broadcast, MANET pseudo-broadcast, and MANET non- broadcast. 278 o Multicast SHOULD be used for OSPF packets. When the MANET 279 interface supports Layer-2 broadcast or pseudo-broadcast, the 280 multicast process is transparent to OSPF. Otherwise, OSPF MUST 281 replicate multicast packets by itself. 283 3.1.1 Interface Operation 285 A MANET node has at least one MANET interface. MANET nodes can 286 communicate with each other through MANET interfaces. MANET nodes 287 can communicate with non-MANET routers only through normal 288 interfaces, such as Ethernet, ATM and etc. 290 For scalability reasons, it is not required to configure IPv6 global 291 unicast addresses on MANET interfaces. Instead, a management 292 loopback interface, with an IPv6 global unicast address, MAY be 293 configured on each MANET node. 295 The LSAs associated with a MANET interface SHOULD have the DC-bit set 296 in the OSPFv3 Options Field and the DoNotAge bit set in the LS Age 297 field as described in [OSPFv3]. 299 3.1.2 LSA Formats and Examples 301 LSA formats are specified in [OSPFv3]. 303 In order to display example LSAs, a network map is included below. 304 Router names are prefixed with the letters RT, network names with the 305 letter N, and router interface names with the letter I. 306 o Four MANET nodes, RT1, RT2, RT3, and RT4, reside in area 2. 307 o RT1 has one MANET interface I11. Through the interface, RT1 is 308 full adjacent to RT2, RT3, and RT4. 309 o RT2 has two MANET interfaces, I21 and I22, and one Ethernet 310 interface I23. RT2 is full adjacent to RT1 and RT4 through the 311 interface I21, and full adjacent to RT4 through the interface I22. 312 Stub network N1 is attached with RT2 through the interface I23. 313 o RT3 has one MANET interface I31, and is full adjacent to RT1 314 through the interface. 315 o RT4 has two MANET interfaces, I41 and I42. It is full adjacent to 316 RT2 through the interface I41, and full adjacent to RT1 and RT2 317 through the interface I42. 318 o Moreover, each MANET node is configured with a management loop- 319 back interface. 321 +---+I11 I21+---+I23 | 322 |RT1|-+----------+-|RT2|------|N1 323 +---+ | | +---+ | 324 | | VI22 325 | | + 326 | | | 327 | | | 328 | | | 329 | | | 330 | | + 331 | | ^I41 332 +---+ | +---+ 333 |RT3|-+ +-|RT4| 334 +---+I31 I42+---+ 336 The assignment of IPv6 global unicast prefixes to network links is 337 shown below. (Note: No IPv6 global unicast addresses are configured 338 on the MANET interfaces) 339 Node Interface IPv6 global unicast prefix 340 ----------------------------------------------------------- 341 RT1 LOOPBACK 5f00:0001::/64 342 I11 n/a 343 RT2 LOOPBACK 5f00:0002::/64 344 I21 n/a 345 I22 n/a 346 I23 5f00:0012::/60 347 RT3 LOOPBACK 5f00:0003::/64 348 I31 n/a 349 RT4 LOOPBACK 5f00:0004::/64 350 I41 n/a 351 I42 n/a 353 The OSPF interface IDs and the link local addresses for the router 354 interfaces in the network illustrated above below. EUIxy represents 355 the 64-bit interface identifier of the interface Ixy, in Modified 356 EUI-64 format [IPV6ADD]. 358 Node Interface Interface ID Link Local address 359 ----------------------------------------------------------- 360 RT1 LOOPBACK 1 n/a 361 I11 2 fe80:0002::EUI11 362 RT2 LOOPBACK 1 n/a 363 I21 2 fe80:0002::EUI21 364 I22 3 fe80:0003::EUI22 365 I23 4 fe80:0004::EUI23 366 RT3 LOOPBACK 1 n/a 367 I31 2 fe80:0002::EUI31 368 RT4 LOOPBACK 1 n/a 369 I41 2 fe80:0002::EUI41 370 I42 3 fe80:0003::EUI42 372 3.1.2.1 Router LSAs 374 As an example, consider the router LSAs that node RT2 would 375 originate. Two MANET interfaces, consisting of 3 point-to-point 376 links, are presented. 378 RT2's router-LSA 380 LS age = DoNotAge+0 ;newly originated 381 LS type = 0x2001 ;router-LSA 382 Link State ID = 0 ;first fragment 383 Advertising Router = 192.0.2.2 ;RT2's Router ID 384 bit E = 0 ;not an AS boundary router 385 bit B = 0 ;not an area border router 386 Options = (V6-bit|E-bit|R-bit) 387 Type = 1 ;p2p link to RT1 over I21 388 Metric = 10 ;cost to RT1 389 Interface ID = 2 ;Interface ID of I21 390 Neighbor Interface ID = 2 ;Interface ID of I11 391 Neighbor Router ID = 192.0.2.1 ;RT1's Router ID 392 Type = 1 ;p2p link to RT4 over I21 393 Metric = 25 ;cost to RT4 394 Interface ID = 2 ;Interface ID of I21 395 Neighbor Interface ID = 3 ;Interface ID of I42 396 Neighbor Router ID = 192.0.2.4 ;RT4's Router ID 397 Type = 1 ;p2p link to RT4 over I22 398 Metric = 15 ;cost to RT4 399 Interface ID = 3 ;Interface ID of I22 400 Neighbor Interface ID = 2 ;Interface ID of I41 401 Neighbor Router ID = 192.0.2.4 ;RT4's Router ID 403 3.1.2.2 Link LSAs 405 A MANET node originates a separate Link-LSA for each attached 406 interface. As an example, consider the Link-LSA that RT3 will build 407 for its MANET interface I31. 409 RT3's Link-LSA for MANET interface I31 411 LS age = DoNotAge+0 ;newly originated 412 LS type = 0x0008 ;Link-LSA 413 Link State ID = 2 ;Interface ID of I31 414 Advertising Router = 192.0.2.3 ;RT3's Router ID 415 Rtr Pri = 1 ;default priority 416 Options = (V6-bit|E-bit|R-bit) 417 Link-local Interface Address = fe80:0002::EUI31 418 # prefixes = 0 ;no global unicast address 420 3.1.2.3 Intra Area Prefix LSAs 422 A MANET node originates an intra area prefix LSA to advertise its own 423 prefixes, and those of its attached stub links. As an example, 424 consider the intra area prefix LSA that RT2 will build. 426 RT2's intra area prefix LSA for its own prefixes 428 LS age = DoNotAge+0 ;newly originated 429 LS type = 0x2009 ;intra area prefix LSA 430 Link State ID = 177 ;or something else 431 Advertising Router = 192.0.2.2 ;RT2's Router ID 432 # prefixes = 2 433 Referenced LS type = 0x2001 ;router LSA reference 434 Referenced Link State ID = 0 ;always 0 for router-LSA 435 ;reference 436 Referenced Advertising Router = 192.0.2.2 437 ;RT2's Router ID 438 PrefixLength = 64 ;prefix on RT2's LOOPBACK 439 PrefixOptions = 0 440 Metric = 0 ;cost of RT2's LOOPBACK 441 Address Prefix = 5f00:0002:: 442 PrefixLength = 60 ;prefix on I23 443 PrefixOptions = 0 444 Metric = 10 ;cost of I23 445 Address Prefix = 5f00:0012:: ;pad to 64-bit 447 Note: MANET nodes may originate Intra-Area-Prefix-LSAs for attached 448 transit (broadcast/NBMA) networks. This is normal behavior defined 449 in [OSPFv3], which is irrelevant to MANET interfaces. Please consult 450 [OSPFv3] for details. 452 3.2 Incremental OSPF-MANET Hellos 454 In MANETs, reducing the size of periodically transmitted packets can 455 be very important in decreasing the total amount of overhead associ- 456 ated with routing. Towards this end, removing the list of neighbors 457 from Hello packets unless that information changes can reduce routing 458 protocol overhead. While the reduction for each hello packet is 459 small, over time it will be significant. 461 A new option bit is defined in this document to facilitate the 462 operation of incremental Hello packets. A new SCS-TLV and Neighbor 463 Drop TLV are also defined, transmitted using LLS [LLS]. 465 3.2.1 The I Option Bit 467 A new I bit is defined in the OSPFv3 option field. The bit is 468 defined for Hello packets and indicates that only incremental 469 information is present. See Section "New Bits in OSPFv3 Options 470 Field" for placement of the I bit within the OSPFv3 options field. 472 3.2.2 State Check Sequence TLV 474 A new TLV is defined that indicates the current state, which is 475 represented by an State Check Sequence (SCS) number of the 476 transmitting router. 478 0 1 2 3 479 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 480 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+-+ 481 | Type | Length | 482 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+-+ 483 | SCS Number |R|FS|N | Reserved | 484 +-----------------------------------------------------------------+ 486 o Type: Type, set to 2. 487 o Length: Set to 4. 488 o SCS Number: A circular two octet unsigned integer indicating the 489 current state of the transmitting device. Note that when the 490 incremental Hello mechanism is invoked (or re-started), an initial 491 SCS value of '1' SHOULD be used for the first incremental Hello 492 packet. This sequence number is referred to as InitialSCS. Note 493 that InitialSCS also implies a full state. 494 o R: Request bit. If set, this is a request for current state. The 495 list of routers who should respond to this request are listed in 496 the 'Request From' TLV defined below. If the 'Request From' TLV 497 is not present, it is assumed that the request is meant for all 498 nodes. 499 o FS: Full State bit. If set, the Hello packet contains full state 500 as far as the neighbor(s) in the 'Full State For' TLV (defined 501 below) are concerned. If the 'Full State For' TLV is not present, 502 the Hello packet contains full state for all neighbors. 503 o N: InComplete bit. If NOT set, the complete state associated with 504 the SCS number is included in the Hello packet. If set, indicates 505 that the appended TLVs are being sent 'persistently', and that 506 there is more state associated with the SCS number that was sent 507 originally, but is not included in this Hello packet. This bit 508 allows any desired TLVs to be sent 'persistently' for a number of 509 Hellos with the same SCS number without requiring all of the TLVs 510 associated with that SCS number to be transmitted. The first time 511 an SCS number is sent, the entire state associated with that SCS 512 number is transmitted, and the 'N' bit MUST NOT be set. 513 o Reserved: Set to 0. Reserved for future use. 515 A Hello with the State Check Sequence TLV appended with the R bit set 516 will be referred to as a Hello request. 518 3.2.3 Neighbor Drop TLV 520 A new TLV is defined in this document which indicates neighbor(s) 521 that have been removed from the list of known neighbors. 523 0 1 2 3 524 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 525 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 526 | Type | Length | 527 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 528 | Dropped Neighbor(s) | 529 +---------------------------------------------------------------+ 530 | .... 531 +-------------------- 533 o Type: Type, set to 3. 534 o Length: Set to the number of dropped neighbors included in the TLV 535 multiplied by 4. 536 o Dropped Neighbor(s) - Router ID of the neighbor being dropped. 538 3.2.4 'Request From' TLV (RF-TLV) 540 A new TLV is defined in this document which indicates neighbor(s) 541 from which the latest Hello state is being requested. 543 0 1 2 3 544 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 545 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 546 | Type | Length | 547 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 548 | Request From Neighbor(s) | 549 +---------------------------------------------------------------+ 550 | .... 551 +-------------------- 553 o Type: set to 4 554 o Length: Set to the number of neighbors included in the TLV 555 multiplied by 4. 556 o Request From Neighbor(s) - Router ID of the neighbor(s) from which 557 o Hello state is being requested. 559 3.2.5 Full State For TLV (FSF-TLV) 561 A new TLV is defined in this document which indicates neighbor(s) to 562 which the transmitting node is responding with full state. 564 0 1 2 3 565 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 566 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 567 | Type | Length | 568 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 569 | Full State For Neighbor(s) | 570 +---------------------------------------------------------------+ 571 | .... 572 +-------------------- 574 o Type: set to 5 575 o Length: Set to the number of neighbors included in the TLV 576 multiplied by 4. 577 o Full State For Neighbor(s) - Router ID of the neighbor(s) should 578 process this packet. 580 3.2.6 Neighbor Adjacencies 582 This section describes building neighbor adjacencies and the failure 583 of such adjacencies using the incremental Hello signaling. 585 3.2.6.1 Building Neighbor Adjacencies 587 Hello packets are sent periodically in accordance with [OSPF] and 588 [OSPFv3]. An OSPF implementation which supports sending only partial 589 neighbor information in Hello packets SHOULD always set the I bit in 590 its transmitted Hello packets, except as described elsewhere in this 591 document. Hello packets MAY be suppressed from being transmitted 592 every HelloInterval if other packet transmissions are sent by the 593 router during that time. 595 On receiving a Hello packet from a new neighbor (in this context, a 596 new neighbor is a neighbor in less than Init state as defined in 597 Section 10.1 [OSPF]), if the Hello has the I bit set, a router will: 598 o Place the new neighbor in the neighbor list described in [OSPFv3], 599 A.3.2. 600 o Increment the router's SCS number that it will use in its next 601 Hello (indicated in the State Check Sequence TLV). 602 o When the neighbor has reached the EXCHANGE state, described in 603 [OSPF], 10.1, it is removed from the list of neighbors described 604 in [OSPFv3], A.3.2. 605 o If the neighbor is not a DR or backup designated router (BDR) on 606 an OSPF broadcast link, and the neighbor is advertised as 607 connected in the Network LSA advertised by the DR, it is removed 608 from the list of neighbors described in [OSPFv3], A.3.2. 610 3.2.6.2 Adjacency Failure 612 On discovering an adjacency failure (going to state less than 613 EXCHANGE), a router using I bit signaling SHOULD: 614 o Remove the adjacent router from local tables, and take the 615 appropriate actions for a failed adjacency described in [OSPF] and 616 [OSPFv3]. 617 o Add the formerly adjacent router to a Neighbor Drop TLV. 618 o Increment the router's SCS number that it will transmit in its 619 next Hello. 620 o Transmit Hellos with this Neighbor Drop TLV - It may be desirable 621 to send the Neighbor Drop TLV in three consecutive Hellos to 622 increase the probability of reception. In this case, 'persistent' 623 Hello packets would be sent with the same SCS number, the Neighbor 624 Drop TLV, and the 'N' bit set. Thus, the receiver knows that the 625 Neighbor Drop TLV is being sent persistently and there is more 626 state associated with the SCS in case it must request missing 627 state presumably transmitted in a previous Hello. 629 3.2.7 Sending Hellos 631 When a device is first attached to a network (whether through being 632 brought into range of another device, powering the device on, or 633 enabling the device's radio interface, etc.), it will need to obtain 634 complete neighbor state from each of its neighbors before it can 635 utilize the incremental Hello mechanism. Thus, upon initialization, 636 a device MAY send a multicast Hello request (and omit the 'Request 637 From' TLV). Neighbors will receive the request and respond with a 638 Hello with their complete neighbor state. 640 If a device is in INIT state with a neighbor and receives a Hello 641 from the neighbor without its router ID listed in the neighbor list, 642 the device SHOULD request the current state from the neighbor. Note 643 that this is to avoid a race condition since the received Hello can 644 either mean that the device is NOT SEEN by the neighbor, or that the 645 device is adjacent and not listed in the incremental list. Thus, by 646 receiving a Hello request, the neighbor will respond with its 647 neighbor state for the neighbor. 649 The first Hello packet with a particular SCS number MUST contain the 650 full state associated with that SCS number, i.e., all state changes 651 since the last SCS number. The 'N' bit MUST NOT be set in the State 652 Check Sequence TLV. 654 Incremental Hello packets can be sent persistently (sent in k 655 successive Hello packets), with flexibility in the actual amount of 656 information being sent. The three options include: 658 o The entire incremental Hello packet is sent persistently. This is 659 accomplished by simply sending the entire state associated with a 660 SCS number for k successive Hellos. Since the SCS number remains 661 the same, the 'N' bit is not set in these incremental Hello 662 packets. 663 o Partial information for a particular SCS number is sent 664 persistently. After the first Hello packet with a particular SCS 665 number is sent, only the TLVs that are desired to be sent 666 persistently are sent in subsequent Hellos with the same SCS 667 number and the 'N' bit set. 668 o No information is sent persistently. This is simply the default 669 behavior where an incremental Hello packet with a particular SCS 670 number is only sent once. 672 3.2.8 Receiving Hellos 674 Each OSPF device supporting incremental Hello signaling, as described 675 in this document, MUST keep the last known SCS number from each 676 neighbor it has received Hellos from as long as the neighbor 677 adjacency structure is maintained. 679 If a device receives a Hello from an adjacent neighbor with an SCS 680 number less than the last known SCS number from that neighbor, it 681 MUST first check if the SCS number is a wrap around. If it is NOT a 682 wrap around, then the device MUST send a Hello request to the 683 neighbor. 685 If it is a wrap around or if a device receives a Hello from an 686 adjacent neighbor with an SCS number one greater than the last known 687 SCS number from that neighbor, it MUST: 688 o Examine the neighbor list described in [OSPFv3], A.3.2. If any 689 neighbors are contained in this list, increment the SCS number 690 contained in the adjacent neighbor's data structure. 691 o Examine the Neighbor-Drop TLV as described in the section 692 Adjacency Failure. If this list contains a neighbor other than 693 the local router, increment the SCS number contained in the 694 adjacent neighbor's data structure. 695 o Examine the Neighbor Drop TLV as described in the section 696 Adjacency Failure. If the local router identifier is contained in 697 this list, destroy the transmitting adjacent neighbor's data 698 structures. 699 o Examine any other TLVs incrementally signaled, as described in 700 drafts referring to this document. If there are other state 701 changes indicated, increment the SCS number contained in the 702 adjacent neighbor's data structure. 703 o If no state change information is contained in the received Hello, 704 a request for current state (by setting the 'R' bit) is sent in 705 the next Hello. 707 If a device receives a Hello from an adjacent neighbor with an SCS 708 number greater than the last known SCS number + 1 from that neighbor, 709 it MUST send a Hello request to the neighbor since it may be missing 710 some neighbor state. 712 3.2.8.1 Receiving Hellos with the N Bit Set 714 If a device receives a Hello with the State Check Sequence TLV 715 included, and the 'N' bit set in this TLV, it MUST verify that it has 716 already received the SCS number with the 'N' bit NOT set from the 717 neighbor. If the device determines that this is the first reception 718 of the SCS number from this neighbor, then it MUST send a Hello 719 request to the neighbor since it missed the initial Hello packet with 720 the SCS number, and thus is missing state. 722 3.2.8.2 Receiving Hellos with the R Bit Set 724 If a device receives a Hello with the State Check Sequence TLV 725 included, and the R bit set, it looks for the 'Request From' TLV. If 726 it's router ID is listed in the 'Request From' TLV or the TLV is not 727 found, it includes its full state in the next Hello. This MUST 728 include: 729 o The neighbor ID of the requesting neighbor(s) in the list of 730 neighbors described in [OSPFv3], A.3.2., 731 o An State Check Sequence TLV with the transmitter's current SCS 732 number, and the FS bit set. Note that the transmitter's SCS 733 number is NOT incremented. 734 o Any other TLVs, defined in other drafts referencing this document, 735 indicating the current state of the local system. 736 o The neighbor ID of all the neighbors who have requested current 737 state, in the 'Full State For' TLV. 739 If the full state is being sent to a large number of existing 740 neighbors, and implementation could choose to instead generate a full 741 state for all neighbors and omit the 'Full State For' TLV. 743 3.2.8.3 Receiving Hellos with the FS Bit Set 745 When a device receives a Hello with the State Check Sequence TLV 746 included, and the FS bit set, the Hello packet contains the 747 neighbor's full state for the device. The packet SHOULD be processed 748 as follows: 749 o If the received SCS number is equal to the last known SCS number, 750 the packet SHOULD be ignored since the device already has the 751 latest state information. 752 o If the received SCS number is different than the last known SCS 753 number, this Hello has new information and MUST be parsed. 755 o If it is listed in the 'Full State For' TLV or if the 'Full State 756 For' TLV is not present, the device MUST save the SCS number, 757 process the Hello as described in the Receiving Hellos section, 758 and process any other appended TLVs. 760 3.2.9 Interoperability 762 On receiving a Hello packet from a new neighbor without the I bit 763 set, the local router will continue to place that router's identifier 764 in transmitted Hellos on this link as described in [OSPFv3], A.3.2. 766 3.2.10 Support for OSPF Graceful Restart 768 OSPF graceful restart, as described in [OSPFREST] and [OSPFGR], 769 relies on the lack of neighbors in the list of neighbors described in 770 [OSPFv3], A.3.2, to determine that an adjacent router has restarted, 771 and other signaling to determine the adjacency should not be torn 772 down. If all Hello packets transmitted by a given router have an 773 empty Hello list, reliance on an empty Hello packet to signal a 774 restart (or to reliably tear down an OSPF adjacency) is no longer 775 possible. Hence, this signaling must be slightly altered. 777 When a router would like to tear down all adjacencies, or signal it 778 has restarted: 779 o On initially restarting, during the first RouterDeadInterval after 780 restart, the router will transmit Hello packets with an empty 781 neighbor list, and the I bit cleared. Any normal restart or other 782 signaling may be included in these initial Hello packets. 783 o As adjacencies are learned, these newly learned adjacent routers 784 are included in the multicast Hellos transmitted on the link. 785 o After one RouterDeadInterval has passed, the incremental Hello 786 mechanism is invoked. An incremental Hello packet with full state 787 is sent with the 'I' bit set, and the SCS TLV included with the 788 'A' bit set and the InitialSCS value, e.g., SCS of '1'. 789 Subsequent Hello packets will include only incremental state. 791 Routers which are neighboring with a restarting router MUST continue 792 sending their Hello packets with the I bit set. 794 3.3 Optimized Flooding (Overlapping Relays) 796 A component that may influence the scalability and convergence 797 characteristics of OSPF [OSPF],[OSPFv3] in a MANET environment is how 798 much information needs to be flooded. The ideal solution is that a 799 router will only receive a particular routing update only once. 800 However, there must be a tradeoff between protocol complexity and 801 ensuring that every speaker in the network receives all of the 802 information. Note that a speaker refers to any node in the network 803 that is running the routing protocol and transmitting routing updates 804 and Hello messages. 806 Controlling the amount of information on the link has increased 807 importance in a MANET environment due to the potential transmission 808 costs and resource availability in general. 810 In some environments, a group of speakers that share the same logical 811 segment may not be directly visible to each other; some of the 812 possible causes are the following: low signal strength, long distance 813 separation, environmental disruptions, partial VC meshing, etc. In 814 these networks, a logical segment refers to the local flooding domain 815 dynamically determined by transmission radius. In these situations, 816 some speakers (the ones not able to directly reach the sender) may 817 never be able to synchronize their databases. To solve the 818 synchronization issues encountered in these environments, a mechanism 819 is needed through which all the nodes on the same logical segment can 820 receive the routing information, regardless of the state of their 821 adjacency to the source. 823 3.3.1 Operation Overview 825 The optimized flooding operation relies on the ability of a speaker 826 to advertise all of its locally connected neighbors. In OSPF, this 827 ability is realized through the use of link state advertisements 828 (LSA)s [OSPF],[OSPFv3]. 830 A speaker receives router LSAs from its adjacent neighbors. A 831 speaker's router LSA conveys the list of the adjacent speakers of the 832 originator ("neighbor list"). The local speaker can compare the 833 neighbor list reported by each speaker to its own neighbor list. If 834 the local neighbor list contains adjacent speakers that the 835 originator cannot reach directly (i.e. those speakers that are not in 836 the originator's neighbor list), then these speakers are locally 837 known as non-overlapping neighbors for the originator. 839 The local speaker should relay any routing information to non- 840 overlapping neighbors of the sender based on the algorithm outlined 841 in the Flooding and Relay Decisions section. Because more than one 842 such speaker may exist, the mechanism is called "overlapping relays." 843 The algorithm, however, does select the set of overlapping relays 844 that should transmit first. This set is known as the active set of 845 overlapping relays for a speaker. 847 3.3.2 Determination of Overlapping Relays 849 The first step in the process is for each speaker to build and 850 propagate their neighbor lists in router LSAs packets. Every speaker 851 is then in a position to determine their two-hop neighborhood, i.e., 852 those nodes that are neighbors of the speaker's one-hop neighbors. A 853 neighbor is considered an overlapping relay for a speaker if it can 854 reach a node in the two-hop neighborhood of the neighbor, i.e., if it 855 has one-hop neighbors. 857 The set of active overlapping relays for a speaker is the minimum set 858 of direct neighbors such that every node in the two-hop neighborhood 859 of the speaker is a neighbor of a least one overlapping relay in the 860 active set. Each speaker SHOULD select a set of active overlapping 861 relays based on a selection algorithm (one such algorithm is 862 suggested in the "Overlapping Relay Discovery Process" Section and is 863 based on the MPR selection algorithm described in [OLSR]). Note that 864 a speaker MUST NOT choose a neighbor to serve as an active 865 overlapping relay if that neighbor set the 'N' bit in its Active 866 Overlapping Relay TLV as defined in Section "Active Overlapping Relay 867 Extension", unless the neighbor is the only neighbor to reach a two- 868 hop neighbor. Election of active overlapping relays is done across 869 interfaces, and thus, it is node-based and not link-based. 871 3.3.3 Terminology 873 The following heuristic and terminology for active overlapping relay 874 selection is largely taken from [OLSR]: 875 o FULL: Neighbor state FULL as defined in [OSPF] & [OSPFv3]. Note 876 that all neighbor references in this document are assumed to be 877 FULL neighbors. 878 o 2-hop FULL neighbors: The list of 2-hop neighbors of the node that 879 are FULL and that can be reached from direct neighbors, excluding 880 any directly connected neighbors. 881 o Active Set: A (sub)set of the neighbors selected such that through 882 these selected nodes, all 2-hop FULL neighbors are reachable. 883 o N: N is the set of FULL neighbors of the node. 884 o N2: A subset of 2-hop FULL neighbors excluding the nodes only 885 reachable by members of N. 886 o D(y): The degree of a one hop neighbor node y (where y is a member 887 of N), is defined as the number of FULL neighbors of node y, 888 EXCLUDING all the members of N and EXCLUDING the node performing 889 the computation. 891 3.3.4 Overlapping Relay Discovery Process 893 A possible algorithm for discovering overlapping relays is the 894 following: 895 1. Start with an active set made of all members of N that have set 896 the 'A' bit in their Active Overlapping Relays TLV as defined in 897 Section "Active Overlapping Relays Extension". 899 2. Calculate D(y), where y is a member of N, for all nodes in N. 900 3. Add to the active set those nodes in N, which are the *only* 901 nodes to provide reachability to a node in N2, i.e., if node-b in 902 N2 can be reached only through a symmetric link to node-a in N, 903 then add node-a to the active set. Remove the nodes from N2 904 which are now covered by a node in the active set. 905 4. While there exist nodes in N2 which are not covered by at least 906 one node in the active set: 907 1. For each node in N, calculate the reachability, i.e., the 908 number of nodes in N2 which are not yet covered by at least 909 one node in the active set, and which are reachable through 910 this one hop neighbor; 911 2. Select as an active overlapping relay the node with highest 912 Willingness among the nodes in N with non-zero reachability. 913 In case of multiple choice select the node which provides 914 reachability to the maximum number of nodes in N2. In case 915 of multiple nodes providing the same amount of reachability, 916 select the node as active whose D(y) is greater. As a final 917 tie breaker, the node with the highest router ID should be 918 chosen. Remove the nodes from N2 which are now covered by a 919 node in the active set. 920 5. As an optimization, process each node, y, in the active set in 921 increasing order of Willingness. If all nodes in N2 are still 922 covered by at least one node in the active set excluding node y, 923 and if Willingness of node y is smaller than MAX_WILLINGNESS, 924 then node y should be removed from the active set. 926 Note that the active overlapping relays selection algorithm is 927 implementation specific, and the above is simply a suggested 928 algorithm. However, the behavior of the overlapping relays MUST 929 follow that specified in the "Flooding and Relay Decisions" Section. 930 Moreover, the same selection algorithm MUST be used by all nodes 931 within an area. 933 3.3.5 The F Option Bit 935 A single new option bit, the F bit, is defined in the OSPFv3 option 936 field. The F bit indicates that the node supports the Optimized 937 Flooding mechanism as specified in this draft. See Section "New Bits 938 in OSPFv3 Options Field" for placement of the F bit. 940 3.3.6 Active Overlapping Relay Extension 942 A new TLV is defined so that each speaker can convey its set of 943 active overlapping relays in the Hello messages. The TLV is 944 transmitted using the Link Local Signaling method described in "Link 945 Local Signaling" Section. 947 0 1 2 3 948 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 949 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 950 | Type | Length | 951 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 952 | Relays Added |A|N| Reserved | 953 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 954 | Router ID(s) of Active Overlapping Relay(s) | 955 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 956 | ... | 957 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 959 o Type: Type, set to 4. 960 o Length - variable; Length of TLV in bytes NOT including Type and 961 Length. 962 o Relays Added - variable; Number of active overlapping relays that 963 are being added. Note that the number of active overlapping 964 relays that are being dropped is then given by: [(Length - 4)/4 - 965 Relays Added]. 966 o A bit - If this bit is set, the node is specifying that it will 967 always flood routing updates that it receives, regardless of 968 whether it is selected as an Active Overlapping Relay. 969 o N bit - If this bit is set, the node is specifying that it most 970 likely will not flood routing updates. The node SHOULD NOT be 971 chosen to be an active overlapping relay unless it is the *only* 972 neighbor that can reach two-hop neighbor(s). Note that if the 973 node is selected as an Active Overlapping relay and the node can 974 not perform the required duties, network behavior is not 975 compromised since it results in the same behavior as if the node 976 was not chosen as an active overlapping relay. 977 o Reserved - Reserved for future use and MUST be ignored upon 978 reception. 979 o Router ID(s) of Active Overlapping Relay(s) - The router ID(s) of 980 neighbor(s) that are either chosen to serve as an active 981 overlapping relay, or removed from serving as an active 982 overlapping relay. The active overlapping relays that are being 983 added MUST be listed first, and the number of such relays MUST 984 equal Add Length. The remaining list of relays are being dropped 985 as active overlapping relays, and the number of such relays MUST 986 equal [(Length - 4)/4 - Relays Added]. 988 Note that the 'A' bit and 'N' bit are independent of any particular 989 selection algorithm to determine the set of Active Overlapping 990 Relays. However, the bits SHOULD be considered as input into the 991 selection algorithm. 993 If a node is selected as an active overlapping relay and it does not 994 support the Incremental Hello mechanism defined in the "Incremental 995 OSPF-MANET Hellos" Section, then it SHOULD always be included as an 996 Active Overlapping Relay in the TLV. Note that while a node needs to 997 know whether it is an active overlapping relay, it does not 998 necessarily have to know the identities of the other active 999 overlapping relays. 1001 3.3.7 Willingness TLV 1003 A new TLV is defined so that each speaker can convey its willingness 1004 to serve as an active overlapping relay in the Hello meassage. The 1005 TLV is transmitted using the Link Local Signaling method described in 1006 the "Link Local Signaling" Section. 1008 0 1 2 3 1009 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 1010 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1011 | Type | Length | 1012 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1013 | Willingness | Reserved | 1014 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1016 o Type: Type, set to 5. 1017 o Length - 4 bytes. It does not include the Type and Length fields. 1018 o Willingness - 1 byte to indicate the willingness of the node to 1019 serve as an active overlapping relay for its neighbors. 1020 * 0: MIN_WILLINGNESS 1021 * 128: DEFAULT_WILLINGNESS 1022 * 255: MAX_WILLINGNESS 1024 The TLV is optional and MUST be silently ignored if not understood. 1025 If the Willingness TLV is not included in the Hello packet, the 1026 Willingness value SHOULD be taken as DEFAULT_WILLINGNESS. 1028 3.3.8 Flooding and Relay Decisions 1030 The decision whether to relay any received LSAs and when to relay 1031 such information, is made depending on the topology and whether the 1032 node is part of the set of active overlapping relays. 1034 Upon receiving an LSA from an adjacent speaker, a node makes flooding 1035 decisions based on the following algorithm: 1036 1. If the node is an active overlapping relay for the adjacent 1037 speaker, then the router SHOULD immediately relay any information 1038 received from the adjacent speaker. 1039 2. If the node is a non-active overlapping relay for the adjacent 1040 speaker, then the router SHOULD wait a specified amount of time 1041 (PushbackInterval plus jitter, see "Important Timers" Section) to 1042 decide whether to transmit. [Jitter is used to try to avoid 1043 several non-active overlapping relays from propagating redundant 1044 information.] Note that a node with the 'N' bit set in the 1045 'Active Overlapping Relays' Extension will not be chosen as an 1046 active overlapping relay unless it is the only node to provide 1047 reachability to a two-hop neighbor. However, it MUST perform the 1048 duties of a non-active overlapping relay as required. Non-active 1049 overlapping relays MUST follow the acknowledgment mechanism 1050 outlined in the section 'Intelligent Transmission of Link State 1051 Acknowledgements.' 1052 1. During this time, if the node determines that flooding the 1053 LSA will only result in a redundant transmission, the node 1054 MUST suppress its transmission. Otherwise, it MUST transmit 1055 upon expiration of PushbackInterval plus jitter. 1056 2. If a non-active overlapping relay hears a re-flood from 1057 another node that covers its non-overlapping neighbors before 1058 its timer to transmit expires, it SHOULD reset its 1059 PushbackInterval plus jitter timer. (Note that the 1060 implementation should take care to avoid resetting the 1061 PushbackInterval timer based on transmissions from active 1062 overlapping relays.) During this time, if the node 1063 determines that flooding the update will only result in a 1064 redundant transmission, the node MUST suppress its 1065 transmission. Otherwise, it MUST transmit upon expiration of 1066 PushbackInterval + jitter. 1067 3. If a non-active overlapping relay hears an old instance of 1068 the LSA during this time, it SHOULD ignore the LSA and it 1069 SHOULD NOT send a unicast packet to the neighbor with the 1070 most recent LSA as specified in [OSPFv3]. 1071 3. For LSAs that are received unicast because of retransmission by 1072 the originator, the node MUST determine whether it has already 1073 received the LSA from another speaker. If it already has the 1074 current instance of the LSA in its database, it MUST do nothing 1075 further in terms of flooding the LSA (since it would have taken 1076 appropriate behavior when it initially received the LSA.) 1077 However, if it does not have the current instance of the LSA in 1078 its database, it MUST take action according to the rules above, 1079 just as if it received the multicast LSA. The acknowledgement 1080 mechanism outlined in the section 'Intelligent Transmission of 1081 Link State Acknowledgements' MUST be followed, and any timeout 1082 mechanism for unicast LSAs MAY be followed. 1084 Note that a node can determine whether further flooding a LSA will 1085 only result in a redundant transmission by already having heard link 1086 state acknowledgements (ACKs) or floods for the LSA from all of its 1087 neighbors. 1089 Due to the dynamic nature of a network, the set of active overlapping 1090 relays may not be up to date at the time the relay decision is made 1091 or may not be able to perform the flooding duties, e.g., due to poor 1092 link quality. The non-active overlapping relays prevent this 1093 situation from causing database synchronization issues and thus, 1094 packet loss. 1096 Since the originator of the information, the relay, and the receiver 1097 are all in the same dynamically determined local flooding domain, the 1098 relay MUST NOT change the routing update information. In general, 1099 LSAs SHOULD be sent to a well-known multicast address. In some 1100 cases, routing updates MAY be sent using unicast packets. 1102 3.3.9 Intelligent Transmission of Link State Acknowledgements 1104 In order to optimize the bandwidth utilization on the link, a speaker 1105 MUST follow these recommendations related to ACK transmissions: 1106 1. All ACKs MUST be sent via multicast. 1107 2. Typically, LSAs are acknowledged by all of the adjacent speakers. 1108 In the case of relayed information, the relay MUST only expect 1109 either explicit or implicit acknowledgements from neighbors that 1110 have not previously acknowledged this LSA. 1111 3. Because routing updates are sent via multicast, the set of 1112 overlapping speakers will usually receive the same update more 1113 than once. A speaker SHOULD only acknowledge the first update 1114 received on the link. 1115 4. An active overlapping relay SHOULD NOT explicitly acknowledge 1116 information that it is relaying. The relayed information will 1117 serve as an acknowledgement to the sender. If no information is 1118 being relayed, than an explicit ACK MUST be sent. 1119 5. Several ACKs MAY be bundled into a single packet. The wait 1120 (AckInterval) before sending one such packet reduces the number 1121 of packet transmissions required in acknowledging multiple LSAs. 1122 6. All ACK packets SHOULD reset the RouterDeadInterval at the 1123 receiver. If there is no state waiting to be transmitted in a 1124 Hello packet at the sender, then the HelloInterval at the sender 1125 SHOULD be reset. Note that an ACK serves as a Hello packet with 1126 no state change. 1127 7. Any LSA received via unicast MUST be acknowledged. (Note that 1128 acknowledgment is via multicast as specified in rule (1) above.) 1130 An ACK received from a non-overlapping neighbor should prevent 1131 redundant transmission of the information to it by another 1132 overlapping relay. 1134 3.3.10 Important Timers 1136 This section details the timers that are introduced in the Flooding 1137 and Relay Decisions and Intelligent Transmission of Link State 1138 Acknowledgements sections. 1140 o PushbackInterval: The length of time in seconds that a non-active 1141 overlapping relay SHOULD wait before further flooding an LSA if 1142 needed. This timer MUST be less than 1/2 of the RxmtInterval 1143 [OSPF],[OSPFv3] minus propagation delays, i.e., (PushbackInterval 1144 + propagation delay) < RxmtInterval/2. The PushbackInterval is 1145 set by a non-active overlapping relay upon reception of an LSA. 1146 o AckInterval: After a node determines that it must transmit an ACK 1147 and the AckInterval timer is not already set, the node SHOULD set 1148 the AckInterval timer. The AckInterval is the length of time in 1149 seconds that a node should wait in order to transmit many ACKs in 1150 the acknowledgement packet. This wait reduces the number of 1151 packet transmissions required in acknowledging multiple LSAs. The 1152 AckInterval MUST be less than the PushbackInterval minus 1153 propagation delays, i.e., (AckInterval + propagation delay) < 1154 PushbackInterval. 1156 3.3.11 Miscellaneous Protocol Considerations 1158 The mechanism described refers to the operation of relays on a common 1159 media segment. In other words, an LSA is only relayed out the same 1160 interface through which it was received. However, the concept of 1161 information relay may be extended to the flooding of all link state 1162 advertisements received on any interface (and forwarded on any other 1163 interface). OSPF works on the premise that all of the nodes in a 1164 flooding domain will receive all of the routing information. Note 1165 that one of the important properties is that the routing information 1166 is not altered when relayed. 1168 If each speaker advertised all of its adjacent neighbors on all 1169 interfaces, then the overlap check would result in the determination 1170 of which speakers are adjacent to both speakers. As a result, link 1171 state information should only be flooded to non-overlapping neighbors 1172 (taking all of the interfaces into account). 1174 The flooding mechanism in OSPF relies on a designated router to 1175 guarantee that any new LSA received by one router attached to the 1176 broadcast network will be reflooded properly to all the other routers 1177 attached to the broadcast network. Such desginated routers must be 1178 able to reach all of the other speakers on the same subnet. A 1179 designated router SHOULD NOT be elected if overlapping relays are 1180 used. 1182 If such designated routers already exist, then the relays MUST be 1183 capable of differentiating them, and then making the relaying 1184 decisions based on the OSPF's normal operation. As a result, there 1185 may be groups of neighbors to which some information should not be 1186 relayed. This mode of operation is NOT RECOMMENDED as it adds to the 1187 complexity of the system. 1189 The intent of the overlapping relay mechanism is to optimize flooding 1190 of routing control information. However, other information (such as 1191 data) may also be relayed in some networks using the same mechanism. 1193 3.3.12 Interoperability 1195 On receiving a Hello packet from a new neighbor without the F bit 1196 set, the local router will assume that the new neighbor will flood 1197 normally as described in [OSPFv3]. Thus, the local router SHOULD 1198 include the neighbor in its overlapping relay set since the neighbor 1199 will flood by default. This will allow the local router to more 1200 optimally select its entire overlapping relay set. 1202 If the F bit is set and the I bit as defined in Section "Incremental 1203 OSPF-MANET Hellos" is not set in the neighbor's Hello and the 1204 neighbor is selected as an overlapping relay by the local router, the 1205 local router will continue to include the neighbor's identifier in 1206 its active relay set. 1208 3.4 New Bits in OSPFv3 Option Field 1210 Three new option bits are defined in the OSPFv3 Options Field 1211 (defined in [OSPFv3], A.2) as follows: 1213 0 1 2 1214 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 1215 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+-+-+--+--+--+--+--+--+ 1216 | | | | | | | | | | | | |F|I|L|AF|*|*|DC| R| N|MC| E|V6| 1217 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+-+-+--+--+--+--+--+--+ 1219 o I bit - defined in Section "I Option Bit": The I bit is only 1220 defined for Hello packets and indicates that only incremental 1221 information is present. 1222 o F bit - defined in Section "F Option Bit": The F bit indicates 1223 that the node supports the Optimized Flooding mechanism as 1224 specified in this draft. 1226 3.5 Smart Peering 1228 There is a significant overhead in OSPF if a router has to establish 1229 adjacencies with every peer it can verify 2-way connectivity with. 1230 OSPF supports a broadcast network type for these scenarios, where you 1231 only have to peer with a designated router (DR). But a full mesh of 1232 connectivity is required for proper DR election, so this doesn't help 1233 in networks with overlapping partial meshes of connectivity. This 1234 draft proposes an optional technique to reduce the number of 1235 adjacencies based on the shortest path tree (SPT) reachability 1236 information. 1238 3.5.1 Introduction 1240 In OSPF [OSPF] [OSPFv3], nodes establish an adjacency by first 1241 verifying 2-way connectivity between them and then synchronizing 1242 their link state databases. Once the peering relationship is complete 1243 and the adjacency is established, the nodes will continue to 1244 advertise each other in their periodic Hellos and LSAs. As a result, 1245 the peers are maintained in the link state database and are included 1246 in all SPF calculations. During the reliable flooding process, a node 1247 must ensure that each peer has indeed received the flooded routing 1248 update via an acknowledgement and retransmission mechanism. 1250 Consequently, maintaining an adjacency for a particular peer is a 1251 tradeoff between the added redundancy in routing paths and network 1252 reachability versus the overhead (memory consumption, SPF 1253 computations, routing overhead, and network convergence). 1255 Consider the possibility of reducing the number of adjacencies that a 1256 node maintains without compromising reachability and redundancy. 1257 This will have direct implications on network scalability and is 1258 especially attractive in environments where the network topology is 1259 dynamic. For example, in a Mobile Ad-Hoc Network (MANET) where nodes 1260 are mobile and the topology is constantly changing, it seems highly 1261 desirable to 'intelligently' become adjacent with only selected peers 1262 and thus, not establish a peering session with every node that comes 1263 within transmission range. Selective peering can be particularly 1264 useful in avoiding the peering process for unstable nodes, i.e., 1265 nodes that come in and out of transmission range. 1267 3.5.2 Previous Related Work 1269 The formation of a FULL adjacency requires the discovery (2-way 1270 relationship) and the database synchronization. To prevent from 1271 achieving the FULL state, others have taken the approach of modifying 1272 link state protocols to use periodic advertisements (instead of a 1273 database exchange). The result is that neighbor discovery is still 1274 required, but the routing information is learned over time. An 1275 example of this approach is: 1277 - OSPFv2 Wireless Interface Type [WINTF] 1278 - where the use of periodic advertisements "eliminates the 1279 formation of full adjacencies on wireless interfaces; all 1280 neighbor states beyond 2-Way are not reached,and no database 1281 synchronization is performed". 1283 What we propose below, goes a step further by not requiring the 1284 formation and maintenance of neighbor state (2-way, or other) *and* 1285 without changing the route distribution mechanisms in the link state 1286 protocols. In other words, the mechanism described is completely 1287 backwards compatible. 1289 3.5.3 Proposed Solution 1291 Two routers are called synchronized when they have identical link 1292 state database. To limit the number of neighbors that are formed, an 1293 algorithm is needed to select which neighbors to peer with. 1295 The algorithm MUST provide reachability to every possible destination 1296 in the network, just like when normal adjacency formation processes 1297 are used. We should always peer with a neighbor if it provides our 1298 only path to currently unreachable destinations. 1300 3.5.3.1 SPT Reachability Heuristics 1302 The peering decision is really a local matter to a router. If a 1303 router can ensure that the reachability to other nodes is available 1304 without bringing up a new adjacency, it can choose to not bring up 1305 the new adjacency. 1307 We propose an algorithm which uses the already existing information 1308 about a new neighbor's reachability in the SPT. If the two routers 1309 can already reach each other in the SPT, it is not necessary to build 1310 up the adjacency between them. 1312 The decision to peer or not, is made when a hello is received. When a 1313 hello is received from a new neighbor or a neighbor in a state lower 1314 than Exchange: 1316 - A check is made in the link state database to see if the peer is 1317 already reachable in the SPT. 1319 - If the peer is either not known in the SPT or is not reachable, 1320 we start the Exchange process. 1322 - If the peer is reachable than bringing up adjacency with this 1323 neighbor does not provide reachability to any new destinations. 1325 Lets take an example of a single OSPF area. This check would look for 1326 the neighbor's Router LSA. If the LSA is present in the database and 1327 is reachable in the SPT, we have a chance to keep this adjacency from 1328 going to Exchange. 1330 It's worth noting that as the number of links and redundancy in the 1331 network is reduced, there may be an increase in suboptimal routing. 1333 3.5.3.2 State Machine 1335 The state machine of a basic implementation of this algorithm is 1336 provided below: An implementation MAY use some heuristics below 1337 (step (3)), beyond the SPT reachability to decide if it considers a 1338 new adjacacency to be of value or not. 1340 ...................... 1341 |Receive a hello | 1342 (1) |from a new potential| 1343 |neighbor | 1344 '`'''''''''''''''''''' 1345 | 1346 | 1347 | 1348 ,''''''''''''''''''''''| 1349 |Check to see if there | 1350 (2) |is a router LSA from |----no--(4)form a 1351 |the new potential | new 1352 |neighbor in the link | neighbor 1353 |state database, which | 1354 |is reachable in SPT | 1355 '`'''''''''''''''''''''' 1356 | 1357 |yes 1358 (3) | 1359 ,'''''''''''''''''''''''''''''''''''''''''''''''''''''''''| 1360 | (3b)........................ | 1361 |(3a),______________________ |Determine if the | | 1362 | |Determine if the new | |number of redundant | | 1363 | |link cost is better | |paths to the potential| | 1364 | |than the current path| |neighbor is < the | | 1365 | |cost by a configured | |maximum configured | | 1366 | |amount | |value | | 1367 | '`''''''''''''''''''''' '`'''''''''''''''''''''' | 1368 | \ / | 1369 | .....\.........../.... | 1370 | |User configurable | | 1371 | |selection algorithm | | 1372 | '`'''/'''''''\'''''''' | 1373 | / \ | 1374 '`'''''''''''''''''''''/'''''''''''\''''''''''''''''''''''' 1375 / \ 1376 requirements requirements 1377 met not met 1378 / \ 1379 / \ 1380 (4) form a new neighbor (5) do not become 1381 neighbors 1383 3.5.3.3 Announce the 2-way link in Router-LSA 1385 While the technique described above minimizes the number of 1386 adjacencies in highly meshed einvironments, it may lead to the 1387 undesirable result of limiting the number of transit links available 1388 on which to forward traffic. 1390 An implementation may choose to allow some (or even all) of these 1391 2-way state neighbors to be announced in the Router-LSA. Since the 1392 state remains 2-way, we don't incur control plan (database sync and 1393 flooding) overhead. But at the same time, announcing the link in the 1394 Router-LSA makes the link available to the data plane. 1396 4. Security Considerations 1398 In a MANET network, security is both more difficult and important due 1399 to the wireless nature of the medium. Controlling the ability of 1400 devices to connect to a MANET network at Layer 2 will be relegated to 1401 Layer 2 security mechanisms, such as 802.1x, and others. Controlling 1402 the ability of attached devices to transit traffic will require some 1403 type of security system (outside the scope of this document) which 1404 can authenticate and provide authorization for individual members of 1405 the routing domain. 1407 5. IANA Considerations 1409 IANA will make assignments as explained below using the policies 1410 outlined in [IANA]. 1412 o An option bit value for the I-bit and F-bit as defined in the "New 1413 Bits in OSPFv3 Options Field" section above. 1415 o TLV type codes for SCS-TLV, Neighbor Drop TLV, Request From TLV, 1416 Full State For TLV and Willingness TLV as defined in this 1417 document. This allocation comes from LLS [LLS] TLV types values. 1419 6. Contributors 1421 The following persons are contributing authors to the document: 1423 Fred Baker 1424 Cisco Systems 1425 1121 Via Del Rey 1426 Santa Barbara, CA 93117 1427 USA 1428 Email: fred@cisco.com 1430 Alvaro Retana 1431 Cisco Systems 1432 7025-4 Kit Creek Road 1433 RTP, NC 27709 1434 USA 1435 Email: aretana@cisco.com 1436 Russ White 1437 Cisco Systems 1438 7025-4 Kit Creek Road 1439 RTP, NC 27709 1440 USA 1441 Email: riw@cisco.com 1443 Dave Cook 1444 Cisco Systems 1445 7025-4 Kit Creek Road 1446 RTP, NC 27709 1447 USA 1448 Email: dacook@cisco.com 1450 Yi Yang 1451 Cisco Systems 1452 7025-4 Kit Creek Road 1453 RTP, NC 27709 1454 USA 1455 Email: yiya@cisco.com 1457 7. Acknowledgements 1459 The authors and contributors would like to thank Pratap Pellakuru and 1460 Stan Ratliff for their feedback and implementation of the document. 1462 References 1464 Normative References 1466 [OSPF] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 1468 [OSPFv3] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6", 1469 RFC 2740, December 1999. 1471 [IANA] Narten, T. and H. Alvestrand, "Guidelines for Writing an 1472 IANA Considerations Section in RFCs", BCP 26, RFC 2434, 1473 October 1998. 1475 [KEY] Bradner, S., "Key words for use in RFCs to Indicate 1476 Requirement Levels", BCP 14, RFC 2119, March 1997. 1478 Informative References 1480 [IPV6ADD] Hinden, R. and S. Deering, "IP Version 6 Addressing 1481 Architecture", RFC 4291, February 2006. 1483 [OSPFGR] Moy, J., Pillay-Esnault, P., and A. Lindem, "Graceful OSPF 1484 Restart", RFC 3623, November 2003. 1486 [OSPFREST] Zinin, A., Roy, A., and L. Nguyen, "OSPF Restart 1487 Signaling", RFC 4812, March 2007. 1489 [LLS] Zinin, A., Roy, A., Nguyen, L., Friedman, B., and D. 1490 Yeung, "OSPF Link-local Signaling", 1491 draft-ietf-ospf-lls-03.txt (work in progress), 1492 February 2008. 1494 [OLSR] Clausen, T. and P. Jacquet, "Optimized Link State Routing 1495 Protocol", RFC 3626, October 2003. 1497 [WINTF] Ahrenholz J. et al, "OSPFv2 Wireless Interface Type", 1498 draft-spagnolo-manet-ospf-wireless-interface 1499 (work in progress) 1501 Authors' Addresses 1503 Madhavi W. Chandra (Editor) 1504 Email: mw.chandra@gmail.com 1506 Abhay Roy (Editor) 1507 Cisco Systems 1508 170 W. Tasman Drive 1509 San Jose, CA 95134 1510 USA 1511 Email: akr@cisco.com 1513 Full Copyright Statement 1515 Copyright (C) The IETF Trust (2008). 1517 This document is subject to the rights, licenses and restrictions 1518 contained in BCP 78, and except as set forth therein, the authors 1519 retain all their rights. 1521 This document and the information contained herein are provided on an 1522 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1523 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 1524 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 1525 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1526 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1527 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1529 Intellectual Property 1531 The IETF takes no position regarding the validity or scope of any 1532 Intellectual Property Rights or other rights that might be claimed to 1533 pertain to the implementation or use of the technology described in 1534 this document or the extent to which any license under such rights 1535 might or might not be available; nor does it represent that it has 1536 made any independent effort to identify any such rights. Information 1537 on the procedures with respect to rights in RFC documents can be 1538 found in BCP 78 and BCP 79. 1540 Copies of IPR disclosures made to the IETF Secretariat and any 1541 assurances of licenses to be made available, or the result of an 1542 attempt made to obtain a general license or permission for the use of 1543 such proprietary rights by implementers or users of this 1544 specification can be obtained from the IETF on-line IPR repository at 1545 http://www.ietf.org/ipr. 1547 The IETF invites any interested party to bring to its attention any 1548 copyrights, patents or patent applications, or other proprietary 1549 rights that may cover technology that may be required to implement 1550 this standard. Please address the information to the IETF at 1551 ietf-ipr@ietf.org. 1553 Acknowledgment 1555 Funding for the RFC Editor function is provided by the IETF 1556 Administrative Support Activity (IASA).