idnits 2.17.1 draft-ietf-ospf-manet-or-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.i or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? (You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Feb 2009 rather than one of the newer Notices. See https://trustee.ietf.org/license-info/.) 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 1 instance of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors 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 contain a disclaimer for pre-RFC5378 work, and may have content which was first submitted before 10 November 2008. The disclaimer is necessary when there are original authors that you have been unable to contact, or if some do not wish to grant the BCP78 rights to the IETF Trust. If you are able to get all authors (current and original) to grant those rights, you can and should remove the disclaimer; otherwise, the disclaimer is needed and you can ignore this comment. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- Couldn't find a document date in the document -- date freshness check skipped. -- 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: Experimental ---------------------------------------------------------------------------- ** Obsolete normative reference: RFC 5226 (ref. 'IANA') (Obsoleted by RFC 8126) Summary: 2 errors (**), 0 flaws (~~), 3 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group A. Roy (Editor) 2 Internet-Draft Cisco Systems 3 Intended status: Experimental M. Chandra (Editor) 4 Expires: July 9 2010 January 9 2010 6 Extensions to OSPF to Support Mobile Ad Hoc Networking 7 draft-ietf-ospf-manet-or-03.txt 9 Status of this Memo 11 This Internet-Draft is submitted to IETF in full conformance with the 12 provisions of BCP 78 and BCP 79. This document may contain material 13 from IETF Documents or IETF Contributions published or made publicly 14 available before November 10, 2008. The person(s) controlling the 15 copyright in some of this material may not have granted the IETF 16 Trust the right to allow modifications of such material outside the 17 IETF Standards Process. Without obtaining an adequate license from 18 the person(s) controlling the copyright in such materials, this 19 document may not be modified outside the IETF Standards Process, and 20 derivative works of it may not be created outside the IETF Standards 21 Process, except to format it for publication as an RFC or to 22 translate it into languages other than English. 24 Internet-Drafts are working documents of the Internet Engineering 25 Task Force (IETF), its areas, and its working groups. Note that 26 other groups may also distribute working documents as Internet- 27 Drafts. 29 Internet-Drafts are draft documents valid for a maximum of six months 30 and may be updated, replaced, or obsoleted by other documents at any 31 time. It is inappropriate to use Internet-Drafts as reference 32 material or to cite them other than as "work in progress." 34 The list of current Internet-Drafts can be accessed at 35 http://www.ietf.org/ietf/1id-abstracts.txt. 37 The list of Internet-Draft Shadow Directories can be accessed at 38 http://www.ietf.org/shadow.html. 40 This Internet-Draft will expire on July 9 2010. 42 Copyright Notice 44 Copyright (c) 2009 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents in effect on the date of 49 publication of this document (http://trustee.ietf.org/license-info). 50 Please review these documents carefully, as they describe your rights 51 and restrictions with respect to this document. 53 Roy, Chandra et al. Expires July 2010 [Page 1] 54 Abstract 56 This document describes extensions to OSPF to support mobile ad hoc 57 networks (MANETs). The extension, called OSPF-OR, includes a 58 mechanism for link-local signaling, a OSPF-MANET interface, a simple 59 technique to reduce the size of Hello packets by only transmitting 60 incremental state changes, and a method for optimized flooding of 61 routing updates. It also provides a means to reduce unnecessary 62 adjacencies to support larger MANET networks. 64 Table of Contents 66 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 67 1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . 3 68 1.2 Motivation for extending OSPF to support MANETs . . . . . 4 69 2. Requirements notation . . . . . . . . . . . . . . . . . . . 4 70 3. Proposed Enhancements . . . . . . . . . . . . . . . . . . . 4 71 3.1 OSPF-MANET Interface . . . . . . . . . . . . . . . . . . . 6 72 3.1.1 Interface Operation . . . . . . . . . . . . . . . . . 6 73 3.1.2 LSA Formats and Examples . . . . . . . . . . . . . . . 6 74 3.2 Incremental OSPF-MANET Hellos . . . . . . . . . . . . . . 10 75 3.2.1 The I Option Bit . . . . . . . . . . . . . . . . . . . 10 76 3.2.2 State Check Sequence TLV (SCS TLV) . . . . . . . . . . 10 77 3.2.3 Neighbor Drop TLV . . . . . . . . . . . . . . . . . . 11 78 3.2.4 Request From TLV (RF TLV) . . . . . . . . . . . . . . 11 79 3.2.5 Full State For TLV (FSF TLV) . . . . . . . . . . . . . 11 80 3.2.6 Neighbor Adjacencies . . . . . . . . . . . . . . . . . 12 81 3.2.7 Sending Hellos . . . . . . . . . . . . . . . . . . . . 13 82 3.2.8 Receiving Hellos . . . . . . . . . . . . . . . . . . . 14 83 3.2.9 Interoperability . . . . . . . . . . . . . . . . . . . 15 84 3.2.10 Support for OSPF Graceful Restart . . . . . . . . . 15 85 3.3 Optimized Flooding (Overlapping Relays) . . . . . . . . . 16 86 3.3.1 Operation Overview . . . . . . . . . . . . . . . . . . 17 87 3.3.2 Determination of Overlapping Relays . . . . . . . . . 17 88 3.3.3 Terminology . . . . . . . . . . . . . . . . . . . . . 18 89 3.3.4 Overlapping Relay Discovery Process . . . . . . . . . 18 90 3.3.5 The F Option Bit . . . . . . . . . . . . . . . . . . . 19 91 3.3.6 Active Overlapping Relay TLV (AOR TLV) . . . . . . . . 19 92 3.3.7 Willingness TLV . . . . . . . . . . . . . . . . . . . 20 93 3.3.8 Flooding and Relay Decisions . . . . . . . . . . . . . 20 94 3.3.9 Intelligent Transmission of Link State 95 Acknowledgments . . . . . . . . . . . . . . . . . . . 22 96 3.3.10 Important Timers . . . . . . . . . . . . . . . . . . 22 97 3.3.11 Miscellaneous Protocol Considerations . . . . . . . 23 98 3.3.12 Interoperability . . . . . . . . . . . . . . . . . . 24 99 3.4 New Bits in LLS Type 1 Extended Options and Flags . . . . 24 100 3.5 Smart Peering . . . . . . . . . . . . . . . . . . . . . . 24 101 3.5.1 Rationale for Smart Peering . . . . . . . . . . . . . . 24 102 3.5.2 Previous Related Work . . . . . . . . . . . . . . . . . 25 103 3.5.3 Smart Peering Solution . . . . . . . . . . . . . . . . 25 104 3.5.4 Advertising 2-Way Links in Router LSAs . . . . . . . . . 27 105 4. Security Considerations . . . . . . . . . . . . . . . . . . 30 106 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . 32 108 Roy, Chandra et al. Expires July 2010 [Page 2] 109 6. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 33 110 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 33 111 References . . . . . . . . . . . . . . . . . . . . . . . . . 34 112 Normative References . . . . . . . . . . . . . . . . . . 34 113 Informative References . . . . . . . . . . . . . . . . . 34 114 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 35 116 1. Introduction 118 Mobile Ad Hoc Networks have been an area of study for some time, 119 within various working groups and areas within the IETF, various 120 Military branches, and various government agencies. Recently, 121 networks with mobile ad hoc requirements are being proposed and 122 seriously considered for deployment in the near term, which means the 123 concepts and research now needs to be applied to deployed networks. 124 Towards that end, this draft applies many of the principles and 125 concepts learned through prior work to [OSPFv3], along with new 126 concepts based on current requirements. 128 1.1 Problem Statement 130 MANETs are synonymous with packet radio networks, which have been 131 around since the 1960s in a limited military capacity. With the boom 132 of mobile devices and wireless communications, MANETs are finding 133 scope in commercial and military environments. The aim of these 134 networks is to support robust and efficient communication in a mobile 135 wireless network by incorporating routing functionality into mobile 136 nodes. 138 A MANET is an autonomous set of nodes distributed over a wide 139 geographical area that communicate over bandwidth-constrained 140 wireless links. Each node may represent a transmitter, receiver, or 141 relay station with varying physical capabilities. Packets may 142 traverse through several intermediate (relay) nodes before reaching 143 their destination. These networks typically lack infrastructure: 144 nodes are mobile, there is no central hub or controller, and thus 145 there is no fixed network topology. Moreover, MANETs must contend 146 with a difficult and variable communication environment. Packet 147 transmissions are plagued by the usual problems of radio 148 communication, which include propagation path loss, signal multipath 149 and fading, and thermal noise. These effects vary with terminal 150 movement, which also induces Doppler spreading in the frequency of 151 the transmitted signal. Finally, transmissions from neighboring 152 terminals, known as multi-access interference, hostile jammers, and 153 impulsive interference, e.g., ignition systems, generators, and other 154 non-similar in-band communications, may contribute additional 155 interference. 157 Given this nature of MANETs, the existence of a communication link 158 between a pair of nodes is a function of their variable link quality, 159 including signal strength and bandwidth. Thus, routing paths vary 160 based on environment, and the resulting network topology. In such 162 Roy, Chandra et al. Expires July 2010 [Page 3] 163 networks, the topology may be stable for periods of time, and then 164 suddenly become unpredictable. Since MANETs are typically 165 decentralized systems, there are no central controllers or specially 166 designated routers to determine the routing paths as the topology 167 changes. All of the routing decisions and forwarding (relaying) of 168 packets must be done by the nodes themselves, and communication is on 169 a peer-to-peer basis. 171 1.2 Motivation for extending OSPF to support MANETs 173 The motivation to extend a standard protocol, OSPF (described in 174 [OSPF] and [OSPFv3]) to operate on MANET networks is twofold. The 175 primary reason is for interoperability--MANET devices need to be able 176 to work when plugged into a wireline network in as many cases as 177 possible. The junction point between a MANET and wire-line network 178 should also be as fluid as possible, allowing a MANET network to 179 "plug in" to just about any location within a wire-line network, and 180 find connectivity, etc., as needed. 182 While routes could be redistributed between two routing protocols, 183 one designed just for wire-line networks, and the other just for 184 MANET networks, this adds complexity and overhead to the MANET/ 185 wireline interface, increases the odds of an error being introduced 186 between the two domains, and decreases flexibility. 188 The second motivation is that OSPF is a well understand and widely 189 deployed routing protocol. This provides a strong basis of 190 experience and skills from which to work. A protocol which is known 191 to work can be extended, rather than developing a new protocol, which 192 must then be completely troubleshoot, tested, and modified over a 193 number of years. Working with a well known protocol allows 194 development effort to be placed in a narrowly focused area, rather 195 than rebuilding, from scratch, many things which are already known to 196 work. 198 2. Requirements notation 200 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 201 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 202 document are to be interpreted as described in [KEY]. 204 3. Proposed Enhancements 206 This document proposes modifications to [OSPFv3] to support mobile ad 207 hoc networks (MANETs). Note that it is possible to use the mechanism 208 defined in Section 3.2 and 3.3 independently of one another. 210 The challenges with deploying standard [OSPFv3] in a MANET 211 environment fit into two categories. First, traditional link-state 212 routing protocols are designed for a statically configured 213 environment. As a result, most of the configuration is done manually 214 when a new router is placed in the network. Thus, OSPF will not 215 function in an environment where routers interconnect and disconnect 217 Roy, Chandra et al. Expires July 2010 [Page 4] 218 in somewhat random topologies and combinations. There are 219 modifications that must be made in order for routers running the same 220 protocol to communicate in a heterogeneous and dynamic environment. 221 Second, a MANET network must transmit more state information to 222 maintain reachability. Therefore, OSPF will need scalability 223 enhancements to support MANETs. 225 Currently there is no defined interface type that describes a 226 wireless network. Wireless links have characteristics of both multi- 227 access and point-to-multipoint links. Treating wireless links as 228 multi-access does not take into account that not all nodes on the 229 same Layer 2 link have bi-directional connectivity. However, any 230 transmission on a link will reach nodes that are within transmission 231 range. In this way, the link is multi-access due to the fact that 232 two simultaneous transmissions may collide. A new interface type 233 needs to be defined in order to accurately describe this behavior. 235 The second category of challenges fall into is scalability. While 236 some flooding optimizations are present in OSPF, such as designated 237 router (DR) election, many of these were built under the assumption 238 of a true multi-access network. Wireless networks are not true 239 multi-access because it cannot be assumed that there is two-way 240 connectivity between everyone on the same Layer 2 link. Therefore, 241 optimizations such as DR election will not perform correctly in MANET 242 networks. Without any further optimizations in link-state flooding, 243 current OSPF would not be able to operate in a highly dynamic 244 environment in which links are constantly being formed and broken. 245 The amount of information that would need to be flooded would 246 overload the network. 248 Another scalability issue is the periodic transmission of Hello 249 messages. Currently, even if there are no changes in a router's 250 neighbor list, the Hello messages still list all the neighbors on a 251 particular link. For a MANET router, where saving bandwidth and 252 transmission power is a critical issue, the transmission of 253 potentially large Hello messages is particularly wasteful. 255 Finally, current routing protocols will form a neighbor relationship 256 with any router on a Layer 2 link that is correctly configured. For 257 MANET routers in a wireless network, this may lead to an excessive 258 number of parallel links between two routers if communication is 259 achieved via multiple interfaces. In a statically configured 260 network, this is not a problem, since the physical topology can be 261 built to prevent excessive redundancy. However, in a dynamic 262 network, there must exist additional mechanisms to prevent too many 263 redundant links. (Note that links between two nodes on different 264 radio types, different antenna, different channels, etc., are 265 considered different links and not redundant links.) In scalability 266 tests, it has been demonstrated that the presence of too many 267 redundant links will increase both the size of routing updates and 268 cause extra flooding resulting in even relatively small networks not 269 converging. 271 Roy, Chandra et al. Expires July 2010 [Page 5] 272 3.1 OSPF-MANET Interface 274 Interfaces are defined as the connection between a router and one of 275 its attached networks [OSPF]. Four types of interfaces have been 276 defined and supported in [OSPF] and [OSPFv3]: broadcast, NBMA, point- 277 to-point, and point-to-multipoint. 279 Point-to-multipoint model has been chosen to represent MANET 280 interfaces. (The features designed in this document MAY be included 281 on other interface types as appropriate.) The MANET interface allows 282 the following: 284 o OSPF treats all router-to-router connections over the MANET 285 interface as if they were point-to-point links. 286 o Link metric can be set on a per neighbor basis. 287 o Broadcast and multicast can be accomplished through Layer-2 288 broadcast or Layer-2 pseudo-broadcast. 289 * The MANET interface supports Layer-2 broadcast if it is able to 290 address a single physical message to all of the attached 291 neighbors. One such example is 802.11. 292 * The MANET interface supports Layer-2 pseudo-broadcast if it is 293 able to pick up a packet from the broadcast queue, replicate 294 the packet, and send a copy over each point-to-point link. One 295 such example is Frame Relay. 296 o An API must be provided for Layer-3 to determine the layer-2 297 broadcast capability. Based on the return of the API, OSPF 298 classifies the MANET interfaces into the following three types: 299 MANET broadcast, MANET pseudo-broadcast, and MANET non- broadcast. 300 o Multicast SHOULD be used for OSPF packets. When the MANET 301 interface supports Layer-2 broadcast or pseudo-broadcast, the 302 multicast process is transparent to OSPF. Otherwise, OSPF MUST 303 replicate multicast packets by itself. 305 3.1.1 Interface Operation 307 A MANET node has at least one MANET interface. MANET nodes can 308 communicate with each other through MANET interfaces. MANET nodes 309 can communicate with non-MANET routers only through normal 310 interfaces, such as Ethernet, ATM and etc. 312 For scalability reasons, it is not required to configure IPv6 global 313 unicast addresses on MANET interfaces. Instead, a management 314 loopback interface, with an IPv6 global unicast address, MAY be 315 configured on each MANET node. 317 The LSAs associated with a MANET interface SHOULD have the DC-bit set 318 in the OSPFv3 Options Field and the DoNotAge bit set in the LS Age 319 field as described in [OSPFv3]. Demand Circuits are an optional 320 feature, hence the DC-bit setting recommendation level is a SHOULD. 322 3.1.2 LSA Formats and Examples 324 LSA formats are specified in [OSPFv3]. 326 Roy, Chandra et al. Expires July 2010 [Page 6] 327 In order to display example LSAs, a network map is included below. 328 Router names are prefixed with the letters RT, network names with the 329 letter N, and router interface names with the letter I. 330 o Four MANET nodes, RT1, RT2, RT3, and RT4, reside in area 2. 331 o RT1 has one MANET interface I11. Through the interface, RT1 is 332 full adjacent to RT2, RT3, and RT4. 333 o RT2 has two MANET interfaces, I21 and I22, and one Ethernet 334 interface I23. RT2 is full adjacent to RT1 and RT4 through the 335 interface I21, and full adjacent to RT4 through the interface I22. 336 Stub network N1 is attached with RT2 through the interface I23. 337 o RT3 has one MANET interface I31, and is full adjacent to RT1 338 through the interface. 339 o RT4 has two MANET interfaces, I41 and I42. It is full adjacent to 340 RT2 through the interface I41, and full adjacent to RT1 and RT2 341 through the interface I42. 342 o Moreover, each MANET node is configured with a management loop- 343 back interface. 345 +---+I11 I21+---+I23 | 346 |RT1|-+----------+-|RT2|------|N1 347 +---+ | | +---+ | 348 | | VI22 349 | | + 350 | | | 351 | | | 352 | | | 353 | | | 354 | | + 355 | | ^I41 356 +---+ | +---+ 357 |RT3|-+ +-|RT4| 358 +---+I31 I42+---+ 360 The assignment of IPv6 global unicast prefixes to network links is 361 shown below. (Note: No IPv6 global unicast addresses are configured 362 on the MANET interfaces) 364 ----------------------------------------------------------- 365 RT1 LOOPBACK 2001:DB8:0001::/64 366 I11 n/a 367 RT2 LOOPBACK 2001:DB8:0002::/64 368 I21 n/a 369 I22 n/a 370 I23 2001:DB8:0012::/60 371 RT3 LOOPBACK 2001:DB8:0003::/64 372 I31 n/a 373 RT4 LOOPBACK 2001:DB8:0004::/64 374 I41 n/a 375 I42 n/a 377 Roy, Chandra et al. Expires July 2010 [Page 7] 378 The OSPF interface IDs and the link local addresses for the router 379 interfaces in the network illustrated above below. EUIxy represents 380 the 64-bit interface identifier of the interface Ixy, in Modified 381 EUI-64 format [IPV6ADD]. 383 Node Interface Interface ID Link Local address 384 ----------------------------------------------------------- 385 RT1 LOOPBACK 1 n/a 386 I11 2 fe80:0002::EUI11 387 RT2 LOOPBACK 1 n/a 388 I21 2 fe80:0002::EUI21 389 I22 3 fe80:0003::EUI22 390 I23 4 fe80:0004::EUI23 391 RT3 LOOPBACK 1 n/a 392 I31 2 fe80:0002::EUI31 393 RT4 LOOPBACK 1 n/a 394 I41 2 fe80:0002::EUI41 395 I42 3 fe80:0003::EUI42 397 3.1.2.1 Router LSAs 399 As an example, consider the router LSAs that node RT2 would 400 originate. Two MANET interfaces, consisting of 3 point-to-point 401 links, are presented. 403 RT2's router-LSA 405 LS age = DoNotAge+0 ;newly originated 406 LS type = 0x2001 ;router-LSA 407 Link State ID = 0 ;first fragment 408 Advertising Router = 192.0.2.2 ;RT2's Router ID 409 bit E = 0 ;not an AS boundary router 410 bit B = 0 ;not an area border router 411 Options = (V6-bit|E-bit|R-bit) 412 Type = 1 ;p2p link to RT1 over I21 413 Metric = 10 ;cost to RT1 414 Interface ID = 2 ;Interface ID of I21 415 Neighbor Interface ID = 2 ;Interface ID of I11 416 Neighbor Router ID = 192.0.2.1 ;RT1's Router ID 417 Type = 1 ;p2p link to RT4 over I21 418 Metric = 25 ;cost to RT4 419 Interface ID = 2 ;Interface ID of I21 420 Neighbor Interface ID = 3 ;Interface ID of I42 421 Neighbor Router ID = 192.0.2.4 ;RT4's Router ID 422 Type = 1 ;p2p link to RT4 over I22 423 Metric = 15 ;cost to RT4 424 Interface ID = 3 ;Interface ID of I22 425 Neighbor Interface ID = 2 ;Interface ID of I41 426 Neighbor Router ID = 192.0.2.4 ;RT4's Router ID 428 Roy, Chandra et al. Expires July 2010 [Page 8] 429 3.1.2.2 Link LSAs 431 A MANET node originates a separate Link-LSA for each attached 432 interface. As an example, consider the Link-LSA that RT3 will build 433 for its MANET interface I31. 435 RT3's Link-LSA for MANET interface I31 437 LS age = DoNotAge+0 ;newly originated 438 LS type = 0x0008 ;Link-LSA 439 Link State ID = 2 ;Interface ID of I31 440 Advertising Router = 192.0.2.3 ;RT3's Router ID 441 Rtr Pri = 1 ;default priority 442 Options = (V6-bit|E-bit|R-bit) 443 Link-local Interface Address = fe80:0002::EUI31 444 # prefixes = 0 ;no global unicast address 446 3.1.2.3 Intra Area Prefix LSAs 448 A MANET node originates an intra area prefix LSA to advertise its own 449 prefixes, and those of its attached stub links. As an example, 451 consider the intra area prefix LSA that RT2 will build. 453 RT2's intra area prefix LSA for its own prefixes 455 LS age = DoNotAge+0 ;newly originated 456 LS type = 0x2009 ;intra area prefix LSA 457 Link State ID = 177 ;or something else 458 Advertising Router = 192.0.2.2 ;RT2's Router ID 459 # prefixes = 2 460 Referenced LS type = 0x2001 ;router LSA reference 461 Referenced Link State ID = 0 ;always 0 for router-LSA 462 ;reference 463 Referenced Advertising Router = 192.0.2.2 464 ;RT2's Router ID 465 PrefixLength = 64 ;prefix on RT2's LOOPBACK 466 PrefixOptions = 0 467 Metric = 0 ;cost of RT2's LOOPBACK 468 Address Prefix = 2001:DB8:0002:: 469 PrefixLength = 60 ;prefix on I23 470 PrefixOptions = 0 471 Metric = 10 ;cost of I23 472 Address Prefix = 2001:DB8:0012:: 474 Note: MANET nodes may originate Intra-Area-Prefix-LSAs for attached 475 transit (broadcast/NBMA) networks. This is normal behavior defined 476 in [OSPFv3], which is irrelevant to MANET interfaces. Please consult 477 [OSPFv3] for details. 479 Roy, Chandra et al. Expires July 2010 [Page 9] 480 3.2 Incremental OSPF-MANET Hellos 482 In MANETs, reducing the size of periodically transmitted packets can 483 be very important in decreasing the total amount of overhead 484 associated with routing. Towards this end, removing the list of 485 neighbors from Hello packets unless that information changes can 486 reduce routing protocol overhead. While the reduction for each hello 487 packet is small, over time it will be significant. 489 A new option bit is defined in this document to facilitate the 490 operation of incremental Hello packets. A new SCS TLV and Neighbor 491 Drop TLV are also defined, transmitted using LLS [LLS]. 493 3.2.1 The I Option Bit 495 A new I bit is defined in the LLS Type 1 Extended Options and Flags 496 field. The bit is defined for Hello packets and indicates that only 497 incremental information is present. See Section 5 for placement of 498 the I bit. 500 3.2.2 State Check Sequence TLV (SCS TLV) 502 A new TLV is defined that indicates the current state, which is 503 represented by an State Check Sequence (SCS) number of the 504 transmitting router. 506 0 1 2 3 507 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 508 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+-+ 509 | Type | Length | 510 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+-+ 511 | SCS Number |R|FS|N | Reserved | 512 +-----------------------------------------------------------------+ 514 o Type: 6 515 o Length: Set to 4. 516 o SCS Number: A circular two octet unsigned integer indicating the 517 current state of the transmitting device. Note that when the 518 incremental Hello mechanism is invoked (or re-started), an initial 519 SCS value of '1' SHOULD be used for the first incremental Hello 520 packet. This sequence number is referred to as InitialSCS. Note 521 that InitialSCS also implies a full state. 522 o R: Request bit. If set, this is a request for current state. The 523 list of routers who should respond to this request are listed in 524 the RF TLV defined below. If the RF TLV is not present, it is 525 assumed that the request is meant for all nodes. 526 o FS: Full State bit. If set, the Hello packet contains full state 527 as far as the neighbor(s) in the FSF TLV (defined below) are 528 concerned. If the FSF TLV is not present, the Hello packet 529 contains full state for all neighbors. 531 Roy, Chandra et al. Expires July 2010 [Page 10] 532 o N: InComplete bit. If NOT set, the complete state associated with 533 the SCS number is included in the Hello packet. If set, indicates 534 that the appended TLVs are being sent 'persistently', and that 535 there is more state associated with the SCS number that was sent 536 originally, but is not included in this Hello packet. This bit 537 allows any desired TLVs to be sent 'persistently' for a number of 538 Hellos with the same SCS number without requiring all of the TLVs 539 associated with that SCS number to be transmitted. The first time 540 an SCS number is sent, the entire state associated with that SCS 541 number is transmitted, and the 'N' bit MUST NOT be set. 542 o Reserved: Set to 0. Reserved for future use. 544 A Hello with the SCS TLV appended with the R bit set will be referred 545 to as a Hello request. 547 3.2.3 Neighbor Drop TLV 549 A new TLV is defined in this document which indicates neighbor(s) 550 that have been removed from the list of known neighbors. 552 0 1 2 3 553 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 554 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 555 | Type | Length | 556 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 557 | Dropped Neighbor(s) | 558 +---------------------------------------------------------------+ 559 | .... 560 +-------------------- 562 o Type: 7 563 o Length: Set to the number of dropped neighbors included in the TLV 564 multiplied by 4. 565 o Dropped Neighbor(s) - Router ID of the neighbor being dropped. 567 3.2.4 Request From TLV (RF-TLV) 569 A new TLV is defined in this document which indicates neighbor(s) 570 from which the latest Hello state is being requested. 572 0 1 2 3 573 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 574 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 575 | Type | Length | 576 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 577 | Request From Neighbor(s) | 578 +---------------------------------------------------------------+ 579 | .... 580 +-------------------- 582 Roy, Chandra et al. Expires July 2010 [Page 11] 583 o Type: 8 584 o Length: Set to the number of neighbors included in the TLV 585 multiplied by 4. 586 o Request From Neighbor(s) - Router ID of the neighbor(s) from which 587 o Hello state is being requested. 589 3.2.5 Full State For TLV (FSF-TLV) 591 A new TLV is defined in this document which indicates neighbor(s) to 592 which the transmitting node is responding with full state. 594 0 1 2 3 595 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 596 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 597 | Type | Length | 598 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 599 | Full State For Neighbor(s) | 600 +---------------------------------------------------------------+ 601 | .... 602 +-------------------- 604 o Type: 9 605 o Length: Set to the number of neighbors included in the TLV 606 multiplied by 4. 607 o Full State For Neighbor(s) - Router ID of the neighbor(s) should 608 process this packet. 610 3.2.6 Neighbor Adjacencies 612 This section describes building neighbor adjacencies and the failure 613 of such adjacencies using the incremental Hello signaling. 615 3.2.6.1 Building Neighbor Adjacencies 617 Hello packets are sent periodically in accordance with [OSPF] and 618 [OSPFv3]. An OSPF implementation which supports sending only partial 619 neighbor information in Hello packets SHOULD always set the I bit in 620 its transmitted Hello packets, except as described elsewhere in this 621 document. Hello packets MAY be suppressed from being transmitted 622 every HelloInterval if other packet transmissions are sent by the 623 router during that time. 625 On receiving a Hello packet from a new neighbor (in this context, a 626 new neighbor is a neighbor in less than Init state as defined in 627 Section 10.1 [OSPF]), if the Hello has the I bit set, a router will: 628 o Place the new neighbor in the neighbor list described in [OSPFv3], 629 A.3.2. 630 o Increment the router's SCS number that it will use in its next 631 Hello (indicated in the SCS TLV). 632 o When the neighbor has reached the EXCHANGE state, described in 633 [OSPF], 10.1, it is removed from the list of neighbors described 634 in [OSPFv3], A.3.2. 636 Roy, Chandra et al. Expires July 2010 [Page 12] 637 o If the neighbor is not a DR or backup designated router (BDR) on 638 an OSPF broadcast link, and the neighbor is advertised as 639 connected in the Network LSA advertised by the DR, it is removed 640 from the list of neighbors described in [OSPFv3], A.3.2. 642 3.2.6.2 Adjacency Failure 644 On discovering an adjacency failure (going to state less than 645 EXCHANGE), a router using I bit signaling SHOULD: 646 o Remove the adjacent router from local tables, and take the 647 appropriate actions for a failed adjacency described in [OSPF] and 648 [OSPFv3]. 649 o Add the formerly adjacent router to a Neighbor Drop TLV. 650 o Increment the router's SCS number that it will transmit in its 651 next Hello. 652 o Transmit Hellos with this Neighbor Drop TLV - It may be desirable 653 to send the Neighbor Drop TLV in three consecutive Hellos to 654 increase the probability of reception. In this case, 'persistent' 655 Hello packets would be sent with the same SCS number, the Neighbor 656 Drop TLV, and the 'N' bit set. Thus, the receiver knows that the 657 Neighbor Drop TLV is being sent persistently and there is more 658 state associated with the SCS in case it must request missing 659 state presumably transmitted in a previous Hello. 661 3.2.7 Sending Hellos 663 When a device is first attached to a network (whether through being 664 brought into range of another device, powering the device on, or 665 enabling the device's radio interface, etc.), it will need to obtain 666 complete neighbor state from each of its neighbors before it can 667 utilize the incremental Hello mechanism. Thus, upon initialization, 668 a device MAY send a multicast Hello request (and omit the 'Request 669 From' TLV). Neighbors will receive the request and respond with a 670 Hello with their complete neighbor state. 672 If a device is in INIT state with a neighbor and receives a Hello 673 from the neighbor without its router ID listed in the neighbor list, 674 the device SHOULD request the current state from the neighbor. Note 675 that this is to avoid a race condition since the received Hello can 676 either mean that the device is NOT SEEN by the neighbor, or that the 677 device is adjacent and not listed in the incremental list. Thus, by 678 receiving a Hello request, the neighbor will respond with its 679 neighbor state for the neighbor. 681 The first Hello packet with a particular SCS number MUST contain the 682 full state associated with that SCS number, i.e., all state changes 683 since the last SCS number. The 'N' bit MUST NOT be set in the State 684 Check Sequence TLV. 686 Incremental Hello packets can be sent persistently (sent in k 687 successive Hello packets), with flexibility in the actual amount of 688 information being sent. The three options include: 690 Roy, Chandra et al. Expires July 2010 [Page 13] 691 o The entire incremental Hello packet is sent persistently. This is 692 accomplished by simply sending the entire state associated with a 693 SCS number for k successive Hellos. Since the SCS number remains 694 the same, the 'N' bit is not set in these incremental Hello 695 packets. 696 o Partial information for a particular SCS number is sent 697 persistently. After the first Hello packet with a particular SCS 698 number is sent, only the TLVs that are desired to be sent 699 persistently are sent in subsequent Hellos with the same SCS 700 number and the 'N' bit set. 701 o No information is sent persistently. This is simply the default 702 behavior where an incremental Hello packet with a particular SCS 703 number is only sent once. 705 3.2.8 Receiving Hellos 707 Each OSPF device supporting incremental Hello signaling, as described 708 in this document, MUST keep the last known SCS number from each 709 neighbor it has received Hellos from as long as the neighbor 710 adjacency structure is maintained. 712 If a device receives a Hello from an adjacent neighbor with an SCS 713 number less than the last known SCS number from that neighbor, it 714 MUST first check if the SCS number is a wrap around. Wrap around is a 715 condition when the last known SCS number is MAX_SCS (65535) and the 716 new SCS number is 1. If it is not a wrap around, then the device MUST 717 send a Hello request to the neighbor. 719 If it is a wrap around or if a device receives a Hello from an 720 adjacent neighbor with an SCS number one greater than the last known 721 SCS number from that neighbor, it MUST: 722 o Examine the neighbor list described in [OSPFv3], A.3.2. If any 723 neighbors are contained in this list, increment the SCS number 724 contained in the adjacent neighbor's data structure. 725 o Examine the Neighbor-Drop TLV as described in the section 3.2.6.2. 726 If this list contains a neighbor other than the local router, 727 increment the SCS number contained in the adjacent neighbor's data 728 structure. 729 o Examine the Neighbor Drop TLV as described in the section 3.2.6.2. 730 If the local router identifier is contained in this list, destroy 731 the transmitting adjacent neighbor's data structures. 732 o Examine any other TLVs incrementally signaled, as described in 733 drafts referring to this document. If there are other state 734 changes indicated, increment the SCS number contained in the 735 adjacent neighbor's data structure. 736 o If no state change information is contained in the received Hello, 737 a request for current state (by setting the 'R' bit) is sent in 738 the next Hello. 740 If a device receives a Hello from an adjacent neighbor with an SCS 741 number greater than the last known SCS number + 1 from that neighbor, 742 it MUST send a Hello request to the neighbor since it may be missing 743 some neighbor state. 745 Roy, Chandra et al. Expires July 2010 [Page 14] 746 3.2.8.1 Receiving Hellos with the N Bit Set 748 If a device receives a Hello with the SCS TLV included, and the 'N' 749 bit set in this TLV, it MUST verify that it has already received the 750 SCS number with the 'N' bit NOT set from the neighbor. If the device 751 determines that this is the first reception of the SCS number from 752 this neighbor, then it MUST send a Hello request to the neighbor 753 since it missed the initial Hello packet with the SCS number, and 754 thus is missing state. 756 3.2.8.2 Receiving Hellos with the R Bit Set 758 If a device receives a Hello with the SCS TLV included, and the R bit 759 set, it looks for the RF TLV. If it's router ID is listed in the RF 760 TLV or the TLV is not found, it includes its full state in the next 761 Hello. This MUST include: 762 o The neighbor ID of the requesting neighbor(s) in the list of 763 neighbors described in [OSPFv3], A.3.2., 764 o An SCS TLV with the transmitter's current SCS number, and the FS 765 bit set. Note that the transmitter's SCS number is NOT 766 incremented. 767 o Any other TLVs, defined in other drafts referencing this document, 768 indicating the current state of the local system. 769 o The neighbor ID of all the neighbors who have requested current 770 state, in the FSF TLV. 772 If the full state is being sent to a large number of existing 773 neighbors, and implementation could choose to instead generate a full 774 state for all neighbors and omit the FSF TLV. 776 3.2.8.3 Receiving Hellos with the FS Bit Set 778 When a device receives a Hello with the SCS TLV included, and the FS 779 bit set, the Hello packet contains the neighbor's full state for the 780 device. The packet SHOULD be processed as follows: 781 o If the received SCS number is equal to the last known SCS number, 782 the packet SHOULD be ignored since the device already has the 783 latest state information. 784 o If the received SCS number is different than the last known SCS 785 number, this Hello has new information and MUST be parsed. 786 o If it is listed in the FSF TLV or if the FSF TLV is not present, 787 the device MUST save the SCS number, process the Hello as 788 described in section 3.2.8, and process any other appended TLVs. 790 3.2.9 Interoperability 792 On receiving a Hello packet from a new neighbor without the I bit 793 set, the local router will continue to place that router's identifier 794 in transmitted Hellos on this link as described in [OSPFv3], A.3.2. 796 3.2.10 Support for OSPF Graceful Restart 798 OSPF graceful restart, as described in [OSPFREST] and [OSPFGR], 800 Roy, Chandra et al. Expires July 2010 [Page 15] 801 relies on the lack of neighbors in the list of neighbors described in 802 [OSPFv3], A.3.2, to determine that an adjacent router has restarted, 803 and other signaling to determine the adjacency should not be torn 804 down. If all Hello packets transmitted by a given router have an 805 empty Hello list, reliance on an empty Hello packet to signal a 806 restart (or to reliably tear down an OSPF adjacency) is no longer 807 possible. Hence, this signaling must be slightly altered. 808 When a router would like to tear down all adjacencies, or signal it 809 has restarted: 810 o On initially restarting, during the first RouterDeadInterval after 811 restart, the router will transmit Hello packets with an empty 812 neighbor list, and the I bit cleared. Any normal restart or other 813 signaling may be included in these initial Hello packets. 814 o As adjacencies are learned, these newly learned adjacent routers 815 are included in the multicast Hellos transmitted on the link. 816 o After one RouterDeadInterval has passed, the incremental Hello 817 mechanism is invoked. An incremental Hello packet with full state 818 is sent with the I bit set, and the SCS TLV included with the 819 FS bit set and the InitialSCS value, e.g., SCS of '1'. 820 Subsequent Hello packets will include only incremental state. 822 Routers which are neighboring with a restarting router MUST continue 823 sending their Hello packets with the I bit set. 825 3.3 Optimized Flooding (Overlapping Relays) 827 A component that may influence the scalability and convergence 828 characteristics of OSPF [OSPF],[OSPFv3] in a MANET environment is how 829 much information needs to be flooded. The ideal solution is that a 830 router will receive a particular routing update only once. 831 However, there must be a trade off between protocol complexity and 832 ensuring that every speaker in the network receives all of the 833 information. Note that a speaker refers to any node in the network 834 that is running the routing protocol and transmitting routing updates 835 and Hello messages. 837 Controlling the amount of information on the link has increased 838 importance in a MANET environment due to the potential transmission 839 costs and resource availability in general. 841 In some environments, a group of speakers that share the same logical 842 segment may not be directly visible to each other; some of the 843 possible causes are the following: low signal strength, long distance 844 separation, environmental disruptions, partial VC meshing, etc. In 845 these networks, a logical segment refers to the local flooding domain 846 dynamically determined by transmission radius. In these situations, 847 some speakers (the ones not able to directly reach the sender) may 848 never be able to synchronize their databases. To solve the 849 synchronization issues encountered in these environments, a mechanism 850 is needed through which all the nodes on the same logical segment can 851 receive the routing information, regardless of the state of their 852 adjacency to the source. 854 Roy, Chandra et al. Expires July 2010 [Page 16] 855 3.3.1 Operation Overview 857 The optimized flooding operation relies on the ability of a speaker 858 to advertise all of its locally connected neighbors. In OSPF, this 859 ability is realized through the use of link state advertisements 860 (LSA)s [OSPF],[OSPFv3]. 862 A speaker receives router LSAs from its adjacent neighbors. A 863 speaker's router LSA conveys the list of the adjacent speakers of the 864 originator ("neighbor list"). The local speaker can compare the 865 neighbor list reported by each speaker to its own neighbor list. If 866 the local neighbor list contains adjacent speakers that the 867 originator cannot reach directly (i.e. those speakers that are not in 868 the originator's neighbor list), then these speakers are locally 869 known as non-overlapping neighbors for the originator. 871 The local speaker should relay any routing information to non- 872 overlapping neighbors of the sender based on the algorithm outlined 873 in the section 3.3.8. Because more than one such speaker may exist, 874 the mechanism is called "overlapping relays." The algorithm, however, 875 does select the set of overlapping relays that should transmit first. 876 This set is known as the active set of overlapping relays for a 877 speaker. 879 3.3.2 Determination of Overlapping Relays 881 The first step in the process is for each speaker to build and 882 propagate their neighbor lists in router LSAs packets. Every speaker 883 is then in a position to determine their two-hop neighborhood, i.e., 884 those nodes that are neighbors of the speaker's one-hop neighbors. 886 A bidirectional neighbor is considered an overlapping relay for a 887 speaker if it can reach a node in the two-hop neighborhood of the 888 speaker, i.e., if it has one-hop neighbors (excluding the speaker 889 itself). 891 The set of active overlapping relays for a speaker is the minimum set 892 of direct neighbors such that every node in the two-hop neighborhood 893 of the speaker is a neighbor of a least one overlapping relay in the 894 active set. 896 Each speaker SHOULD select a set of active overlapping relays based 897 on a selection algorithm (one such algorithm is suggested in section 898 3.3.4 and is based on the MPR selection algorithm described in 899 [OLSR]). The behavior of the overlapping relays MUST follow that 900 specified in section 3.3.8. 902 Note that a speaker MUST NOT choose a neighbor to serve as an active 903 overlapping relay if that neighbor set the 'N' bit in its Active 904 Overlapping Relay TLV as defined in Section 3.3.6, unless the 905 neighbor is the only neighbor to reach a two-hop neighbor. 907 Roy, Chandra et al. Expires July 2010 [Page 17] 908 Election of active overlapping relays is done across interfaces, and 909 thus, it is node-based and not link-based. 911 3.3.3 Terminology 913 The following heuristic and terminology for active overlapping relay 914 selection is largely taken from [OLSR]: 915 o FULL: Neighbor state FULL as defined in [OSPF] & [OSPFv3]. Note 916 that all neighbor references in this document are assumed to be 917 FULL neighbors. 918 o N: N is the set of FULL neighbors of the node. 919 o 2-hop FULL neighbors (N2): The list of 2-hop neighbors of the node 920 that are FULL and that can be reached from direct neighbors, 921 excluding any directly connected neighbors. 922 o Active Set: A (sub)set of the neighbors selected such that through 923 these selected nodes, all 2-hop FULL neighbors are reachable. 924 o D(y): The degree of a one hop neighbor node y (where y is a member 925 of N), is defined as the number of FULL neighbors of node y, 926 EXCLUDING all the members of N and EXCLUDING the node performing 927 the computation. 929 3.3.4 Overlapping Relay Discovery Process 931 A possible algorithm for discovering overlapping relays is the 932 following: 933 1. Start with an active set made of all members of N that have set 934 the 'A' bit in their Active Overlapping Relays TLV as defined in 935 Section 3.3.6. 936 2. Calculate D(y), where y is a member of N, for all nodes in N. 937 3. Add to the active set those nodes in N, which are the *only* 938 nodes to provide reachability to a node in N2, i.e., if node-b in 939 N2 can be reached only through a symmetric link to node-a in N, 940 then add node-a to the active set. Remove the nodes from N2 941 which are now covered by a node in the active set. 942 4. While there exist nodes in N2 which are not covered by at least 943 one node in the active set: 944 1. For each node in N, calculate the reachability, i.e., the 945 number of nodes in N2 which are not yet covered by at least 946 one node in the active set, and which are reachable through 947 this one hop neighbor; 948 2. Select as an active overlapping relay the node with highest 949 Willingness among the nodes in N with non-zero reachability. 950 In case of multiple choice select the node which provides 951 reachability to the maximum number of nodes in N2. In case 952 of multiple nodes providing the same amount of reachability, 953 select the node as active whose D(y) is greater. As a final 954 tie breaker, the node with the highest router ID should be 955 chosen. Remove the nodes from N2 which are now covered by a 956 node in the active set. 957 5. As an optimization, process each node, y, in the active set in 958 increasing order of Willingness. If all nodes in N2 are still 959 covered by at least one node in the active set excluding node y, 961 Roy, Chandra et al. Expires July 2010 [Page 18] 962 and if Willingness of node y is smaller than MAX_WILLINGNESS, 963 then node y should be removed from the active set. 965 3.3.5 The F Option Bit 967 A single new option bit, the F bit, is defined in the LLS Type 1 968 Extended Options and Flags field. The F bit indicates that the node 969 supports the Optimized Flooding mechanism as specified in this draft. 970 See Section 5 for placement of the F bit. 972 3.3.6 Active Overlapping Relay TLV (AOR TLV) 974 A new TLV is defined so that each speaker can convey its set of 975 active overlapping relays in the Hello messages. The TLV is 976 transmitted using LLS [LLS]. 978 0 1 2 3 979 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 980 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 981 | Type | Length | 982 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 983 | Relays Added |A|N| Reserved | 984 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 985 | Router ID(s) of Active Overlapping Relay(s) | 986 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 987 | ... | 988 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 990 o Type: 10 991 o Length - variable; Length of TLV in bytes NOT including Type and 992 Length. 993 o Relays Added - variable; Number of active overlapping relays that 994 are being added. Note that the number of active overlapping 995 relays that are being dropped is then given by: [(Length - 4)/4 - 996 Relays Added]. 997 o A bit - If this bit is set, the node is specifying that it will 998 always flood routing updates that it receives, regardless of 999 whether it is selected as an Active Overlapping Relay. 1000 o N bit - If this bit is set, the node is specifying that it most 1001 likely will not flood routing updates. The node SHOULD NOT be 1002 chosen to be an active overlapping relay unless it is the *only* 1003 neighbor that can reach two-hop neighbor(s). Note that if the 1004 node is selected as an Active Overlapping relay and the node can 1005 not perform the required duties, network behavior is not 1006 compromised since it results in the same behavior as if the node 1007 was not chosen as an active overlapping relay. 1008 o Reserved - Reserved for future use. MUST be set to zero by the 1009 sender and MUST be ignored upon reception. 1010 o Router ID(s) of Active Overlapping Relay(s) - The router ID(s) of 1011 neighbor(s) that are either chosen to serve as an active 1012 overlapping relay, or removed from serving as an active 1013 overlapping relay. The active overlapping relays that are being 1015 Roy, Chandra et al. Expires July 2010 [Page 19] 1016 added MUST be listed first, and the number of such relays MUST 1017 equal Add Length. The remaining list of relays are being dropped 1018 as active overlapping relays, and the number of such relays MUST 1019 equal [(Length - 4)/4 - Relays Added]. 1021 Note that the 'A' bit and 'N' bit are independent of any particular 1022 selection algorithm to determine the set of Active Overlapping 1023 Relays. However, the bits SHOULD be considered as input into the 1024 selection algorithm. 1026 If a node is selected as an active overlapping relay and it does not 1027 support the Incremental Hello mechanism defined in section 3.2, then 1028 it SHOULD always be included as an Active Overlapping Relay in the 1029 TLV. Note that while a node needs to know whether it is an active 1030 overlapping relay, it does not necessarily have to know the 1031 identities of the other active overlapping relays. 1033 3.3.7 Willingness TLV 1035 A new TLV is defined so that each speaker can convey its willingness 1036 to serve as an active overlapping relay in the Hello message. The 1037 TLV is transmitted using the LLS [LLS]. 1039 0 1 2 3 1040 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 1041 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1042 | Type | Length | 1043 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1044 | Willingness | Reserved | 1045 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1047 o Type: 11 1048 o Length - 4 bytes. It does not include the Type and Length fields. 1049 o Willingness - 1 byte to indicate the willingness of the node to 1050 serve as an active overlapping relay for its neighbors. 1051 * 0: MIN_WILLINGNESS 1052 * 128: DEFAULT_WILLINGNESS 1053 * 255: MAX_WILLINGNESS 1055 The TLV is optional and MUST be silently ignored if not understood. 1056 If the Willingness TLV is not included in the Hello packet, the 1057 Willingness value SHOULD be taken as DEFAULT_WILLINGNESS. 1059 3.3.8 Flooding and Relay Decisions 1061 The decision whether to relay any received LSAs and when to relay 1062 such information, is made depending on the topology and whether the 1063 node is part of the set of active overlapping relays. 1065 Upon receiving an LSA from an bi-directional neighbor, a node makes 1066 flooding decisions based on the following algorithm: 1068 Roy, Chandra et al. Expires July 2010 [Page 20] 1069 1. If the node is an active overlapping relay for the adjacent 1070 speaker, then the router SHOULD immediately relay any information 1071 received from the adjacent speaker. 1073 2. If the node is a non-active overlapping relay for the adjacent 1074 speaker, then the router SHOULD wait a specified amount of time 1075 (PushbackInterval plus jitter, see section 3.3.10) to 1076 decide whether to transmit. [Jitter is used to try to avoid 1077 several non-active overlapping relays from propagating redundant 1078 information.] Note that a node with the 'N' bit set in the 1079 'Active Overlapping Relays' Extension will not be chosen as an 1080 active overlapping relay unless it is the only node to provide 1081 reachability to a two-hop neighbor. However, it MUST perform the 1082 duties of a non-active overlapping relay as required. Non-active 1083 overlapping relays MUST follow the acknowledgment mechanism 1084 outlined in the section 3.3.9. 1085 1. During this time, if the node determines that flooding the 1086 LSA will only result in a redundant transmission, the node 1087 MUST suppress its transmission. Otherwise, it MUST transmit 1088 upon expiration of PushbackInterval plus jitter. 1089 2. If a non-active overlapping relay hears a re-flood from 1090 another node that covers its non-overlapping neighbors before 1091 its timer to transmit expires, it SHOULD reset its 1092 PushbackInterval plus jitter timer. (Note that the 1093 implementation should take care to avoid resetting the 1094 PushbackInterval timer based on transmissions from active 1095 overlapping relays.) During this time, if the node 1096 determines that flooding the update will only result in a 1097 redundant transmission, the node MUST suppress its 1098 transmission. Otherwise, it MUST transmit upon expiration of 1099 PushbackInterval + jitter. 1100 3. If a non-active overlapping relay hears an old instance of 1101 the LSA during this time, it SHOULD ignore the LSA and it 1102 SHOULD NOT send a unicast packet to the neighbor with the 1103 most recent LSA as specified in [OSPFv3]. 1104 3. For LSAs that are received unicast because of retransmission by 1105 the originator, the node MUST determine whether it has already 1106 received the LSA from another speaker. If it already has the 1107 current instance of the LSA in its database, it MUST do nothing 1108 further in terms of flooding the LSA (since it would have taken 1109 appropriate behavior when it initially received the LSA.) 1110 However, if it does not have the current instance of the LSA in 1111 its database, it MUST take action according to the rules above, 1112 just as if it received the multicast LSA. The acknowledgment 1113 mechanism outlined in the section 3.3.9 MUST be followed, and any 1114 timeout mechanism for unicast LSAs MAY be followed. 1116 Note that a node can determine whether further flooding a LSA will 1117 only result in a redundant transmission by already having heard link 1118 state acknowledgments (ACKs) or floods for the LSA from all of its 1119 neighbors. 1121 Roy, Chandra et al. Expires July 2010 [Page 21] 1122 Due to the dynamic nature of a network, the set of active overlapping 1123 relays may not be up to date at the time the relay decision is made 1124 or may not be able to perform the flooding duties, e.g., due to poor 1125 link quality. The non-active overlapping relays prevent this 1126 situation from causing database synchronization issues and thus, 1127 packet loss. 1129 Since the originator of the information, the relay, and the receiver 1130 are all in the same dynamically determined local flooding domain, the 1131 relay MUST NOT change the routing update information. In general, 1132 LSAs SHOULD be sent to a well-known multicast address. In some 1133 cases, routing updates MAY be sent using unicast packets. 1135 3.3.9 Intelligent Transmission of Link State Acknowledgments 1137 In order to optimize the bandwidth utilization on the link, a speaker 1138 MUST follow these recommendations related to ACK transmissions: 1139 1. All ACKs MUST be sent via multicast. 1140 2. Typically, LSAs are acknowledged by all of the adjacent speakers. 1141 In the case of relayed information, the relay MUST only expect 1142 either explicit or implicit acknowledgments from neighbors that 1143 have not previously acknowledged this LSA. 1144 3. Because routing updates are sent via multicast, the set of 1145 overlapping speakers will usually receive the same update more 1146 than once. A speaker SHOULD only acknowledge the first update 1147 received on the link. 1148 4. An active overlapping relay SHOULD NOT explicitly acknowledge 1149 information that it is relaying. The relayed information will 1150 serve as an acknowledgment to the sender. If no information is 1151 being relayed, than an explicit ACK MUST be sent. 1152 5. Several ACKs MAY be bundled into a single packet. The wait 1153 (AckInterval) before sending one such packet reduces the number 1154 of packet transmissions required in acknowledging multiple LSAs. 1155 6. All ACK packets SHOULD reset the RouterDeadInterval at the 1156 receiver. If there is no state waiting to be transmitted in a 1157 Hello packet at the sender, then the HelloInterval at the sender 1158 SHOULD be reset. Note that an ACK serves as a Hello packet with 1159 no state change. 1160 7. Any LSA received via unicast MUST be acknowledged. (Note that 1161 acknowledgment is via multicast as specified in rule (1) above.) 1163 An ACK received from a non-overlapping neighbor should prevent 1164 redundant transmission of the information to it by another 1165 overlapping relay. 1167 3.3.10 Important Timers 1169 This section details the timers that are introduced in sections 3.3.8 1170 and 3.3.9. 1172 o PushbackInterval: The length of time in seconds that a non-active 1173 overlapping relay SHOULD wait before further flooding an LSA if 1175 Roy, Chandra et al. Expires July 2010 [Page 22] 1176 needed. This timer MUST be less than 1/2 of the RxmtInterval 1177 [OSPF],[OSPFv3] minus propagation delays, i.e., (PushbackInterval 1178 + propagation delay) < RxmtInterval/2. The PushbackInterval is 1179 set by a non-active overlapping relay upon reception of an LSA. 1180 o AckInterval: After a node determines that it must transmit an ACK 1181 and the AckInterval timer is not already set, the node SHOULD set 1182 the AckInterval timer. The AckInterval is the length of time in 1183 seconds that a node should wait in order to transmit many ACKs in 1184 the acknowledgment packet. This wait reduces the number of 1185 packet transmissions required in acknowledging multiple LSAs. The 1186 AckInterval MUST be less than the PushbackInterval minus 1187 propagation delays, i.e., (AckInterval + propagation delay) < 1188 PushbackInterval. 1190 3.3.11 Miscellaneous Protocol Considerations 1192 The mechanism described refers to the operation of relays on a common 1193 media segment. In other words, an LSA is only relayed out the same 1194 interface through which it was received. However, the concept of 1195 information relay may be extended to the flooding of all link state 1196 advertisements received on any interface (and forwarded on any other 1197 interface). OSPF works on the premise that all of the nodes in a 1198 flooding domain will receive all of the routing information. Note 1199 that one of the important properties is that the routing information 1200 is not altered when relayed. 1202 If each speaker advertised all of its adjacent neighbors on all 1203 interfaces, then the overlap check would result in the determination 1204 of which speakers are adjacent to both speakers. As a result, link 1205 state information should only be flooded to non-overlapping neighbors 1206 (taking all of the interfaces into account). 1208 The flooding mechanism in OSPF relies on a designated router to 1209 guarantee that any new LSA received by one router attached to the 1210 broadcast network will be re-flooded properly to all the other 1211 routers attached to the broadcast network. Such designated routers 1212 must be able to reach all of the other speakers on the same subnet. 1213 A designated router SHOULD NOT be elected if overlapping relays are 1214 used. 1216 If such designated routers already exist, then the relays MUST be 1217 capable of differentiating them, and then making the relaying 1218 decisions based on the OSPF's normal operation. As a result, there 1219 may be groups of neighbors to which some information should not be 1220 relayed. This mode of operation is NOT RECOMMENDED as it adds to the 1221 complexity of the system. 1223 The intent of the overlapping relay mechanism is to optimize flooding 1224 of routing control information. However, other information (such as 1225 data) may also be relayed in some networks using the same mechanism. 1227 Roy, Chandra et al. Expires July 2010 [Page 23] 1228 3.3.12 Interoperability 1230 On receiving a Hello packet from a new neighbor without the F bit 1231 set, the local router will assume that the new neighbor will flood 1232 normally as described in [OSPFv3]. Thus, the local router SHOULD 1233 include the neighbor in its overlapping relay set since the neighbor 1234 will flood by default. This will allow the local router to more 1235 optimally select its entire overlapping relay set. 1237 If the F bit is set and the I bit as defined in Section 3.2 is not 1238 set in the neighbor's Hello and the neighbor is selected as an 1239 overlapping relay by the local router, the local router will continue 1240 to include the neighbor's identifier in its active relay set. 1242 3.4 New Bits in LLS Type 1 Extended Options and Flags 1244 Two new option bits are defined in the "LLS Type 1 Extended Options 1245 and Flags" Field [LLS] as follows: 1247 o I bit - defined in Section 3.2.1: The I bit is only defined for 1248 Hello packets and indicates that only incremental information is 1249 present. 1250 o F bit - defined in Section 3.3.5: The F bit indicates that the 1251 node supports the Optimized Flooding mechanism as specified in 1252 this draft. 1254 3.5 Smart Peering 1256 There is significant overhead in OSPF when a router has to establish 1257 adjacencies with every peer with whom it can verify 2-way 1258 connectivity. OSPF supports the broadcast network type for these 1259 scenarios, where you only have to peer with the designated router 1260 (DR). However,a full mesh of connectivity is required for proper 1261 operation and this doesn't help in networks with overlapping partial 1262 meshes of connectivity. This draft proposes a technique to reduce 1263 the number of adjacencies based on shortest path tree (SPT) 1264 reachability information. 1266 3.5.1. Rationale for Smart Peering 1268 In OSPF [OSPF] [OSPFv3], nodes establish an adjacency by first 1269 verifying 2-way connectivity between them and then synchronizing 1270 their link state databases. Once the peering relationship is 1271 complete and the adjacency is established, the nodes will continue to 1272 advertise each other in their LSAs. As a result, the peers are 1273 maintained in the link state database and are included in all SPF 1274 calculations. During the reliable flooding process, a node must 1275 ensure that each peer has indeed received the flooded routing update 1276 via an acknowledgment and retransmission mechanism. 1278 Roy, Chandra et al. Expires July 2010 [Page 24] 1279 Consequently, maintaining an adjacency for a particular peer is a 1280 trade off between the added redundancy in routing paths and network 1281 reachability versus the associated overhead (memory consumption, SPF 1282 computations, routing overhead, and network convergence). 1284 Consider the possibility of reducing the number of adjacencies that a 1285 node maintains without compromising reachability and redundancy. 1286 This will have direct implications on network scalability and is 1287 especially attractive in environments where the network topology is 1288 dynamic. For example, in a Mobile Ad-Hoc Network (MANET) where nodes 1289 are mobile and the topology is constantly changing, it seems highly 1290 desirable to 'intelligently' become adjacent with only selected peers 1291 and not establish a peering session with every node that comes within 1292 transmission range. Selective peering can be particularly useful in 1293 avoiding the peering process for unstable nodes, i.e., nodes that 1294 come in and out of transmission range. 1296 3.5.2. Previous Related Work 1298 The formation of a FULL adjacency requires the discovery (2-way 1299 relationship) and the database synchronization. To prevent from 1300 achieving the FULL state, others have taken the approach of modifying 1301 link state protocols to use periodic advertisements (instead of a 1302 database exchange). The result is that neighbor discovery is still 1303 required, but routing information is learned over time. An example 1304 of this approach is: 1306 o OSPFv2 Wireless Interface Type [WINTF] 1308 * where the use of periodic advertisements "eliminates the 1309 formation of full adjacencies on wireless interfaces; all 1310 neighbor states beyond 2-Way are not reached,and no database 1311 synchronization is performed". 1313 What we propose in this specification goes a step further by not 1314 requiring the formation and maintenance of neighbor state (2-way, or 1315 other) *and* without changing the route distribution mechanisms in 1316 the link state protocols. In other words, the mechanism described is 1317 completely backwards compatible. 1319 3.5.3. Smart Peering Solution 1321 Two routers are defined as synchronized when they have identical link 1322 state database. To limit the number of neighbors that are formed, an 1323 algorithm is needed to select which neighbors with whom to peer. 1325 The algorithm MUST provide reachability to every possible destination 1326 in the network, just like when normal adjacency formation processes 1327 are used. We should always peer with a neighbor if it provides our 1328 only path to currently unreachable destinations. 1330 Roy, Chandra et al. Expires July 2010 [Page 25] 1331 3.5.3.1. SPT Reachability Heuristics 1333 The peering decision is really a local matter to a router. If a 1334 router can ensure that reachability to other nodes is available 1335 without bringing up a new adjacency, it can choose not to bring up 1336 the new adjacency. 1338 We propose an algorithm which uses the existing information about a 1339 new neighbor's reachability in the SPT. If the two routers can 1340 already reach each other in the SPT, it is not necessary to form an 1341 adjacency between them. 1343 The decision to peer or not, is made when a hello is received. When 1344 a hello is received from a new neighbor or a neighbor in a state 1345 lower than Exchange: 1347 o A check is made in the link state database to see if the peer is 1348 already reachable in the SPT. 1350 * If the peer is either not known in the SPT or is not reachable, 1351 we start the Exchange process. 1353 * If the peer is reachable than bringing up adjacency with this 1354 neighbor does not provide reachability to any new destinations. 1356 Let's take an example of a single OSPF area. This check would look 1357 for the neighbor's Router LSA. If the LSA is present in the database 1358 and is reachable in the SPT, we have a chance to suppress adjacency 1359 formation. 1361 It's worth noting that as the number of links and redundancy in the 1362 network is reduced, the likelihood of suboptimal routing increases. 1364 3.5.3.2. State Machine 1366 The state machine of a basic implementation of this algorithm is 1367 provided below: An implementation MAY use some heuristics below (step 1368 (3)), beyond the SPT reachability to decide whether or not it 1369 considers a new adjacency to be of value. 1371 Roy, Chandra et al. Expires July 2010 [Page 26] 1372 ...................... 1373 |Receive a hello | 1374 (1) |from a new potential| 1375 |neighbor | 1376 '`'''''''''''''''''''' 1377 | 1378 | 1379 | 1380 ,''''''''''''''''''''''| 1381 |Check to see if there | 1382 (2) |is a router LSA from |----no--(4)form a 1383 |the new potential | new 1384 |neighbor in the link | neighbor 1385 |state database, which | 1386 |is reachable in SPT | 1387 '`'''''''''''''''''''''' 1388 | 1389 |yes 1390 (3) | 1391 ,'''''''''''''''''''''''''''''''''''''''''''''''''''''''''| 1392 | (3b)........................ | 1393 |(3a),______________________ |Determine if the | | 1394 | |Determine if the new | |number of redundant | | 1395 | |link cost is better | |paths to the potential| | 1396 | |than the current path| |neighbor is < the | | 1397 | |cost by a configured | |maximum configured | | 1398 | |amount | |value | | 1399 | '`''''''''''''''''''''' '`'''''''''''''''''''''' | 1400 | \ / | 1401 | .....\.........../.... | 1402 | |User configurable | | 1403 | |selection algorithm | | 1404 | '`'''/'''''''\'''''''' | 1405 | / \ | 1406 '`'''''''''''''''''''''/'''''''''''\''''''''''''''''''''''' 1407 / \ 1408 requirements requirements 1409 met not met 1410 / \ 1411 / \ 1412 (4) form a new neighbor (5) do not become 1413 neighbors 1415 3.5.4 Advertising 2-Way Links in Router LSAs 1417 The technique described in Section 3.5.3 minimizes the number of 1418 adjacencies in highly meshed environments. This is especially useful 1419 when the network is in motion and the average adjacency lifetime is 1420 small. 1422 However, it suffers from an undesirable side effect of limiting the 1423 number of transit links available to forward traffic. 1425 Roy, Chandra et al. Expires July 2010 [Page 27] 1426 An implementation may choose to allow some (or even all) of these 1427 2-way state neighbors to be announced in the Router-LSA. Since the 1428 state remains 2-way, we don't incur control plane (database sync and 1429 flooding) overhead. However, advertising the link in the Router-LSA 1430 makes the link available to the data plane. 1432 This can be safely done if the neighbor is reachable in a special SPT 1433 constructed by ignoring any other 2-way links in the network. This 1434 optional optimization is described below. 1436 3.5.4.1. Unsynchronized Adjacencies 1438 If the new neighbor is already reachable in the SPT, there is no 1439 urgency in doing a full database sync with it. These are the steps 1440 we need to perform when a neighbor has reached 2-way state. 1442 Note that when we say SPT in this section, we mean the special SPT 1443 constructed based on rules in Section 3.5.4.2. 1445 o After 2-WayReceived event, check if the neighbor is reachable in 1446 the SPT. If yes, mark the neighbor as FULL with respect to link 1447 advertisement. 1449 o This means that the router-LSA or network-LSA link corresponding 1450 to the neighbor is advertised as if the neighbor is FULL. 1452 o The adjacency information is constructed with U-bit (see below). 1454 o Database synchronization is postponed: 1456 * By a configured amount of time -OR- 1458 * Until the time it's absolutely "necessary" 1460 In either case, if a database sync is currently pending, it is 1461 started as soon as we detect the neighbor is no longer reachable in 1462 the SPT. The database sync can be done by Out-of-band Sync [OOB], 1463 which maintains the current adjacency and does the sync in the 1464 background. A normal Resync can alternately be done with the 1465 drawback of adjacency flap. 1467 In standard OSPF we first bring up adjacency and then announce a 1468 transit link. The approach described above will allow the link to be 1469 used as a forwarding path very quickly and still allows the database 1470 to be synchronized in a timely fashion when the alternate flooding 1471 path has recently been broken. 1473 There is a circular dependency issue which also needs to be resolved. 1474 Once you start announcing the link, the shortest path will likely be 1475 via this very link. So it's non-trivial to detect when the alternate 1476 dependent path is gone. What we would like to be able to detect is 1477 that the neighbor is reachable via a path which doesn't traverse an 1478 unsynchronized path. 1480 Roy, Chandra et al. Expires July 2010 [Page 28] 1481 We have generally solved this class of problems by running an SPF and 1482 pretending that the link in question doesn't exist. It doesn't 1483 require a full SPF, just enough to see if ANY other path is available 1484 to reach the neighbor. The worst case is when the alternate path is 1485 really gone and we find that out by building a full SPT. This needs 1486 to be done every time the link state database changes, and for EACH 1487 link which has SPT dependence for it's viability. This approach has 1488 scalability concerns and is not considered further here. 1490 We can achieve the same results with just ONE additional SPF which is 1491 capable of ignoring these Unsynchronized links. The result from this 1492 SPT can be used to satisfy the reachability condition for ANY number 1493 of Unsynchronized Adjacencies. This basically requires that we can 1494 actually tell the difference between a normal FULL adjacency and this 1495 new Unsynchronized Adjacency. We can do this in one of two ways: 1497 (A) Define LD Options and use a bit in it, as shown below: 1499 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1500 | Type | LD Options | Metric | 1501 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1502 | Interface ID | 1503 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1504 | Neighbor Interface ID | 1505 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1506 | Neighbor Router ID | 1507 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1509 Link Description in a Router-LSA 1511 LD Options 1512 Link Description options. Used to specify some special 1513 capability or state of a link. 1515 +-+-+-+-+-+-+-+-+ 1516 | | | | | | | |U| 1517 +-+-+-+-+-+-+-+-+ 1519 LD Options 1521 U-bit 1522 The "Unsynchronized" bit. This is set if the adjacency is being 1523 announced before databases are fully synchronized. 1525 This approach is backward compatible because the only routers 1526 looking at this bit are those that support the mechanisms 1527 specified in this document. 1529 Roy, Chandra et al. Expires July 2010 [Page 29] 1530 (B) Introducing a new link type in Router-LSA. 1532 This is a much more complex solution with backward compatibility 1533 concerns due to the fact that unknown link type handling is not 1534 defined in OSPF standard [OSPF]. Hence this solution isn't 1535 considered further. 1537 3.5.4.2. Unsynchronized SPT 1539 Whenever link state changes happen, we need to run ONE additional SPF 1540 by ignoring all links with U-bit set. This SPT is then consulted to 1541 see if any of our Unsynchronized Adjacencies need to start database 1542 sync. This SPT is also consulted when a new neighbor goes into 2-way 1543 to decide if we should form the adjacency immediately or defer it for 1544 later. 1546 3.5.4.3. Flooding Considerations 1548 One of the main goals in trying to delay the database synchronization 1549 is to be able to reduce unnecessary OSPF packets traversing these 1550 links. Since the unsynchronized Adjacencies remain in 2-way state, 1551 OSPF updates will not be flooded over the corresponding interfaces 1552 resulting in additional savings. 1554 An option is provided to enable or disable flooding over these 1555 Unsynchronized Adjacencies. The advantage of allowing flooding is 1556 being able to use more links for control plane purposes. We will 1557 still have the savings of not having to form the adjacency. 1559 3.5.4.4. Overlapping Relay (OR) election impact 1561 The overlapping relay election algorithm uses the two hop 1562 neighborhood it gleans from our neighbor's Router-LSAs. The 1563 introduction of Unsynchronized Adjacencies needs to be considered in 1564 the relay election algorithm. 1566 If flooding is enabled on unsynchronized Adjacencies, no change is 1567 needed in the relay election algorithm. If flooding is disabled, 1568 then the relay election algorithm needs to prune neighbors that are 1569 connected via an Unsynchronized Adjacency from our 1-hop and 2-hop 1570 neighbor lists. 1572 4. Security Considerations 1574 In a MANET network, security is both more difficult and important due 1575 to the wireless nature of the medium. Controlling the ability of 1576 devices to connect to a MANET network at Layer 2 will be relegated to 1577 Layer 2 security mechanisms, such as 802.1x, and others. Controlling 1578 the ability of attached devices to transit traffic will require some 1579 type of security system (outside the scope of this document) which 1580 can authenticate and provide authorization for individual members of 1581 the routing domain. 1583 Roy, Chandra et al. Expires July 2010 [Page 30] 1584 Additional security considerations are similar to any MANET protocol 1585 extension. The following text is from [MDR]: 1587 As with OSPFv3 [OSPFv3], OSPF-OR can use the IPv6 Authentication 1588 Header (AH) [AH] and/or the IPv6 Encapsulation Security Payload 1589 (ESP) [ESP] to provide authentication, integrity, and/or 1590 confidentiality. The use of AH and ESP for OSPFv3 is described in 1591 [OSPFv3-SEC]. 1593 Generic threats to routing protocols are described and categorized in 1594 [THREATS]. The mechanisms described in [OSPFv3-SEC] provide 1595 protection against many of these threats, but not all of them. In 1596 particular, as mentioned in [OSPFv3], these mechanisms do not provide 1597 protection against compromised, malfunctioning, or misconfigured 1598 routers (also called Byzantine routers); this is true for both OSPFv3 1599 and OSPF-OR. 1601 The extension of OSPFv3 to include MANET routers does not introduce 1602 any new security threats. However, the use of a wireless medium and 1603 lack of infrastructure, inherent with MANET routers, may render some 1604 of the attacks described in [THREATS] easier to mount. Depending on 1605 the network context, these increased vulnerabilities may increase the 1606 need to provide authentication, integrity, and/or confidentiality, as 1607 well as anti-replay service. 1609 For example, sniffing of routing information and traffic analysis are 1610 easier tasks with wireless routers than with wired routers, since the 1611 attacker only needs to be within the radio range of a router. The 1612 use of confidentiality (encryption) provides protection against 1613 sniffing but not traffic analysis. 1615 Similarly, interference attacks are also easier to mount against 1616 MANET routers due to their wireless nature. Such attacks can be 1617 mounted even if OSPF packets are protected by authentication and 1618 confidentiality, e.g., by transmitting noise or replaying out-dated 1619 OSPF packets. As discussed below, an anti-replay service (provided 1620 by both ESP and AH) can be used to protect against the latter attack. 1622 The following threat actions are also easier with MANET routers: 1623 spoofing (assuming the identify of a legitimate router), 1624 falsification (sending false routing information), and overloading 1625 (sending or triggering an excessive amount of routing updates). 1626 These attacks are only possible if authentication is not used, or the 1627 attacker takes control of a router or is able to forge legitimacy 1628 (e.g., by discovering the cryptographic key). 1630 [OSPFv3-SEC] mandates the use of manual keying when current IPsec 1631 protocols are used with OSPFv3. Routers are required to use manually 1632 configured keys with the same security association (SA) parameters 1633 for both inbound and outbound traffic. For MANET routers, this 1634 implies that all routers attached to the same MANET must use the same 1635 key for multicasting packets. This is required in order to achieve 1637 Roy, Chandra et al. Expires July 2010 [Page 31] 1638 scalability and feasibility, as explained in [OSPFv3-SEC]. Future 1639 specifications can explore the use of automated key management 1640 protocols that may be suitable for MANETs. 1642 As discussed in [OSPFv3-SEC], the use of manual keys can increase 1643 vulnerability. For example, manual keys are usually long lived, thus 1644 giving an attacker more time to discover the keys. In addition, the 1645 use of the same key on all routers attached to the same MANET leaves 1646 all routers insecure against impersonation attacks if any one of the 1647 routers is compromised. 1649 Although [AH] and [ESP] state that implementations of AH and 1650 ESP SHOULD NOT provide anti-replay service in conjunction with SAs 1651 that are manually keyed, it is important to note that such service is 1652 allowed if the sequence number counter at the sender is correctly 1653 maintained across local reboots until the key is replaced. 1654 Therefore, it may be possible for MANET routers to make use of the 1655 anti-replay service provided by AH and ESP. 1657 When an OSPF routing domain includes both MANET networks and fixed 1658 networks, the frequency of OSPF updates either due to actual topology 1659 changes or malfeasance could result in instability in the fixed 1660 networks. In situations where this is a concern, it is recommended 1661 that the border routers segregate the MANET networks from the fixed 1662 networks with either separate OSPF areas or, in cases where legacy 1663 routers are very sensitive to OSPF update frequency, separate OSPF 1664 instances. With separate OSPF areas, the 5 second MinLSInterval will 1665 dampen the frequency of changes originated in the MANET networks. 1666 Additionally, OSPF ranges can be configured to aggregate prefixes for 1667 the areas supporting MANET networks. With separate OSPF instances, 1668 more conservative local policies can be employed to limit the volume 1669 of updates emanating from the MANET networks. 1671 5. IANA Considerations 1673 IANA will make assignments as explained below using the policies 1674 outlined in [IANA]. 1676 o I bit and F bit from "LLS Type 1 Extended Options and Flags" 1677 registry as defined below: 1679 +---+---+---+---+---+---+---+- -+---+---+---+---+---+---+---+---+ 1680 | * | * | * | * | * | * | * |...| * | * | * | * | F | I | RS| LR| 1681 +---+---+---+---+---+---+---+- -+---+---+---+---+---+---+---+---+ 1683 Bits in Extended Options and Flags TLV 1685 o New TLV types from "Link Local Signalling TLV Identifiers (LLS 1686 Types)" registry as defined below: 1688 Roy, Chandra et al. Expires July 2010 [Page 32] 1689 TLV Name TLV Type 1690 -------- -------- 1691 State Check Sequence TLV 6 1692 Neighbor Drop TLV 7 1693 Request From TLV 8 1694 Full State For TLV 9 1695 Active Overlapping Relay TLV 10 1696 Willingness TLV 11 1698 o A new registry is defined for LD Options as defined in Section 1699 3.5.4.1. U-bit is allocated by this document. 1701 All future additions to LD Options are subject to OSPF WG review 1702 and require IETF Review. 1704 6. Contributors 1706 The following persons are contributing authors to the document: 1708 Fred Baker Dave Cook 1709 Cisco Systems Cisco Systems 1710 1121 Via Del Rey 7025-4 Kit Creek Road 1711 Santa Barbara, CA 93117 RTP, NC 27709 1712 USA USA 1713 Email: fred@cisco.com Email: dacook@cisco.com 1715 Alvaro Retana Yi Yang 1716 Cisco Systems Cisco Systems 1717 7025-4 Kit Creek Road 7025-4 Kit Creek Road 1718 RTP, NC 27709 RTP, NC 27709 1719 USA USA 1720 Email: aretana@cisco.com Email: yiya@cisco.com 1722 Russ White 1723 Cisco Systems 1724 7025-4 Kit Creek Road 1725 RTP, NC 27709 1726 USA 1727 Email: riw@cisco.com 1729 7. Acknowledgments 1731 The authors and contributors would like to thank Pratap Pellakuru, 1732 Stan Ratliff for their feedback and implementation of the document. 1733 Thanks to Richard Ogier and John Avery for doing a final review. 1735 Roy, Chandra et al. Expires July 2010 [Page 33] 1736 References 1738 Normative References 1740 [OSPF] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 1742 [OSPFv3] Coltun, R., Ferguson, D., J. Moy and A. Lindem, 1743 "OSPF for IPv6", RFC 5340, July 2008. 1745 [LLS] Zinin, A., Roy, A., Nguyen, L., Friedman, B., and D. 1746 Yeung, "OSPF Link-local Signaling", RFC5613, August 2009 1748 [IANA] Narten, T. and H. Alvestrand, "Guidelines for Writing an 1749 IANA Considerations Section in RFCs", RFC 5226, May 2008. 1751 [KEY] Bradner, S., "Key words for use in RFCs to Indicate 1752 Requirement Levels", BCP 14, RFC 2119, March 1997. 1754 Informative References 1756 [IPV6ADD] Hinden, R. and S. Deering, "IP Version 6 Addressing 1757 Architecture", RFC 4291, February 2006. 1759 [OSPFGR] Moy, J., Pillay-Esnault, P., and A. Lindem, "Graceful OSPF 1760 Restart", RFC 3623, November 2003. 1762 [OSPFREST] Zinin, A., Roy, A., and L. Nguyen, "OSPF Restart 1763 Signaling", RFC 4812, March 2007. 1765 [OOB] Zinin, A., Roy, A., and L. Nguyen, "OSPF Out-of-band LSDB 1766 resynchronization", RFC 4811, March 2007. 1768 [OLSR] Clausen, T. and P. Jacquet, "Optimized Link State Routing 1769 Protocol", RFC 3626, October 2003. 1771 [WINTF] Ahrenholz J. et al, "OSPFv2 Wireless Interface Type", 1772 draft-spagnolo-manet-ospf-wireless-interface 1773 (work in progress) 1775 [MDR] Ogier, R. and Spagnolo P., "MANET Extension of OSPF using 1776 CDS Flooding", RFC5614, August 2009 1778 [AH] Kent, S., "IP Authentication Header", RFC 4302, December 1779 2005. 1781 [ESP] Kent, S., "IP Encapsulating Security Payload (ESP)", RFC 1782 4303, December 2005. 1784 [OSPFv3-SEC] Gupta, M. and N. Melam, "Authentication/Confidentiality 1785 for OSPFv3", RFC 4552, June 2006. 1787 Roy, Chandra et al. Expires July 2010 [Page 34] 1789 [THREATS] Barbir, A., Murphy, S., and Y. Yang, "Generic Threats to 1790 Routing Protocols", RFC 4593, October 2006. 1792 Authors' Addresses 1794 Abhay Roy (Editor) Madhavi W. Chandra (Editor) 1795 Cisco Systems Email: mw.chandra@gmail.com 1796 170 W. Tasman Drive 1797 San Jose, CA 95134 1798 USA 1799 Email: akr@cisco.com 1801 Roy, Chandra et al. Expires July 2010 [Page 35]