Network Working Group M. Chandra (Editor) Internet-Draft A. Roy (Editor) Intended status: Experimental Cisco Systems Expires: March 2009 September 21, 2008 Extensions to OSPF to Support Mobile Ad Hoc Networking draft-ietf-ospf-manet-or-01 Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Copyright Notice Copyright (C) The IETF Trust (2008). Abstract This document describes extensions to OSPF to support mobile ad hoc networking. Specifically, the document specifies a mechanism for link-local signaling, a OSPF-MANET interface, a simple technique to reduce the size of Hello packets by only transmitting incremental state changes, and a method for optimized flooding of routing updates. Chandra, Roy et al. Expires March 2009 [Page 1] Internet-Draft Extensions to OSPF to Support MANETs September 2008 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . 3 1.2 Motivation for extending OSPF to support MANETs . . . . . 4 2. Requirements notation . . . . . . . . . . . . . . . . . . . 4 3. Proposed Enhancements . . . . . . . . . . . . . . . . . . . 4 3.1 OSPF-MANET Interface . . . . . . . . . . . . . . . . . . . 5 3.1.1 Interface Operation . . . . . . . . . . . . . . . . . 6 3.1.2 LSA Formats and Examples . . . . . . . . . . . . . . . 6 3.2 Incremental OSPF-MANET Hellos . . . . . . . . . . . . . . 9 3.2.1 The I Option Bit . . . . . . . . . . . . . . . . . . . 10 3.2.2 State Check Sequence TLV (SCS TLV) . . . . . . . . . . 10 3.2.3 Neighbor Drop TLV . . . . . . . . . . . . . . . . . . 11 3.2.4 Request From TLV (RF TLV) . . . . . . . . . . . . . . 11 3.2.5 Full State For TLV (FSF TLV) . . . . . . . . . . . . . 11 3.2.6 Neighbor Adjacencies . . . . . . . . . . . . . . . . . 12 3.2.7 Sending Hellos . . . . . . . . . . . . . . . . . . . . 13 3.2.8 Receiving Hellos . . . . . . . . . . . . . . . . . . . 14 3.2.9 Interoperability . . . . . . . . . . . . . . . . . . . 15 3.2.10 Support for OSPF Graceful Restart . . . . . . . . . 15 3.3 Optimized Flooding (Overlapping Relays) . . . . . . . . . 16 3.3.1 Operation Overview . . . . . . . . . . . . . . . . . . 16 3.3.2 Determination of Overlapping Relays . . . . . . . . . 17 3.3.3 Terminology . . . . . . . . . . . . . . . . . . . . . 17 3.3.4 Overlapping Relay Discovery Process . . . . . . . . . 18 3.3.5 The F Option Bit . . . . . . . . . . . . . . . . . . . 19 3.3.6 Active Overlapping Relay TLV (AOR TLV) . . . . . . . . 19 3.3.7 Willingness TLV . . . . . . . . . . . . . . . . . . . 20 3.3.8 Flooding and Relay Decisions . . . . . . . . . . . . . 20 3.3.9 Intelligent Transmission of Link State Acknowledgements . . . . . . . . . . . . . . . . . . . 22 3.3.10 Important Timers . . . . . . . . . . . . . . . . . . 22 3.3.11 Miscellaneous Protocol Considerations . . . . . . . 23 3.3.12 Interoperability . . . . . . . . . . . . . . . . . . 23 3.4 New Bits in OSPFv3 Option Field . . . . . . . . . . . . . 24 3.5 Smart Peering . . . . . . . . . . . . . . . . . . . . . . 24 3.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . 24 3.5.2 Previous Related Work . . . . . . . . . . . . . . . . . 25 3.5.3 Proposed Solution . . . . . . . . . . . . . . . . . . . 25 3.5.4 Advertise the 2-way link in Router-LSA . . . . . . . . . 27 4. Security Considerations . . . . . . . . . . . . . . . . . . 30 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . 31 6. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 31 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 32 References . . . . . . . . . . . . . . . . . . . . . . . . . 32 Normative References . . . . . . . . . . . . . . . . . . 32 Informative References . . . . . . . . . . . . . . . . . 32 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 33 Intellectual Property and Copyright Statements . . . . . . . 34 Chandra, Roy et al. Expires March 2009 [Page 2] Internet-Draft Extensions to OSPF to Support MANETs September 2008 1. Introduction Mobile Ad Hoc Networks have been an area of study for some time, within various working groups and areas within the IETF, various Military branches, and various government agencies. Recently, networks with mobile ad hoc requirements are being proposed and seriously considered for deployment in the near term, which means the concepts and research now needs to be applied to deployed networks. Towards that end, this draft applies many of the principles and concepts learned through prior work to [OSPFv3], along with new concepts based on current requirements. 1.1 Problem Statement MANETs are synonymous with packet radio networks, which have been around since the 1960s in a limited military capacity. With the boom of mobile devices and wireless communications, MANETs are finding scope in commercial and military environments. The aim of these networks is to support robust and efficient communication in a mobile wireless network by incorporating routing functionality into mobile nodes. A MANET is an autonomous set of nodes distributed over a wide geographical area that communicate over bandwidth-constrained wireless links. Each node may represent a transmitter, receiver, or relay station with varying physical capabilities. Packets may traverse through several intermediate (relay) nodes before reaching their destination. These networks typically lack infrastructure: nodes are mobile, there is no central hub or controller, and thus there is no fixed network topology. Moreover, MANETs must contend with a difficult and variable communication environment. Packet transmissions are plagued by the usual problems of radio communication, which include propagation path loss, signal multipath and fading, and thermal noise. These effects vary with terminal movement, which also induces Doppler spreading in the frequency of the transmitted signal. Finally, transmissions from neighboring terminals, known as multi-access interference, hostile jammers, and impulsive interference, e.g., ignition systems, generators, and other non-similar in-band communications, may contribute additional interference. Given this nature of MANETs, the existence of a communication link between a pair of nodes is a function of their variable link quality, including signal strength and bandwidth. Thus, routing paths vary based on environment, and the resulting network topology. In such networks, the topology may be stable for periods of time, and then suddenly become unpredictable. Since MANETs are typically decentralized systems, there are no central controllers or specially designated routers to determine the routing paths as the topology changes. All of the routing decisions and forwarding (relaying) of packets must be done by the nodes themselves, and communication is on a peer-to-peer basis. Chandra, Roy et al. Expires March 2009 [Page 3] Internet-Draft Extensions to OSPF to Support MANETs September 2008 1.2 Motivation for extending OSPF to support MANETs The motivation to extend a standard protocol, OSPF (described in [OSPF] and [OSPFv3]) to operate on MANET networks is twofold. The primary reason is for interoperability--MANET devices need to be able to work when plugged into a wireline network in as many cases as possible. The junction point between a MANET and wire-line network should also be as fluid as possible, allowing a MANET network to "plug in" to just about any location within a wire-line network, and find connectivity, etc., as needed. While routes could be redistributed between two routing protocols, one designed just for wire-line networks, and the other just for MANET networks, this adds complexity and overhead to the MANET/ wireline interface, increases the odds of an error being introduced between the two domains, and decreases flexibility. The second motivation is that OSPF is a well understand and widely deployed routing protocol. This provides a strong basis of experience and skills from which to work. A protocol which is known to work can be extended, rather than developing a new protocol, which must then be completely troubleshoot, tested, and modified over a number of years. Working with a well known protocol allows development effort to be placed in a narrowly focused area, rather than rebuilding, from scratch, many things which are already known to work. 2. Requirements notation The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [KEY]. 3. Proposed Enhancements This document proposes modifications to [OSPFv3] to support mobile ad hoc networks (MANETs). Note that it is possible to use the mechanism defined in Section "Incremental OSPF-MANET Hellos" and the mechanism defined in Section "Optimized Flooding (Overlapping Relays)" independently of one another. The challenges with deploying standard [OSPFv3] in a MANET environment fit into two categories. First, traditional link-state routing protocols are designed for a statically configured environment. As a result, most of the configuration is done manually when a new router is placed in the network. Thus, OSPF will not function in an environment where routers interconnect and disconnect in somewhat random topologies and combinations. There are modifications that must be made in order for routers running the same protocol to communicate in a heterogeneous and dynamic environment. Second, a MANET network must transmit more state information to maintain reachability. Therefore, OSPF will need scalability enhancements to support MANETs. Chandra, Roy et al. Expires March 2009 [Page 4] Internet-Draft Extensions to OSPF to Support MANETs September 2008 Currently there is no defined interface type that describes a wireless network. Wireless links have characteristics of both multi- access and point-to-multipoint links. Treating wireless links as multi-access does not take into account that not all nodes on the same Layer 2 link have bi-directional connectivity. However, any transmission on a link will reach nodes that are within transmission range. In this way, the link is multi-access due to the fact that two simultaneous transmissions may collide. A new interface type needs to be defined in order to accurately describe this behavior. The second category of challenges fall into is scalability. While some flooding optimizations are present in OSPF, such as designated router (DR) election, many of these were built under the assumption of a true multi-access network. Wireless networks are not true multi-access because it cannot be assumed that there is two-way connectivity between everyone on the same Layer 2 link. Therefore, optimizations such as DR election will not perform correctly in MANET networks. Without any further optimizations in link-state flooding, current OSPF would not be able to operate in a highly dynamic environment in which links are constantly being formed and broken. The amount of information that would need to be flooded would overload the network. Another scalability issue is the periodic transmission of Hello messages. Currently, even if there are no changes in a router's neighbor list, the Hello messages still list all the neighbors on a particular link. For a MANET router, where saving bandwidth and transmission power is a critical issue, the transmission of potentially large Hello messages is particularly wasteful. Finally, current routing protocols will form a neighbor relationship with any router on a Layer 2 link that is correctly configured. For MANET routers in a wireless network, this may lead to an excessive number of parallel links between two routers if communication is achieved via multiple interfaces. In a statically configured network, this is not a problem, since the physical topology can be built to prevent excessive redundancy. However, in a dynamic network, there must exist additional mechanisms to prevent too many redundant links. (Note that links between two nodes on different radio types, different antenna, different channels, etc., are considered different links and not redundant links.) In scalability tests, it has been demonstrated that the presence of too many redundant links will increase both the size of routing updates and cause extra flooding resulting in even relatively small networks not converging. 3.1 OSPF-MANET Interface Interfaces are defined as the connection between a router and one of its attached networks [OSPF]. Four types of interfaces have been defined and supported in [OSPF] and [OSPFv3]: broadcast, NBMA, point- to-point, and point-to-multipoint. Chandra, Roy et al. Expires March 2009 [Page 5] Internet-Draft Extensions to OSPF to Support MANETs September 2008 Point-to-multipoint model has been chosen to represent MANET interfaces. (The features designed in this document MAY be included on other interface types as appropriate.) The MANET interface allows the following: o OSPF treats all router-to-router connections over the MANET interface as if they were point-to-point links. o Link metric can be set on a per neighbor basis. o Broadcast and multicast can be accomplished through Layer-2 broadcast or Layer-2 pseudo-broadcast. * The MANET interface supports Layer-2 broadcast if it is able to address a single physical message to all of the attached neighbors. One such example is 802.11. * The MANET interface supports Layer-2 pseudo-broadcast if it is able to pick up a packet from the broadcast queue, replicate the packet, and send a copy over each point-to-point link. One such example is Frame Relay. o An API must be provided for Layer-3 to determine the layer-2 broadcast capability. Based on the return of the API, OSPF classifies the MANET interfaces into the following three types: MANET broadcast, MANET pseudo-broadcast, and MANET non- broadcast. o Multicast SHOULD be used for OSPF packets. When the MANET interface supports Layer-2 broadcast or pseudo-broadcast, the multicast process is transparent to OSPF. Otherwise, OSPF MUST replicate multicast packets by itself. 3.1.1 Interface Operation A MANET node has at least one MANET interface. MANET nodes can communicate with each other through MANET interfaces. MANET nodes can communicate with non-MANET routers only through normal interfaces, such as Ethernet, ATM and etc. For scalability reasons, it is not required to configure IPv6 global unicast addresses on MANET interfaces. Instead, a management loopback interface, with an IPv6 global unicast address, MAY be configured on each MANET node. The LSAs associated with a MANET interface SHOULD have the DC-bit set in the OSPFv3 Options Field and the DoNotAge bit set in the LS Age field as described in [OSPFv3]. 3.1.2 LSA Formats and Examples LSA formats are specified in [OSPFv3]. In order to display example LSAs, a network map is included below. Router names are prefixed with the letters RT, network names with the letter N, and router interface names with the letter I. o Four MANET nodes, RT1, RT2, RT3, and RT4, reside in area 2. o RT1 has one MANET interface I11. Through the interface, RT1 is full adjacent to RT2, RT3, and RT4. Chandra, Roy et al. Expires March 2009 [Page 6] Internet-Draft Extensions to OSPF to Support MANETs September 2008 o RT2 has two MANET interfaces, I21 and I22, and one Ethernet interface I23. RT2 is full adjacent to RT1 and RT4 through the interface I21, and full adjacent to RT4 through the interface I22. Stub network N1 is attached with RT2 through the interface I23. o RT3 has one MANET interface I31, and is full adjacent to RT1 through the interface. o RT4 has two MANET interfaces, I41 and I42. It is full adjacent to RT2 through the interface I41, and full adjacent to RT1 and RT2 through the interface I42. o Moreover, each MANET node is configured with a management loop- back interface. +---+I11 I21+---+I23 | |RT1|-+----------+-|RT2|------|N1 +---+ | | +---+ | | | VI22 | | + | | | | | | | | | | | | | | + | | ^I41 +---+ | +---+ |RT3|-+ +-|RT4| +---+I31 I42+---+ The assignment of IPv6 global unicast prefixes to network links is shown below. (Note: No IPv6 global unicast addresses are configured on the MANET interfaces) ----------------------------------------------------------- RT1 LOOPBACK 2001:DB8:0001::/64 I11 n/a RT2 LOOPBACK 2001:DB8:0002::/64 I21 n/a I22 n/a I23 2001:DB8:0012::/60 RT3 LOOPBACK 2001:DB8:0003::/64 I31 n/a RT4 LOOPBACK 2001:DB8:0004::/64 I41 n/a I42 n/a The OSPF interface IDs and the link local addresses for the router interfaces in the network illustrated above below. EUIxy represents the 64-bit interface identifier of the interface Ixy, in Modified EUI-64 format [IPV6ADD]. Chandra, Roy et al. Expires March 2009 [Page 7] Internet-Draft Extensions to OSPF to Support MANETs September 2008 Node Interface Interface ID Link Local address ----------------------------------------------------------- RT1 LOOPBACK 1 n/a I11 2 fe80:0002::EUI11 RT2 LOOPBACK 1 n/a I21 2 fe80:0002::EUI21 I22 3 fe80:0003::EUI22 I23 4 fe80:0004::EUI23 RT3 LOOPBACK 1 n/a I31 2 fe80:0002::EUI31 RT4 LOOPBACK 1 n/a I41 2 fe80:0002::EUI41 I42 3 fe80:0003::EUI42 3.1.2.1 Router LSAs As an example, consider the router LSAs that node RT2 would originate. Two MANET interfaces, consisting of 3 point-to-point links, are presented. RT2's router-LSA LS age = DoNotAge+0 ;newly originated LS type = 0x2001 ;router-LSA Link State ID = 0 ;first fragment Advertising Router = 192.0.2.2 ;RT2's Router ID bit E = 0 ;not an AS boundary router bit B = 0 ;not an area border router Options = (V6-bit|E-bit|R-bit) Type = 1 ;p2p link to RT1 over I21 Metric = 10 ;cost to RT1 Interface ID = 2 ;Interface ID of I21 Neighbor Interface ID = 2 ;Interface ID of I11 Neighbor Router ID = 192.0.2.1 ;RT1's Router ID Type = 1 ;p2p link to RT4 over I21 Metric = 25 ;cost to RT4 Interface ID = 2 ;Interface ID of I21 Neighbor Interface ID = 3 ;Interface ID of I42 Neighbor Router ID = 192.0.2.4 ;RT4's Router ID Type = 1 ;p2p link to RT4 over I22 Metric = 15 ;cost to RT4 Interface ID = 3 ;Interface ID of I22 Neighbor Interface ID = 2 ;Interface ID of I41 Neighbor Router ID = 192.0.2.4 ;RT4's Router ID 3.1.2.2 Link LSAs A MANET node originates a separate Link-LSA for each attached interface. As an example, consider the Link-LSA that RT3 will build for its MANET interface I31. Chandra, Roy et al. Expires March 2009 [Page 8] Internet-Draft Extensions to OSPF to Support MANETs September 2008 RT3's Link-LSA for MANET interface I31 LS age = DoNotAge+0 ;newly originated LS type = 0x0008 ;Link-LSA Link State ID = 2 ;Interface ID of I31 Advertising Router = 192.0.2.3 ;RT3's Router ID Rtr Pri = 1 ;default priority Options = (V6-bit|E-bit|R-bit) Link-local Interface Address = fe80:0002::EUI31 # prefixes = 0 ;no global unicast address 3.1.2.3 Intra Area Prefix LSAs A MANET node originates an intra area prefix LSA to advertise its own prefixes, and those of its attached stub links. As an example, consider the intra area prefix LSA that RT2 will build. RT2's intra area prefix LSA for its own prefixes LS age = DoNotAge+0 ;newly originated LS type = 0x2009 ;intra area prefix LSA Link State ID = 177 ;or something else Advertising Router = 192.0.2.2 ;RT2's Router ID # prefixes = 2 Referenced LS type = 0x2001 ;router LSA reference Referenced Link State ID = 0 ;always 0 for router-LSA ;reference Referenced Advertising Router = 192.0.2.2 ;RT2's Router ID PrefixLength = 64 ;prefix on RT2's LOOPBACK PrefixOptions = 0 Metric = 0 ;cost of RT2's LOOPBACK Address Prefix = 2001:DB8:0002:: PrefixLength = 60 ;prefix on I23 PrefixOptions = 0 Metric = 10 ;cost of I23 Address Prefix = 2001:DB8:0012:: Note: MANET nodes may originate Intra-Area-Prefix-LSAs for attached transit (broadcast/NBMA) networks. This is normal behavior defined in [OSPFv3], which is irrelevant to MANET interfaces. Please consult [OSPFv3] for details. 3.2 Incremental OSPF-MANET Hellos In MANETs, reducing the size of periodically transmitted packets can be very important in decreasing the total amount of overhead associ- ated with routing. Towards this end, removing the list of neighbors from Hello packets unless that information changes can reduce routing protocol overhead. While the reduction for each hello packet is small, over time it will be significant. Chandra, Roy et al. Expires March 2009 [Page 9] Internet-Draft Extensions to OSPF to Support MANETs September 2008 A new option bit is defined in this document to facilitate the operation of incremental Hello packets. A new SCS TLV and Neighbor Drop TLV are also defined, transmitted using LLS [LLS]. 3.2.1 The I Option Bit A new I bit is defined in the OSPFv3 option field. The bit is defined for Hello packets and indicates that only incremental information is present. See Section "New Bits in OSPFv3 Options Field" for placement of the I bit within the OSPFv3 options field. 3.2.2 State Check Sequence TLV (SCS TLV) A new TLV is defined that indicates the current state, which is represented by an State Check Sequence (SCS) number of the transmitting router. 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SCS Number |R|FS|N | Reserved | +-----------------------------------------------------------------+ o Type: 3 o Length: Set to 4. o SCS Number: A circular two octet unsigned integer indicating the current state of the transmitting device. Note that when the incremental Hello mechanism is invoked (or re-started), an initial SCS value of '1' SHOULD be used for the first incremental Hello packet. This sequence number is referred to as InitialSCS. Note that InitialSCS also implies a full state. o R: Request bit. If set, this is a request for current state. The list of routers who should respond to this request are listed in the RF TLV defined below. If the RF TLV is not present, it is assumed that the request is meant for all nodes. o FS: Full State bit. If set, the Hello packet contains full state as far as the neighbor(s) in the FSF TLV (defined below) are concerned. If the FSF TLV is not present, the Hello packet contains full state for all neighbors. o N: InComplete bit. If NOT set, the complete state associated with the SCS number is included in the Hello packet. If set, indicates that the appended TLVs are being sent 'persistently', and that there is more state associated with the SCS number that was sent originally, but is not included in this Hello packet. This bit allows any desired TLVs to be sent 'persistently' for a number of Hellos with the same SCS number without requiring all of the TLVs associated with that SCS number to be transmitted. The first time an SCS number is sent, the entire state associated with that SCS number is transmitted, and the 'N' bit MUST NOT be set. o Reserved: Set to 0. Reserved for future use. Chandra, Roy et al. Expires March 2009 [Page 10] Internet-Draft Extensions to OSPF to Support MANETs September 2008 A Hello with the SCS TLV appended with the R bit set will be referred to as a Hello request. 3.2.3 Neighbor Drop TLV A new TLV is defined in this document which indicates neighbor(s) that have been removed from the list of known neighbors. 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Dropped Neighbor(s) | +---------------------------------------------------------------+ | .... +-------------------- o Type: 4 o Length: Set to the number of dropped neighbors included in the TLV multiplied by 4. o Dropped Neighbor(s) - Router ID of the neighbor being dropped. 3.2.4 Request From TLV (RF-TLV) A new TLV is defined in this document which indicates neighbor(s) from which the latest Hello state is being requested. 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Request From Neighbor(s) | +---------------------------------------------------------------+ | .... +-------------------- o Type: 5 o Length: Set to the number of neighbors included in the TLV multiplied by 4. o Request From Neighbor(s) - Router ID of the neighbor(s) from which o Hello state is being requested. 3.2.5 Full State For TLV (FSF-TLV) A new TLV is defined in this document which indicates neighbor(s) to which the transmitting node is responding with full state. Chandra, Roy et al. Expires March 2009 [Page 11] Internet-Draft Extensions to OSPF to Support MANETs September 2008 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Full State For Neighbor(s) | +---------------------------------------------------------------+ | .... +-------------------- o Type: 6 o Length: Set to the number of neighbors included in the TLV multiplied by 4. o Full State For Neighbor(s) - Router ID of the neighbor(s) should process this packet. 3.2.6 Neighbor Adjacencies This section describes building neighbor adjacencies and the failure of such adjacencies using the incremental Hello signaling. 3.2.6.1 Building Neighbor Adjacencies Hello packets are sent periodically in accordance with [OSPF] and [OSPFv3]. An OSPF implementation which supports sending only partial neighbor information in Hello packets SHOULD always set the I bit in its transmitted Hello packets, except as described elsewhere in this document. Hello packets MAY be suppressed from being transmitted every HelloInterval if other packet transmissions are sent by the router during that time. On receiving a Hello packet from a new neighbor (in this context, a new neighbor is a neighbor in less than Init state as defined in Section 10.1 [OSPF]), if the Hello has the I bit set, a router will: o Place the new neighbor in the neighbor list described in [OSPFv3], A.3.2. o Increment the router's SCS number that it will use in its next Hello (indicated in the SCS TLV). o When the neighbor has reached the EXCHANGE state, described in [OSPF], 10.1, it is removed from the list of neighbors described in [OSPFv3], A.3.2. o If the neighbor is not a DR or backup designated router (BDR) on an OSPF broadcast link, and the neighbor is advertised as connected in the Network LSA advertised by the DR, it is removed from the list of neighbors described in [OSPFv3], A.3.2. 3.2.6.2 Adjacency Failure On discovering an adjacency failure (going to state less than EXCHANGE), a router using I bit signaling SHOULD: o Remove the adjacent router from local tables, and take the appropriate actions for a failed adjacency described in [OSPF] and [OSPFv3]. Chandra, Roy et al. Expires March 2009 [Page 12] Internet-Draft Extensions to OSPF to Support MANETs September 2008 o Add the formerly adjacent router to a Neighbor Drop TLV. o Increment the router's SCS number that it will transmit in its next Hello. o Transmit Hellos with this Neighbor Drop TLV - It may be desirable to send the Neighbor Drop TLV in three consecutive Hellos to increase the probability of reception. In this case, 'persistent' Hello packets would be sent with the same SCS number, the Neighbor Drop TLV, and the 'N' bit set. Thus, the receiver knows that the Neighbor Drop TLV is being sent persistently and there is more state associated with the SCS in case it must request missing state presumably transmitted in a previous Hello. 3.2.7 Sending Hellos When a device is first attached to a network (whether through being brought into range of another device, powering the device on, or enabling the device's radio interface, etc.), it will need to obtain complete neighbor state from each of its neighbors before it can utilize the incremental Hello mechanism. Thus, upon initialization, a device MAY send a multicast Hello request (and omit the 'Request From' TLV). Neighbors will receive the request and respond with a Hello with their complete neighbor state. If a device is in INIT state with a neighbor and receives a Hello from the neighbor without its router ID listed in the neighbor list, the device SHOULD request the current state from the neighbor. Note that this is to avoid a race condition since the received Hello can either mean that the device is NOT SEEN by the neighbor, or that the device is adjacent and not listed in the incremental list. Thus, by receiving a Hello request, the neighbor will respond with its neighbor state for the neighbor. The first Hello packet with a particular SCS number MUST contain the full state associated with that SCS number, i.e., all state changes since the last SCS number. The 'N' bit MUST NOT be set in the State Check Sequence TLV. Incremental Hello packets can be sent persistently (sent in k successive Hello packets), with flexibility in the actual amount of information being sent. The three options include: o The entire incremental Hello packet is sent persistently. This is accomplished by simply sending the entire state associated with a SCS number for k successive Hellos. Since the SCS number remains the same, the 'N' bit is not set in these incremental Hello packets. o Partial information for a particular SCS number is sent persistently. After the first Hello packet with a particular SCS number is sent, only the TLVs that are desired to be sent persistently are sent in subsequent Hellos with the same SCS number and the 'N' bit set. Chandra, Roy et al. Expires March 2009 [Page 13] Internet-Draft Extensions to OSPF to Support MANETs September 2008 o No information is sent persistently. This is simply the default behavior where an incremental Hello packet with a particular SCS number is only sent once. 3.2.8 Receiving Hellos Each OSPF device supporting incremental Hello signaling, as described in this document, MUST keep the last known SCS number from each neighbor it has received Hellos from as long as the neighbor adjacency structure is maintained. If a device receives a Hello from an adjacent neighbor with an SCS number less than the last known SCS number from that neighbor, it MUST first check if the SCS number is a wrap around. If it is NOT a wrap around, then the device MUST send a Hello request to the neighbor. If it is a wrap around or if a device receives a Hello from an adjacent neighbor with an SCS number one greater than the last known SCS number from that neighbor, it MUST: o Examine the neighbor list described in [OSPFv3], A.3.2. If any neighbors are contained in this list, increment the SCS number contained in the adjacent neighbor's data structure. o Examine the Neighbor-Drop TLV as described in the section Adjacency Failure. If this list contains a neighbor other than the local router, increment the SCS number contained in the adjacent neighbor's data structure. o Examine the Neighbor Drop TLV as described in the section Adjacency Failure. If the local router identifier is contained in this list, destroy the transmitting adjacent neighbor's data structures. o Examine any other TLVs incrementally signaled, as described in drafts referring to this document. If there are other state changes indicated, increment the SCS number contained in the adjacent neighbor's data structure. o If no state change information is contained in the received Hello, a request for current state (by setting the 'R' bit) is sent in the next Hello. If a device receives a Hello from an adjacent neighbor with an SCS number greater than the last known SCS number + 1 from that neighbor, it MUST send a Hello request to the neighbor since it may be missing some neighbor state. 3.2.8.1 Receiving Hellos with the N Bit Set If a device receives a Hello with the SCS TLV included, and the 'N' bit set in this TLV, it MUST verify that it has already received the SCS number with the 'N' bit NOT set from the neighbor. If the device determines that this is the first reception of the SCS number from this neighbor, then it MUST send a Hello request to the neighbor since it missed the initial Hello packet with the SCS number, and thus is missing state. Chandra, Roy et al. Expires March 2009 [Page 14] Internet-Draft Extensions to OSPF to Support MANETs September 2008 3.2.8.2 Receiving Hellos with the R Bit Set If a device receives a Hello with the SCS TLV included, and the R bit set, it looks for the RF TLV. If it's router ID is listed in the RF TLV or the TLV is not found, it includes its full state in the next Hello. This MUST include: o The neighbor ID of the requesting neighbor(s) in the list of neighbors described in [OSPFv3], A.3.2., o An SCS TLV with the transmitter's current SCS number, and the FS bit set. Note that the transmitter's SCS number is NOT incremented. o Any other TLVs, defined in other drafts referencing this document, indicating the current state of the local system. o The neighbor ID of all the neighbors who have requested current state, in the FSF TLV. If the full state is being sent to a large number of existing neighbors, and implementation could choose to instead generate a full state for all neighbors and omit the FSF TLV. 3.2.8.3 Receiving Hellos with the FS Bit Set When a device receives a Hello with the SCS TLV included, and the FS bit set, the Hello packet contains the neighbor's full state for the device. The packet SHOULD be processed as follows: o If the received SCS number is equal to the last known SCS number, the packet SHOULD be ignored since the device already has the latest state information. o If the received SCS number is different than the last known SCS number, this Hello has new information and MUST be parsed. o If it is listed in the FSF TLV or if the FSF TLV is not present, the device MUST save the SCS number, process the Hello as described in the Receiving Hellos section, and process any other appended TLVs. 3.2.9 Interoperability On receiving a Hello packet from a new neighbor without the I bit set, the local router will continue to place that router's identifier in transmitted Hellos on this link as described in [OSPFv3], A.3.2. 3.2.10 Support for OSPF Graceful Restart OSPF graceful restart, as described in [OSPFREST] and [OSPFGR], relies on the lack of neighbors in the list of neighbors described in [OSPFv3], A.3.2, to determine that an adjacent router has restarted, and other signaling to determine the adjacency should not be torn down. If all Hello packets transmitted by a given router have an empty Hello list, reliance on an empty Hello packet to signal a restart (or to reliably tear down an OSPF adjacency) is no longer possible. Hence, this signaling must be slightly altered. Chandra, Roy et al. Expires March 2009 [Page 15] Internet-Draft Extensions to OSPF to Support MANETs September 2008 When a router would like to tear down all adjacencies, or signal it has restarted: o On initially restarting, during the first RouterDeadInterval after restart, the router will transmit Hello packets with an empty neighbor list, and the I bit cleared. Any normal restart or other signaling may be included in these initial Hello packets. o As adjacencies are learned, these newly learned adjacent routers are included in the multicast Hellos transmitted on the link. o After one RouterDeadInterval has passed, the incremental Hello mechanism is invoked. An incremental Hello packet with full state is sent with the I bit set, and the SCS TLV included with the FS bit set and the InitialSCS value, e.g., SCS of '1'. Subsequent Hello packets will include only incremental state. Routers which are neighboring with a restarting router MUST continue sending their Hello packets with the I bit set. 3.3 Optimized Flooding (Overlapping Relays) A component that may influence the scalability and convergence characteristics of OSPF [OSPF],[OSPFv3] in a MANET environment is how much information needs to be flooded. The ideal solution is that a router will only receive a particular routing update only once. However, there must be a tradeoff between protocol complexity and ensuring that every speaker in the network receives all of the information. Note that a speaker refers to any node in the network that is running the routing protocol and transmitting routing updates and Hello messages. Controlling the amount of information on the link has increased importance in a MANET environment due to the potential transmission costs and resource availability in general. In some environments, a group of speakers that share the same logical segment may not be directly visible to each other; some of the possible causes are the following: low signal strength, long distance separation, environmental disruptions, partial VC meshing, etc. In these networks, a logical segment refers to the local flooding domain dynamically determined by transmission radius. In these situations, some speakers (the ones not able to directly reach the sender) may never be able to synchronize their databases. To solve the synchronization issues encountered in these environments, a mechanism is needed through which all the nodes on the same logical segment can receive the routing information, regardless of the state of their adjacency to the source. 3.3.1 Operation Overview The optimized flooding operation relies on the ability of a speaker to advertise all of its locally connected neighbors. In OSPF, this ability is realized through the use of link state advertisements (LSA)s [OSPF],[OSPFv3]. Chandra, Roy et al. Expires March 2009 [Page 16] Internet-Draft Extensions to OSPF to Support MANETs September 2008 A speaker receives router LSAs from its adjacent neighbors. A speaker's router LSA conveys the list of the adjacent speakers of the originator ("neighbor list"). The local speaker can compare the neighbor list reported by each speaker to its own neighbor list. If the local neighbor list contains adjacent speakers that the originator cannot reach directly (i.e. those speakers that are not in the originator's neighbor list), then these speakers are locally known as non-overlapping neighbors for the originator. The local speaker should relay any routing information to non- overlapping neighbors of the sender based on the algorithm outlined in the Flooding and Relay Decisions section. Because more than one such speaker may exist, the mechanism is called "overlapping relays." The algorithm, however, does select the set of overlapping relays that should transmit first. This set is known as the active set of overlapping relays for a speaker. 3.3.2 Determination of Overlapping Relays The first step in the process is for each speaker to build and propagate their neighbor lists in router LSAs packets. Every speaker is then in a position to determine their two-hop neighborhood, i.e., those nodes that are neighbors of the speaker's one-hop neighbors. A bidirectional neighbor is considered an overlapping relay for a speaker if it can reach a node in the two-hop neighborhood of the speaker, i.e., if it has one-hop neighbors (excluding the speaker itself). The set of active overlapping relays for a speaker is the minimum set of direct neighbors such that every node in the two-hop neighborhood of the speaker is a neighbor of a least one overlapping relay in the active set. Each speaker SHOULD select a set of active overlapping relays based on a selection algorithm (one such algorithm is suggested in the "Overlapping Relay Discovery Process" Section and is based on the MPR selection algorithm described in [OLSR]). Note that a speaker MUST NOT choose a neighbor to serve as an active overlapping relay if that neighbor set the 'N' bit in its Active Overlapping Relay TLV as defined in Section "Active Overlapping Relay Extension", unless the neighbor is the only neighbor to reach a two- hop neighbor. Election of active overlapping relays is done across interfaces, and thus, it is node-based and not link-based. 3.3.3 Terminology The following heuristic and terminology for active overlapping relay selection is largely taken from [OLSR]: o FULL: Neighbor state FULL as defined in [OSPF] & [OSPFv3]. Note that all neighbor references in this document are assumed to be FULL neighbors. o N: N is the set of FULL neighbors of the node. Chandra, Roy et al. Expires March 2009 [Page 17] Internet-Draft Extensions to OSPF to Support MANETs September 2008 o 2-hop FULL neighbors (N2): The list of 2-hop neighbors of the node that are FULL and that can be reached from direct neighbors, excluding any directly connected neighbors. o Active Set: A (sub)set of the neighbors selected such that through these selected nodes, all 2-hop FULL neighbors are reachable. o D(y): The degree of a one hop neighbor node y (where y is a member of N), is defined as the number of FULL neighbors of node y, EXCLUDING all the members of N and EXCLUDING the node performing the computation. 3.3.4 Overlapping Relay Discovery Process A possible algorithm for discovering overlapping relays is the following: 1. Start with an active set made of all members of N that have set the 'A' bit in their Active Overlapping Relays TLV as defined in Section "Active Overlapping Relays Extension". 2. Calculate D(y), where y is a member of N, for all nodes in N. 3. Add to the active set those nodes in N, which are the *only* nodes to provide reachability to a node in N2, i.e., if node-b in N2 can be reached only through a symmetric link to node-a in N, then add node-a to the active set. Remove the nodes from N2 which are now covered by a node in the active set. 4. While there exist nodes in N2 which are not covered by at least one node in the active set: 1. For each node in N, calculate the reachability, i.e., the number of nodes in N2 which are not yet covered by at least one node in the active set, and which are reachable through this one hop neighbor; 2. Select as an active overlapping relay the node with highest Willingness among the nodes in N with non-zero reachability. In case of multiple choice select the node which provides reachability to the maximum number of nodes in N2. In case of multiple nodes providing the same amount of reachability, select the node as active whose D(y) is greater. As a final tie breaker, the node with the highest router ID should be chosen. Remove the nodes from N2 which are now covered by a node in the active set. 5. As an optimization, process each node, y, in the active set in increasing order of Willingness. If all nodes in N2 are still covered by at least one node in the active set excluding node y, and if Willingness of node y is smaller than MAX_WILLINGNESS, then node y should be removed from the active set. Note that the active overlapping relays selection algorithm is implementation specific, and the above is simply a suggested algorithm. However, the behavior of the overlapping relays MUST follow that specified in the "Flooding and Relay Decisions" Section. Moreover, the same selection algorithm MUST be used by all nodes within an area. Chandra, Roy et al. Expires March 2009 [Page 18] Internet-Draft Extensions to OSPF to Support MANETs September 2008 3.3.5 The F Option Bit A single new option bit, the F bit, is defined in the OSPFv3 option field. The F bit indicates that the node supports the Optimized Flooding mechanism as specified in this draft. See Section "New Bits in OSPFv3 Options Field" for placement of the F bit. 3.3.6 Active Overlapping Relay TLV (AOR TLV) A new TLV is defined so that each speaker can convey its set of active overlapping relays in the Hello messages. The TLV is transmitted using LLS [LLS]. 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Relays Added |A|N| Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID(s) of Active Overlapping Relay(s) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ o Type: 7 o Length - variable; Length of TLV in bytes NOT including Type and Length. o Relays Added - variable; Number of active overlapping relays that are being added. Note that the number of active overlapping relays that are being dropped is then given by: [(Length - 4)/4 - Relays Added]. o A bit - If this bit is set, the node is specifying that it will always flood routing updates that it receives, regardless of whether it is selected as an Active Overlapping Relay. o N bit - If this bit is set, the node is specifying that it most likely will not flood routing updates. The node SHOULD NOT be chosen to be an active overlapping relay unless it is the *only* neighbor that can reach two-hop neighbor(s). Note that if the node is selected as an Active Overlapping relay and the node can not perform the required duties, network behavior is not compromised since it results in the same behavior as if the node was not chosen as an active overlapping relay. o Reserved - Reserved for future use and MUST be ignored upon reception. o Router ID(s) of Active Overlapping Relay(s) - The router ID(s) of neighbor(s) that are either chosen to serve as an active overlapping relay, or removed from serving as an active overlapping relay. The active overlapping relays that are being added MUST be listed first, and the number of such relays MUST equal Add Length. The remaining list of relays are being dropped as active overlapping relays, and the number of such relays MUST equal [(Length - 4)/4 - Relays Added]. Chandra, Roy et al. Expires March 2009 [Page 19] Internet-Draft Extensions to OSPF to Support MANETs September 2008 Note that the 'A' bit and 'N' bit are independent of any particular selection algorithm to determine the set of Active Overlapping Relays. However, the bits SHOULD be considered as input into the selection algorithm. If a node is selected as an active overlapping relay and it does not support the Incremental Hello mechanism defined in the "Incremental OSPF-MANET Hellos" Section, then it SHOULD always be included as an Active Overlapping Relay in the TLV. Note that while a node needs to know whether it is an active overlapping relay, it does not necessarily have to know the identities of the other active overlapping relays. 3.3.7 Willingness TLV A new TLV is defined so that each speaker can convey its willingness to serve as an active overlapping relay in the Hello meassage. The TLV is transmitted using the LLS [LLS]. 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Willingness | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ o Type: 8 o Length - 4 bytes. It does not include the Type and Length fields. o Willingness - 1 byte to indicate the willingness of the node to serve as an active overlapping relay for its neighbors. * 0: MIN_WILLINGNESS * 128: DEFAULT_WILLINGNESS * 255: MAX_WILLINGNESS The TLV is optional and MUST be silently ignored if not understood. If the Willingness TLV is not included in the Hello packet, the Willingness value SHOULD be taken as DEFAULT_WILLINGNESS. 3.3.8 Flooding and Relay Decisions The decision whether to relay any received LSAs and when to relay such information, is made depending on the topology and whether the node is part of the set of active overlapping relays. Upon receiving an LSA from an bi-directional neighbor, a node makes flooding decisions based on the following algorithm: 1. If the node is an active overlapping relay for the adjacent speaker, then the router SHOULD immediately relay any information received from the adjacent speaker. Chandra, Roy et al. Expires March 2009 [Page 20] Internet-Draft Extensions to OSPF to Support MANETs September 2008 2. If the node is a non-active overlapping relay for the adjacent speaker, then the router SHOULD wait a specified amount of time (PushbackInterval plus jitter, see "Important Timers" Section) to decide whether to transmit. [Jitter is used to try to avoid several non-active overlapping relays from propagating redundant information.] Note that a node with the 'N' bit set in the 'Active Overlapping Relays' Extension will not be chosen as an active overlapping relay unless it is the only node to provide reachability to a two-hop neighbor. However, it MUST perform the duties of a non-active overlapping relay as required. Non-active overlapping relays MUST follow the acknowledgment mechanism outlined in the section 'Intelligent Transmission of Link State Acknowledgements.' 1. During this time, if the node determines that flooding the LSA will only result in a redundant transmission, the node MUST suppress its transmission. Otherwise, it MUST transmit upon expiration of PushbackInterval plus jitter. 2. If a non-active overlapping relay hears a re-flood from another node that covers its non-overlapping neighbors before its timer to transmit expires, it SHOULD reset its PushbackInterval plus jitter timer. (Note that the implementation should take care to avoid resetting the PushbackInterval timer based on transmissions from active overlapping relays.) During this time, if the node determines that flooding the update will only result in a redundant transmission, the node MUST suppress its transmission. Otherwise, it MUST transmit upon expiration of PushbackInterval + jitter. 3. If a non-active overlapping relay hears an old instance of the LSA during this time, it SHOULD ignore the LSA and it SHOULD NOT send a unicast packet to the neighbor with the most recent LSA as specified in [OSPFv3]. 3. For LSAs that are received unicast because of retransmission by the originator, the node MUST determine whether it has already received the LSA from another speaker. If it already has the current instance of the LSA in its database, it MUST do nothing further in terms of flooding the LSA (since it would have taken appropriate behavior when it initially received the LSA.) However, if it does not have the current instance of the LSA in its database, it MUST take action according to the rules above, just as if it received the multicast LSA. The acknowledgement mechanism outlined in the section 'Intelligent Transmission of Link State Acknowledgements' MUST be followed, and any timeout mechanism for unicast LSAs MAY be followed. Note that a node can determine whether further flooding a LSA will only result in a redundant transmission by already having heard link state acknowledgements (ACKs) or floods for the LSA from all of its neighbors. Due to the dynamic nature of a network, the set of active overlapping relays may not be up to date at the time the relay decision is made or may not be able to perform the flooding duties, e.g., due to poor Chandra, Roy et al. Expires March 2009 [Page 21] Internet-Draft Extensions to OSPF to Support MANETs September 2008 link quality. The non-active overlapping relays prevent this situation from causing database synchronization issues and thus, packet loss. Since the originator of the information, the relay, and the receiver are all in the same dynamically determined local flooding domain, the relay MUST NOT change the routing update information. In general, LSAs SHOULD be sent to a well-known multicast address. In some cases, routing updates MAY be sent using unicast packets. 3.3.9 Intelligent Transmission of Link State Acknowledgements In order to optimize the bandwidth utilization on the link, a speaker MUST follow these recommendations related to ACK transmissions: 1. All ACKs MUST be sent via multicast. 2. Typically, LSAs are acknowledged by all of the adjacent speakers. In the case of relayed information, the relay MUST only expect either explicit or implicit acknowledgements from neighbors that have not previously acknowledged this LSA. 3. Because routing updates are sent via multicast, the set of overlapping speakers will usually receive the same update more than once. A speaker SHOULD only acknowledge the first update received on the link. 4. An active overlapping relay SHOULD NOT explicitly acknowledge information that it is relaying. The relayed information will serve as an acknowledgement to the sender. If no information is being relayed, than an explicit ACK MUST be sent. 5. Several ACKs MAY be bundled into a single packet. The wait (AckInterval) before sending one such packet reduces the number of packet transmissions required in acknowledging multiple LSAs. 6. All ACK packets SHOULD reset the RouterDeadInterval at the receiver. If there is no state waiting to be transmitted in a Hello packet at the sender, then the HelloInterval at the sender SHOULD be reset. Note that an ACK serves as a Hello packet with no state change. 7. Any LSA received via unicast MUST be acknowledged. (Note that acknowledgment is via multicast as specified in rule (1) above.) An ACK received from a non-overlapping neighbor should prevent redundant transmission of the information to it by another overlapping relay. 3.3.10 Important Timers This section details the timers that are introduced in the Flooding and Relay Decisions and Intelligent Transmission of Link State Acknowledgements sections. o PushbackInterval: The length of time in seconds that a non-active overlapping relay SHOULD wait before further flooding an LSA if needed. This timer MUST be less than 1/2 of the RxmtInterval [OSPF],[OSPFv3] minus propagation delays, i.e., (PushbackInterval + propagation delay) < RxmtInterval/2. The PushbackInterval is Chandra, Roy et al. Expires March 2009 [Page 22] Internet-Draft Extensions to OSPF to Support MANETs September 2008 set by a non-active overlapping relay upon reception of an LSA. o AckInterval: After a node determines that it must transmit an ACK and the AckInterval timer is not already set, the node SHOULD set the AckInterval timer. The AckInterval is the length of time in seconds that a node should wait in order to transmit many ACKs in the acknowledgement packet. This wait reduces the number of packet transmissions required in acknowledging multiple LSAs. The AckInterval MUST be less than the PushbackInterval minus propagation delays, i.e., (AckInterval + propagation delay) < PushbackInterval. 3.3.11 Miscellaneous Protocol Considerations The mechanism described refers to the operation of relays on a common media segment. In other words, an LSA is only relayed out the same interface through which it was received. However, the concept of information relay may be extended to the flooding of all link state advertisements received on any interface (and forwarded on any other interface). OSPF works on the premise that all of the nodes in a flooding domain will receive all of the routing information. Note that one of the important properties is that the routing information is not altered when relayed. If each speaker advertised all of its adjacent neighbors on all interfaces, then the overlap check would result in the determination of which speakers are adjacent to both speakers. As a result, link state information should only be flooded to non-overlapping neighbors (taking all of the interfaces into account). The flooding mechanism in OSPF relies on a designated router to guarantee that any new LSA received by one router attached to the broadcast network will be reflooded properly to all the other routers attached to the broadcast network. Such desginated routers must be able to reach all of the other speakers on the same subnet. A designated router SHOULD NOT be elected if overlapping relays are used. If such designated routers already exist, then the relays MUST be capable of differentiating them, and then making the relaying decisions based on the OSPF's normal operation. As a result, there may be groups of neighbors to which some information should not be relayed. This mode of operation is NOT RECOMMENDED as it adds to the complexity of the system. The intent of the overlapping relay mechanism is to optimize flooding of routing control information. However, other information (such as data) may also be relayed in some networks using the same mechanism. 3.3.12 Interoperability On receiving a Hello packet from a new neighbor without the F bit set, the local router will assume that the new neighbor will flood normally as described in [OSPFv3]. Thus, the local router SHOULD Chandra, Roy et al. Expires March 2009 [Page 23] Internet-Draft Extensions to OSPF to Support MANETs September 2008 include the neighbor in its overlapping relay set since the neighbor will flood by default. This will allow the local router to more optimally select its entire overlapping relay set. If the F bit is set and the I bit as defined in Section "Incremental OSPF-MANET Hellos" is not set in the neighbor's Hello and the neighbor is selected as an overlapping relay by the local router, the local router will continue to include the neighbor's identifier in its active relay set. 3.4 New Bits in OSPFv3 Option Field Two new option bits are defined in the OSPFv3 Options Field (defined in [OSPFv3], A.2) as follows: o I bit - defined in Section "I Option Bit": The I bit is only defined for Hello packets and indicates that only incremental information is present. o F bit - defined in Section "F Option Bit": The F bit indicates that the node supports the Optimized Flooding mechanism as specified in this draft. 3.5 Smart Peering There is significant overhead in OSPF when a router has to establish adjacencies with every peer with whom it can verify 2-way connectivity. OSPF supports the broadcast network type for these scenarios, where you only have to peer with the designated router (DR). However,a full mesh of connectivity is required for proper operation and this doesn't help in networks with overlapping partial meshes of connectivity. This draft proposes a technique to reduce the number of adjacencies based on shortest path tree (SPT) reachability information. 3.5.1. Introduction In OSPF [OSPF] [OSPFv3], nodes establish an adjacency by first verifying 2-way connectivity between them and then synchronizing their link state databases. Once the peering relationship is complete and the adjacency is established, the nodes will continue to advertise each other in their LSAs. As a result, the peers are maintained in the link state database and are included in all SPF calculations. During the reliable flooding process, a node must ensure that each peer has indeed received the flooded routing update via an acknowledgment and retransmission mechanism. Consequently, maintaining an adjacency for a particular peer is a tradeoff between the added redundancy in routing paths and network reachability versus the associated overhead (memory consumption, SPF computations, routing overhead, and network convergence). Consider the possibility of reducing the number of adjacencies that a node maintains without compromising reachability and redundancy. Chandra, Roy et al. Expires March 2009 [Page 24] Internet-Draft Extensions to OSPF to Support MANETs September 2008 This will have direct implications on network scalability and is especially attractive in environments where the network topology is dynamic. For example, in a Mobile Ad-Hoc Network (MANET) where nodes are mobile and the topology is constantly changing, it seems highly desirable to 'intelligently' become adjacent with only selected peers and not establish a peering session with every node that comes within transmission range. Selective peering can be particularly useful in avoiding the peering process for unstable nodes, i.e., nodes that come in and out of transmission range. 3.5.2. Previous Related Work The formation of a FULL adjacency requires the discovery (2-way relationship) and the database synchronization. To prevent from achieving the FULL state, others have taken the approach of modifying link state protocols to use periodic advertisements (instead of a database exchange). The result is that neighbor discovery is still required, but routing information is learned over time. An example of this approach is: o OSPFv2 Wireless Interface Type [WINTF] * where the use of periodic advertisements "eliminates the formation of full adjacencies on wireless interfaces; all neighbor states beyond 2-Way are not reached,and no database synchronization is performed". What we propose in this specification goes a step further by not requiring the formation and maintenance of neighbor state (2-way, or other) *and* without changing the route distribution mechanisms in the link state protocols. In other words, the mechanism described is completely backwards compatible. 3.5.3. Proposed Solution Two routers are defined synchronized when they have identical link state database. To limit the number of neighbors that are formed, an algorithm is needed to select which neighbors with whom to peer. The algorithm MUST provide reachability to every possible destination in the network, just like when normal adjacency formation processes are used. We should always peer with a neighbor if it provides our only path to currently unreachable destinations. 3.5.3.1. SPT Reachability Heuristics The peering decision is really a local matter to a router. If a router can ensure that reachability to other nodes is available without bringing up a new adjacency, it can choose not to bring up the new adjacency. Chandra, Roy et al. Expires March 2009 [Page 25] Internet-Draft Extensions to OSPF to Support MANETs September 2008 We propose an algorithm which uses the existing information about a new neighbor's reachability in the SPT. If the two routers can already reach each other in the SPT, it is not necessary to form an adjacency between them. The decision to peer or not, is made when a hello is received. When a hello is received from a new neighbor or a neighbor in a state lower than Exchange: o A check is made in the link state database to see if the peer is already reachable in the SPT. * If the peer is either not known in the SPT or is not reachable, we start the Exchange process. * If the peer is reachable than bringing up adjacency with this neighbor does not provide reachability to any new destinations. Let's take an example of a single OSPF area. This check would look for the neighbor's Router LSA. If the LSA is present in the database and is reachable in the SPT, we have a chance to suppress adjacency formation. It's worth noting that as the number of links and redundancy in the network is reduced, the likelihood of suboptimal routing increases. 3.5.3.2. State Machine The state machine of a basic implementation of this algorithm is provided below: An implementation MAY use some heuristics below (step (3)), beyond the SPT reachability to decide whether or not it considers a new adjacency to be of value. Chandra, Roy et al. Expires March 2009 [Page 26] Internet-Draft Extensions to OSPF to Support MANETs September 2008 ...................... |Receive a hello | (1) |from a new potential| |neighbor | '`'''''''''''''''''''' | | | ,''''''''''''''''''''''| |Check to see if there | (2) |is a router LSA from |----no--(4)form a |the new potential | new |neighbor in the link | neighbor |state database, which | |is reachable in SPT | '`'''''''''''''''''''''' | |yes (3) | ,'''''''''''''''''''''''''''''''''''''''''''''''''''''''''| | (3b)........................ | |(3a),______________________ |Determine if the | | | |Determine if the new | |number of redundant | | | |link cost is better | |paths to the potential| | | |than the current path| |neighbor is < the | | | |cost by a configured | |maximum configured | | | |amount | |value | | | '`''''''''''''''''''''' '`'''''''''''''''''''''' | | \ / | | .....\.........../.... | | |User configurable | | | |selection algorithm | | | '`'''/'''''''\'''''''' | | / \ | '`'''''''''''''''''''''/'''''''''''\''''''''''''''''''''''' / \ requirements requirements met not met / \ / \ (4) form a new neighbor (5) do not become neighbors 3.5.4. Advertise the 2-way link in Router-LSA The technique described in Section 3.5.3 minimizes the number of adjacencies in highly meshed environments. This is especially useful when the network is in motion and the average adjacency lifetime is small. However, it suffers from an undesirable side effect of limiting the number of transit links available to forward traffic. Chandra, Roy et al. Expires March 2009 [Page 27] Internet-Draft Extensions to OSPF to Support MANETs September 2008 An implementation may choose to allow some (or even all) of these 2-way state neighbors to be announced in the Router-LSA. Since the state remains 2-way, we don't incur control plane (database sync and flooding) overhead. However, advertising the link in the Router-LSA makes the link available to the data plane. This can be safely done if the neighbor is reachable in a special SPT constructed by ignoring any other 2-way links in the network. This optional optimization is described below. 3.5.4.1. Unsynchronized Adjacencies If the new neighbor is already reachable in the SPT, there is no urgency in doing a full database sync with it. These are the steps we need to perform when a neighbor has reached 2-way state. Note that when we say SPT in this section, we mean the special SPT constructed based on rules in Section 3.5.4.2. o After 2-WayReceived event, check if the neighbor is reachable in the SPT. If yes, mark the neighbor as FULL with respect to link advertisement. o This means that the router-LSA or network-LSA link corresponding to the neighbor is advertised as if the neighbor is FULL. o The adjacency information is constructed with U-bit (see below). o Database synchronization is postponed: * By a configured amount of time -OR- * Until the time it's absolutely "necessary" In either case, if a database sync is currently pending, it is started as soon as we detect the neighbor is no longer reachable in the SPT. The database sync can be done by Out-of-band Sync [OOB], which maintains the current adjacency and does the sync in the background. A normal Resync can alternately be done with the drawback of adjacency flap. In standard OSPF we first bring up adjacency and then announce a transit link. The approach described above will allow the link to be used as a forwarding path very quickly and still allows the database to be synchronized in a timely fashion when the alternate flooding path has recently been broken. There is a circular dependency issue which also needs to be resolved. Once you start announcing the link, the shortest path will likely be via this very link. So it's non-trivial to detect when the alternate dependent path is gone. What we would like to be able to detect is that the neighbor is reachable via a path which doesn't traverse an unsynchronized path. Chandra, Roy et al. Expires March 2009 [Page 28] Internet-Draft Extensions to OSPF to Support MANETs September 2008 We have generally solved this class of problems by running an SPF and pretending that the link in question doesn't exist. It doesn't require a full SPF, just enough to see if ANY other path is available to reach the neighbor. The worst case is when the alternate path is really gone and we find that out by building a full SPT. This needs to be done every time the link state database changes, and for EACH link which has SPT dependence for it's viability. This approach has scalability concerns and is not considered further here. We can achieve the same results with just ONE additional SPF which is capable of ignoring these Unsynchronized links. The result from this SPT can be used to satisfy the reachability condition for ANY number of Unsynchronized Adjacencies. This basically requires that we can actually tell the difference between a normal FULL adjacency and this new Unsynchronized Adjacency. We can do this in one of two ways: (A) Define LD Options and use a bit in it, as shown below: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | LD Options | Metric | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interface ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Interface ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Link Description in a Router-LSA LD Options Link Description options. Used to specify some special capability or state of a link. +-+-+-+-+-+-+-+-+ | | | | | | | |U| +-+-+-+-+-+-+-+-+ LD Options U-bit The "Unsynchronized" bit. This is set if the adjacency is being announced before databases are fully synchronized. This approach is backward compatible because the only routers looking at this bit are those that support the mechanisms specified in this document. Chandra, Roy et al. Expires March 2009 [Page 29] Internet-Draft Extensions to OSPF to Support MANETs September 2008 (B) Introducing a new link type in Router-LSA. This is a much more complex solution with backward compatibility concerns due to the fact that unknown link type handling is not defined in OSPF standard [OSPF]. Hence this solution isn't considered further. 3.5.4.2. Unsynchronized SPT Whenever link state changes happen, we need to run ONE additional SPF by ignoring all links with U-bit set. This SPT is then consulted to see if any of our Unsynchronized Adjacencies need to start database sync. This SPT is also consulted when a new neighbor goes into 2-way to decide if we should form the adjacency immediately or defer it for later. 3.5.4.3. Flooding Considerations One of the main goals in trying to delay the database synchronization is to be able to reduce unnecessary OSPF packets traversing these links. Since the unsynchronized Adjacencies remain in 2-way state, OSPF updates will not be flooded over the corresponding interfaces resulting in additional savings. An option is provided to enable or disable flooding over these Unsynchronized Adjacencies. The advantage of allowing flooding is being able to use more links for control plane purposes. We will still have the savings of not having to form the adjacency. 3.5.4.4. Overlapping Relay (OR) election impact The overlapping relay election algorithm uses the two hop neighborhood it gleans from our neighbor's Router-LSAs. The introduction of Unsynchronized Adjacencies needs to be considered in the relay election algorithm. If flooding is enabled on unsynchronized Adjacencies, no change is needed in the relay election algorithm. If flooding is disabled, then the relay election algorithm needs to prune neighbors that are connected via an Unsynchronized Adjacency from our 1-hop and 2-hop neighbor lists. 4. Security Considerations In a MANET network, security is both more difficult and important due to the wireless nature of the medium. Controlling the ability of devices to connect to a MANET network at Layer 2 will be relegated to Layer 2 security mechanisms, such as 802.1x, and others. Controlling the ability of attached devices to transit traffic will require some type of security system (outside the scope of this document) which can authenticate and provide authorization for individual members of the routing domain. Chandra, Roy et al. Expires March 2009 [Page 30] Internet-Draft Extensions to OSPF to Support MANETs September 2008 5. IANA Considerations IANA will make assignments as explained below using the policies outlined in [IANA]. o I-bit and F-bit as defined below: 0 1 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+--+--+--+--+ | | | | | | | | | | | | |F|I|*|*|*|*|DC| R| N| x| E|V6| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+--+--+--+--+ The Options field o New TLV type codes are defined from LLS [LLS] TLV types values. TLV Name TLV Type -------- -------- State Check Sequence TLV 3 Neighbor Drop TLV 4 Request From TLV 5 Full State For TLV 6 Active Overlapping Relay TLV 7 Willingness TLV 8 o A new registry is defined for LD Options as defined in Section 3.5.4.1. U-bit is allocated by this document. All future additions to LD Options are subject to OSPF WG review and require IETF standards action. 6. Contributors The following persons are contributing authors to the document: Fred Baker Dave Cook Cisco Systems Cisco Systems 1121 Via Del Rey 7025-4 Kit Creek Road Santa Barbara, CA 93117 RTP, NC 27709 USA USA Email: fred@cisco.com Email: dacook@cisco.com Alvaro Retana Yi Yang Cisco Systems Cisco Systems 7025-4 Kit Creek Road 7025-4 Kit Creek Road RTP, NC 27709 RTP, NC 27709 USA USA Email: aretana@cisco.com Email: yiya@cisco.com Chandra, Roy et al. Expires March 2009 [Page 31] Internet-Draft Extensions to OSPF to Support MANETs September 2008 Russ White Cisco Systems 7025-4 Kit Creek Road RTP, NC 27709 USA Email: riw@cisco.com 7. Acknowledgements The authors and contributors would like to thank Pratap Pellakuru, Stan Ratliff for their feedback and implementation of the document. Thanks to Richard Ogier and John Avery for doing a final review. References Normative References [OSPF] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. [OSPFv3] Coltun, R., Ferguson, D., J. Moy and A. Lindem, "OSPF for IPv6", RFC 5340, July 2008. [IANA] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", RFC 5226, May 2008. [KEY] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. Informative References [IPV6ADD] Hinden, R. and S. Deering, "IP Version 6 Addressing Architecture", RFC 4291, February 2006. [OSPFGR] Moy, J., Pillay-Esnault, P., and A. Lindem, "Graceful OSPF Restart", RFC 3623, November 2003. [OSPFREST] Zinin, A., Roy, A., and L. Nguyen, "OSPF Restart Signaling", RFC 4812, March 2007. [OOB] Zinin, A., Roy, A., and L. Nguyen, "OSPF Out-of-band LSDB resynchronization", RFC 4811, March 2007. [LLS] Zinin, A., Roy, A., Nguyen, L., Friedman, B., and D. Yeung, "OSPF Link-local Signaling", draft-ietf-ospf-lls-05.txt (work in progress), April 2008. [OLSR] Clausen, T. and P. Jacquet, "Optimized Link State Routing Protocol", RFC 3626, October 2003. [WINTF] Ahrenholz J. et al, "OSPFv2 Wireless Interface Type", draft-spagnolo-manet-ospf-wireless-interface (work in progress) Chandra, Roy et al. Expires March 2009 [Page 32] Internet-Draft Extensions to OSPF to Support MANETs September 2008 Authors' Addresses Madhavi W. Chandra (Editor) Abhay Roy (Editor) Email: mw.chandra@gmail.com Cisco Systems 170 W. Tasman Drive San Jose, CA 95134 USA Email: akr@cisco.com Full Copyright Statement Copyright (C) The IETF Trust (2008). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Intellectual Property The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Chandra, Roy et al. Expires March 2009 [Page 33] Internet-Draft Extensions to OSPF to Support MANETs September 2008 Acknowledgment Funding for the RFC Editor function is provided by the IETF Administrative Support Activity (IASA). Chandra, Roy et al. Expires March 2009 [Page 34]