diff options
Diffstat (limited to 'doc/rfc/rfc5614.txt')
| -rw-r--r-- | doc/rfc/rfc5614.txt | 3979 |
1 files changed, 3979 insertions, 0 deletions
diff --git a/doc/rfc/rfc5614.txt b/doc/rfc/rfc5614.txt new file mode 100644 index 0000000..c7bad5e --- /dev/null +++ b/doc/rfc/rfc5614.txt @@ -0,0 +1,3979 @@ + + + + + + +Network Working Group R. Ogier +Request for Comments: 5614 SRI International +Category: Experimental P. Spagnolo + Boeing + August 2009 + + + Mobile Ad Hoc Network (MANET) Extension of OSPF + Using Connected Dominating Set (CDS) Flooding + +Abstract + + This document specifies an extension of OSPFv3 to support mobile ad + hoc networks (MANETs). The extension, called OSPF-MDR, is designed + as a new OSPF interface type for MANETs. OSPF-MDR is based on the + selection of a subset of MANET routers, consisting of MANET + Designated Routers (MDRs) and Backup MDRs. The MDRs form a connected + dominating set (CDS), and the MDRs and Backup MDRs together form a + biconnected CDS for robustness. This CDS is exploited in two ways. + First, to reduce flooding overhead, an optimized flooding procedure + is used in which only (Backup) MDRs flood new link state + advertisements (LSAs) back out the receiving interface; reliable + flooding is ensured by retransmitting LSAs along adjacencies. + Second, adjacencies are formed only between (Backup) MDRs and a + subset of their neighbors, allowing for much better scaling in dense + networks. The CDS is constructed using 2-hop neighbor information + provided in a Hello protocol extension. The Hello protocol is + further optimized by allowing differential Hellos that report only + changes in neighbor states. Options are specified for originating + router-LSAs that provide full or partial topology information, + allowing overhead to be reduced by advertising less topology + information. + +Status of This Memo + + This memo defines an Experimental Protocol for the Internet + community. It does not specify an Internet standard of any kind. + Discussion and suggestions for improvement are requested. + Distribution of this memo is unlimited. + + + + + + + + + + + + +Ogier & Spagnolo Experimental [Page 1] + +RFC 5614 MANET Extension of OSPF August 2009 + + +Copyright Notice + + Copyright (c) 2009 IETF Trust and the persons identified as the + document authors. All rights reserved. + + This document is subject to BCP 78 and the IETF Trust's Legal + Provisions Relating to IETF Documents in effect on the date of + publication of this document (http://trustee.ietf.org/license-info). + Please review these documents carefully, as they describe your rights + and restrictions with respect to this document. + + This document may contain material from IETF Documents or IETF + Contributions published or made publicly available before November + 10, 2008. The person(s) controlling the copyright in some of this + material may not have granted the IETF Trust the right to allow + modifications of such material outside the IETF Standards Process. + Without obtaining an adequate license from the person(s) controlling + the copyright in such materials, this document may not be modified + outside the IETF Standards Process, and derivative works of it may + not be created outside the IETF Standards Process, except to format + it for publication as an RFC or to translate it into languages other + than English. + +Table of Contents + + 1. Introduction ....................................................4 + 1.1. Terminology ................................................5 + 2. Overview ........................................................7 + 2.1. Selection of MDRs, BMDRs, Parents, and Adjacencies .........8 + 2.2. Flooding Procedure .........................................9 + 2.3. Link State Acknowledgments ................................10 + 2.4. Routable Neighbors ........................................10 + 2.5. Partial and Full Topology LSAs ............................11 + 2.6. Hello Protocol ............................................12 + 3. Interface and Neighbor Data Structures .........................12 + 3.1. Changes to Interface Data Structure .......................12 + 3.2. New Configurable Interface Parameters .....................13 + 3.3. Changes to Neighbor Data Structure ........................15 + 4. Hello Protocol .................................................17 + 4.1. Sending Hello Packets .....................................17 + 4.2. Receiving Hello Packets ...................................20 + 4.3. Neighbor Acceptance Condition .............................24 + 5. MDR Selection Algorithm ........................................25 + 5.1. Phase 1: Creating the Neighbor Connectivity Matrix ........27 + 5.2. Phase 2: MDR Selection ....................................27 + 5.3. Phase 3: Backup MDR Selection .............................29 + 5.4. Phase 4: Parent Selection .................................29 + 5.5. Phase 5: Optional Selection of Non-Flooding MDRs ..........30 + + + +Ogier & Spagnolo Experimental [Page 2] + +RFC 5614 MANET Extension of OSPF August 2009 + + + 6. Interface State Machine ........................................31 + 6.1. Interface States ..........................................31 + 6.2. Events that Cause Interface State Changes .................31 + 6.3. Changes to Interface State Machine ........................32 + 7. Adjacency Maintenance ..........................................32 + 7.1. Changes to Neighbor State Machine .........................33 + 7.2. Whether to Become Adjacent ................................34 + 7.3. Whether to Eliminate an Adjacency .........................35 + 7.4. Sending Database Description Packets ......................35 + 7.5. Receiving Database Description Packets ....................36 + 8. Flooding Procedure .............................................37 + 8.1. LSA Forwarding Procedure ..................................38 + 8.2. Sending Link State Acknowledgments ........................41 + 8.3. Retransmitting LSAs .......................................42 + 8.4. Receiving Link State Acknowledgments ......................42 + 9. Router-LSAs ....................................................43 + 9.1. Routable Neighbors ........................................44 + 9.2. Backbone Neighbors ........................................45 + 9.3. Selected Advertised Neighbors .............................45 + 9.4. Originating Router-LSAs ...................................46 + 10. Calculating the Routing Table .................................47 + 11. Security Considerations .......................................49 + 12. IANA Considerations ...........................................50 + 13. Acknowledgments ...............................................51 + 14. Normative References ..........................................51 + 15. Informative References ........................................51 + Appendix A. Packet Formats .......................................52 + A.1. Options Field ............................................52 + A.2. Link-Local Signaling .....................................52 + A.3. Hello Packet DR and Backup DR Fields .....................57 + A.4. LSA Formats and Examples .................................57 + Appendix B. Detailed Algorithms for MDR/BMDR Selection ...........62 + B.1. Detailed Algorithm for Step 2.4 (MDR Selection) ..........62 + B.2. Detailed Algorithm for Step 3.2 (BMDR Selection) .........63 + Appendix C. Min-Cost LSA Algorithm ...............................65 + Appendix D. Non-Ackable LSAs for Periodic Flooding ...............68 + Appendix E. Simulation Results ...................................69 + + + + + + + + + + + + + + +Ogier & Spagnolo Experimental [Page 3] + +RFC 5614 MANET Extension of OSPF August 2009 + + +1. Introduction + + This document specifies an extension of OSPFv3 [RFC5340] to support a + new interface type for mobile ad hoc networks (MANETs), i.e., for + broadcast-capable, multihop wireless networks in which routers and + hosts can be mobile. Note that OSPFv3 is specified by describing the + modifications to OSPFv2 [RFC2328]. This MANET extension of OSPFv3 is + also applicable to non-mobile mesh networks using layer-3 routing. + This extension does not preclude the use of any existing OSPF + interface types, and is fully compatible with legacy OSPFv3 + implementations. + + Existing OSPF interface types do not perform adequately in MANETs, + due to scaling issues regarding the flooding protocol operation, + inability of the Designated Router election protocol to converge in + all scenarios, and large numbers of adjacencies when using a point- + to-multipoint interface type. + + The approach taken is to generalize the concept of an OSPF Designated + Router (DR) and Backup DR to multihop wireless networks, in order to + reduce overhead by reducing the number of routers that must flood new + LSAs and reducing the number of adjacencies. The generalized + (Backup) Designated Routers are called (Backup) MANET Designated + Routers (MDRs). The MDRs form a connected dominating set (CDS), and + the MDRs and Backup MDRs together form a biconnected CDS for + robustness (if the network itself is biconnected). By definition, + each router in the MANET either belongs to the CDS or is one hop away + from it. A distributed algorithm is used to select and dynamically + maintain the biconnected CDS. Adjacencies are established only + between (Backup) MDRs and a subset of their neighbors, thus resulting + in a dramatic reduction in the number of adjacencies in dense + networks, compared to the approach of forming adjacencies between all + neighbor pairs. The OSPF extension is called OSPF-MDR. + + Hello packets are modified, using OSPF link-local signaling (LLS; see + [RFC5613]), for two purposes: to provide neighbors with 2-hop + neighbor information that is required by the MDR selection algorithm, + and to allow differential Hellos that report only changes in neighbor + states. Differential Hellos can be sent more frequently without a + significant increase in overhead, in order to respond more quickly to + topology changes. + + Each MANET router advertises a subset of its MANET neighbors as + point-to-point links in its router-LSA. The choice of which + neighbors to advertise is flexible, allowing overhead to be reduced + by advertising less topology information. Options are specified for + originating router-LSAs that provide full or partial topology + information. + + + +Ogier & Spagnolo Experimental [Page 4] + +RFC 5614 MANET Extension of OSPF August 2009 + + + This document is organized as follows. Section 2 presents an + overview of OSPF-MDR, Section 3 presents the new interface and + neighbor data items that are required for the extension, Section 4 + describes the Hello protocol, including procedures for maintaining + the 2-hop neighbor information, Section 5 describes the MDR selection + algorithm, Section 6 describes changes to the Interface state + machine, Section 7 describes the procedures for forming adjacencies + and deciding which neighbors should become adjacent, Section 8 + describes the flooding procedure, Section 9 specifies the + requirements and options for the contents of router-LSAs, and Section + 10 describes changes in the calculation of the routing table. + + The appendices specify packet formats, detailed algorithms for the + MDR selection algorithm, an algorithm for the selection of a subset + of neighbors to advertise in the router-LSA to provide shortest-path + routing, a proposed option that uses non-ackable LSAs to provide + periodic flooding without the overhead of Link State Acknowledgments, + and simulation results that predict the performance of OSPF-MDR in + mobile networks with up to 200 nodes. Additional information and + resources for OSPF-MDR can be found at http://www.manet-routing.org. + +1.1. Terminology + + 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 [RFC2119]. + + In addition, this document uses the following terms: + + MANET Interface + A MANET Interface is a new OSPF interface type that supports + broadcast-capable, multihop wireless networks. Two neighboring + routers on a MANET interface may not be able to communicate + directly with each other. A neighboring router on a MANET + interface is called a MANET neighbor. MANET neighbors are + discovered dynamically using a modification of OSPF's Hello + protocol. + + MANET Router + A MANET Router is an OSPF router that has at least one MANET + interface. + + Differential Hello + A Differential Hello is a Hello packet that reduces the overhead + of sending full Hellos, by including only the Router IDs of + neighbors whose state changed recently. + + + + + +Ogier & Spagnolo Experimental [Page 5] + +RFC 5614 MANET Extension of OSPF August 2009 + + + 2-Hop Neighbor Information + This information specifies the bidirectional neighbors of each + neighbor. The modified Hello protocol provides each MANET router + with 2-hop neighbor information, which is used for selecting MDRs + and Backup MDRs. + + MANET Designated Router (MDR) + A MANET Designated Router is one of a set of routers responsible + for flooding new LSAs, and for determining the set of adjacencies + that must be formed. The set of MDRs forms a connected dominating + set and is a generalization of the DR found in broadcast networks. + Each router runs the MDR selection algorithm for each MANET + interface, to decide whether the router is an MDR, Backup MDR, or + neither for that interface. + + Backup MANET Designated Router (Backup MDR or BMDR) + A Backup MANET Designated Router is one of a set of routers + responsible for providing backup flooding when neighboring MDRs + fail. The set of MDRs and Backup MDRs forms a biconnected + dominating set. The Backup MDR is a generalization of the Backup + DR found in broadcast networks. + + MDR Other + A router is an MDR Other for a particular MANET interface if it is + neither an MDR nor a Backup MDR for that interface. + + Parent + Each router selects a Parent for each MANET interface. The Parent + of a non-MDR router will be a neighboring MDR if one exists. The + Parent of an MDR is always the router itself. Each non-MDR router + becomes adjacent with its Parent. The Router ID of the Parent is + advertised in the DR field of each Hello sent on the interface. + + Backup Parent + If the option of biconnected adjacencies is chosen, then each MDR + Other selects a Backup Parent, which will be a neighboring MDR or + BMDR if one exists that is not the Parent. The Backup Parent of a + BMDR is always the router itself. Each MDR Other becomes adjacent + with its Backup Parent if it exists. The Router ID of the Backup + Parent is advertised in the Backup DR field of each Hello sent on + the interface. + + Bidirectional Neighbor + A bidirectional neighbor is a neighboring router whose neighbor + state is 2-Way or greater. + + + + + + +Ogier & Spagnolo Experimental [Page 6] + +RFC 5614 MANET Extension of OSPF August 2009 + + + Routable Neighbor + A bidirectional MANET neighbor becomes routable if the SPF + calculation has produced a route to the neighbor and the neighbor + satisfies a quality condition. Once a neighbor becomes routable, + it remains routable as long as it remains bidirectional. Only + routable and Full neighbors can be used as next hops in the SPF + calculation, and can be included in the router-LSA originated by + the router. + + Non-Flooding MDR + A non-flooding MDR is an MDR that does not automatically flood + received LSAs back out the receiving interface, but performs + backup flooding like a BMDR. Some MDRs may declare themselves + non-flooding in order to reduce flooding overhead. + +2. Overview + + This section provides an overview of OSPF-MDR, including motivation + and rationale for some of the design choices. + + OSPF-MDR was motivated by the desire to extend OSPF to support + MANETs, while keeping the same design philosophy as OSPF and using + techniques that are similar to those of OSPF. For example, OSPF + reduces overhead in a broadcast network by electing a Designated + Router (DR) and Backup DR, and by having two neighboring routers form + an adjacency only if one of them is the DR or Backup DR. This idea + can be generalized to a multihop wireless network by forming a + spanning tree, with the edges of the tree being the adjacencies and + the interior (non-leaf) nodes of the tree being the generalized DRs, + called MANET Designated Routers (MDRs). + + To provide better robustness and fast response to topology changes, + it was decided that a router should decide whether it is an MDR based + only on local information that can be obtained from neighbors' + Hellos. The resulting set of adjacencies therefore does not always + form a tree globally, but appears to be a tree locally. Similarly, + the Backup DR can be generalized to Backup MDRs (BMDRs), to provide + robustness through biconnected redundancy. The set of MDRs forms a + connected dominating set (CDS), and the set of MDRs and BMDRs forms a + biconnected dominating set (if the network itself is biconnected). + + The following subsections provide an overview of each of the main + features of OSPF-MDR, starting with a summary of how MDRs, BMDRs, and + adjacencies are selected. + + + + + + + +Ogier & Spagnolo Experimental [Page 7] + +RFC 5614 MANET Extension of OSPF August 2009 + + +2.1. Selection of MDRs, BMDRs, Parents, and Adjacencies + + The MDR selection algorithm is distributed; each router selects + itself as an MDR, BMDR, or other router (called an "MDR Other") based + on information about its one-hop neighborhood, which is obtained from + Hello packets received from neighbors. Routers are ordered + lexicographically based on the tuple (RtrPri, MDR Level, RID), where + RtrPri is the Router Priority, MDR Level represents the current state + of the router (2 for an MDR, 1 for a BMDR, and 0 for an MDR Other), + and RID is the Router ID. Routers with lexicographically larger + values of (RtrPri, MDR Level, RID) are given preference for becoming + MDRs. + + The MDR selection algorithm can be summarized as follows. If the + router itself has a larger value of (RtrPri, MDR Level, RID) than all + of its neighbors, it selects itself as an MDR. Otherwise, let Rmax + denote the neighbor with the largest value of (RtrPri, MDR Level, + RID). The router then selects itself as an MDR unless each neighbor + can be reached from Rmax in at most k hops via neighbors that have a + larger value of (RtrPri, MDR Level, RID) than the router itself, + where k is the parameter MDRConstraint, whose default value is 3. + + This parameter serves to control the density of the MDR set, since + the MDR set need not be strictly minimal. + + Similarly, a router that does not select itself as an MDR will select + itself as a BMDR unless each neighbor can be reached from Rmax via + two node-disjoint paths, using as intermediate hops only neighbors + that have a larger value of (RtrPri, MDR Level, RID) than the router + itself. + + When a router selects itself as an MDR, it also decides which MDR + neighbors it should become adjacent with, to ensure that the set of + MDRs and the adjacencies between them form a connected backbone. + Each non-MDR router selects and becomes adjacent with an MDR neighbor + called its Parent, thus ensuring that all routers are connected to + the MDR backbone. + + If the option of biconnected adjacencies is chosen (AdjConnectivity = + 2), then additional adjacencies are selected to ensure that the set + of MDRs and BMDRs, and the adjacencies between them, form a + biconnected backbone. In this case, each MDR Other selects and + becomes adjacent with an MDR/BMDR neighbor called its Backup Parent, + in addition to its Parent. + + + + + + + +Ogier & Spagnolo Experimental [Page 8] + +RFC 5614 MANET Extension of OSPF August 2009 + + + OSPF-MDR also provides the option of full-topology adjacencies + (AdjConnectivity = 0). If this option is selected, then each router + forms an adjacency with each bidirectional neighbor. Although BMDR + selection is optional if AdjConnectivity is 0 or 1, it is recommended + since BMDRs improve robustness by providing backup flooding. + + Prioritizing routers according to (RtrPri, MDR Level, RID) allows + neighboring routers to agree on which routers should become an MDR, + and gives higher priority to existing MDRs, which increases the + lifetime of MDRs and the adjacencies between them. In addition, + Parents are selected to be existing adjacent neighbors whenever + possible, to avoid forming new adjacencies unless necessary. Once a + neighbor becomes adjacent, it remains adjacent as long as the + neighbor is bidirectional and either the neighbor or the router + itself is an MDR or BMDR (similar to OSPF). The above rules reduce + the rate at which new adjacencies are formed, which is important + since database exchange must be performed whenever a new adjacency is + formed. + +2.2. Flooding Procedure + + When an MDR receives a new link state advertisement (LSA) on a MANET + interface, it floods the LSA back out the receiving interface unless + it can be determined that such flooding is unnecessary (as specified + in Section 8.1). The router MAY delay the flooding of the LSA by a + small random amount of time (e.g., less than 100 ms). The delayed + flooding is useful for coalescing multiple LSAs in the same Link + State Update packet, and it can reduce the possibility of a collision + in case multiple MDRs received the same LSA at the same time. + However, such collisions are usually avoided with wireless MAC + protocols. + + When a Backup MDR receives a new LSA on a MANET interface, it waits a + short interval (BackupWaitInterval), and then floods the LSA only if + it has a neighbor that did not flood or acknowledge the LSA and is + not known to be a neighbor of another neighbor (of the Backup MDR) + that flooded the LSA. + + MDR Other routers never flood LSAs back out the receiving interface. + To exploit the broadcast nature of MANETs, a new LSA is processed + (and possibly forwarded) if it is received from any neighbor in state + 2-Way or greater. The flooding procedure also avoids redundant + forwarding of LSAs when multiple interfaces exist. + + + + + + + + +Ogier & Spagnolo Experimental [Page 9] + +RFC 5614 MANET Extension of OSPF August 2009 + + +2.3. Link State Acknowledgments + + All Link State Acknowledgment packets are multicast. An LSA is + acknowledged if it is a new LSA, or if it is a duplicate LSA received + as a unicast. (A duplicate LSA received as multicast is not + acknowledged.) An LSA that is flooded back out the same interface is + treated as an implicit acknowledgment. Link State Acknowledgments + may be delayed to allow coalescing multiple acknowledgments in the + same packet. The only exception is that (Backup) MDRs send a + multicast Link State Acknowledgment immediately when a duplicate LSA + is received as a unicast, in order to prevent additional + retransmissions. Only Link State Acknowledgments from adjacent + neighbors are processed, and retransmitted LSAs are sent (via + unicast) only to adjacent neighbors. + +2.4. Routable Neighbors + + In OSPF, a neighbor must typically be fully adjacent (in state Full) + for it to be used in the SPF calculation. An exception exists for an + OSPF broadcast network, to avoid requiring all pairs of routers in + such a network to form adjacencies, which would generate a large + amount of overhead. In such a network, a router can use a non- + adjacent neighbor as a next hop as long as both routers are fully + adjacent with the Designated Router. We define this neighbor + relationship as a "routable neighbor" and extend its usage to the + MANET interface type. + + A MANET neighbor becomes routable if it is bidirectional and the SPF + calculation has produced a route to the neighbor. (A flexible + quality condition may also be required.) Only routable and Full + neighbors can be used as next hops in the SPF calculation, and can be + included in the router-LSA originated by the router. The idea is + that if the SPF calculation has produced a route to the neighbor, + then it makes sense to take a "shortcut" and forward packets directly + to the neighbor. + + The routability condition is a generalization of the way that + neighbors on broadcast networks are treated in the SPF calculation. + The network-LSA of an OSPF broadcast network implies that a router + can use a non-adjacent neighbor as a next hop. But a network-LSA + cannot describe the general topology of a MANET, making it necessary + to explicitly include non-adjacent neighbors in the router-LSA. + Allowing only adjacent neighbors in LSAs would either result in + suboptimal routes or require a large number of adjacencies. + + + + + + + +Ogier & Spagnolo Experimental [Page 10] + +RFC 5614 MANET Extension of OSPF August 2009 + + +2.5. Partial and Full Topology LSAs + + OSPF-MDR allows routers to originate both full-topology LSAs, which + advertise links to all routable and Full neighbors, and partial- + topology LSAs, which advertise only a subset of such links. In a + dense network, partial-topology LSAs are typically much smaller than + full-topology LSAs, thus achieving better scalability. + + Each router advertises a subset of its neighbors as point-to-point + links in its router-LSA. The choice of which neighbors to advertise + is flexible. As a minimum requirement, each router must advertise a + minimum set of "backbone" neighbors in its router-LSA. An LSA that + includes only this minimum set of neighbors is called a minimal LSA + and corresponds to LSAFullness = 0. This choice results in the + minimum amount of LSA flooding overhead, but does not ensure routing + along shortest paths. However, it is useful for achieving + scalability to networks with a large number of nodes. + + At the other extreme, if LSAFullness = 4, then the router originates + a full-topology LSA, which includes all routable and Full neighbors. + + Setting LSAFullness to 1 results in min-cost LSAs, which provide + routing along shortest (minimum-cost) paths. Each router decides + which neighbors to include in its router-LSA based on 2-hop neighbor + information obtained from its neighbors' Hellos. Each router + includes in its LSA the minimum set of neighbors necessary to provide + a shortest path between each pair of its neighbors. + + Setting LSAFullness to 2 also provides shortest-path routing, but + allows the router to advertise additional neighbors to provide + redundant routes. + + Setting LSAFullness to 3 results in MDR full LSAs, causing each MDR + to originate a full-topology LSA while other routers originate + minimal LSAs. This choice does not provide routing along shortest + paths, but simulations have shown that it provides routing along + nearly shortest paths with relatively low overhead. + + The above LSA options are interoperable with each other, because they + all require the router-LSA to include a minimum set of neighbors, and + because the construction of the router-LSA (described in Section 9.4) + ensures that the router-LSAs originated by different routers are + consistent. Routing along shortest paths is provided if and only if + every router selects LSAFullness to be 1, 2, or 4. + + + + + + + +Ogier & Spagnolo Experimental [Page 11] + +RFC 5614 MANET Extension of OSPF August 2009 + + +2.6. Hello Protocol + + OSPF-MDR uses the same Hello format as OSPFv3, but appends additional + information to Hello packets using link-local signaling (LLS), in + order to indicate the set of bidirectional neighbors and other + information that is used by the MDR selection algorithm and the min- + cost LSA algorithm. In addition to full Hellos, which include the + same set of neighbor IDs as OSPFv3 Hellos, OSPF-MDR allows the use of + differential Hellos, which include only the IDs of neighbors whose + state (or other information) has recently changed (within the last + HelloRepeatCount Hellos). + + Hellos are sent every HelloInterval seconds. Full Hellos are sent + every 2HopRefresh Hellos, and differential Hellos are sent at all + other times. For example, if 2HopRefresh is equal to 3, then every + third Hello is a full Hello. The default value of 2HopRefresh is 1; + i.e., the default is to send only full Hellos. The default value for + HelloInterval is 2 seconds. Differential Hellos are used to reduce + overhead and to allow Hellos to be sent more frequently, for faster + reaction to topology changes. + +3. Interface and Neighbor Data Structures + +3.1. Changes to Interface Data Structure + + The following modified or new data items are required for the + Interface Data Structure of a MANET interface: + + Type + A router that implements this extension can have one or more + interfaces of type MANET, in addition to the OSPF interface types + defined in [RFC2328]. + + State + The possible states for a MANET interface are the same as for a + broadcast interface. However, the DR and Backup states now imply + that the router is an MDR or Backup MDR, respectively. + + MDR Level + The MDR Level is equal to MDR (value 2) if the router is an MDR, + Backup MDR (value 1) if the router is a Backup MDR, and MDR Other + (value 0) otherwise. The MDR Level is used by the MDR selection + algorithm. + + Parent + The Parent replaces the Designated Router (DR) data item of OSPF. + Each router selects a Parent as described in Section 5.4. The + Parent of an MDR is the router itself, and the Parent of a non-MDR + + + +Ogier & Spagnolo Experimental [Page 12] + +RFC 5614 MANET Extension of OSPF August 2009 + + + router will be a neighboring MDR, if one exists. The Parent is + initialized to 0.0.0.0, indicating the lack of a Parent. Each + router advertises the Router ID of its Parent in the DR field of + each Hello sent on the interface. + + Backup Parent + The Backup Parent replaces the Backup Designated Router data item + of OSPF. The Backup Parent of a BMDR is the router itself. If + the option of biconnected adjacencies is chosen, then each MDR + Other selects a Backup Parent, which will be a neighboring + MDR/BMDR if one exists that is not the Parent. The Backup Parent + is initialized to 0.0.0.0, indicating the lack of a Backup Parent. + Each router advertises the Router ID of its Backup Parent in the + Backup DR field of each Hello sent on the interface. + + Router Priority + An 8-bit unsigned integer. A router with a larger Router Priority + is more likely to be selected as an MDR. The Router Priority for + a MANET interface can be changed dynamically based on any + criteria, including bandwidth capacity, willingness to be a relay + (which can depend on battery life, for example), number of + neighbors (degree), and neighbor stability. A router that has + been a (Backup) MDR for a certain amount of time can reduce its + Router Priority so that the burden of being a (Backup) MDR can be + shared among all routers. If the Router Priority for a MANET + interface is changed, then the interface variable + MDRNeighborChange must be set. + + Hello Sequence Number (HSN) + The 16-bit sequence number carried by the MDR-Hello TLV. The HSN + is incremented by 1 (modulo 2^16) every time a Hello packet is + sent on the interface. + + MDRNeighborChange + A single-bit variable set to 1 if a neighbor change has occurred + that requires the MDR selection algorithm to be executed. + +3.2. New Configurable Interface Parameters + + The following new configurable interface parameters are required for + a MANET interface. The default values for HelloInterval, + RouterDeadInterval, and RxmtInterval for a MANET interface are 2, 6, + and 7 seconds, respectively. + + The default configuration for OSPF-MDR uses uniconnected adjacencies + (AdjConnectivity = 1) and partial-topology LSAs that provide + shortest-path routing (LSAFullness = 1). This is the most scalable + configuration that provides shortest-path routing. Other + + + +Ogier & Spagnolo Experimental [Page 13] + +RFC 5614 MANET Extension of OSPF August 2009 + + + configurations may be preferable in special circumstances. For + example, setting LSAFullness to 4 provides full-topology LSAs, and + setting LSAFullness to 0 provides minimal LSAs that minimize overhead + but do not ensure shortest-path routing. Setting AdjConnectivity to + 2 may improve robustness by providing a biconnected adjacency + subgraph, and setting AdjConnectivity to 0 results in full-topology + adjacencies. + + All possible configurations of the new interface parameters are + functional, except that if AdjConnectivity is 0 (full-topology + adjacencies), then LSAFullness must be 1, 2, or 4 (see Section 9.3). + + Differential Hellos should be used to reduce the size of Hello + packets when the average number of neighbors is large (e.g., greater + than 50). Differential Hellos are obtained by setting the parameter + 2HopRefresh to an integer greater than 1, with the recommended value + being 3. Good performance in simulated mobile networks with up to + 160 nodes has been obtained using the default configuration with + differential Hellos. Good performance in simulated mobile networks + with up to 200 nodes has been obtained using the same configuration + except with minimal LSAs (LSAFullness = 0). Simulation results are + presented in Appendix E. + + Although all routers should preferably choose the same values for the + new configurable interface parameters, this is not required. OSPF- + MDR was carefully designed so that correct interoperation is achieved + even if each router sets these parameters independently of the other + routers. + + AdjConnectivity + If equal to the default value of 1, then the set of adjacencies + forms a (uni)connected graph. If equal to the optional value of + 2, then the set of adjacencies forms a biconnected graph. If + AdjConnectivity is 0, then adjacency reduction is not used; i.e., + the router becomes adjacent with all of its neighbors. + + MDRConstraint + A parameter of the MDR selection algorithm, which affects the + number of MDRs selected and must be an integer greater than or + equal to 2. The default value of 3 results in nearly the minimum + number of MDRs. Values larger than 3 result in slightly fewer + MDRs, and the value 2 results in a larger number of MDRs. + + BackupWaitInterval + The number of seconds that a Backup MDR must wait after receiving + a new LSA before it decides whether to flood the LSA. The default + value is 0.5 second. + + + + +Ogier & Spagnolo Experimental [Page 14] + +RFC 5614 MANET Extension of OSPF August 2009 + + + AckInterval + The interval between Link State Acknowledgment packets when only + delayed acknowledgments need to be sent. AckInterval MUST be less + than RxmtInterval, and SHOULD NOT be larger than 1 second. The + default value is 1 second. + + LSAFullness + Determines which neighbors a router should advertise in its + router-LSA. The value 0 results in minimal LSAs that include only + "backbone" neighbors. The values 1 and 2 result in partial- + topology LSAs that provide shortest-path routing, with the value 2 + providing redundant routes. The value 3 results in MDRs + originating full-topology LSAs and other routers originating + minimal LSAs. The value 4 results in all routers originating + full-topology LSAs. The default value is 1. + + 2HopRefresh + One out of every 2HopRefresh Hellos sent on the interface must be + a full Hello. All other Hellos are differential. The default + value is 1; i.e., the default is to send only full Hellos. If + differential Hellos are used, the recommended value of 2HopRefresh + is 3. + + HelloRepeatCount + The number of consecutive Hellos in which a neighbor must be + included when its state changes, if differential Hellos are used. + This parameter must be set to 3. + +3.3. Changes to Neighbor Data Structure + + The neighbor states are the same as for OSPF. However, the data for + a MANET neighbor that has transitioned to the Down state must be + maintained for at least HelloInterval * HelloRepeatCount seconds, to + allow the state change to be reported in differential Hellos. The + following new data items are required for the Neighbor Data Structure + of a neighbor on a MANET interface. + + Neighbor Hello Sequence Number (NHSN) + The Hello sequence number contained in the last Hello received + from the neighbor. + + A-bit + The A-bit copied from the MDR-Hello TLV of the last Hello received + from the neighbor. This bit is 1 if the neighbor is using full- + topology adjacencies, i.e., is not using adjacency reduction. + + + + + + +Ogier & Spagnolo Experimental [Page 15] + +RFC 5614 MANET Extension of OSPF August 2009 + + + FullHelloRcvd + A single-bit variable equal to 1 if a full Hello has been received + from the neighbor. + + Neighbor's MDR Level + The MDR Level of the neighbor, based on the DR and Backup DR + fields of the last Hello packet received from the neighbor or from + the MDR-DD TLV in a Database Description (DD) packet received from + the neighbor. + + Neighbor's Parent + The neighbor's choice for Parent, obtained from the DR field of + the last Hello packet received from the neighbor or from the MDR- + DD TLV in a DD packet received from the neighbor. + + Neighbor's Backup Parent + The neighbor's choice for Backup Parent, obtained from the Backup + DR field of the last Hello packet received from the neighbor or + from the MDR-DD TLV in a DD packet received from the neighbor. + + Child + A single-bit variable equal to 1 if the neighbor is a child, i.e., + if the neighbor has selected the router as a (Backup) Parent. + + Dependent Neighbor + A single-bit variable equal to 1 if the neighbor is a Dependent + Neighbor, which is decided by the MDR selection algorithm. Each + MDR/BMDR router becomes adjacent with its Dependent Neighbors + (which are also MDR/BMDR routers) to form a connected backbone. + The set of all Dependent Neighbors on a MANET interface is called + the Dependent Neighbor Set (DNS) for the interface. + + Dependent Selector + A single-bit variable equal to 1 if the neighbor has selected the + router to be dependent. + + Selected Advertised Neighbor (SAN) + A single-bit variable equal to 1 if the neighbor is a Selected + Advertised Neighbor. Selected Advertised Neighbors are neighbors + that the router has selected to be included in the router-LSA, + along with other neighbors that are required to be included. The + set of all Selected Advertised Neighbors on a MANET interface is + called the Selected Advertised Neighbor Set (SANS) for the + interface. + + Routable + A single-bit variable equal to 1 if the neighbor is routable. + + + + +Ogier & Spagnolo Experimental [Page 16] + +RFC 5614 MANET Extension of OSPF August 2009 + + + Neighbor's Bidirectional Neighbor Set (BNS) + The neighbor's set of bidirectional neighbors, which is updated + when a Hello is received from the neighbor. + + Neighbor's Dependent Neighbor Set (DNS) + The neighbor's set of Dependent Neighbors, which is updated when a + Hello is received from the neighbor. + + Neighbor's Selected Advertised Neighbor Set (SANS) + The neighbor's set of Selected Advertised Neighbors, which is + updated when a Hello is received from the neighbor. + + Neighbor's Link Metrics + The link metric for each of the neighbor's bidirectional + neighbors, obtained from the Metric TLV appended to Hello packets. + +4. Hello Protocol + + The MANET interface utilizes Hellos for neighbor discovery and for + enabling neighbors to learn 2-hop neighbor information. The protocol + is flexible because it allows the use of full or differential Hellos. + Full Hellos list all neighbors on the interface that are in state + Init or greater, as in OSPFv3, whereas differential Hellos list only + neighbors whose status as a bidirectional neighbor, Dependent + Neighbor, or Selected Advertised Neighbor has recently changed. + Differential Hellos are used to reduce overhead, and they allow + Hellos to be sent more frequently (for faster reaction to topology + changes). If differential Hellos are used, full Hellos are sent less + frequently to ensure that all neighbors have current 2-hop neighbor + information. + +4.1. Sending Hello Packets + + Hello packets are sent according to [RFC5340], Section 4.2.1.1, and + [RFC2328], Section 9.5, with the following MANET-specific + specifications beginning after paragraph 3 of Section 9.5. The Hello + packet format is defined in [RFC5340], Section A.3.2, except for the + ordering of the Neighbor IDs and the meaning of the DR and Backup DR + fields as described below. + + Similar to [RFC2328], the DR and Backup DR fields indicate whether + the router is an MDR or Backup MDR. If the router is an MDR, then + the DR field is the router's own Router ID, and if the router is a + Backup MDR, then the Backup DR field is the router's own Router ID. + These fields are also used to advertise the router's Parent and + Backup Parent, as specified in Section A.3 and Section 5.4. + + + + + +Ogier & Spagnolo Experimental [Page 17] + +RFC 5614 MANET Extension of OSPF August 2009 + + + Hellos are sent every HelloInterval seconds. Full Hellos are sent + every 2HopRefresh Hellos, and differential Hellos are sent at all + other times. For example, if 2HopRefresh is equal to 3, then every + third Hello is a full Hello. If 2HopRefresh is set to 1, then all + Hellos are full (the default). + + The neighbor IDs included in the body of each Hello are divided into + the following five disjoint lists of neighbors (some of which may be + empty), and must appear in the following order: + + List 1. Neighbors whose state recently changed to Down (included only + in differential Hellos). + + List 2. Neighbors in state Init. + + List 3. Dependent Neighbors. + + List 4. Selected Advertised Neighbors. + + List 5. Unselected bidirectional neighbors, defined as bidirectional + neighbors that are neither Dependent nor Selected Advertised + Neighbors. + + Note that all neighbors in Lists 3 through 5 are bidirectional + neighbors. These lists are used to update the neighbor's + Bidirectional Neighbor Set (BNS), Dependent Neighbor Set (DNS), and + Selected Advertised Neighbor Set (SANS) when a Hello is received. + + Note that the above five lists are disjoint, so each neighbor can + appear in at most one list. Also note that some or all of the five + lists can be empty. + + Link-local signaling (LLS) is used to append up to two TLVs to each + MANET Hello packet. The format for LLS is given in Section A.2. The + MDR-Hello TLV is appended to each (full or differential) MANET Hello + packet. It indicates whether the Hello is full or differential, and + gives the Hello Sequence Number (HSN) and the number of neighbor IDs + in each of Lists 1 through 4 defined above. The size of List 5 is + then implied by the packet length field of the Hello. The format of + the MDR-Hello TLV is given in Section A.2.3. + + In both full and differential Hellos, the appended MDR-Hello TLV is + built as follows. + + o The Sequence Number field is set to the current HSN for the + interface; the HSN is then incremented (modulo 2^16). + + + + + +Ogier & Spagnolo Experimental [Page 18] + +RFC 5614 MANET Extension of OSPF August 2009 + + + o The D-bit of the MDR-Hello TLV is set to 1 for a differential + Hello and 0 for a full Hello. + + o The A-bit of the MDR-Hello TLV is set to 1 if AdjConnectivity is 0 + (the router is using full-topology adjacencies); otherwise, it is + set to 0. + + o The N1, N2, N3, and N4 fields are set to the number of neighbor + IDs in the body of the Hello that are in List 1, List 2, List 3, + and List 4, respectively. (N1 is always zero in a full Hello.) + + The MDR-Metric TLV (or Metric TLV) advertises the link cost to each + bidirectional neighbor on the interface, to allow the selection of + neighbors to include in partial-topology LSAs. If LSAFullness is 1 + or 2, a Metric TLV must be appended to each MANET Hello packet unless + all link costs are 1. The format of the Metric TLV is given in + Section A.2.5. The I bit of the Metric TLV can be set to 0 or 1. If + the I bit is set to 0, then the Metric TLV does not contain neighbor + IDs, and contains the metric for each bidirectional neighbor listed + in the (full or differential) Hello, in the same order. If the I bit + is set to 1, then the Metric TLV includes the neighbor ID and metric + for each bidirectional neighbor listed in the Hello whose metric is + not equal to the Default Metric field of the TLV. + + The I bit should be chosen to minimize the size of the Metric TLV. + This can be achieved by choosing the I bit to be 1 if and only if the + number of bidirectional neighbors listed in the Hello whose metric + differs from the Default Metric field is less than 1/3 of the total + number of bidirectional neighbors listed in the Hello. + + For example, if all neighbors have the same metric, then the I bit + should be set to 1, with the Default Metric equal to this metric, + avoiding the need to include neighbor IDs and corresponding metrics + in the TLV. At the other extreme, if all neighbors have different + metrics, then the I bit should be set to 0 to avoid listing the same + neighbor IDs in both the body of the Hello and the Metric TLV. + + In both full and differential Hello packets, the L bit is set in the + Hello's option field to indicate LLS. + +4.1.1. Full Hello Packet + + In a full Hello, the neighbor ID list includes all neighbors on the + interface that are in state Init or greater, in the order described + above. The MDR-Hello TLV is built as described above. If a Metric + TLV is appended, it is built as specified in Section A.2.5. + + + + + +Ogier & Spagnolo Experimental [Page 19] + +RFC 5614 MANET Extension of OSPF August 2009 + + +4.1.2. Differential Hello Packet + + In a differential Hello, the five neighbor ID lists defined in + Section 4.1 are populated as follows: + + List 1 includes each neighbor in state Down that has not yet been + included in HelloRepeatCount Hellos since transitioning to this + state. + + List 2 includes each neighbor in state Init that has not yet been + included in HelloRepeatCount Hellos since transitioning to this + state. + + List 3 includes each Dependent Neighbor that has not yet been + included in HelloRepeatCount Hellos since becoming a Dependent + Neighbor. + + List 4 includes each Selected Advertised Neighbor that has not yet + been included in HelloRepeatCount Hellos since becoming a Selected + Advertised Neighbor. + + List 5 includes each unselected bidirectional neighbor (defined in + Section 4.1) that has not yet been included in HelloRepeatCount + Hellos since becoming an unselected bidirectional neighbor. + + In addition, a bidirectional neighbor must be included (in the + appropriate list) if the neighbor's BNS does not include the router + (indicating that the neighbor does not consider the router to be + bidirectional). + + If a Metric TLV is appended to the Hello, then a bidirectional + neighbor must be included (in the appropriate list) if it has not yet + been included in HelloRepeatCount Hellos since its metric last + changed. + +4.2. Receiving Hello Packets + + A Hello packet received on a MANET interface is processed as + described in [RFC5340], Section 4.2.2.1, and the first two paragraphs + of [RFC2328], Section 10.5, followed by the processing specified + below. + + The source of a received Hello packet is identified by the Router ID + found in the Hello's OSPF packet header. If a matching neighbor + cannot be found in the interface's data structure, one is created + + + + + + +Ogier & Spagnolo Experimental [Page 20] + +RFC 5614 MANET Extension of OSPF August 2009 + + + with the Neighbor ID set to the Router ID found in the OSPF packet + header, the state initialized to Down, all MANET-specific neighbor + variables (specified in Section 3.3) initialized to zero, and the + neighbor's DNS, SANS, and BNS initialized to empty sets. + + The neighbor structure's Router Priority is set to the value of the + corresponding field in the received Hello packet. The Neighbor's + Parent is set to the value of the DR field, and the Neighbor's Backup + Parent is set to the value of the Backup DR field. + + Now the rest of the Hello Packet is examined, generating events to be + given to the neighbor and interface state machines. These state + machines are specified to be either executed or scheduled (see + [RFC2328], Section 4.4, "Tasking support"). For example, by + specifying below that the neighbor state machine be executed in line, + several neighbor state transitions may be affected by a single + received Hello. + + o If the L bit in the options field is not set, then an error has + occurred and the Hello is discarded. + + o If the LLS contains an MDR-Hello TLV, the neighbor state machine + is executed with the event HelloReceived. Otherwise, an error has + occurred and the Hello is discarded. + + o The Hello Sequence Number and the A-bit in the MDR-Hello TLV are + copied to the neighbor's data structure. + + o The DR and Backup DR fields are processed as follows. + + (1) If the DR field is equal to the neighbor's Router ID, set the + neighbor's MDR Level to MDR. + + (2) Else if the Backup DR field is equal to the neighbor's Router + ID, set the neighbor's MDR Level to Backup MDR. + + (3) Else, set the neighbor's MDR Level to MDR Other and set the + neighbor's Dependent Neighbor variable to 0. (Only MDR/BMDR + neighbors can be Dependent.) + + (4) If the DR or Backup DR field is equal to the router's own + Router ID, set the neighbor's Child variable to 1; otherwise, + set it to 0. + + The neighbor ID list of the Hello is divided as follows into the five + lists defined in Section 4.1, where N1, N2, N3, and N4 are obtained + from the corresponding fields of the MDR-Hello TLV. List 1 is + defined to be the first N1 neighbor IDs, List 2 is defined to be the + + + +Ogier & Spagnolo Experimental [Page 21] + +RFC 5614 MANET Extension of OSPF August 2009 + + + next N2 neighbor IDs, List 3 is defined to be the next N3 neighbor + IDs, List 4 is defined to be the next N4 neighbor IDs, and List 5 is + defined to be the remaining neighbor IDs in the Hello. + + Further processing of the Hello depends on whether it is full or + differential, which is indicated by the value of the D-bit of the + MDR-Hello TLV. + +4.2.1. Full Hello Packet + + If the received Hello is full (the D-bit of the MDR-Hello TLV is 0), + the following steps are performed: + + o If the N1 field of the MDR-Hello TLV is not zero, then an error + has occurred and the Hello is discarded. Otherwise, set + FullHelloRcvd to 1. + + o In the neighbor structure, modify the neighbor's DNS to equal the + set of neighbor IDs in the Hello's List 3, modify the neighbor's + SANS to equal the set of neighbor IDs in the Hello's List 4, and + modify the neighbor's BNS to equal the set of neighbor IDs in the + union of Lists 3, 4, and 5. + + o If the router itself appears in the Hello's neighbor ID list, the + neighbor state machine is executed with the event 2-WayReceived + after the Hello is processed. Otherwise, the neighbor state + machine is executed with the event 1-WayReceived after the Hello + is processed. + +4.2.2. Differential Hello Packet + + If the received Hello is differential (the D-bit of the MDR-Hello TLV + is 1), the following steps are performed: + + (1) For each neighbor ID in List 1 or List 2 of the Hello: + + o Remove the neighbor ID from the neighbor's DNS, SANS, and BNS, + if it belongs to the neighbor set. + + (2) For each neighbor ID in List 3 of the Hello: + + o Add the neighbor ID to the neighbor's DNS and BNS, if it does + not belong to the neighbor set. + + o Remove the neighbor ID from the neighbor's SANS, if it belongs + to the neighbor set. + + (3) For each neighbor ID in List 4 of the Hello: + + + +Ogier & Spagnolo Experimental [Page 22] + +RFC 5614 MANET Extension of OSPF August 2009 + + + o Add the neighbor ID to the neighbor's SANS and BNS, if it does + not belong to the neighbor set. + + o Remove the neighbor ID from the neighbor's DNS, if it belongs + to the neighbor set. + + (4) For each neighbor ID in List 5 of the Hello: + + o Add the neighbor ID to the neighbor's BNS, if it does not + belong to the neighbor set. + + o Remove the neighbor ID from the neighbor's DNS and SANS, if it + belongs to the neighbor set. + + (5) If the router's own RID appears in List 1, execute the neighbor + state machine with the event 1-WayReceived after the Hello is + processed. + + (6) If the router's own RID appears in List 2, 3, 4, or 5, execute + the neighbor state machine with the event 2-WayReceived after the + Hello is processed. + + (7) If the router's own RID does not appear in the Hello's neighbor + ID list, and the neighbor state is 2-Way or greater, and the + Hello Sequence Number is less than or equal to the previous + sequence number plus HelloRepeatCount, then the neighbor state + machine is executed with the event 2-WayReceived after the Hello + is processed (the state does not change). + + (8) If 2-WayReceived is not executed, then 1-WayReceived is executed + after the Hello is processed. + +4.2.3. Additional Processing for Both Hello Types + + The following applies to both full and differential Hellos. + + If the router itself belongs to the neighbor's DNS, the neighbor's + Dependent Selector variable is set to 1; otherwise, it is set to 0. + + The receiving interface's MDRNeighborChange variable is set to 1 if + any of the following changes occurred as a result of processing the + Hello: + + o The neighbor's state changed from less than 2-Way to 2-Way or + greater, or vice versa. + + + + + + +Ogier & Spagnolo Experimental [Page 23] + +RFC 5614 MANET Extension of OSPF August 2009 + + + o The neighbor is bidirectional and any of the following neighbor + variables has changed: MDR Level, Router Priority, FullHelloRcvd, + and Bidirectional Neighbor Set (BNS). + + The neighbor state machine is scheduled with the event AdjOK? if any + of the following changes occurred as a result of processing the + Hello: + + o The neighbor's state changed from less than 2-Way to 2-Way or + greater. + + o The neighbor is bidirectional and its MDR Level has changed, or + its Child variable or Dependent Selector variable has changed from + 0 to 1. + + If the LLS contains a Metric TLV, it is processed by updating the + neighbor's link metrics according to the format of the Metric TLV + specified in Section A.2.5. If the LLS does not contain a Metric TLV + and LSAFullness is 1 or 2, the metric for each of the neighbor's + links is set to 1. + +4.3. Neighbor Acceptance Condition + + In wireless networks, a single Hello can be received from a neighbor + with which a poor connection exists, e.g., because the neighbor is + almost out of range. To avoid accepting poor-quality neighbors, and + to employ hysteresis, a router may require that a stricter condition + be satisfied before changing the state of a MANET neighbor from Down + to Init or greater. This condition is called the "neighbor + acceptance condition", which by default is the reception of a single + Hello or DD packet. For example, the neighbor acceptance condition + may require that 2 consecutive Hellos be received from a neighbor + before changing the neighbor's state from Down to Init. Other + possible conditions include the reception of 3 consecutive Hellos, or + the reception of 2 of the last 3 Hellos. The neighbor acceptance + condition may also impose thresholds on other measurements such as + received signal strength. + + The neighbor state transition for state Down and event HelloReceived + is thus modified (see Section 7.1) to depend on the neighbor + acceptance condition. + + + + + + + + + + +Ogier & Spagnolo Experimental [Page 24] + +RFC 5614 MANET Extension of OSPF August 2009 + + +5. MDR Selection Algorithm + + This section describes the MDR selection algorithm, which is run for + each MANET interface to determine whether the router is an MDR, + Backup MDR, or MDR Other for that interface. The algorithm also + selects the Dependent Neighbors and the (Backup) Parent, which are + used to decide which neighbors should become adjacent (see Section + 7.2). + + The MDR selection algorithm must be executed just before sending a + Hello if the MDRNeighborChange bit is set for the interface. The + algorithm SHOULD also be executed whenever a bidirectional neighbor + transitions to less than 2-Way, and MAY be executed at other times + when the MDRNeighborChange bit is set. The bit is cleared after the + algorithm is executed. + + To simplify the implementation, the MDR selection algorithm MAY be + executed periodically just before sending each Hello, to avoid having + to determine when the MDRNeighborChange bit should be set. After + running the MDR selection algorithm, the AdjOK? event may be invoked + for some or all neighbors as specified in Section 7. + + The purpose of the MDRs is to provide a minimal set of relays for + flooding LSAs, and the purpose of the Backup MDRs is to provide + backup relays to flood LSAs when flooding by MDRs does not succeed. + The set of MDRs forms a CDS, and the set of MDRs and Backup MDRs + forms a biconnected CDS (if the network itself is biconnected). + + Each MDR selects and becomes adjacent with a subset of its MDR + neighbors, called Dependent Neighbors, forming a connected backbone. + Each non-MDR router connects to this backbone by selecting and + becoming adjacent with an MDR neighbor called its Parent. Each MDR + selects itself as Parent, to inform neighbors that it is an MDR. + + If AdjConnectivity = 2, then each (Backup) MDR selects and becomes + adjacent with additional (Backup) MDR neighbors to form a biconnected + backbone, and each MDR Other selects and becomes adjacent with a + second (Backup) MDR neighbor called its Backup Parent, thus becoming + connected to the backbone via two adjacencies. Each BMDR selects + itself as Backup Parent, to inform neighbors that it is a BMDR. + + The MDR selection algorithm is a distributed CDS algorithm that uses + 2-hop neighbor information obtained from Hellos. More specifically, + it uses as inputs the set of bidirectional neighbors (in state 2-Way + or greater), the triplet (Router Priority, MDR Level, Router ID) for + each such neighbor and for the router itself, and the neighbor + + + + + +Ogier & Spagnolo Experimental [Page 25] + +RFC 5614 MANET Extension of OSPF August 2009 + + + variables Bidirectional Neighbor Set (BNS) and FullHelloRcvd for each + such neighbor. The MDR selection algorithm can be implemented in + O(d^2) time, where d is the number of neighbors. + + The above triplet will be abbreviated as (RtrPri, MDR Level, RID). + The triplet (RtrPri, MDR Level, RID) is said to be larger for Router + A than for Router B if the triplet for Router A is lexicographically + greater than the triplet for Router B. Routers that have larger + values of this triplet are preferred for selection as an MDR. The + algorithm therefore prefers routers that are already MDRs, resulting + in a longer average MDR lifetime. + + The MDR selection algorithm consists of five phases, the last of + which is optional. Phase 1 creates the neighbor connectivity matrix + for the interface, which determines which pairs of neighbors are + neighbors of each other. Phase 2 decides whether the calculating + router is an MDR, and which MDR neighbors are Dependent. Phase 3 + decides whether the calculating router is a Backup MDR and, if + AdjConnectivity = 2, which additional MDR/BMDR neighbors are + Dependent. Phase 4 selects the Parent and Backup Parent. + + The algorithm simplifies considerably if AdjConnectivity is 0 (full- + topology adjacencies). In this case, the set of Dependent Neighbors + is empty and MDR Other routers need not select Parents. Also, Phase + 3 (BMDR selection) is not required if AdjConnectivity is 0 or 1. + However, Phase 3 MUST be executed if AdjConnectivity is 2, and SHOULD + be executed if AdjConnectivity is 0 or 1, since BMDRs improve + robustness by providing backup flooding. + + A router that has selected itself as an MDR in Phase 2 MAY execute + Phase 5 to possibly declare itself a non-flooding MDR. A non- + flooding MDR is the same as a flooding MDR except that it does not + automatically flood received LSAs back out the receiving interface, + because it has determined that neighboring MDRs are sufficient to + flood the LSA to all neighbors. Instead, a non-flooding MDR performs + backup flooding just like a BMDR. A non-flooding MDR maintains its + MDR level (rather than being demoted to a BMDR) in order to maximize + the stability of adjacencies. (The decision to form an adjacency + does not depend on whether an MDR is non-flooding.) By having MDRs + declare themselves to be non-flooding when possible, flooding + overhead is reduced. The resulting reduction in flooding overhead + can be dramatic for certain regular topologies, but has been found to + be less than 15% for random topologies. + + The following subsections describe the MDR selection algorithm, which + is applied independently to each MANET interface. For convenience, + the term "bi-neighbor" will be used as an abbreviation for + "bidirectional neighbor". + + + +Ogier & Spagnolo Experimental [Page 26] + +RFC 5614 MANET Extension of OSPF August 2009 + + +5.1. Phase 1: Creating the Neighbor Connectivity Matrix + + Phase 1 creates the neighbor connectivity matrix (NCM) for the + interface. The NCM is a symmetric matrix that defines a topology + graph for the set of bi-neighbors on the interface. The NCM assigns + a value of 0 or 1 for each pair of bi-neighbors; a value of 1 + indicates that the neighbors are assumed to be bi-neighbors of each + other in the MDR selection algorithm. Letting i denote the router + itself, NCM(i,j) and NCM(j,i) are set to 1 for each bi-neighbor j. + The value of the matrix is set as follows for each pair of bi- + neighbors j and k on the interface. + + (1.1) If FullHelloRcvd is 1 for both neighbors j and k: NCM(j,k) = + NCM(k,j) is 1 only if j belongs to the BNS of neighbor k and k + belongs to the BNS of neighbor j. + + (1.2) If FullHelloRcvd is 1 for neighbor j and is 0 for neighbor k: + NCM(j,k) = NCM(k,j) is 1 only if k belongs to the BNS of + neighbor j. + + (1.3) If FullHelloRcvd is 0 for both neighbors j and k: NCM(j,k) = + NCM(k,j) = 0. + + In Step 1.1 above, two neighbors are considered to be bi-neighbors of + each other only if they both agree that the other router is a bi- + neighbor. This provides faster response to the failure of a link + between two neighbors, since it is likely that one router will detect + the failure before the other router. In Step 1.2 above, only + neighbor j has reported its full BNS, so neighbor j is believed in + deciding whether j and k are bi-neighbors of each other. As Step 1.3 + indicates, two neighbors are assumed not to be bi-neighbors of each + other if neither neighbor has reported its full BNS. + +5.2. Phase 2: MDR Selection + + Phase 2 depends on the parameter MDRConstraint, which affects the + number of MDRs selected. The default value of 3 results in nearly + the minimum number of MDRs, while the value 2 results in a larger + number of MDRs. If AdjConnectivity = 0 (full-topology adjacencies), + then the following steps are modified in that Dependent Neighbors are + not selected. + + (2.1) The set of Dependent Neighbors is initialized to be empty. + + + + + + + + +Ogier & Spagnolo Experimental [Page 27] + +RFC 5614 MANET Extension of OSPF August 2009 + + + (2.2) If the router has a larger value of (RtrPri, MDR Level, RID) + than all of its bi-neighbors, the router selects itself as an + MDR; selects all of its MDR bi-neighbors as Dependent + Neighbors; if AdjConnectivity = 2, selects all of its BMDR bi- + neighbors as Dependent Neighbors; then proceeds to Phase 4. + + (2.3) Let Rmax be the bi-neighbor with the largest value of (RtrPri, + MDR Level, RID). + + (2.4) Using NCM to determine the connectivity of bi-neighbors, + compute the minimum number of hops, denoted hops(u), from Rmax + to each other bi-neighbor u, using only intermediate nodes that + are bi-neighbors with a larger value of (RtrPri, MDR Level, + RID) than the router itself. If no such path from Rmax to u + exists, then hops(u) equals infinity. (See Appendix B for a + detailed algorithm using breadth-first search.) + + (2.5) If hops(u) is at most MDRConstraint for each bi-neighbor u, the + router selects no Dependent Neighbors, and sets its MDR Level + as follows: If the MDR Level is currently MDR, then it is + changed to BMDR if Phase 3 will be executed and to MDR Other if + Phase 3 will not be executed. Otherwise, the MDR Level is not + changed. + + (2.6) Else, the router sets its MDR Level to MDR and selects the + following neighbors as Dependent Neighbors: Rmax if it is an + MDR or BMDR; each MDR bi-neighbor u such that hops(u) is + greater than MDRConstraint; and if AdjConnectivity = 2, each + BMDR bi-neighbor u such that hops(u) is greater than + MDRConstraint. + + (2.7) If steps 2.1 through 2.6 resulted in the MDR Level changing to + BMDR, or to MDR with AdjConnectivity equal to 1 or 2, then + execute steps 2.1 through 2.6 again. (This is necessary + because the change in MDR Level can cause the set of Dependent + Neighbors and the BFS tree to change.) This step is not + required if the MDR selection algorithm is executed + periodically. + + Step 2.4 can be implemented using a breadth-first search (BFS) + algorithm to compute min-hop paths from Rmax to all other bi- + neighbors, modified to allow a bi-neighbor to be an intermediate node + only if its value of (RtrPri, MDR Level, RID) is larger than that of + the router itself. A detailed description of this algorithm, which + runs in O(d^2) time, is given in Appendix B. + + + + + + +Ogier & Spagnolo Experimental [Page 28] + +RFC 5614 MANET Extension of OSPF August 2009 + + +5.3. Phase 3: Backup MDR Selection + + (3.1) If the MDR Level is MDR (after running Phase 2) and + AdjConnectivity is not 2, then proceed to Phase 4. (If the MDR + Level is MDR and AdjConnectivity = 2, then Phase 3 may select + additional Dependent Neighbors to create a biconnected + backbone.) + + (3.2) Using NCM to determine the connectivity of bi-neighbors, + determine whether or not there exist two node-disjoint paths + from Rmax to each other bi-neighbor u, using only intermediate + nodes that are bi-neighbors with a larger value of (RtrPri, MDR + Level, RID) than the router itself. (See Appendix B for a + detailed algorithm.) + + (3.3) If there exist two such node-disjoint paths from Rmax to each + other bi-neighbor u, then the router selects no additional + Dependent Neighbors and sets its MDR Level to MDR Other. + + (3.4) Else, the router sets its MDR Level to Backup MDR unless it + already selected itself as an MDR in Phase 2, and if + AdjConnectivity = 2, adds each of the following neighbors to + the set of Dependent Neighbors: Rmax if it is an MDR or BMDR, + and each MDR/BMDR bi-neighbor u such that Step 3.2 did not find + two node-disjoint paths from Rmax to u. + + (3.5) If steps 3.1 through 3.4 resulted in the MDR Level changing + from MDR Other to BMDR, then run Phases 2 and 3 again. (This + is necessary because running Phase 2 again can cause the MDR + Level to change to MDR.) This step is not required if the MDR + selection algorithm is executed periodically. + + Step 3.2 can be implemented in O(d^2) time using the algorithm given + in Appendix B. A simplified version of the algorithm is also + specified, which results in a larger number of BMDRs. + +5.4. Phase 4: Parent Selection + + Each router selects a Parent for each MANET interface. The Parent of + a non-MDR router will be a neighboring MDR if one exists. If the + option of biconnected adjacencies is chosen, then each MDR Other + selects a Backup Parent, which will be a neighboring MDR/BMDR if one + exists that is not the Parent. The Parent of an MDR is always the + router itself, and the Backup Parent of a BMDR is always the router + itself. + + + + + + +Ogier & Spagnolo Experimental [Page 29] + +RFC 5614 MANET Extension of OSPF August 2009 + + + The (Backup) Parent is advertised in the (Backup) DR field of each + Hello sent on the interface. As specified in Section 7.2, each + router forms an adjacency with its Parent and Backup Parent if it + exists and is a neighboring MDR/BMDR. + + For a given MANET interface, let Rmax denote the router with the + largest value of (RtrPri, MDR Level, RID) among all bidirectional + neighbors, if such a neighbor exists that has a larger value of + (RtrPri, MDR Level, RID) than the router itself. Otherwise, Rmax is + null. + + If the calculating router has selected itself as an MDR, then the + Parent is equal to the router itself, and the Backup Parent is Rmax. + (The latter design choice was made because it results in slightly + better performance than choosing no Backup Parent.) If the router + has selected itself as a BMDR, then the Backup Parent is equal to the + router itself. + + If the calculating router is a BMDR or MDR Other, the Parent is + selected to be any adjacent neighbor that is an MDR, if such a + neighbor exists. If no adjacent MDR neighbor exists, then the Parent + is selected to be Rmax. By giving preference to neighbors that are + already adjacent, the formation of a new adjacency is avoided when + possible. Note that the Parent can be a non-MDR neighbor temporarily + when no MDR neighbor exists. (This design choice was also made for + performance reasons.) + + If AdjConnectivity = 2 and the calculating router is an MDR Other, + then the Backup Parent is selected to be any adjacent neighbor that + is an MDR or BMDR, other than the Parent selected in the previous + paragraph, if such a neighbor exists. If no such adjacent neighbor + exists, then the Backup Parent is selected to be the bidirectional + neighbor, excluding the selected Parent, with the largest value of + (RtrPri, MDR Level, RID), if such a neighbor exists. Otherwise, the + Backup Parent is null. + +5.5. Phase 5: Optional Selection of Non-Flooding MDRs + + A router that has selected itself as an MDR MAY execute the following + steps to possibly declare itself a non-flooding MDR. An MDR that + does not execute the following steps is by default a flooding MDR. + + (5.1) If the router has a larger value of (RtrPri, MDR Level, RID) + than all of its bi-neighbors, the router is a flooding MDR. + Else, proceed to Step 5.2. + + (5.2) Let Rmax be the bi-neighbor that has the largest value of + (RtrPri, MDR Level, RID). + + + +Ogier & Spagnolo Experimental [Page 30] + +RFC 5614 MANET Extension of OSPF August 2009 + + + (5.3) Using NCM to determine the connectivity of bi-neighbors, + compute the minimum number of hops, denoted hops(u), from Rmax + to each other bi-neighbor u, using only intermediate nodes that + are MDR bi-neighbors with a smaller value of (RtrPri, RID) than + the router itself. (This can be done using BFS as in Step 2.4). + + (5.4) If hops(u) is at most MDRConstraint for each bi-neighbor u, + then the router is a non-flooding MDR. Else, it is a flooding + MDR. + +6. Interface State Machine + +6.1. Interface States + + No new states are defined for a MANET interface. However, the DR and + Backup states now imply that the router is an MDR or Backup MDR, + respectively. The following modified definitions apply to MANET + interfaces: + + Waiting + In this state, the router learns neighbor information from the + Hello packets it receives, but is not allowed to run the MDR + selection algorithm until it transitions out of the Waiting state + (when the Wait Timer expires). This prevents unnecessary changes + in the MDR selection resulting from incomplete neighbor + information. The length of the Wait Timer is 2HopRefresh * + HelloInterval seconds (the interval between full Hellos). + + DR Other + The router has run the MDR selection algorithm and determined that + it is not an MDR or a Backup MDR. + + Backup + The router has selected itself as a Backup MDR. + + DR + The router has selected itself as an MDR. + +6.2. Events that Cause Interface State Changes + + All interface events defined in [RFC2328], Section 9.2, apply to + MANET interfaces, except for BackupSeen and NeighborChange. + BackupSeen is never invoked for a MANET interface (since seeing a + Backup MDR does not imply that the router itself cannot also be an + MDR or Backup MDR). + + + + + + +Ogier & Spagnolo Experimental [Page 31] + +RFC 5614 MANET Extension of OSPF August 2009 + + + The event NeighborChange is replaced with the new interface variable + MDRNeighborChange, which indicates that the MDR selection algorithm + must be executed due to a change in neighbor information (see Section + 4.2.3). + +6.3. Changes to Interface State Machine + + This section describes the changes to the interface state machine for + a MANET interface. The two state transitions specified below are for + state-event pairs that are described in [RFC2328], but have modified + action descriptions because MDRs are selected instead of DRs. The + state transition in [RFC2328] for the event NeighborChange is + omitted; instead, the new interface variable MDRNeighborChange is + used to indicate when the MDR selection algorithm needs to be + executed. The state transition for the event BackupSeen does not + apply to MANET interfaces, since this event is never invoked for a + MANET interface. The interface state transitions for the events + Loopback and UnloopInd are unchanged from [RFC2328]. + + State: Down + Event: InterfaceUp + New state: Depends on action routine. + + Action: Start the interval Hello Timer, enabling the periodic + sending of Hello packets out the interface. The state + transitions to Waiting and the single shot Wait Timer + is started. + + + State: Waiting + Event: WaitTimer + New state: Depends on action routine. + + Action: Run the MDR selection algorithm, which may result in a + change to the router's MDR Level, Dependent Neighbors, + and (Backup) Parent. As a result of this calculation, + the new interface state will be DR Other, Backup, or DR. + + As a result of these changes, the AdjOK? neighbor event + may be invoked for some or all neighbors. (See + Section 7.) + +7. Adjacency Maintenance + + Adjacency forming and eliminating on non-MANET interfaces remain + unchanged. Adjacency maintenance on a MANET interface requires + changes to transitions in the neighbor state machine ([RFC2328], + Section 10.3), to deciding whether to become adjacent ([RFC2328], + + + +Ogier & Spagnolo Experimental [Page 32] + +RFC 5614 MANET Extension of OSPF August 2009 + + + Section 10.4), sending of DD packets ([RFC2328], Section 10.8), and + receiving of DD packets ([RFC2328], Section 10.6). The specification + below relates to the MANET interface only. + + If full-topology adjacencies are used (AdjConnectivity = 0), the + router forms an adjacency with each bidirectional neighbor. If + adjacency reduction is used (AdjConnectivity is 1 or 2), the router + forms adjacencies with a subset of its neighbors, according to the + rules specified in Section 7.2. + + An adjacency maintenance decision is made when any of the following + four events occur between a router and its neighbor. The decision is + made by executing the neighbor event AdjOK?. + + (1) The neighbor state changes from Init to 2-Way. + + (2) The MDR Level changes for the neighbor or for the router + itself. + + (3) The neighbor is selected to be the (Backup) Parent. + + (4) The neighbor selects the router to be its (Backup) Parent. + +7.1. Changes to Neighbor State Machine + + The following specifies new transitions in the neighbor state + machine. + + State(s): Down + Event: HelloReceived + New state: Depends on action routine. + + Action: If the neighbor acceptance condition is satisfied (see + Section 4.3), the neighbor state transitions to Init and + the Inactivity Timer is started. Otherwise, the neighbor + remains in the Down state. + + + State(s): Init + Event: 2-WayReceived + New state: 2-Way + + Action: Transition to neighbor state 2-Way. + + State(s): 2-Way + Event: AdjOK? + New state: Depends on action routine. + + + + +Ogier & Spagnolo Experimental [Page 33] + +RFC 5614 MANET Extension of OSPF August 2009 + + + Action: Determine whether an adjacency should be formed with the + neighboring router (see Section 7.2). If not, the + neighbor state remains at 2-Way and no further action is + taken. + + Otherwise, the neighbor state changes to ExStart, and the + following actions are performed. If the neighbor has a + larger Router ID than the router's own ID, and the + received packet is a DD packet with the initialize (I), + more (M), and master (MS) bits set, then execute the + event NegotiationDone, which causes the state to + transition to Exchange. + + Otherwise (negotiation is not complete), the router + increments the DD sequence number in the neighbor data + structure. If this is the first time that an adjacency + has been attempted, the DD sequence number should be + assigned a unique value (like the time of day clock). It + then declares itself master (sets the master/slave bit to + master), and starts sending Database Description packets, + with the initialize (I), more (M), and master (MS) bits + set, the MDR-DD TLV included in an LLS, and the L bit + set. This Database Description packet should be + otherwise empty. This Database Description packet should + be retransmitted at intervals of RxmtInterval until the + next state is entered (see [RFC2328], Section 10.8). + + + State(s): ExStart or greater + Event: AdjOK? + New state: Depends on action routine. + + Action: Determine whether the neighboring router should still be + adjacent (see Section 7.3). If yes, there is no state + change and no further action is necessary. Otherwise, + the (possibly partially formed) adjacency must be + destroyed. The neighbor state transitions to 2-Way. The + Link state retransmission list, Database summary list, + and Link state request list are cleared of LSAs. + +7.2. Whether to Become Adjacent + + The following defines the method to determine if an adjacency should + be formed between neighbors in state 2-Way. The following procedure + does not depend on whether AdjConnectivity is 1 or 2, but the + selection of Dependent Neighbors (by the MDR selection algorithm) + depends on AdjConnectivity. + + + + +Ogier & Spagnolo Experimental [Page 34] + +RFC 5614 MANET Extension of OSPF August 2009 + + + If adjacency reduction is not used (AdjConnectivity = 0), then an + adjacency is formed with each neighbor in state 2-Way. Otherwise, an + adjacency is formed with a neighbor in state 2-Way if any of the + following conditions is true: + + (1) The router is a (Backup) MDR and the neighbor is a (Backup) MDR + and is either a Dependent Neighbor or a Dependent Selector. + + (2) The neighbor is a (Backup) MDR and is the router's (Backup) + Parent. + + (3) The router is a (Backup) MDR and the neighbor is a child. + + (4) The neighbor's A-bit is 1, indicating that the neighbor is using + full-topology adjacencies. + + Otherwise, an adjacency is not established and the neighbor remains + in state 2-Way. + +7.3. Whether to Eliminate an Adjacency + + The following defines the method to determine if an existing + adjacency should be eliminated. An existing adjacency is maintained + if any of the following is true: + + (1) The router is an MDR or Backup MDR. + + (2) The neighbor is an MDR or Backup MDR. + + (3) The neighbor's A-bit is 1, indicating that the neighbor is using + full-topology adjacencies. + + Otherwise, the adjacency MAY be eliminated. + +7.4. Sending Database Description Packets + + Sending a DD packet on a MANET interface is the same as [RFC5340], + Section 4.2.1.2, and [RFC2328], Section 10.8, with the following + additions to paragraph 3 of Section 10.8. + + If the neighbor state is ExStart, the standard initialization packet + is sent with an MDR-DD TLV appended using LLS, and the L bit is set + in the DD packet's option field. The format for the MDR-DD TLV is + specified in Section A.2.4. The DR and Backup DR fields of the MDR- + DD TLV are set exactly the same as the DR and Backup DR fields of a + Hello sent on the same interface. + + + + + +Ogier & Spagnolo Experimental [Page 35] + +RFC 5614 MANET Extension of OSPF August 2009 + + +7.5. Receiving Database Description Packets + + Processing a DD packet received on a MANET interface is the same as + [RFC2328], Section 10.6, except for the changes described in this + section. The following additional steps are performed before + processing the packet based on neighbor state in paragraph 3 of + Section 10.6. + + o If the DD packet's L bit is set in the options field and an MDR-DD + TLV is appended, then the MDR-DD TLV is processed as follows. + + (1) If the DR field is equal to the neighbor's Router ID: + + (a) Set the MDR Level of the neighbor to MDR. + + (b) Set the neighbor's Dependent Selector variable to 1. + + (2) Else if the Backup DR field is equal to the neighbor's Router + ID: + + (a) Set the MDR Level of the neighbor to Backup MDR. + + (b) Set the neighbor's Dependent Selector variable to 1. + + (3) Else: + + (a) Set the MDR Level of the neighbor to MDR Other. + + (b) Set the neighbor's Dependent Neighbor variable to 0. + + (4) If the DR or Backup DR field is equal to the router's own + Router ID, set the neighbor's Child variable to 1; otherwise, + set it to 0. + + o If the neighbor state is Init, the neighbor event 2-WayReceived is + executed. + + o If the MDR Level of the neighbor changed, the neighbor state + machine is scheduled with the event AdjOK?. + + o If the neighbor's Child status has changed from 0 to 1, the + neighbor state machine is scheduled with the event AdjOK?. + + o If the neighbor's neighbor state changed from less than 2-Way to + 2-Way or greater, the neighbor state machine is scheduled with the + event AdjOK?. + + + + + +Ogier & Spagnolo Experimental [Page 36] + +RFC 5614 MANET Extension of OSPF August 2009 + + + In addition, the Database Exchange optimization described in + [RFC5243] SHOULD be performed as follows. If the router accepts a + received DD packet as the next in sequence, the following additional + step should be performed for each LSA listed in the DD packet + (whether the router is master or slave). If the Database summary + list contains an instance of the LSA that is the same as or less + recent than the listed LSA, the LSA is removed from the Database + summary list. This avoids listing the LSA in a DD packet sent to the + neighbor, when the neighbor already has an instance of the LSA that + is the same or more recent. This optimization reduces overhead due + to DD packets by approximately 50% in large networks. + +8. Flooding Procedure + + This section specifies the changes to [RFC2328], Section 13, for + routers that support OSPF-MDR. The first part of Section 13 (before + Section 13.1) is the same except for the following three changes. + + o To exploit the broadcast nature of MANETs, if the Link State + Update (LSU) packet was received on a MANET interface, then the + packet is dropped without further processing only if the sending + neighbor is in a lesser state than 2-Way. Otherwise, the LSU + packet is processed as described in this section. + + o If the received LSA is the same instance as the database copy, the + following actions are performed in addition to Step 7. For each + MANET interface for which a BackupWait Neighbor List exists for + the LSA (see Section 8.1): + + (a) Remove the sending neighbor from the BackupWait Neighbor List + if it belongs to the list. + + (b) For each neighbor on the receiving interface that belongs to + the BNS for the sending neighbor, remove the neighbor from the + BackupWait Neighbor List if it belongs to the list. + + o Step 8, which handles the case in which the database copy of the + LSA is more recent than the received LSA, is modified as follows. + If the sending neighbor is in a lesser state than Exchange, then + the router does not send the LSA back to the sending neighbor. + + There are no changes to Sections 13.1, 13.2, or 13.4. The following + subsections describe the changes to Sections 13.3 (Next step in the + flooding procedure), 13.5 (Sending Link State Acknowledgments), 13.6 + (Retransmitting LSAs), and 13.7 (Receiving Link State + Acknowledgments) of [RFC2328]. + + + + + +Ogier & Spagnolo Experimental [Page 37] + +RFC 5614 MANET Extension of OSPF August 2009 + + +8.1. LSA Forwarding Procedure + + When a new LSA is received, Steps 1 through 5 of [RFC2328], Section + 13.3, are performed without modification for each eligible (outgoing) + interface that is not of type MANET. This section specifies the + modified steps that must be performed for each eligible MANET + interface. The eligible interfaces depend on the LSA's flooding + scope as described in [RFC5340], Section 4.5.2. Whenever an LSA is + flooded out a MANET interface, it is included in an LSU packet that + is sent to the multicast address AllSPFRouters. (Retransmitted LSAs + are always unicast, as specified in Section 8.3.) + + Step 1 of [RFC2328], Section 13.3, is performed for each eligible + MANET interface with the following modification, so that the new LSA + is placed on the Link State retransmission list for each appropriate + adjacent neighbor. Step 1c is replaced with the following action, so + that the LSA is not placed on the retransmission list for a neighbor + that has already acknowledged the LSA. + + o If the new LSA was received from this neighbor, or a Link State + Acknowledgment (LS Ack) for the new LSA has already been received + from this neighbor, examine the next neighbor. + + To determine whether an Ack for the new LSA has been received from + the neighbor, the router maintains an Acked LSA List for each + adjacent neighbor, as described in Section 8.4. When a new LSA is + received, the Acked LSA List for each neighbor, on each MANET + interface, should be updated by removing any LS Ack that is for an + older instance of the LSA than the one received. + + The following description will use the notion of a "covered" + neighbor. A neighbor k is defined to be covered if the LSA was sent + as a multicast by a MANET neighbor j, and neighbor k belongs to the + Bidirectional Neighbor Set (BNS) for neighbor j. A neighbor k is + also defined to be covered if the LSA was sent to the multicast + address AllSPFRouters by a neighbor j on a broadcast interface on + which both j and k are neighbors. (Note that j must be the DR or + Backup DR for the broadcast network, since only these routers may + send LSAs to AllSPFRouters on a broadcast network.) + + The following steps must be performed for each eligible MANET + interface, to determine whether the new LSA should be forwarded on + the interface. + + (2) If every bidirectional neighbor on the interface satisfies at + least one of the following three conditions, examine the next + interface (the LSA is not flooded out this interface). + + + + +Ogier & Spagnolo Experimental [Page 38] + +RFC 5614 MANET Extension of OSPF August 2009 + + + (a) The LSA was received from the neighbor. + + (b) The LSA was received on a MANET or broadcast interface and the + neighbor is covered (defined above). + + (c) An Ack for the LSA has been received from the neighbor. + + Condition (c) MAY be omitted (thus ignoring Acks) in order to + simplify this step. Note that the above conditions do not + assume the outgoing interface is the same as the receiving + interface. + + (3) If the LSA was received on this interface, and the router is an + MDR Other for this interface, examine the next interface (the LSA + is not flooded out this interface). + + (4) If the LSA was received on this interface, and the router is a + Backup MDR or a non-flooding MDR for this interface, then the + router waits BackupWaitInterval before deciding whether to flood + the LSA. To accomplish this, the router creates a BackupWait + Neighbor List for the LSA, which initially includes every + bidirectional neighbor on this interface that does not satisfy + any of the conditions in Step 2. A single-shot BackupWait Timer + associated with the LSA is started, which is set to expire after + BackupWaitInterval seconds plus a small amount of random jitter. + (The actions performed when the BackupWait Timer expires are + described below in Section 8.1.2.) Examine the next interface + (the LSA is not yet flooded out this interface). + + (5) If the router is a flooding MDR for this interface, or if the LSA + was originated by the router itself, then the LSA is flooded out + the interface (whether or not the LSA was received on this + interface) and the next interface is examined. + + (6) If the LSA was received on a MANET or broadcast interface that is + different from this (outgoing) interface, then the following two + steps SHOULD be performed to avoid redundant flooding. + + (a) If the router has a larger value of (RtrPri, MDR Level, RID) + on the outgoing interface than every covered neighbor (defined + above) that is a neighbor on BOTH the receiving and outgoing + interfaces (or if no such neighbor exists), then the LSA is + flooded out the interface and the next interface is examined. + + (b) Else, the router waits BackupWaitInterval before deciding + whether to flood the LSA on the interface, by performing the + actions in Step 4 for a Backup MDR (whether or not the router + is a Backup MDR on this interface). A separate BackupWait + + + +Ogier & Spagnolo Experimental [Page 39] + +RFC 5614 MANET Extension of OSPF August 2009 + + + Neighbor List is created for each MANET interface, but only + one BackupWait Timer is associated with the LSA. Examine the + next interface (the LSA is not yet flooded out this + interface). + + (7) If this step is reached, the LSA is flooded out the interface. + +8.1.1. Note on Step 6 of LSA Forwarding Procedure + + Performing the optional Step 6 can greatly reduce flooding overhead + if the LSA was received on a MANET or broadcast interface. For + example, assume that the LSA was received from the DR of a broadcast + network that includes 100 routers, and 50 of the routers (not + including the DR) are also attached to a MANET. Assume that these 50 + routers are neighbors of each other in the MANET and that each has a + neighbor in the MANET that is not attached to the broadcast network + (and is therefore not covered). Then by performing Step 6 of the LSA + forwarding procedure, the number of routers that forward the LSA from + the broadcast network to the MANET is reduced from 50 to just 1 + (assuming that at most 1 of the 50 routers is an MDR). + +8.1.2. BackupWait Timer Expiration + + If the BackupWait Timer for an LSA expires, then the following steps + are performed for each (MANET) interface for which a BackupWait + Neighbor List exists for the LSA. + + (1) If the BackupWait Neighbor List for the interface contains at + least one router that is currently a bidirectional neighbor, the + following actions are performed. + + (a) The LSA is flooded out the interface. + + (b) If the LSA is on the Ack List for the interface (i.e., is + scheduled to be included in a delayed Link State + Acknowledgment packet), then the router SHOULD remove the LSA + from the Ack List, since the flooded LSA will be treated as an + implicit Ack. + + (c) If the LSA is on the Link State retransmission list for any + neighbor, the retransmission SHOULD be rescheduled to occur + after RxmtInterval seconds. + + (2) The BackupWait Neighbor List is then deleted (whether or not the + LSA is flooded). + + + + + + +Ogier & Spagnolo Experimental [Page 40] + +RFC 5614 MANET Extension of OSPF August 2009 + + +8.2. Sending Link State Acknowledgments + + This section describes the procedure for sending Link State + Acknowledgments (LS Acks) on MANET interfaces. Section 13.5 of + [RFC2328] remains unchanged for non-MANET interfaces, but does not + apply to MANET interfaces. To minimize overhead due to LS Acks, and + to take advantage of the broadcast nature of MANETs, all LS Ack + packets sent on a MANET interface are multicast using the IP address + AllSPFRouters. In addition, duplicate LSAs received as a multicast + are not acknowledged. + + When a router receives an LSA, it must decide whether to send a + delayed Ack, an immediate Ack, or no Ack. The interface parameter + AckInterval is the interval between LS Ack packets when only delayed + Acks need to be sent. A delayed Ack SHOULD be delayed by at least + (RxmtInterval - AckInterval - 0.5) seconds and at most (RxmtInterval + - 0.5) seconds after the LSA instance being acknowledged was first + received. If AckInterval and RxmtInterval are equal to their default + values of 1 and 7 seconds, respectively, this reduces Ack traffic by + increasing the chance that a new instance of the LSA will be received + before the delayed Ack is sent. An immediate Ack is sent immediately + in a multicast LS Ack packet, which may also include delayed Acks + that were scheduled to be sent. + + The decision whether to send a delayed or immediate Ack depends on + whether the received LSA is new (i.e., is more recent than the + database copy) or a duplicate (the same instance as the database + copy), and on whether the LSA was received as a multicast or a + unicast (which indicates a retransmitted LSA). The following rules + are used to make this decision. + + (1) If the received LSA is new, a delayed Ack is sent on each MANET + interface associated with the area, unless the LSA is flooded out + the interface. + + (2) If the LSA is a duplicate and was received as a multicast, the + LSA is not acknowledged. + + (3) If the LSA is a duplicate and was received as a unicast: + + (a) If the router is an MDR, or AdjConnectivity = 2 and the + router is a Backup MDR, or AdjConnectivity = 0, then an + immediate Ack is sent out the receiving interface. + + (b) Otherwise, a delayed Ack is sent out the receiving interface. + + + + + + +Ogier & Spagnolo Experimental [Page 41] + +RFC 5614 MANET Extension of OSPF August 2009 + + + The reason that (Backup) MDRs send an immediate Ack when a + retransmitted LSA is received is to try to prevent other adjacent + neighbors from retransmitting the LSA, since (Backup) MDRs usually + have a large number of adjacent neighbors. MDR Other routers do not + send an immediate Ack (unless AdjConnectivity = 0) because they have + fewer adjacent neighbors, and so the potential benefit does not + justify the additional overhead resulting from sending immediate + Acks. + +8.3. Retransmitting LSAs + + LSAs are retransmitted according to Section 13.6 of [RFC2328]. Thus, + LSAs are retransmitted only to adjacent routers. Therefore, since + OSPF-MDR does not allow an adjacency to be formed between two MDR + Other routers, an MDR Other never retransmits an LSA to another MDR + Other, only to its Parents, which are (Backup) MDRs. + + Retransmitted LSAs are included in LSU packets that are unicast + directly to an adjacent neighbor that did not acknowledge the LSA + (explicitly or implicitly). The length of time between + retransmissions is given by the configurable interface parameter + RxmtInterval, whose default is 7 seconds for a MANET interface. To + reduce overhead, several retransmitted LSAs should be included in a + single LSU packet whenever possible. + +8.4. Receiving Link State Acknowledgments + + A Link State Acknowledgment (LS Ack) packet that is received from an + adjacent neighbor (in state Exchange or greater) is processed as + described in Section 13.7 of [RFC2328], with the additional steps + described in this section. An LS Ack packet that is received from a + neighbor in a lesser state than Exchange is discarded. + + Each router maintains an Acked LSA List for each adjacent neighbor, + to keep track of any LSA instances the neighbor has acknowledged but + that the router itself has NOT yet received. This is necessary + because (unlike [RFC2328]) each router acknowledges an LSA only the + first time it is received as a multicast. + + If the neighbor from which the LS Ack packet was received is in state + Exchange or greater, then the following steps are performed for each + LS Ack in the received LS Ack packet: + + (1) If the router does not have a database copy of the LSA being + acknowledged, or has a database copy that is less recent than the + one being acknowledged, the LS Ack is added to the Acked LSA List + for the sending neighbor. + + + + +Ogier & Spagnolo Experimental [Page 42] + +RFC 5614 MANET Extension of OSPF August 2009 + + + (2) If the router has a database copy of the LSA being acknowledged, + which is the same as the instance being acknowledged, then the + following action is performed. For each MANET interface for + which a BackupWait Neighbor List exists for the LSA (see Section + 8.1), remove the sending neighbor from the BackupWait Neighbor + List if it belongs to the list. + +9. Router-LSAs + + Unlike the DR of an OSPF broadcast network, an MDR does not originate + a network-LSA, since a network-LSA cannot be used to describe the + general topology of a MANET. Instead, each router advertises a + subset of its MANET neighbors as point-to-point links in its router- + LSA. The choice of which MANET neighbors to include in the router- + LSA is flexible. Whether or not adjacency reduction is used, the + router can originate either partial-topology or full-topology LSAs. + + If adjacency reduction is used (AdjConnectivity is 1 or 2), then as a + minimum requirement each router must advertise a minimum set of + "backbone" neighbors in its router-LSA. This minimum choice + corresponds to LSAFullness = 0, and results in the minimum amount of + LSA flooding overhead, but does not provide routing along shortest + paths. + + Therefore, to allow routers to calculate shortest paths, without + requiring every pair of neighboring routers along the shortest paths + to be adjacent (which would be inefficient due to requiring a large + number of adjacencies), a router-LSA may also advertise non-adjacent + neighbors that satisfy a synchronization condition described below. + + To motivate this, we note that OSPF already allows a non-adjacent + neighbor to be a next hop, if both the router and the neighbor belong + to the same broadcast network (and are both adjacent to the DR). A + network-LSA for a broadcast network (which includes all routers + attached to the network) implies that any router attached to the + network can forward packets directly to any other router attached to + the network (which is why the distance from the network to all + attached routers is zero in the graph representing the link-state + database). + + Since a network-LSA cannot be used to describe the general topology + of a MANET, the only way to advertise non-adjacent neighbors that can + be used as next hops is to include them in the router-LSA. However, + to ensure that such neighbors are sufficiently synchronized, only + "routable" neighbors are allowed to be included in LSAs, and to be + used as next hops in the SPF calculation. + + + + + +Ogier & Spagnolo Experimental [Page 43] + +RFC 5614 MANET Extension of OSPF August 2009 + + +9.1. Routable Neighbors + + If adjacency reduction is used, a bidirectional MANET neighbor + becomes routable if the SPF calculation has found a route to the + neighbor and the neighbor satisfies the routable neighbor quality + condition (defined below). Since only routable and Full neighbors + are advertised in router-LSAs, and since adjacencies are selected to + form a connected spanning subgraph, this definition implies that + there exists, or recently existed, a path of full adjacencies from + the router to the routable neighbor. The idea is that, since a + routable neighbor can be reached through an acceptable path, it makes + sense to take a "shortcut" and forward packets directly to the + routable neighbor. + + This requirement does not guarantee perfect synchronization, but + simulations have shown that it performs well in mobile networks. + This requirement avoids, for example, forwarding packets to a new + neighbor that is poorly synchronized because it was not reachable + before it became a neighbor. + + To avoid selecting poor-quality neighbors as routable neighbors, a + neighbor that is selected as a routable neighbor must satisfy the + routable neighbor quality condition. By default, this condition is + that the neighbor's BNS must include the router itself (indicating + that the neighbor agrees the connection is bidirectional). + Optionally, a router may impose a stricter condition. For example, a + router may require that two Hellos have been received from the + neighbor that (explicitly or implicitly) indicate that the neighbor's + BNS includes the router itself. + + The single-bit neighbor variable Routable indicates whether the + neighbor is routable, and is initially set to 0. If adjacency + reduction is used, Routable is updated as follows when the state of + the neighbor changes, or the SPF calculation finds a route to the + neighbor, or a Hello is received that affects the routable neighbor + quality condition. + + (1) If Routable is 0 for the neighbor, the state of the neighbor is + 2-Way or greater, there exists a route to the neighbor, and the + routable neighbor quality condition (defined above) is satisfied, + then Routable is set to 1 for the neighbor. + + (2) If Routable is 1 for the neighbor and the state of the neighbor + is less than 2-Way, Routable is set to 0 for the neighbor. + + If adjacency reduction is not used (AdjConnectivity = 0), then + routable neighbors are not computed and the set of routable neighbors + remains empty. + + + +Ogier & Spagnolo Experimental [Page 44] + +RFC 5614 MANET Extension of OSPF August 2009 + + +9.2. Backbone Neighbors + + The flexible choice for the router-LSA is made possible by defining + two types of neighbors that are included in the router-LSA: backbone + neighbors and Selected Advertised Neighbors. + + If adjacency reduction is used, a bidirectional neighbor is defined + to be a backbone neighbor if and only if it satisfies the condition + for becoming adjacent (see Section 7.2). If adjacency reduction is + not used (AdjConnectivity = 0), a bidirectional neighbor is a + backbone neighbor if and only if the neighbor's A-bit is 0 + (indicating that the neighbor is using adjacency reduction). This + definition allows the interoperation between routers that use + adjacency reduction and routers that do not. + + If adjacency reduction is used, then a router MUST include in its + router-LSA all Full neighbors and all routable backbone neighbors. A + minimal LSA, corresponding to LSAFullness = 0, includes only these + neighbors. This choice guarantees connectivity, but does not ensure + shortest paths. However, this choice is useful in large networks to + achieve maximum scalability. + +9.3. Selected Advertised Neighbors + + To allow flexibility while ensuring that router-LSAs are symmetric + (i.e., router i advertises a link to router j if and only if router j + advertises a link to router i), each router maintains a Selected + Advertised Neighbor set (SANS), which consists of MANET neighbors + that the router has selected to advertise in its router-LSA, not + including backbone neighbors. Since the SANS does not include + backbone neighbors (and thus Dependent Neighbors), the SANS and DNS + are disjoint. Both of these neighbor sets are advertised in Hellos. + + If LSAFullness is 0 (minimal LSAs), then the SANS is empty. At the + other extreme, if LSAFullness is 4 (full-topology LSAs), the SANS + includes all bidirectional MANET neighbors except backbone neighbors. + In between these two extremes, a router that is using adjacency + reduction may select any subset of bidirectional non-backbone + neighbors as its SANS. The resulting router-LSA is constructed as + specified in Section 9.4. + + Since a router that is not using adjacency reduction typically has no + backbone neighbors (unless it has neighbors that are using adjacency + reduction), to ensure connectivity, such a router must choose its + SANS to contain the SANS corresponding to LSAFullness = 1. Thus, if + AdjConnectivity is 0 (no adjacency reduction), then LSAFullness must + be 1, 2, or 4. + + + + +Ogier & Spagnolo Experimental [Page 45] + +RFC 5614 MANET Extension of OSPF August 2009 + + + If LSAFullness is 1, the router originates min-cost LSAs, which are + partial-topology LSAs that (when flooded) provide each router with + sufficient information to calculate a shortest (minimum-cost) path to + each destination. Appendix C describes the algorithm for selecting + the neighbors to include in the SANS that results in min-cost LSAs. + The input to this algorithm includes information obtained from Hellos + received from each MANET neighbor, including the neighbor's + Bidirectional Neighbor Set (BNS), Dependent Neighbor Set (DNS), + Selected Advertised Neighbor Set (SANS), and the Metric TLV. The + Metric TLV, specified in Section A.2.5, is appended to each Hello + (unless all link costs are 1) to advertise the link cost to each + bidirectional neighbor. + + If LSAFullness is 2, the SANS must be selected to be a superset of + the SANS corresponding to LSAFullness = 1. This choice provides + shortest-path routing while allowing the router to advertise + additional neighbors to provide redundant routes. + + If LSAFullness is 3, each MDR originates a full-topology LSA (which + includes all Full and routable neighbors), while each non-MDR router + originates a minimal LSA. If the router has multiple MANET + interfaces, the router-LSA includes all Full and routable neighbors + on each interface for which it is an MDR, and advertises only Full + neighbors and routable backbone neighbors on its other interfaces. + This choice provides routing along nearly shortest paths with + relatively low overhead. + + Although this document specifies a few choices of the SANS, which + correspond to different values of LSAFullness, it is important to + note that other choices are possible. In addition, it is not + necessary for different routers to choose the same value of + LSAFullness. The different choices are interoperable because they + all require the router-LSA to include a minimum set of neighbors, and + because the construction of the router-LSA (described below) ensures + that the router-LSAs originated by different routers are consistent. + +9.4. Originating Router-LSAs + + When a new router-LSA is originated, it includes a point-to-point + (type 1) link for each MANET neighbor that is advertised. The set of + neighbors to be advertised is determined as follows. If adjacency + reduction is used, the router advertises all Full neighbors, and + advertises each routable neighbor j that satisfies any of the + following three conditions. If adjacency reduction is not used + (AdjConnectivity = 0), the router advertises each Full neighbor j + that satisfies any of the following three conditions. + + (1) The router's SANS (for any interface) includes j. + + + +Ogier & Spagnolo Experimental [Page 46] + +RFC 5614 MANET Extension of OSPF August 2009 + + + (2) Neighbor j's SANS includes the router (to ensure symmetry). + + (3) Neighbor j is a backbone neighbor. + + Note that backbone neighbors and neighbors in the SANS need not be + routable or Full, but only routable and Full neighbors may be + included in the router-LSA. This is done so that the SANS, which is + advertised in Hellos, does not depend on routability. + + The events that cause a new router-LSA to be originated are the same + as in [RFC2328] and [RFC5340] except that a MANET neighbor changing + to/from the Full state does not always cause a new router-LSA to be + originated. Instead, a new router-LSA is originated whenever a + change occurs that causes any of the following three conditions to + occur: + + o There exists a MANET neighbor j that satisfies the above + conditions for inclusion in the router-LSA, but is not included in + the current router-LSA. + + o The current router-LSA includes a MANET neighbor that is no longer + bidirectional. + + o The link metric has changed for a MANET neighbor that is included + in the current router-LSA. + + The above conditions may be checked periodically just before sending + each Hello, instead of checking them every time one of the neighbor + sets changes. The following implementation was found to work well. + Just before sending each Hello, and whenever a bidirectional neighbor + transitions to less than 2-Way, the router runs the MDR selection + algorithm; updates its adjacencies, routable neighbors, and Selected + Advertised Neighbors; then checks the above conditions to see if a + new router-LSA should be originated. In addition, if a neighbor + becomes bidirectional or Full, the router updates its routable + neighbors and checks the above conditions. + +10. Calculating the Routing Table + + The routing table calculation is the same as specified in [RFC2328], + except for the following changes to Section 16.1 (Calculating the + shortest-path tree for an area). If full-topology adjacencies and + full-topology LSAs are used (AdjConnectivity = 0 and LSAFullness = + 4), there is no change to Section 16.1. + + If adjacency reduction is used (AdjConnectivity is 1 or 2), then + Section 16.1 is modified as follows. Recall from Section 9 that a + router can use any routable neighbor as a next hop to a destination, + + + +Ogier & Spagnolo Experimental [Page 47] + +RFC 5614 MANET Extension of OSPF August 2009 + + + whether or not the neighbor is advertised in the router-LSA. This is + accomplished by modifying Step 2 so that the router-LSA associated + with the root vertex is replaced with a dummy router-LSA that + includes links to all Full neighbors and all routable MANET + neighbors. In addition, Step 2b (checking for a link from W back to + V) MUST be skipped when V is the root vertex and W is a routable + MANET neighbor. However, Step 2b must still be executed when V is + not the root vertex, to ensure compatibility with OSPFv3. + + If LSAFullness is 0 (minimal LSAs), then the calculated paths need + not be shortest paths. In this case, the path actually taken by a + packet can be shorter than the calculated path, since intermediate + routers may have routable neighbors that are not advertised in any + router-LSA. + + If full-topology adjacencies and partial-topology LSAs are used, then + Section 16.1 is modified as follows. Step 2 is modified so that the + router-LSA associated with the root vertex is replaced with a dummy + router-LSA that includes links to all Full neighbors. In addition, + Step 2b MUST be skipped when V is the root vertex and W is a Full + MANET neighbor. (This is necessary since the neighbor's router-LSA + need not contain a link back to the router.) + + If adjacency reduction is used with partial-topology LSAs, then the + set of routable neighbors can change without causing the contents of + the router-LSA to change. This could happen, for example, if a + routable neighbor that was not included in the router-LSA transitions + to the Down or Init state. Therefore, if the set of routable + neighbors changes, the shortest-path tree must be recalculated, even + if the router-LSA does not change. + + After the shortest-path tree and routing table are calculated, the + set of routable neighbors must be updated, since a route to a non- + routable neighbor may have been discovered. If the set of routable + neighbors changes, then the shortest-path tree and routing table must + be calculated a second time. The second calculation will not change + the set of routable neighbors again, so two calculations are + sufficient. If the set of routable neighbors is updated periodically + every HelloInterval seconds, then it is not necessary to update the + set of routable neighbors immediately after the routing table is + updated. + + + + + + + + + + +Ogier & Spagnolo Experimental [Page 48] + +RFC 5614 MANET Extension of OSPF August 2009 + + +11. Security Considerations + + As with OSPFv3 [RFC5340], OSPF-MDR can use the IPv6 Authentication + Header (AH) [RFC4302] and/or the IPv6 Encapsulation Security Payload + (ESP) [RFC4303] to provide authentication, integrity, and/or + confidentiality. The use of AH and ESP for OSPFv3 is described in + [RFC4552]. + + Generic threats to routing protocols are described and categorized in + [RFC4593]. The mechanisms described in [RFC4552] provide protection + against many of these threats, but not all of them. In particular, + as mentioned in [RFC5340], these mechanisms do not provide protection + against compromised, malfunctioning, or misconfigured routers (also + called Byzantine routers); this is true for both OSPFv3 and OSPF-MDR. + + The extension of OSPFv3 to include MANET routers does not introduce + any new security threats. However, the use of a wireless medium and + lack of infrastructure, inherent with MANET routers, may render some + of the attacks described in [RFC4593] easier to mount. Depending on + the network context, these increased vulnerabilities may increase the + need to provide authentication, integrity, and/or confidentiality, as + well as anti-replay service. + + For example, sniffing of routing information and traffic analysis are + easier tasks with wireless routers than with wired routers, since the + attacker only needs to be within the radio range of a router. The + use of confidentiality (encryption) provides protection against + sniffing but not traffic analysis. + + Similarly, interference attacks are also easier to mount against + MANET routers due to their wireless nature. Such attacks can be + mounted even if OSPF packets are protected by authentication and + confidentiality, e.g., by transmitting noise or replaying outdated + OSPF packets. As discussed below, an anti-replay service (provided + by both ESP and AH) can be used to protect against the latter attack. + + The following threat actions are also easier with MANET routers: + spoofing (assuming the identify of a legitimate router), + falsification (sending false routing information), and overloading + (sending or triggering an excessive amount of routing updates). + These attacks are only possible if authentication is not used, or the + attacker takes control of a router or is able to forge legitimacy + (e.g., by discovering the cryptographic key). + + [RFC4552] mandates the use of manual keying when current IPsec + protocols are used with OSPFv3. Routers are required to use manually + configured keys with the same security association (SA) parameters + for both inbound and outbound traffic. For MANET routers, this + + + +Ogier & Spagnolo Experimental [Page 49] + +RFC 5614 MANET Extension of OSPF August 2009 + + + implies that all routers attached to the same MANET must use the same + key for multicasting packets. This is required in order to achieve + scalability and feasibility, as explained in [RFC4552]. Future + specifications can explore the use of automated key management + protocols that may be suitable for MANETs. + + As discussed in [RFC4552], the use of manual keys can increase + vulnerability. For example, manual keys are usually long lived, thus + giving an attacker more time to discover the keys. In addition, the + use of the same key on all routers attached to the same MANET leaves + all routers insecure against impersonation attacks if any one of the + routers is compromised. + + Although [RFC4302] and [RFC4303] state that implementations of AH and + ESP SHOULD NOT provide anti-replay service in conjunction with SAs + that are manually keyed, it is important to note that such service is + allowed if the sequence number counter at the sender is correctly + maintained across local reboots until the key is replaced. + Therefore, it may be possible for MANET routers to make use of the + anti-replay service provided by AH and ESP. + + When an OSPF routing domain includes both MANET networks and fixed + networks, the frequency of OSPF updates either due to actual topology + changes or malfeasance could result in instability in the fixed + networks. In situations where this is a concern, it is recommended + that the border routers segregate the MANET networks from the fixed + networks with either separate OSPF areas or, in cases where legacy + routers are very sensitive to OSPF update frequency, separate OSPF + instances. With separate OSPF areas, the 5-second MinLSInterval will + dampen the frequency of changes originated in the MANET networks. + Additionally, OSPF ranges can be configured to aggregate prefixes for + the areas supporting MANET networks. With separate OSPF instances, + more conservative local policies can be employed to limit the volume + of updates emanating from the MANET networks. + +12. IANA Considerations + + This document defines three new LLS TLV types: MDR-Hello TLV (14), + MDR-Metric TLV (16), and MDR-DD TLV (15) (see Section A.2). + + + + + + + + + + + + +Ogier & Spagnolo Experimental [Page 50] + +RFC 5614 MANET Extension of OSPF August 2009 + + +13. Acknowledgments + + Thanks to Aniket Desai for helpful discussions and comments, + including the suggestion that Router Priority should come before MDR + Level in the lexicographical comparison of (RtrPri, MDR Level, RID) + when selecting MDRs and BMDRs, and that the MDR calculation should be + repeated if it causes the MDR Level to change. Thanks also to Tom + Henderson, Acee Lindem, and Emmanuel Baccelli for helpful discussions + and comments. + +14. Normative References + + [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate + Requirement Levels", BCP 14, RFC 2119, March 1997. + + [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. + + [RFC4302] Kent, S., "IP Authentication Header", RFC 4302, December + 2005. + + [RFC4303] Kent, S., "IP Encapsulating Security Payload (ESP)", RFC + 4303, December 2005. + + [RFC4552] Gupta, M. and N. Melam, "Authentication/Confidentiality + for OSPFv3", RFC 4552, June 2006. + + [RFC5243] Ogier, R., "OSPF Database Exchange Summary List + Optimization", RFC 5243, May 2008. + + [RFC5340] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF + for IPv6", RFC 5340, July 2008. + + [RFC5613] Zinin, A., Roy, A., Nguyen, L., Friedman, B., and D. + Yeung, "OSPF Link-Local Signaling", RFC 5613, August + 2009. + +15. Informative References + + [Lawler] Lawler, E., "Combinatorial Optimization: Networks and + Matroids", Holt, Rinehart, and Winston, New York, 1976. + + [Suurballe] Suurballe, J.W. and R.E. Tarjan, "A Quick Method for + Finding Shortest Pairs of Disjoint Paths", Networks, Vol. + 14, pp. 325-336, 1984. + + [RFC4593] Barbir, A., Murphy, S., and Y. Yang, "Generic Threats to + Routing Protocols", RFC 4593, October 2006. + + + + +Ogier & Spagnolo Experimental [Page 51] + +RFC 5614 MANET Extension of OSPF August 2009 + + +Appendix A. Packet Formats + +A.1. Options Field + + The L bit of the OSPF options field is used for link-local signaling, + as described in [RFC5613]. Routers set the L bit in Hello and DD + packets to indicate that the packet contains an LLS data block. + Routers set the L bit in a self-originated router-LSA to indicate + that the LSA is non-ackable. + +A.2. Link-Local Signaling + + OSPF-MDR uses link-local signaling [RFC5613] to append the MDR-Hello + TLV and MDR-Metric TLV to Hello packets, and to append the MDR-DD TLV + to Database Description packets. Link-local signaling is an + extension of OSPFv2 and OSPFv3 that allows the exchange of arbitrary + data using existing OSPF packet types. Here we use LLS for OSPFv3, + which is accomplished by adding an LLS data block at the end of the + OSPFv3 packet. The OSPF packet length field does not include the + length of the LLS data block, but the IPv6 packet length does include + this length. + +A.2.1. LLS Data Block + + The data block used for link-local signaling is formatted as + described below in Figure A.1. + + 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 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Checksum | LLS Data Length | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | + | LLS TLVs | + . . + . . + . . + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Figure A.1: Format of LLS Data Block + + The Checksum field contains the standard IP checksum of the entire + contents of the LLS block. + + The 16-bit LLS Data Length field contains the length (in 32-bit + words) of the LLS block including the header and payload. + Implementations should not use the Length field in the IPv6 packet + header to determine the length of the LLS data block. + + + +Ogier & Spagnolo Experimental [Page 52] + +RFC 5614 MANET Extension of OSPF August 2009 + + + The rest of the block contains a set of Type/Length/Value (TLV) + triplets as described in the following section. All TLVs must be + 32-bit aligned (with padding if necessary). + +A.2.2. LLS TLV Format + + The contents of the LLS data block are constructed using TLVs. See + Figure A.2 for the TLV format. + + The Type field contains the TLV ID, which is unique for each type of + TLV. The Length field contains the length of the Value field (in + bytes) that is variable and contains arbitrary data. + + 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 | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | + . . + . Value . + . . + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Figure A.2: Format of LLS TLVs + + Note that TLVs are always padded to a 32-bit boundary, but padding + bytes are not included in the TLV Length field (though they are + included in the LLS Data Length field of the LLS block header). All + unknown TLVs MUST be silently ignored. + +A.2.3. MDR-Hello TLV + + The MDR-Hello TLV is appended to each MANET Hello using LLS. It + includes the current Hello sequence number (HSN) for the transmitting + interface and the number of neighbors of each type that are listed in + the body of the Hello (see Section 4.1). It also indicates whether + the Hello is differential (via the D-bit), and whether the router is + using full-topology adjacencies (via the A-bit). + + + + + + + + + + + + +Ogier & Spagnolo Experimental [Page 53] + +RFC 5614 MANET Extension of OSPF August 2009 + + + 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 | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Hello Sequence Number | Reserved |A|D| + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | N1 | N2 | N3 | N4 | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + o Type: Set to 14. + + o Length: Set to 8. + + o Hello Sequence Number: A circular two-octet unsigned integer + indicating the current HSN for the transmitting interface. The + HSN for the interface is incremented by 1 (modulo 2^16) every time + a (differential or full) Hello is sent on the interface. + + o Reserved: Set to 0. Reserved for future use. + + o A (1 bit): Set to 1 if AdjConnectivity is 0; otherwise, set to 0. + + o D (1 bit): Set to 1 for a differential Hello and 0 for a full + Hello. + + o N1 (8 bits): The number of neighbors listed in the Hello that are + in state Down. N1 is zero if the Hello is not differential. + + o N2 (8 bits): The number of neighbors listed in the Hello that are + in state Init. + + o N3 (8 bits): The number of neighbors listed in the Hello that are + Dependent. + + o N4 (8 bits): The number of neighbors listed in the Hello that are + Selected Advertised Neighbors. + +A.2.4. MDR-DD TLV + + When a Database Description packet is sent to a neighbor in state + ExStart, an MDR-DD TLV is appended to the packet using LLS. It + includes the same two Router IDs that are included in the DR and + Backup DR fields of a Hello sent by the router, and is used to + indicate the router's MDR Level and Parent(s). + + + + + + +Ogier & Spagnolo Experimental [Page 54] + +RFC 5614 MANET Extension of OSPF August 2009 + + + 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 | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+ + | DR | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+ + | Backup DR | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+ + + o Type: Set to 15. + + o Length: Set to 8. + + o DR: The same Router ID that is included in the DR field of a Hello + sent by the router (see Section A.3). + + o Backup DR: The same Router ID that is included in the Backup DR + field of a Hello sent by the router (see Section A.3). + +A.2.5. MDR-Metric TLV + + If LSAFullness is 1 or 2, an MDR-Metric TLV must be appended to each + MANET Hello packet using LLS, unless all link metrics are 1. This + TLV advertises the link metric for each bidirectional neighbor listed + in the body of the Hello. At a minimum, this TLV advertises a single + default metric. If the I bit is set, the Router ID and link metric + are included for each bidirectional neighbor listed in the body of + the Hello whose link metric is not equal to the default metric. This + option reduces overhead when all neighbors have the same link metric, + or only a few neighbors have a link metric that differs from the + default metric. If the I bit is zero, the link metric is included + for each bidirectional neighbor that is listed in the body of the + Hello and the neighbor RIDs are omitted from the TLV. + + + + + + + + + + + + + + + + + +Ogier & Spagnolo Experimental [Page 55] + +RFC 5614 MANET Extension of OSPF August 2009 + + + 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 | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Default Metric | Reserved |I| + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Neighbor ID (1) | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Neighbor ID (2) | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | ... | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Metric (1) | Metric (2) | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | ... + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + o Type: Set to 16. + + o Length: Set to 4 + 6*N if the I bit is 1, and to 4 + 2*N if the I + bit is 0, where N is the number of neighbors included in the TLV. + + o Default Metric: If the I bit is 1, this is the link metric that + applies to every bidirectional neighbor listed in the body of the + Hello whose RID is not listed in the Metric TLV. + + o Neighbor ID: If the I bit is 1, the RID is listed for each + bidirectional neighbor (Lists 3 through 5 as defined in Section + 4.1) in the body of the Hello whose link metric is not equal to + the default metric. Omitted if the I bit is 0. + + o Metric: Link metric for each bidirectional neighbor, listed in the + same order as the Neighbor IDs in the TLV if the I bit is 1, and + in the same order as the Neighbor IDs of bidirectional neighbors + (Lists 3 through 5 as defined in Section 4.1) in the body of the + Hello if the I bit is 0. + + + + + + + + + + + + + + +Ogier & Spagnolo Experimental [Page 56] + +RFC 5614 MANET Extension of OSPF August 2009 + + +A.3. Hello Packet DR and Backup DR Fields + + The Designated Router (DR) and Backup DR fields of a Hello packet are + set as follows: + + o DR: This field is the router's Parent, or is 0.0.0.0 if the + Parent is null. The Parent of an MDR is always the router's own + RID. + + o Backup DR: This field is the router's Backup Parent, or is + 0.0.0.0 if the Backup Parent is null. The Backup Parent of a BMDR + is always the router's own RID. + +A.4. LSA Formats and Examples + + LSA formats are specified in [RFC5340], Section 4.4. Figure A.3 + below gives an example network map for a MANET in a single area. + + o Four MANET routers RT1, RT2, RT3, and RT4 are in area 1. + + o RT1's MANET interface has links to RT2 and RT3's MANET interfaces. + + o RT2's MANET interface has links to RT1 and RT3's MANET interfaces. + + o RT3's MANET interface has links to RT1, RT2, and RT3's MANET + interfaces. + + o RT4's MANET interface has a link to RT3's MANET interface. + + o RT1 and RT2 have stub networks attached on broadcast interfaces. + + o RT3 has a transit network attached on a broadcast interface. + + + + + + + + + + + + + + + + + + + +Ogier & Spagnolo Experimental [Page 57] + +RFC 5614 MANET Extension of OSPF August 2009 + + + .......................................... + . Area 1. + . + . + . | . + . | 2+---+1 1+---+ + . N1 |---|RT1|----+ +---|RT4|---- + . | +---+ |\ / +---+ + . | | \ / . + . + | \ N3 / . + . | \ / . + . + | \ / . + . | | \ / . + . | 2+---+1 | \ / . + . N2 |---|RT2|----+-------+ . + . | +---+ |1 . + . | +---+ . + . | |RT3|---------------- + . + +---+ . + . |2 . + . +------------+ . + . |1 N4 . + . +---+ . + . |RT5| . + . +---+ . + .......................................... + + Figure A.3: Area 1 with IP Addresses Shown + + + Network IPv6 prefix + ----------------------------------- + N1 5f00:0000:c001:0200::/56 + N2 5f00:0000:c001:0300::/56 + N4 5f00:0000:c001:0400::/56 + + Table 1: IPv6 link prefixes for sample network + + + + + + + + + + + + + + + +Ogier & Spagnolo Experimental [Page 58] + +RFC 5614 MANET Extension of OSPF August 2009 + + + Router interface Interface ID IPv6 global unicast prefix + ----------------------------------------------------------- + RT1 LOOPBACK 0 5f00:0001::/64 + to N3 1 n/a + to N1 2 5f00:0000:c001:0200::RT1/56 + RT2 LOOPBACK 0 5f00:0002::/64 + to N3 1 n/a + to N2 2 5f00:0000:c001:0300::RT2/56 + RT3 LOOPBACK 0 5f00:0003::/64 + to N3 1 n/a + to N4 2 5f00:0000:c001:0400::RT3/56 + RT4 LOOPBACK 0 5f00:0004::/64 + to N3 1 n/a + RT5 to N4 1 5f00:0000:c001:0400::RT5/56 + + Table 2: IPv6 link prefixes for sample network + + + Router interface Interface ID link-local address + ------------------------------------------------------- + RT1 LOOPBACK 0 n/a + to N1 1 fe80:0001::RT1 + to N3 2 fe80:0002::RT1 + RT2 LOOPBACK 0 n/a + to N2 1 fe80:0001::RT2 + to N3 2 fe80:0002::RT2 + RT3 LOOPBACK 0 n/a + to N3 1 fe80:0001::RT3 + to N4 2 fe80:0002::RT3 + RT4 LOOPBACK 0 n/a + to N3 1 fe80:0001::RT4 + RT5 to N4 1 fe80:0002::RT5 + + Table 3: OSPF interface IDs and link-local addresses + + + + + + + + + + + + + + + + + +Ogier & Spagnolo Experimental [Page 59] + +RFC 5614 MANET Extension of OSPF August 2009 + + +A.4.1. Router-LSAs + + As an example, consider the router-LSA that node RT3 would originate. + The node consists of one MANET, one broadcast, and one loopback + interface. + + RT3's router-LSA + + LS age = DoNotAge+0 ;newly originated + LS type = 0x2001 ;router-LSA + Link State ID = 0 ;first fragment + Advertising Router = 192.1.1.3 ;RT3's Router ID + bit E = 0 ;not an AS boundary router + bit B = 1 ;area border router + Options = (V6-bit|E-bit|R-bit) + Type = 1 ;p2p link to RT1 + Metric = 1 ;cost to RT1 + Interface ID = 1 ;Interface ID + Neighbor Interface ID = 1 ;Interface ID + Neighbor Router ID = 192.1.1.1 ;RT1's Router ID + Type = 1 ;p2p link to RT2 + Metric = 1 ;cost to RT2 + Interface ID = 1 ;Interface ID + Neighbor Interface ID = 1 ;Interface ID + Neighbor Router ID = 192.1.1.2 ;RT2's Router ID + Type = 1 ;p2p link to RT4 + Metric = 1 ;cost to RT4 + Interface ID = 1 ;Interface ID + Neighbor Interface ID = 1 ;Interface ID + Neighbor Router ID = 192.1.1.4 ;RT4's Router ID + Type = 2 ;connects to N4 + Metric = 1 ;cost to N4 + Interface ID = 2 ;RT3's Interface ID + Neighbor Interface ID = 1 ;RT5's Interface ID (elected DR) + Neighbor Router ID = 192.1.1.5 ;RT5's Router ID (elected DR) + + + + + + + + + + + + + + + + +Ogier & Spagnolo Experimental [Page 60] + +RFC 5614 MANET Extension of OSPF August 2009 + + +A.4.2. Link-LSAs + + Consider the link-LSA that RT3 would originate for its MANET + interface. + + RT3's link-LSA for its MANET interface + + LS age = DoNotAge+0 ;newly originated + LS type = 0x0008 ;Link-LSA + Link State ID = 1 ;Interface ID + Advertising Router = 192.1.1.3 ;RT3's Router ID + RtrPri = 1 ;default priority + Options = (V6-bit|E-bit|R-bit) + Link-local Interface Address = fe80:0001::RT3 + # prefixes = 0 ;no global unicast address + +A.4.3. Intra-Area-Prefix-LSAs + + A MANET node originates an intra-area-prefix-LSA to advertise its own + prefixes, and those of its attached networks or stub links. As an + example, consider the intra-area-prefix-LSA that RT3 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 + Advertising Router = 192.1.1.3 ;RT3'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.1.1.3 ;RT2's Router ID + PrefixLength = 64 ;prefix on RT3's LOOPBACK + PrefixOptions = 0 + Metric = 0 ;cost of RT3's LOOPBACK + Address Prefix = 5f00:0003::/64 + PrefixLength = 56 ;prefix on RT3's interface 2 + PrefixOptions = 0 + Metric = 1 ;cost of RT3's interface 2 + Address Prefix = 5f00:0000:c001:0400::RT3/56 ;pad + + + + + + + + + + + +Ogier & Spagnolo Experimental [Page 61] + +RFC 5614 MANET Extension of OSPF August 2009 + + +Appendix B. Detailed Algorithms for MDR/BMDR Selection + + This section provides detailed algorithms for Step 2.4 of Phase 2 + (MDR selection) and Step 3.2 of Phase 3 (BMDR selection) of the MDR + selection algorithm described in Section 5. Step 2.4 uses a breadth- + first search (BFS) algorithm, and Step 3.2 uses an efficient + algorithm for finding pairs of node-disjoint paths from Rmax to all + other neighbors. Both algorithms run in O(d^2) time, where d is the + number of neighbors. + + For convenience, in the following description, the term "bi-neighbor" + will be used as an abbreviation for "bidirectional neighbor". Also, + node i denotes the router performing the calculation. + +B.1. Detailed Algorithm for Step 2.4 (MDR Selection) + + The following algorithm performs Step 2.4 of the MDR selection + algorithm, and assumes that Phase 1 and Steps 2.1 through 2.3 have + been performed, so that the neighbor connectivity matrix NCM has been + computed and Rmax is the bi-neighbor with the (lexicographically) + largest value of (RtrPri, MDR Level, RID). The BFS algorithm uses a + FIFO queue so that all nodes 1 hop from node Rmax are processed + first, then 2 hops, etc. When the BFS algorithm terminates, hops(u), + for each bi-neighbor node u of node i, will be equal to the minimum + number of hops from node Rmax to node u, using only intermediate + nodes that are bi-neighbors of node i and that have a larger value of + (RtrPri, MDR Level, RID) than node i. The algorithm also computes, + for each node u, the tree parent p(u) and the second node r(u) on the + tree path from Rmax to u, which will be used in Step 3.2. + + (a) Compute a matrix of link costs c(u,v) for each pair of bi- + neighbors u and v as follows: If node u has a larger value of + (RtrPri, MDR Level, RID) than node i, and NCM(u,v) = 1, then set + c(u,v) to 1. Otherwise, set c(u,v) to infinity. (Note that the + matrix NCM(u,v) is symmetric, but the matrix c(u,v) is not.) + + (b) Set hops(u) = infinity for all bi-neighbors u other than Rmax, + and set hops(Rmax) = 0. Initially, p(u) is undefined for each + neighbor u. For each bi-neighbor u such that c(Rmax,u) = 1, set + r(u) = u; for all other u, r(u) is initially undefined. Add + node Rmax to the FIFO queue. + + (c) While the FIFO queue is nonempty: Remove the node at the head + of the queue; call it node u. For each bi-neighbor v of node i + such that c(u,v) = 1: + If hops(v) > hops(u) + 1, then set hops(v) = hops(u) + 1, set + p(v) = u, set r(v) = r(u) if hops(v) > 1, and add node v to + the tail of the queue. + + + +Ogier & Spagnolo Experimental [Page 62] + +RFC 5614 MANET Extension of OSPF August 2009 + + +B.2. Detailed Algorithm for Step 3.2 (BMDR Selection) + + Step 3.2 of the MDR selection algorithm requires the router to + determine whether there exist two node-disjoint paths from Rmax to + each other bi-neighbor u, via bi-neighbors that have a larger value + of (RtrPri, MDR Level, RID) than the router itself. This information + is needed to determine whether the router should select itself as a + BMDR. + + It is possible to determine separately for each bi-neighbor u whether + there exist two node-disjoint paths from Rmax to u, using the well- + known augmenting path algorithm [Lawler] that runs in O(n^2) time, + but this must be done for all bi-neighbors u, thus requiring a total + run time of O(n^3). The algorithm described below makes the same + determination simultaneously for all bi-neighbors u, achieving a much + faster total run time of O(n^2). The algorithm is a simplified + variation of the Suurballe-Tarjan algorithm [Suurballe] for finding + pairs of disjoint paths. + + The algorithm described below uses the following output of Phase 2: + the tree parent p(u) of each node (which defines the BFS tree + computed in Phase 2), and the second node r(u) on the tree path from + Rmax to u. + + The algorithm uses the following concepts. For any node u on the BFS + tree other than Rmax, we define g(u) to be the first labeled node on + the reverse tree path from u to Rmax, if such a labeled node exists + other than Rmax. (The reverse tree path consists of u, p(u), + p(p(u)), ..., Rmax.) If no such labeled node exists, then g(u) is + defined to be r(u). In particular, if u is labeled then g(u) = u. + Note that g(u) either must be labeled or must be a neighbor of Rmax. + + For any node k that either is labeled or is a neighbor of Rmax, we + define the unlabeled subtree rooted at k, denoted S(k), to be the set + of nodes u such that g(u) = k. Thus, S(k) includes node k itself and + the set of unlabeled nodes downstream of k on the BFS tree that can + be reached without going through any labeled nodes. This set can be + obtained in linear time using a depth-first search starting at node + k, and using labeled nodes to indicate the boundaries of the search. + Note that g(u) and S(k) are not maintained as variables in the + algorithm given below, but simply refer to the definitions given + above. + + The BMDR algorithm maintains a set B, which is initially empty. A + node u is added to B when it is known that two node-disjoint paths + exist from Rmax to u via nodes that have a larger value of (RtrPri, + MDR Level, RID) than the router itself. When the algorithm + terminates, B consists of all nodes that have this property. + + + +Ogier & Spagnolo Experimental [Page 63] + +RFC 5614 MANET Extension of OSPF August 2009 + + + The algorithm consists of the following two steps. + + (a) Mark Rmax as labeled. For each pair of nodes u, v on the BFS + tree other than Rmax such that r(u) is not equal to r(v) (i.e., u + and v have different second nodes), NCM(u,v) = 1, and node u has + a greater value of (RtrPri, MDR level, RID) than the router + itself, add v to B. (Clearly there are two disjoint paths from + Rmax to v.) + + (b) While there exists a node in B that is not labeled, do the + following. Choose any node k in B that is not labeled, and let j + = g(k). Now mark k as labeled. (This creates a new unlabeled + subtree S(k), and makes S(j) smaller by removing S(k) from it.) + For each pair of nodes u, v such that u is in S(k), v is in S(j), + and NCM(u,v) = 1: + + o If u has a larger value of (RtrPri, MDR level, RID) than the + router itself, and v is not in B, then add v to B. + + o If v has a larger value of (RtrPri, MDR level, RID) than the + router itself, and u is not in B, then add u to B. + + A simplified version of the algorithm MAY be performed by omitting + step (b). However, the simplified algorithm will result in more + BMDRs, and is not recommended if AdjConnectivity = 2 since it will + result in more adjacencies. + + The above algorithm can be executed in O(n^2) time, where n is the + number of neighbors. Step (a) clearly requires O(n^2) time since it + considers all pairs of nodes u and v. Step (b) also requires O(n^2) + time because each pair of nodes is considered at most once. This is + because labeling nodes divides unlabeled subtrees into smaller + unlabeled subtrees, and a given pair u, v is considered only the + first time u and v belong to different unlabeled subtrees. + + + + + + + + + + + + + + + + + +Ogier & Spagnolo Experimental [Page 64] + +RFC 5614 MANET Extension of OSPF August 2009 + + +Appendix C. Min-Cost LSA Algorithm + + This section describes the algorithm for determining which MANET + neighbors to include in the router-LSA when LSAFullness is 1. The + min-cost LSA algorithm ensures that the link-state database provides + sufficient information to calculate at least one shortest (minimum- + cost) path to each destination. The algorithm assumes that a router + may have multiple interfaces, at least one of which is a MANET + interface. The algorithm becomes significantly simpler if the router + has only a single (MANET) interface. + + The input to this algorithm includes information obtained from Hellos + received from each neighbor on each MANET interface, including the + neighbor's Bidirectional Neighbor Set (BNS), Dependent Neighbor Set + (DNS), Selected Advertised Neighbor Set (SANS), and link metrics. + The input also includes the link-state database if the router has a + non-MANET interface. + + The output of the algorithm is the router's SANS for each MANET + interface. The SANS is used to construct the router-LSA as described + in Section 9.4. The min-cost LSA algorithm must be run to update the + SANS (and possibly originate a new router-LSA) either periodically + just before sending each Hello, or whenever any of the following + events occurs: + + o The state or routability of a neighbor changes. + + o A Hello received from a neighbor indicates a change in its MDR + Level, Router Priority, FullHelloRcvd, BNS, DNS, SANS, Parent(s), + or link metrics. + + o An LSA originated by a non-MANET neighbor is received. + + Although the algorithm described below runs in O(d^3) time, where d + is the number of neighbors, an incremental version for a single + topology change runs in O(d^2) time, as discussed following the + algorithm description. + + For convenience, in the following description, the term "bi-neighbor" + will be used as an abbreviation for "bidirectional neighbor". Also, + router i will denote the router doing the calculation. To perform + the min-cost LSA algorithm, the following steps are performed. + + (1) Create the neighbor connectivity matrix (NCM) for each MANET + interface, as described in Section 5.1. Create the multiple- + interface neighbor connectivity matrix MNCM as follows. For each + bi-neighbor j, set MNCM(i,j) = MNCM(j,i) = 1. For each pair j, k + of MANET bi-neighbors, set MNCM(j,k) = 1 if NCM(j,k) equals 1 for + + + +Ogier & Spagnolo Experimental [Page 65] + +RFC 5614 MANET Extension of OSPF August 2009 + + + any MANET interface. For each pair j, k of non-MANET bi- + neighbors, set MNCM(j,k) = 1 if the link-state database indicates + that a direct link exists between j and k. Otherwise, set + MNCM(j,k) = 0. (Note that a given router can be a neighbor on + both a MANET interface and a non-MANET interface.) + + (2) Create the inter-neighbor cost matrix (COST) as follows. For + each pair j, k of routers such that each of j and k is a bi- + neighbor or router i itself: + + (a) If MNCM(j,k) = 1, set COST(j,k) to the metric of the link + from j to k obtained from j's Hellos (for a MANET interface), + or from the link-state database (for a non-MANET interface). + If there are multiple links from j to k (via multiple + interfaces), COST(j,k) is set to the minimum cost of these + links. + + (b) Otherwise, set COST(j,k) to LSInfinity. + + (3) Create the backbone neighbor matrix (BNM) as follows. BNM + indicates which pairs of MANET bi-neighbors are backbone + neighbors of each other, as defined in Section 9.2.1. If + adjacency reduction is not used (AdjConnectivity = 0), set all + entries of BNM to zero and proceed to Step 4. + + In the following, if a link exists from router j to router k on + more than one interface, we consider only interfaces for which + the cost from j to k equals COST(j,k); such interfaces will be + called "candidate" interfaces. + + For each pair j, k of MANET bi-neighbors, BNM(j,k) is set to 1 if + j and k are backbone neighbors of each other on a candidate MANET + interface. That is, BNM(j,k) is set to 1 if, for any candidate + MANET interface, NCM(j,k) = 1 and either of the following + conditions is satisfied: + + (a) Router k is included in j's DNS or router j is included in + k's DNS. + + (b) Router j is the (Backup) Parent of router k or router k is + the (Backup) Parent of router j. + + Otherwise, BNM(j,k) is set to 0. + + (4) Create the Selected Advertised Neighbor Matrix (SANM) as follows. + For each pair j, k of routers such that each of j and k is a bi- + neighbor or router i itself, SANM(j,k) is set to 1 if, for any + + + + +Ogier & Spagnolo Experimental [Page 66] + +RFC 5614 MANET Extension of OSPF August 2009 + + + candidate MANET interface, NCM(j,k) = 1 and k is included in j's + SANS. Otherwise, SANM(j,k) is set to 0. Note that SANM(i,k) is + set to 1 if k is currently a Selected Advertised Neighbor. + + (5) Compute the new set of Selected Advertised Neighbors as follows. + For each MANET bi-neighbor j, initialize the bit variable + new_sel_adv(j) to 0. (This bit will be set to 1 if j is + selected.) For each MANET bi-neighbor j: + + (a) If j is a bi-neighbor on more than one interface, consider + only candidate interfaces (for which the cost to j is + minimum). If one of the candidate interfaces is a non-MANET + interface, examine the next neighbor (j is not selected since + it will be advertised anyway). + + (b) If adjacency reduction is used, and one of the candidate + interfaces is a MANET interface on which j is a backbone + neighbor (see Section 9.2), examine the next neighbor (j is + not selected since it will be advertised anyway). + + (c) Otherwise, if there is more than one candidate MANET + interface, select the "preferred" interface by using the + following preference rules in the given order: an interface + is preferred if (1) router i's SANS for that interface + already includes j, (2) router i's Router Priority is larger + on that interface, and (3) router i's MDR Level is larger on + that interface. + + (d) For each bi-neighbor k (on any interface) such that COST(k,j) + > COST(k,i) + COST(i,j), determine whether there exists + another bi-neighbor u such that either COST(k,u) + COST(u,j) + < COST(k,i) + COST(i,j), or COST(k,u) + COST(u,j) = COST(k,i) + + COST(i,j) and either of the following conditions is true: + + o BNM(u,j) = 1, or + + o (SANM(j,u), SANM(u,j), RtrPri(u), RID(u)) is + lexicographically greater than (SANM(j,i), SANM(i,j), + RtrPri(i), RID(i)). + + If for some such bi-neighbor k, there does not exist such a bi- + neighbor u, then set new_sel_adv(j) = 1. + + (6) For each MANET interface I, update the SANS to equal the set of + all bi-neighbors j such that new_sel_adv(j) = 1 and I is the + preferred interface for j. + + + + + +Ogier & Spagnolo Experimental [Page 67] + +RFC 5614 MANET Extension of OSPF August 2009 + + + (7) With the SANS updated, a new router-LSA may need to be originated + as described in Section 9.4. + + The lexicographical comparison of Step 5d gives preference to links + that are already advertised, in order to improve LSA stability. + + The above algorithm can be run in O(d^2) time if a single link change + occurs. For example, if link (x,y) fails where x and y are neighbors + of router i, and either SANS(x,y) = 1 or BNM(x,y) = 1, then Step 5 + need only be performed for pairs j, k such that either j or k is + equal to x or y. + +Appendix D. Non-Ackable LSAs for Periodic Flooding + + In a highly mobile network, it is possible that a router almost + always originates a new router-LSA every MinLSInterval seconds. In + this case, it should not be necessary to send Acks for such an LSA, + or to retransmit such an LSA as a unicast, or to describe such an LSA + in a DD packet. In this case, the originator of an LSA MAY indicate + that the router-LSA is "non-ackable" by setting the L bit in the + options field of the LSA (see Section A.1). For example, a router + can originate non-ackable LSAs if it determines (e.g., based on an + exponential moving average) that a new LSA is originated every + MinLSInterval seconds at least 90 percent of the time. (Simulations + can be used to determine the best threshold.) + + A non-ackable LSA is never acknowledged, nor is it ever retransmitted + as a unicast or described in a DD packet, thus saving substantial + overhead. However, the originating router must periodically + retransmit the current instance of its router-LSA as a multicast + (until it originates a new LSA, which will usually happen before the + previous instance is retransmitted), and each MDR must periodically + retransmit each non-ackable LSA as a multicast (until it receives a + new instance of the LSA, which will usually happen before the + previous instance is retransmitted). For this option to work, + RxmtInterval must be larger than MinLSInterval so that a new instance + of the LSA is usually received before the previous one is + retransmitted. Note that the reception of a retransmitted + (duplicate) LSA does not result in immediate forwarding of the LSA; + only a new LSA (with a larger sequence number) may be forwarded + immediately, according to the flooding procedure of Section 8. + + + + + + + + + + +Ogier & Spagnolo Experimental [Page 68] + +RFC 5614 MANET Extension of OSPF August 2009 + + +Appendix E. Simulation Results + + This section presents simulation results that predict the performance + of OSPF-MDR for up to 160 nodes with min-cost LSAs and up to 200 + nodes with minimal LSAs. The results were obtained using the GTNetS + simulator with OSPF-MDR version 1.01, available at + http://hipserver.mct.phantomworks.org/ietf/ospf. + + The following scenario parameter values were used: radio range = 200 + m and 250 m, grid length = 500 m, wireless alpha = 0.5, (maximum) + velocity = 10 m/s, pause time = 0, packet rate = 10 pkts/s, packet + size = 40 bytes, random seed = 8, start time (for gathering + statistics) = 1800 s. The stop time was 3600 s for up to 80 nodes + and 2700 s for more than 80 nodes. The source and destination are + selected randomly for each generated UDP packet. The simulated MAC + protocol is 802.11b. + + Tables 4 and 6 show the results for the default configuration of + OSPF-MDR, except that differential Hellos were used (2HopRefresh = 3) + since they are recommended when the number of neighbors is large. + Tables 5 and 7 show the results for the same configuration except + that minimal LSAs were used instead of min-cost LSAs. The tables + show the results for total OSPF overhead in kb/s, the total number of + OSPF packets per second, the delivery ratio for UDP packets, and the + average number of hops traveled by UDP packets that reach their + destination. + + Tables 5 and 7 for minimal LSAs also show the following statistics: + the average number of bidirectional neighbors per node, the average + number of fully adjacent neighbors per node, the number of changes in + the set of bidirectional neighbors per node per second, and the + number of changes in the set of fully adjacent neighbors per node per + second. These statistics do not change significantly when min-cost + LSAs are used instead of minimal LSAs. + + The results show that OSPF-MDR achieves good performance for up to at + least 160 nodes when min-cost LSAs are used, and up to at least 200 + nodes when minimal LSAs are used. Also, the results for the number + of hops show that the routes obtained with minimal LSAs are only 2.3% + to 4.5% longer than with min-cost LSAs when the range is 250 m, and + 3.5% to 7.4% longer when the range is 200 m. + + The results also show that the number of adjacencies per node and the + number of adjacency changes per node per second do not increase as + the number of nodes increases, and are dramatically smaller than the + number of neighbors per node and the number of neighbor changes per + node per second, respectively. These factors contribute to the low + overhead achieved by OSPF-MDR. For example, the results in Table 5 + + + +Ogier & Spagnolo Experimental [Page 69] + +RFC 5614 MANET Extension of OSPF August 2009 + + + imply that with 200 nodes and range 250 m, there are 2.136/.039 = 55 + times as many adjacency formations with full-topology adjacencies as + with uniconnected adjacencies. Additional simulation results for + OSPF-MDR can be found at http://www.manet-routing.org. + + Number of nodes + 20 40 60 80 100 120 160 + ------------------------------------------------------------------ + OSPF kb/s 27.1 74.2 175.3 248.6 354.6 479.2 795.7 + OSPF pkts/s 29.9 69.2 122.9 163.7 210.3 257.2 357.7 + Delivery ratio .970 .968 .954 .958 .957 .956 .953 + Avg no. hops 1.433 1.348 1.389 1.368 1.411 1.361 1.386 + + Table 4: Results for range 250 m with min-cost LSAs + + + Number of nodes + 20 40 60 80 120 160 200 + ------------------------------------------------------------------ + OSPF kb/s 15.5 41.6 91.0 132.9 246.3 419.0 637.4 + OSPF pkts/sec 18.8 42.5 78.6 102.8 166.8 245.6 321.0 + Delivery ratio .968 .968 .951 .953 .962 .956 .951 + Avg no. hops 1.466 1.387 1.433 1.412 1.407 1.430 1.411 + Avg no. nbrs/node 11.38 25.82 36.30 50.13 75.87 98.65 125.59 + Avg no. adjs/node 2.60 2.32 2.38 2.26 2.25 2.32 2.13 + Nbr changes/node/s .173 .372 .575 .752 1.223 1.654 2.136 + Adj changes/node/s .035 .036 .046 .040 .032 .035 .039 + + Table 5: Results for range 250 m with minimal LSAs + + + Number of nodes + 20 40 60 80 100 120 160 + ------------------------------------------------------------------ + OSPF kb/s 40.5 123.4 286.5 415.7 597.5 788.9 1309.8 + OSPF pkts/s 37.6 83.9 135.1 168.6 205.4 247.7 352.3 + Delivery ratio .926 .919 .897 .900 .898 .895 .892 + Avg no. hops 1.790 1.628 1.666 1.632 1.683 1.608 1.641 + + Table 6: Results for range 200 m with min-cost LSAs + + + + + + + + + + + +Ogier & Spagnolo Experimental [Page 70] + +RFC 5614 MANET Extension of OSPF August 2009 + + + Number of nodes + 20 40 60 80 120 160 200 + ------------------------------------------------------------------ + OSPF kb/s 24.0 63.6 140.6 195.2 346.9 573.2 824.6 + OSPF pkts/sec 26.4 58.8 108.3 138.8 215.2 311.3 401.3 + Delivery ratio .930 .927 .897 .907 .907 .904 .902 + Avg no. hops 1.853 1.714 1.771 1.743 1.727 1.758 1.747 + Avg no. nbrs/node 7.64 18.12 25.27 35.29 52.99 68.13 86.74 + Avg no. adjs/node 2.78 2.60 2.70 2.50 2.39 2.36 2.24 + Nbr changes/node/s .199 .482 .702 .959 1.525 2.017 2.611 + Adj changes/node/s .068 .069 .081 .068 .055 .058 .057 + + Table 7: Results for range 200 m with minimal LSAs + +Authors' Addresses + + Richard G. Ogier + SRI International + + EMail: rich.ogier@earthlink.net or rich.ogier@gmail.com + + + Phil Spagnolo + Boeing Phantom Works + + EMail: phillipspagnolo@gmail.com + + + + + + + + + + + + + + + + + + + + + + + + + +Ogier & Spagnolo Experimental [Page 71] + |