RFC 5614

Mobile Ad Hoc Network (MANET) Extension of OSPF Using Connected Dominating Set (CDS) Flooding

📅 published August 2009, from ietf

RFC 5614: Mobile Ad Hoc Network (MANET) Extension of OSPF Using Connected Dominating Set (CDS) Flooding ✨

okay bestie, title block time 💖 This one is an Experimental doc from the Network Working Group, dated August 2009. The authors are R. Ogier (SRI International) and P. Spagnolo (Boeing). The title block doesn't list any RFCs it obsoletes or updates, so it doesn't replace or change anything else. 🎀

Abstract 🦋

okay so this doc is an extension of OSPFv3 for mobile ad hoc networks (MANETs) 🛰️ it's called OSPF-MDR and it's a brand new OSPF interface type made for MANETs 💅

the big idea: pick a subset of the MANET routers to be MANET Designated Routers (MDRs) and Backup MDRs. the MDRs form a connected dominating set (CDS), and the MDRs plus Backup MDRs together form a biconnected CDS for robustness 🔥

the CDS gets used in two ways, and it's giving efficiency:

First, flooding gets cheaper ✨ with an optimized flooding procedure, only (Backup) MDRs flood new link state advertisements (LSAs) back out the interface they came in on. reliable flooding still happens because LSAs get retransmitted along adjacencies 🫶

Second, adjacencies are only formed between (Backup) MDRs and a subset of their neighbors. that means way better scaling in dense networks 🌸

the CDS is built using 2-hop neighbor info carried in a Hello protocol extension 🧚 and the Hello protocol gets even better because it can send differential Hellos that only report changes in neighbor states 💜

last thing: you can originate router-LSAs with full or partial topology information. advertise less topology, and the overhead drops 😭👑

Status of This Memo 🌈

this memo defines an Experimental Protocol for the Internet community. it's not an Internet standard of any kind 🙈 discussion and suggestions for improvement are welcome, so go for it 💅 and distribution of this memo is unlimited ✨

Copyright Notice 💜

this document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents as they stand on the publication date. the details live at http://trustee.ietf.org/license-info, and you should really read them because they spell out your rights and restrictions 🫶

here's the tea 🍵 this doc might include material from IETF Documents or IETF Contributions that were published or made public before November 10, 2008. the people who control the copyright in some of that material may not have given the IETF Trust permission to allow changes to it outside the IETF Standards Process 😭

so unless you get an adequate license from whoever controls that copyright, this document can't be modified outside the IETF Standards Process, and derivative works can't be made outside it either. the one exceptions: formatting it for publication as an RFC, or translating 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

   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

1. Introduction 🦋

okay, the intro! this doc extends OSPFv3 [RFC5340] to support a new interface type for mobile ad hoc networks (MANETs) 🛰️ that means broadcast-capable, multihop wireless networks where the routers and hosts can move around 🏃‍♀️💨

quick note: OSPFv3 is specified by describing the changes made to OSPFv2 [RFC2328] 📝 and this MANET extension of OSPFv3 also works for non-mobile mesh networks that use layer-3 routing 🌸 it doesn't stop you from using any existing OSPF interface types, and it's fully compatible with legacy OSPFv3 implementations 🫶

why do we even need this? 😭 existing OSPF interface types don't perform well in MANETs, for a few reasons:

the flooding protocol has scaling issues
the Designated Router election protocol can't converge in every scenario
point-to-multipoint interface types end up with a huge number of adjacencies

so the approach is to generalize the OSPF Designated Router (DR) and Backup DR idea for multihop wireless networks 💅 this cuts overhead by reducing the number of routers that have to flood new LSAs, and by reducing the number of adjacencies. the generalized roles 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, every router in the MANET is either part of the CDS or one hop away from it 🧚 a distributed algorithm picks the biconnected CDS and keeps it up to date as things change 🔄

adjacencies only form between (Backup) MDRs and a subset of their neighbors 🎀 compare that to forming adjacencies between every neighbor pair, and the number of adjacencies in dense networks drops dramatically 🔥 the OSPF extension is called OSPF-MDR 💖

next, the Hello packets get modified using OSPF link-local signaling (LLS; see [RFC5613]) for two reasons 💜

to give neighbors the 2-hop neighbor information that the MDR selection algorithm needs
to allow differential Hellos that only report changes in neighbor states

differential Hellos can be sent more often without a big jump in overhead, which means the network can respond faster to topology changes ⚡

Also, each MANET router advertises a subset of its MANET neighbors as point-to-point links in its router-LSA 🦋 which neighbors get advertised is flexible, so you can cut overhead by advertising less topology information 🌷 and yep, there are options for originating router-LSAs that give full or partial topology information 🫶

here's the roadmap 🗺️ Section 2 gives an overview of OSPF-MDR. Section 3 covers the new interface and neighbor data items the extension needs. Section 4 describes the Hello protocol, including how the 2-hop neighbor information gets maintained. Section 5 describes the MDR selection algorithm. Section 6 describes changes to the Interface state machine. Section 7 describes how adjacencies get formed and how it's decided which neighbors should become adjacent. Section 8 describes the flooding procedure. Section 9 specifies the requirements and options for the contents of router-LSAs. Section 10 describes changes to how the routing table is calculated 🧠💅

the appendices are the extra goodies 🎁 they cover packet formats, detailed algorithms for MDR selection, and an algorithm for choosing which subset of neighbors to advertise in the router-LSA so you get shortest-path routing 🛣️ there's also a proposed option that uses non-ackable LSAs for periodic flooding without the overhead of Link State Acknowledgments 🙈 and finally, simulation results predicting how OSPF-MDR performs in mobile networks with up to 200 nodes 📈

for more info and resources, check out 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].

Okay, so this doc also uses a bunch of special terms, and you need these to follow along 💅

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 talk to each other directly. 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. So lowkey efficient 😭

2-Hop Neighbor Information 🧚 This information specifies the bidirectional neighbors of each neighbor. The modified Hello protocol gives each MANET router 2-hop neighbor information, and that's what gets 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 deciding the set of adjacencies that must be formed. The set of MDRs forms a connected dominating set, and it's a generalization of the DR found in broadcast networks. Each router runs the MDR selection algorithm for each MANET interface to figure out whether it's an MDR, a Backup MDR, or neither for that interface. Main character energy 🎀

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. It's the backup squad 🔥

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.

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 stays routable as long as it stays bidirectional. Only routable and Full neighbors can be used as next hops in the SPF calculation, and they can be included in the router-LSA originated by the router. Queen behavior 👑

Non-Flooding MDR 🙈 A non-flooding MDR is an MDR that does not automatically flood received LSAs back out the receiving interface, but it does perform backup flooding like a BMDR. Some MDRs may declare themselves non-flooding in order to reduce flooding overhead. Less spam, more vibes 🦋

2. Overview 💖

This section gives you an overview of OSPF-MDR, including the motivation and rationale for some of the design choices. Let's gooo 🧚

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 OSPF's. 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, where the edges of the tree are the adjacencies and the interior (non-leaf) nodes of the tree are the generalized DRs, called MANET Designated Routers (MDRs). It's giving OSPF but make it wireless 📡✨

To give better robustness and a 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. So the resulting set of adjacencies doesn't always form a tree globally, but it looks like 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). Redundancy is everything 💅

The following subsections give an overview of each of the main features of OSPF-MDR, starting with a summary of how MDRs, BMDRs, and adjacencies are selected. Let's dive in 🫶

2.1. Selection of MDRs, BMDRs, Parents, and Adjacencies 🌈

The MDR selection algorithm is distributed. Each router selects itself as an MDR, a BMDR, or another router (called an "MDR Other") based on information about its one-hop neighborhood, which it gets 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) get preference for becoming MDRs. Ranking energy 👑

The MDR selection algorithm can be summarized like this. 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 controls the density of the MDR set, since the MDR set doesn't need to 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, so that the set of MDRs and the adjacencies between them form a connected backbone. Each non-MDR router selects an MDR neighbor called its Parent and becomes adjacent with it, which makes sure all routers are connected to the MDR backbone. 🦋

If the option of biconnected adjacencies is chosen (AdjConnectivity = 2), then extra adjacencies get selected so that the set of MDRs and BMDRs, and the adjacencies between them, form a biconnected backbone. In this case, each MDR Other selects an MDR/BMDR neighbor called its Backup Parent and becomes adjacent with it, in addition to its Parent. Double protection 🛡️✨

OSPF-MDR also gives you 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) lets neighboring routers agree on which routers should become an MDR, and it gives higher priority to existing MDRs, which increases the lifetime of MDRs and the adjacencies between them. On top of that, Parents are selected to be existing adjacent neighbors whenever possible, so new adjacencies only form when they really need to. Once a neighbor becomes adjacent, it stays 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 rules above cut down the rate at which new adjacencies form, which matters a lot because database exchange has to happen every time a new adjacency forms. Stability is the whole mood 🥹💜

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). Delayed flooding is useful for coalescing multiple LSAs in the same Link State Update packet, and it can reduce the chance of a collision when multiple MDRs received the same LSA at the same time. Still, 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. Backup squad doing its thing 🛟

MDR Other routers never flood LSAs back out the receiving interface. To use 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. No duplicate energy here 🙅‍♀️✨

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 so that multiple acknowledgments can be coalesced into 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. Acks with a purpose 🫶💜

2.4. Routable Neighbors ✨

Okay so, in OSPF a neighbor usually has to be fully adjacent (in state Full) before it can be used in the SPF calculation 🧠. There's one exception, and it's for OSPF broadcast networks. Otherwise every pair of routers on a broadcast network would have to form an adjacency, which would make a huge pile of overhead 😭. On a broadcast 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 call this neighbor relationship a "routable neighbor," and we're extending it to the MANET interface type 🦋.

A MANET neighbor becomes routable if it is bidirectional and the SPF calculation has already produced a route to it 💖. (A flexible quality condition may also be required, bestie 👀.) Only routable and Full neighbors can be used as next hops in the SPF calculation, and they can be included in the router-LSA that the router originates ✨. The whole idea is that if SPF already found a route to the neighbor, then it makes total sense to take a "shortcut" and forward packets straight to that neighbor 🏃‍♀️💨.

The routability condition is basically a generalization of how neighbors on broadcast networks are treated in the SPF calculation 💅. A broadcast network's network-LSA already implies that a router can use a non-adjacent neighbor as a next hop. But a network-LSA can't describe the general topology of a MANET 🙈, so non-adjacent neighbors have to be included explicitly in the router-LSA. If we only allowed adjacent neighbors in LSAs, we'd either get suboptimal routes or need a massive number of adjacencies. Neither is it, honestly 💀.

2.5. Partial and Full Topology LSAs 🌈

OSPF-MDR lets routers originate two kinds of LSAs. Full-topology LSAs advertise links to all routable and Full neighbors, and partial-topology LSAs advertise only a subset of those links 🧚. In a dense network, partial-topology LSAs are typically much smaller than full-topology ones, which gives you way better scalability 📈🔥.

Each router advertises a subset of its neighbors as point-to-point links in its router-LSA. Which neighbors it picks 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 is called a minimal LSA, and it corresponds to LSAFullness = 0 🍓. This gives the least LSA flooding overhead, but it doesn't guarantee routing along shortest paths. Still, it's super useful for scaling to networks with a huge number of nodes 🌸.

At the other extreme, if LSAFullness = 4, the router originates a full-topology LSA that includes all routable and Full neighbors 👑.

Setting LSAFullness to 1 gives you min-cost LSAs, which route along shortest (minimum-cost) paths ⭐. Each router decides which neighbors to include in its router-LSA based on 2-hop neighbor information it learned from its neighbors' Hellos. It includes the minimum set of neighbors needed to provide a shortest path between each pair of its neighbors 🧩.

Setting LSAFullness to 2 also gives shortest-path routing, but it lets the router advertise additional neighbors so it has redundant routes 💜.

Setting LSAFullness to 3 gives you MDR full LSAs, where each MDR originates a full-topology LSA and everyone else originates minimal LSAs 🦋. This choice doesn't route along shortest paths, but simulations have shown it still gets routing along nearly shortest paths with relatively low overhead 📊✨.

The LSA options above are interoperable with each other, and here's why it works 💅: they all require the router-LSA to include a minimum set of neighbors, and the construction of the router-LSA (described in Section 9.4) makes sure the router-LSAs originated by different routers stay consistent 🫶. Routing along shortest paths is provided if and only if every router selects LSAFullness to be 1, 2, or 4 🔥.

2.6. Hello Protocol 💌

OSPF-MDR uses the same Hello format as OSPFv3, but it appends extra information to Hello packets using link-local signaling (LLS) 📡. That extra info indicates the set of bidirectional neighbors and other details used by the MDR selection algorithm and the min-cost LSA algorithm 🧠. On top of full Hellos, which include the same set of neighbor IDs as OSPFv3 Hellos, OSPF-MDR also allows differential Hellos. These only include the IDs of neighbors whose state (or other information) has recently changed, meaning within the last HelloRepeatCount Hellos 🌷.

Hellos are sent every HelloInterval seconds. Full Hellos go out 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 exist to cut down on overhead and to let Hellos go out more frequently, so the network can react faster to topology changes 🚀💖.

3. Interface and Neighbor Data Structures 🗂️

3.1. Changes to Interface Data Structure 🎀

Okay, so these 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, on top of the OSPF interface types defined in [RFC2328] 🌐.

State The possible states for a MANET interface are the same as for a broadcast interface. The difference is that the DR and Backup states now imply that the router is an MDR or Backup MDR, respectively 👑.

MDR Level The MDR Level equals 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 selection algorithm uses it 🧮.

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 router will be a neighboring MDR, if one exists 💜. The Parent is initialized to 0.0.0.0, which indicates 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, which indicates 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 the burden of being a (Backup) MDR gets 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 ✨

okay bestie, a MANET interface comes with some brand new configurable interface parameters, and they're required 🎀 no skipping! The defaults for HelloInterval, RouterDeadInterval, and RxmtInterval on a MANET interface are 2, 6, and 7 seconds, respectively 💖

The default setup for OSPF-MDR is giving uniconnected adjacencies (AdjConnectivity = 1) plus partial-topology LSAs that give you shortest-path routing (LSAFullness = 1) 👑 It's the most scalable config that still gives shortest-path routing, and other setups might be better in special situations. For example, LSAFullness set to 4 gives you full-topology LSAs, and LSAFullness set to 0 gives you minimal LSAs that keep overhead low but don't guarantee shortest-path routing 🧚 AdjConnectivity set to 2 may make things more robust by giving you a biconnected adjacency subgraph, and AdjConnectivity set to 0 gives you full-topology adjacencies 🌸

Every possible combo of the new interface parameters works, with one catch: 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 shrink Hello packets when the average number of neighbors is large (e.g., greater than 50) 🍓 You turn them on by setting 2HopRefresh to an integer greater than 1, and the recommended value is 3 ✨ The default config with differential Hellos did well in simulated mobile networks with up to 160 nodes 🦋 The same config but with minimal LSAs (LSAFullness = 0) did well with up to 200 nodes in simulated mobile networks 🔥 The simulation results are in Appendix E.

Ideally, all routers pick the same values for the new configurable interface parameters, but it's not required 🫶 OSPF-MDR was carefully designed so that routers still interoperate correctly even when each one sets these parameters on its own 💜

AdjConnectivity

If it's equal to the default value of 1, then the set of adjacencies forms a (uni)connected graph. If it's 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

This is a parameter of the MDR selection algorithm. It affects how many MDRs get selected and it must be an integer greater than or equal to 2 💖 The default of 3 gives you nearly the minimum number of MDRs. Values bigger than 3 give slightly fewer MDRs, and the value 2 gives you a bigger number of MDRs 🧁

BackupWaitInterval

This is how many seconds a Backup MDR waits after receiving a new LSA before it decides whether to flood that LSA ⏳ The default is 0.5 seconds.

AckInterval

This is the interval between Link State Acknowledgment packets when only delayed acknowledgments need to be sent. AckInterval MUST be less than RxmtInterval, and it SHOULD NOT be larger than 1 second 🙈 The default is 1 second.

LSAFullness

This decides which neighbors a router should advertise in its router-LSA 📣 The value 0 gives minimal LSAs that only include "backbone" neighbors. The values 1 and 2 give partial-topology LSAs that provide shortest-path routing, and the value 2 also gives redundant routes. The value 3 means MDRs originate full-topology LSAs and other routers originate minimal LSAs. The value 4 means all routers originate full-topology LSAs. The default is 1 👑

2HopRefresh

One out of every 2HopRefresh Hellos sent on the interface must be a full Hello, and all the other Hellos are differential. The default is 1, which means the default is to send only full Hellos. If differential Hellos are used, the recommended value of 2HopRefresh is 3 ✨

HelloRepeatCount

This is 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 moved to the Down state must be kept for at least HelloInterval * HelloRepeatCount seconds, so the state change can get 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)

This is the Hello sequence number in the last Hello received from the neighbor 🔢

A-bit

This is the A-bit copied from the MDR-Hello TLV of the last Hello received from the neighbor. The bit is 1 if the neighbor is using full-topology adjacencies, i.e., is not using adjacency reduction 🌸

FullHelloRcvd

This is a single-bit variable equal to 1 if a full Hello has been received from the neighbor 💜

Neighbor's MDR Level

This is the MDR Level of the neighbor. It's based on the DR and Backup DR fields of the last Hello packet received from the neighbor, or on the MDR-DD TLV in a Database Description (DD) packet received from the neighbor 🧚

Neighbor's Parent

This is the neighbor's choice for Parent. It comes 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

This is the neighbor's choice for Backup Parent. It comes 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

This is 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

This is a single-bit variable equal to 1 if the neighbor is a Dependent Neighbor, which the MDR selection algorithm decides. 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

This is a single-bit variable equal to 1 if the neighbor has selected the router to be dependent 🫶

Selected Advertised Neighbor (SAN)

This is a single-bit variable equal to 1 if the neighbor is a Selected Advertised Neighbor. Selected Advertised Neighbors are neighbors that the router has picked to include 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

This is a single-bit variable equal to 1 if the neighbor is routable 🛣️

Neighbor's Bidirectional Neighbor Set (BNS)

This is the neighbor's set of bidirectional neighbors, and it gets updated when a Hello is received from the neighbor 🔁

Neighbor's Dependent Neighbor Set (DNS)

This is the neighbor's set of Dependent Neighbors, and it gets updated when a Hello is received from the neighbor 💖

Neighbor's Selected Advertised Neighbor Set (SANS)

This is the neighbor's set of Selected Advertised Neighbors, and it gets updated when a Hello is received from the neighbor ✨

Neighbor's Link Metrics

This is the link metric for each of the neighbor's bidirectional neighbors, taken from the Metric TLV appended to Hello packets 📊

4. Hello Protocol 🦋

The MANET interface uses Hellos for neighbor discovery and for letting neighbors learn 2-hop neighbor information 🫧 The protocol is flexible because it allows full or differential Hellos. Full Hellos list all neighbors on the interface that are in state Init or greater, same as in OSPFv3 💅 Differential Hellos list only the neighbors whose status as a bidirectional neighbor, Dependent Neighbor, or Selected Advertised Neighbor has recently changed 🌸 Differential Hellos cut down on overhead, and they let Hellos be sent more often (for faster reactions to topology changes) ⚡ If differential Hellos are used, full Hellos are sent less often so that all neighbors keep current 2-hop neighbor information 💜

4.1. Sending Hello Packets ✨

Hello packets get sent following [RFC5340], Section 4.2.1.1 and [RFC2328], Section 9.5, and the MANET-specific stuff kicks in right after paragraph 3 of Section 9.5 🧚. The Hello packet format comes from [RFC5340], Section A.3.2, except the Neighbor IDs get ordered differently and the DR and Backup DR fields mean something new, as we'll see 💅.

Like [RFC2328], the DR and Backup DR fields tell everyone whether you're an MDR or a Backup MDR 👑. If you're an MDR, the DR field holds your own Router ID. If you're a Backup MDR, the Backup DR field holds your own Router ID. These fields also advertise your Parent and Backup Parent, as laid out in Section A.3 and Section 5.4 🫶.

Hellos go out every HelloInterval seconds. Full Hellos go out every 2HopRefresh Hellos, and differential Hellos fill in all the other times 🌸. For example, if 2HopRefresh is 3, then every third Hello is a full one. If 2HopRefresh is set to 1, then all Hellos are full (that's the default) ✨.

The neighbor IDs in the body of each Hello are split into the following five disjoint lists (some of which may be empty), and they must appear in this 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.

Lists 3 through 5 only ever hold bidirectional neighbors 🦋. These lists are what update the neighbor's Bidirectional Neighbor Set (BNS), Dependent Neighbor Set (DNS), and Selected Advertised Neighbor Set (SANS) when a Hello comes in.

Since the five lists are disjoint, each neighbor shows up in at most one list 🙈. Also, some or all of the five lists can be empty, so don't panic if you see that 🍓.

Link-local signaling (LLS) tacks up to two TLVs onto each MANET Hello packet 🎀. The LLS format is in Section A.2. The MDR-Hello TLV goes on every full and differential MANET Hello 💜. It says whether the Hello is full or differential, and it gives the Hello Sequence Number (HSN) plus the number of neighbor IDs in each of Lists 1 through 4. The size of List 5 is then implied by the packet length field of the Hello 🔥. The MDR-Hello TLV format is in Section A.2.3.

In both full and differential Hellos, the appended MDR-Hello TLV gets built like this 💅:

The Sequence Number field is set to the current HSN for the interface; the HSN is then incremented (modulo 2^16).
The D-bit of the MDR-Hello TLV is set to 1 for a differential Hello and 0 for a full Hello.
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.
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 📈. That's how the selection of neighbors to include in partial-topology LSAs happens ✨. If LSAFullness is 1 or 2, a Metric TLV must be appended to each MANET Hello packet unless all link costs are 1. The Metric TLV format is 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 it 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, bestie 🧚. The move is to set the I bit to 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, so you don't need to include neighbor IDs and their metrics in the TLV 🌈. At the other extreme, if all neighbors have different metrics, then the I bit should be set to 0, so you're not 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 ✨.

4.1.2. Differential Hello Packet

In a differential Hello, the five neighbor ID lists defined in Section 4.1 get 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.

On top of that, a bidirectional neighbor must be included (in the appropriate list) if the neighbor's BNS does not include the router (which means the neighbor doesn't 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 gets processed as described in [RFC5340], Section 4.2.2.1, and the first two paragraphs of [RFC2328], Section 10.5 🧚. After that, the processing specified below kicks in 💖.

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 can't be found in the interface's data structure, one gets created. Its Neighbor ID is set to the Router ID from the OSPF packet header, its state is initialized to Down, all MANET-specific neighbor variables (specified in Section 3.3) are initialized to zero, and its DNS, SANS, and BNS are 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 gets examined, generating events for 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 🔥.

If the L bit in the options field is not set, then an error has occurred and the Hello is discarded 🙅‍♀️.
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.
The Hello Sequence Number and the A-bit in the MDR-Hello TLV are copied to the neighbor's data structure.
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 gets divided up into the five lists defined in Section 4.1 🧩. N1, N2, N3, and N4 come from the corresponding fields of the MDR-Hello TLV. List 1 is the first N1 neighbor IDs, List 2 is the next N2 neighbor IDs, List 3 is the next N3 neighbor IDs, List 4 is the next N4 neighbor IDs, and List 5 is the remaining neighbor IDs in the Hello.

Further processing of the Hello depends on whether it's full or differential, which the D-bit of the MDR-Hello TLV tells you 🎀.

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 happen 🌸:

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.
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 🦋.
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 ✨

okay so if the received Hello is differential (the D-bit of the MDR-Hello TLV is 1), these steps happen 💅

(1) For each neighbor ID in List 1 or List 2 of the Hello:

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:

Add the neighbor ID to the neighbor's DNS and BNS, if it does not belong to the neighbor set.
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:

Add the neighbor ID to the neighbor's SANS and BNS, if it does not belong to the neighbor set.
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:

Add the neighbor ID to the neighbor's BNS, if it does not belong to the neighbor set.
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:

The neighbor's state changed from less than 2-Way to 2-Way or greater, or vice versa.
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:

The neighbor's state changed from less than 2-Way to 2-Way or greater.
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. 🧚

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 (RtrPri, MDR Level, RID) for each such neighbor and for the router itself, and the neighbor 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. 🛡️

⚠️ Phase 3 is a MUST when AdjConnectivity is 2, and a SHOULD when it's 0 or 1. Don't skip it unless you're in one of the cases where it's not required!

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". 🫧

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. 🥹💜

Phase 1 is basically the "who's friends with who" check, and I'm obsessed with how it trusts whoever actually reported their full list 🫶

5.2. Phase 2: MDR Selection 💅✨

okay so Phase 2 is where the MDR count gets decided 👑 It depends on MDRConstraint, and the default of 3 gives you almost the minimum number of MDRs, while 2 gives you more MDRs 🦋 If AdjConnectivity = 0 (full-topology adjacencies), the steps below change a bit: Dependent Neighbors just don't get selected 🙈

(2.1) The set of Dependent Neighbors starts out empty 🫶
(2.2) If the router has a bigger (RtrPri, MDR Level, RID) than all of its bi-neighbors, it selects itself as an MDR 🔥 Then it selects all of its MDR bi-neighbors as Dependent Neighbors. If AdjConnectivity = 2, it also selects all of its BMDR bi-neighbors as Dependent Neighbors. Then it skips ahead to Phase 4 💖
(2.3) Let Rmax be the bi-neighbor with the largest (RtrPri, MDR Level, RID) 👑
(2.4) Using NCM to figure out bi-neighbor connectivity, compute the minimum number of hops, written hops(u), from Rmax to each other bi-neighbor u. You can only use intermediate nodes that are bi-neighbors with a bigger (RtrPri, MDR Level, RID) than the router itself 🧚 If there's no path from Rmax to u, then hops(u) equals infinity. (See Appendix B for a detailed breadth-first search algorithm 🍓)
(2.5) If hops(u) is at most MDRConstraint for every bi-neighbor u, the router selects no Dependent Neighbors. Then it sets its MDR Level: if it's currently MDR, it becomes BMDR when Phase 3 is going to run, and MDR Other when Phase 3 isn't going to run 🌸 Otherwise, the MDR Level stays exactly the same ✨
(2.6) Else, the router sets its MDR Level to MDR and selects these as Dependent Neighbors: Rmax if it's an MDR or BMDR 💜 Each MDR bi-neighbor u where hops(u) is greater than MDRConstraint 💜 And if AdjConnectivity = 2, each BMDR bi-neighbor u where hops(u) is greater than MDRConstraint too 😭
(2.7) If steps 2.1 through 2.6 ended with the MDR Level changing to BMDR, or to MDR while AdjConnectivity is 1 or 2, then run steps 2.1 through 2.6 again 🔁 This is needed because changing the MDR Level can change both the Dependent Neighbors and the BFS tree. This step isn't required if the MDR selection algorithm runs periodically 🌈

Step 2.4 can use a BFS to compute min-hop paths from Rmax to every other bi-neighbor. The one tweak is that a bi-neighbor can only be an intermediate node if its (RtrPri, MDR Level, RID) is bigger than the router's own 💅 The detailed version, which runs in O(d^2) time, is in Appendix B 🫧

5.3. Phase 3: Backup MDR Selection 🦋

(3.1) If the MDR Level is MDR (after Phase 2 ran) and AdjConnectivity isn't 2, skip ahead to Phase 4 🏃‍♀️ (If the MDR Level is MDR and AdjConnectivity = 2, then Phase 3 can pick extra Dependent Neighbors to build a biconnected backbone 🎀)
(3.2) Using NCM to figure out bi-neighbor connectivity, check whether there are two node-disjoint paths from Rmax to each other bi-neighbor u. You can only use intermediate nodes that are bi-neighbors with a bigger (RtrPri, MDR Level, RID) than the router itself 🧠 (See Appendix B for the detailed algorithm ✨)
(3.3) If there are two such node-disjoint paths from Rmax to every other bi-neighbor u, 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 picked itself as an MDR in Phase 2 🌷 And if AdjConnectivity = 2, it adds these to the set of Dependent Neighbors: Rmax if it's an MDR or BMDR, plus each MDR/BMDR bi-neighbor u where Step 3.2 did not find two node-disjoint paths from Rmax to u 😭
(3.5) If steps 3.1 through 3.4 changed the MDR Level from MDR Other to BMDR, run Phases 2 and 3 again 🔄 This is needed because running Phase 2 again can flip the MDR Level to MDR. This step isn't required if the MDR selection algorithm runs periodically 💜

Step 3.2 can be done in O(d^2) time with the Appendix B algorithm. There's also a simplified version that's specified too, and it ends up with a larger number of BMDRs 🍓

5.4. Phase 4: Parent Selection 👑

Every router selects a Parent for each MANET interface 🧚 A non-MDR router's Parent will be a neighboring MDR, if one exists 💖 If you've picked biconnected adjacencies, then each MDR Other selects a Backup Parent. That'll be a neighboring MDR/BMDR if one exists that isn't the Parent 🫶 An MDR's Parent is always the router itself, and a BMDR's Backup Parent is always the router itself 🦋

The (Backup) Parent gets advertised in the (Backup) DR field of every Hello sent on the interface 📣 As Section 7.2 spells out, each router forms an adjacency with its Parent and Backup Parent, as long as they exist and are neighboring MDR/BMDRs 🌸

For a given MANET interface, Rmax is the router with the largest (RtrPri, MDR Level, RID) among all bidirectional neighbors, but only if that neighbor has a bigger (RtrPri, MDR Level, RID) than the router itself 🔥 Otherwise, Rmax is null 💀

If the calculating router picked itself as an MDR, then its Parent is itself, and its Backup Parent is Rmax. (This design choice was made because it performs slightly better than having no Backup Parent 🏆) If the router picked itself as a BMDR, then its Backup Parent is itself 🫧

If the calculating router is a BMDR or an MDR Other, its Parent is any adjacent neighbor that's an MDR, if one exists 💅 If no adjacent MDR neighbor exists, the Parent becomes Rmax 🌈 Giving preference to neighbors that are already adjacent helps avoid forming new adjacencies when possible ✨ Heads up: the Parent can temporarily be a non-MDR neighbor when no MDR neighbor exists. (This choice was also made for performance reasons 🎀)

If AdjConnectivity = 2 and the calculating router is an MDR Other, the Backup Parent is any adjacent neighbor that's an MDR or BMDR, other than the Parent we just picked above, if one exists 🦋 If no such adjacent neighbor exists, the Backup Parent is the bidirectional neighbor (excluding the selected Parent) with the largest (RtrPri, MDR Level, RID), if one exists 🍓 Otherwise, the Backup Parent is null 🙈

5.5. Phase 5: Optional Selection of Non-Flooding MDRs 🌙

A router that picked itself as an MDR MAY run the following steps to possibly declare itself a non-flooding MDR ✨ An MDR that doesn't run these steps is a flooding MDR by default 💜

(5.1) If the router has a bigger (RtrPri, MDR Level, RID) than all of its bi-neighbors, the router is a flooding MDR. Else, go on to Step 5.2 🫶
(5.2) Let Rmax be the bi-neighbor with the largest (RtrPri, MDR Level, RID) 👑
(5.3) Using NCM to figure out bi-neighbor connectivity, compute the minimum number of hops, written hops(u), from Rmax to each other bi-neighbor u. You can only use intermediate nodes that are MDR bi-neighbors with a smaller (RtrPri, RID) than the router itself 🧚 (This can be done with BFS, like in Step 2.4 🌸)
(5.4) If hops(u) is at most MDRConstraint for every bi-neighbor u, then the router is a non-flooding MDR. Else, it's a flooding MDR 💅

6. Interface State Machine 🎀

6.1. Interface States 🦋

No new states are defined for a MANET interface 🙌 But the DR and Backup states now mean the router is an MDR or a Backup MDR, respectively 💖 Here are the modified definitions that apply to MANET interfaces:

Waiting

In this state, the router learns neighbor information from the Hello packets it receives, but it isn't allowed to run the MDR selection algorithm until it leaves the Waiting state (when the Wait Timer expires) 🕰️ This stops unnecessary MDR selection changes that would come from incomplete neighbor information 😭 The Wait Timer lasts 2HopRefresh * HelloInterval seconds (the interval between full Hellos) 🍓

DR Other

The router has run the MDR selection algorithm and figured out that it's neither an MDR nor a Backup MDR 🌷

Backup

The router has selected itself as a Backup MDR 🫶

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 doesn't mean the router itself can't also be an MDR or Backup MDR 💅

The NeighborChange event gets replaced with the new interface variable MDRNeighborChange, which says the MDR selection algorithm has to run because the neighbor information changed (see Section 4.2.3) 🔁

6.3. Changes to Interface State Machine 🧚

This section covers the changes to the interface state machine for a MANET interface 🌈 The two state transitions below are for state-event pairs described in [RFC2328], but their action descriptions are modified because MDRs get picked instead of DRs 🎀 The [RFC2328] transition for the NeighborChange event is left out. Instead, the new interface variable MDRNeighborChange tells you when the MDR selection algorithm needs to run 💜 The BackupSeen transition doesn't apply to MANET interfaces, since that event is never invoked there 🙈 The Loopback and UnloopInd transitions stay 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 ✨

okay so forming and tearing down adjacencies on non-MANET interfaces stays exactly the same 🎀 Adjacency maintenance on a MANET interface needs changes to a few spots: the transitions in the neighbor state machine ([RFC2328], Section 10.3), deciding whether to become adjacent ([RFC2328], Section 10.4), sending DD packets ([RFC2328], Section 10.8), and receiving DD packets ([RFC2328], Section 10.6). The spec below only applies to the MANET interface 💅

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, following the rules in Section 7.2 🦋

An adjacency maintenance decision happens when any of these four events occur between a router and its neighbor. The decision gets made by running 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

this section lists the new transitions in the neighbor state machine 🧚

Down + HelloReceived: the new state depends on the action routine. If the neighbor acceptance condition is satisfied (see Section 4.3), the neighbor moves to Init and the Inactivity Timer starts. Otherwise, the neighbor just stays in Down 🌸
Init + 2-WayReceived: the new state is 2-Way. The action is to transition to neighbor state 2-Way ✨
2-Way + AdjOK?: the new state depends on the action routine. The router first decides whether an adjacency should be formed with the neighboring router (see Section 7.2). If not, the neighbor stays at 2-Way and nothing else happens 💅

Otherwise, the neighbor moves to ExStart and these actions run. 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 the event NegotiationDone runs, which moves the state to Exchange 🔥

Otherwise (negotiation isn't complete), the router increments the DD sequence number in the neighbor data structure. If this is the first time an adjacency has been attempted, the DD sequence number should be assigned a unique value (like the time of day clock). Then it declares itself master (sets the master/slave bit to master) and starts sending Database Description packets with the I, M, and MS bits set, the MDR-DD TLV included in an LLS, and the L bit set. This Database Description packet should be otherwise empty. It should be retransmitted at intervals of RxmtInterval until the next state is entered (see [RFC2328], Section 10.8) 🎀

ExStart or greater + AdjOK?: the new state depends on the action routine. The router checks whether the neighboring router should still be adjacent (see Section 7.3). If yes, there's no state change and nothing else is needed. Otherwise, the (possibly partially formed) adjacency must be destroyed 💀 The neighbor state transitions to 2-Way, and the Link state retransmission list, Database summary list, and Link state request list get cleared of LSAs 🫶

7.2. Whether to Become Adjacent

this is the method for deciding if an adjacency should be formed between neighbors in state 2-Way 🦋 The procedure doesn't depend on whether AdjConnectivity is 1 or 2, but the selection of Dependent Neighbors (by the MDR selection algorithm) does depend on AdjConnectivity.

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 these 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 stays in state 2-Way 🌈

7.3. Whether to Eliminate an Adjacency

this is how the router decides whether an existing adjacency should be torn down 😭 An existing adjacency is kept if any of these 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 gets 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 💖

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 in this section 🌸 The extra steps below run before the packet gets processed based on neighbor state in paragraph 3 of Section 10.6.

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 gets processed like this:
- (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.
If the neighbor state is Init, the neighbor event 2-WayReceived is executed.
If the MDR Level of the neighbor changed, the neighbor state machine is scheduled with the event AdjOK?.
If the neighbor's Child status has changed from 0 to 1, the neighbor state machine is scheduled with the event AdjOK?.
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?.

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 extra 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 cuts DD packet overhead 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 these three changes 🫶

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 👑
If the received LSA is the same instance as the database copy, the following actions run 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.
Step 8, which handles the case where the database copy of the LSA is more recent than the received LSA, is modified like this. 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 subsections that follow 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] 🦋

8.1. LSA Forwarding Procedure ✨

okay so when a new LSA gets 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 covers the MANET-specific changes, which are the modified steps that must be performed for each eligible MANET interface. Which interfaces count as eligible depends on the LSA's flooding scope, as described in [RFC5340], Section 4.5.2. Whenever an LSA gets flooded out a MANET interface, it goes inside an LSU packet that's sent to the multicast address AllSPFRouters 🦋. (Retransmitted LSAs are always unicast though, as specified in Section 8.3, so they're a different vibe 💀.)

Step 1 of [RFC2328], Section 13.3, is run for each eligible MANET interface with one tweak, so the new LSA lands on the Link State retransmission list for each appropriate adjacent neighbor 🧚. Step 1c gets replaced with the following action, so the LSA doesn't end up on the retransmission list for a neighbor that already acknowledged it:

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 figure out whether an Ack for the new LSA has come back from a neighbor, the router keeps an Acked LSA List for each adjacent neighbor, as described in Section 8.4 📝. When a new LSA comes in, 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.

Next up is the notion of a "covered" neighbor 👑. A neighbor k is 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 covered if the LSA was sent to the multicast address AllSPFRouters by a neighbor j on a broadcast interface where 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 decide whether the new LSA should get forwarded out that 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).

(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 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

Doing the optional Step 6 can seriously cut down flooding overhead if the LSA was received on a MANET or broadcast interface 🌸. Picture this: the LSA was received from the DR of a broadcast network that includes 100 routers, and 50 of those routers (not counting the DR) are also attached to a MANET. Say those 50 routers are neighbors of each other in the MANET, and each one has a MANET neighbor that isn't attached to the broadcast network (so it isn't 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 drops from 50 to just 1 (assuming that at most 1 of the 50 routers is an MDR) ✨ wild, right?

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) 🧹.

8.2. Sending Link State Acknowledgments

This section is all about how to send Link State Acknowledgments (LS Acks) on MANET interfaces 🫶. Section 13.5 of [RFC2328] remains unchanged for non-MANET interfaces, but it does not apply to MANET interfaces. To keep LS Ack overhead low and make the most of the broadcast nature of MANETs, all LS Ack packets sent on a MANET interface are multicast using the IP address AllSPFRouters. Also, 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 between a delayed and an 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.

The reason (Backup) MDRs send an immediate Ack when a retransmitted LSA is received is to try to stop 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, so the potential benefit does not justify the extra overhead that immediate Acks would add 💅.

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 ✨

okay so an LS Ack packet from an adjacent neighbor (anything in state Exchange or greater) gets processed the way [RFC2328] says in Section 13.7 of [RFC2328] 💅, plus some extra steps we're adding here. if the LS Ack comes from a neighbor in a lesser state than Exchange, it gets tossed 🗑️

every router keeps an Acked LSA List for each adjacent neighbor 🦋 it's where we track the LSA instances that neighbor has acknowledged but that we ourselves have not received yet. this is needed because, unlike [RFC2328], each router only acknowledges an LSA the first time it arrives as a multicast. so the list is basically the receipts we need to remember. iconic memory skills 🧠✨

if the neighbor that sent the LS Ack is in state Exchange or greater, we do the following for each LS Ack in the packet:

if the router doesn't have a database copy of the LSA being acknowledged, or its copy is less recent than the one being acknowledged, the LS Ack gets added to the Acked LSA List for the sending neighbor 📝
if the router has a database copy of the LSA being acknowledged, and that copy is the same instance being acknowledged, then we do this: for each MANET interface that has a BackupWait Neighbor List for the LSA (see Section 8.1), we remove the sending neighbor from that BackupWait Neighbor List if it's on it 🧹

9. Router-LSAs 🌸

okay this part is so pretty bestie 🥹 unlike the DR on an OSPF broadcast network, an MDR doesn't originate a network-LSA, because a network-LSA just can't describe the general topology of a MANET 🙅‍♀️ so instead, each router advertises a subset of its MANET neighbors as point-to-point links in its router-LSA. which neighbors go in there is flexible 💖 and whether or not adjacency reduction is in use, the router can originate either partial-topology or full-topology LSAs ✨

if adjacency reduction is used (AdjConnectivity is 1 or 2), then as a bare minimum, each router has to advertise a minimum set of "backbone" neighbors in its router-LSA 🦴 this minimum choice matches LSAFullness = 0. it gives the least LSA flooding overhead, but it doesn't give you routing along shortest paths 😬

so, to let routers calculate shortest paths without making every pair of neighboring routers along those paths adjacent (which would be super inefficient because it needs tons of adjacencies 🙃), a router-LSA can also advertise non-adjacent neighbors that meet a synchronization condition (described below) 🔥

to motivate this: OSPF already lets a non-adjacent neighbor be a next hop, as long as the router and the neighbor are on the same broadcast network and both are adjacent to the DR 🫶 a network-LSA for a broadcast network (which includes every router attached to it) means any attached router can forward packets directly to any other attached router. that's why the distance from the network to every attached router is zero in the graph built from the link-state database 🧚

but since a network-LSA can't describe the general topology of a MANET, the only way to advertise non-adjacent neighbors that can be used as next hops is to put them in the router-LSA. and to make sure those neighbors are synchronized enough, only "routable" neighbors are allowed in LSAs and as next hops in the SPF calculation 🔐

9.1. Routable Neighbors 🎀

if adjacency reduction is used, a bidirectional MANET neighbor becomes routable once the SPF calculation has found a route to it AND it meets the routable neighbor quality condition (defined below) 🛣️ since only routable and Full neighbors get advertised in router-LSAs, and adjacencies are picked to form a connected spanning subgraph, this means there is, or recently was, a path of full adjacencies from the router to that routable neighbor. the vibe is: if a routable neighbor is reachable through an acceptable path, it makes total sense to take a "shortcut" and forward packets straight to it 🏃‍♀️💨

this doesn't guarantee perfect synchronization, but simulations have shown it performs well in mobile networks 📈 it also avoids, for example, forwarding packets to a brand new neighbor that is poorly synchronized because it wasn't reachable before it became a neighbor 🙅‍♀️

to avoid picking poor-quality neighbors as routable ones, a neighbor that gets selected as routable has to meet the routable neighbor quality condition. by default, that condition is that the neighbor's BNS includes the router itself (basically, the neighbor agrees the connection is bidirectional) 🤝 a router may also impose a stricter condition if it wants. for example, it may require that two Hellos have been received from the neighbor that (explicitly or implicitly) indicate the neighbor's BNS includes the router itself 👀

the single-bit neighbor variable Routable tells you whether the neighbor is routable, and it starts out at 0 🔢 if adjacency reduction is used, Routable gets updated like this whenever the neighbor's state changes, or the SPF calculation finds a route to the neighbor, or a Hello comes in that affects the routable neighbor quality condition:

if Routable is 0 for the neighbor, the neighbor's state is 2-Way or greater, there's a route to the neighbor, and the routable neighbor quality condition (defined above) is satisfied, then Routable is set to 1 for the neighbor 🎉
if Routable is 1 for the neighbor and the neighbor's state is less than 2-Way, Routable is set to 0 for the neighbor 💔

if adjacency reduction is not used (AdjConnectivity = 0), then routable neighbors aren't computed and the set of routable neighbors just stays empty 🫥

9.2. Backbone Neighbors 🦴

the flexible router-LSA is possible because there are two types of neighbors that go into it: backbone neighbors and Selected Advertised Neighbors 🧩

if adjacency reduction is used, a bidirectional neighbor is a backbone neighbor if and only if it meets 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 (which tells you the neighbor is using adjacency reduction) 🌈 this lets routers that use adjacency reduction and routers that don't play nicely together 🤝✨

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, which matches LSAFullness = 0, only includes these neighbors. this choice guarantees connectivity but doesn't ensure shortest paths. still, it's super useful in large networks for maximum scalability 🏔️

9.3. Selected Advertised Neighbors 💜

okay the big goal here is making sure router-LSAs are symmetric 🪞 (meaning router i advertises a link to router j if and only if router j advertises a link to router i). so each router keeps a Selected Advertised Neighbor set (SANS). that's the MANET neighbors the router picked to advertise in its router-LSA, not counting backbone neighbors 🙈 since the SANS doesn't include backbone neighbors (and so doesn't include Dependent Neighbors), the SANS and DNS are disjoint 🧃 both of these neighbor sets get advertised in Hellos 📣

if LSAFullness is 0 (minimal LSAs), 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, a router that's using adjacency reduction can select any subset of bidirectional non-backbone neighbors as its SANS 🧁 the resulting router-LSA gets built as specified in Section 9.4 🛠️

now, a router that isn't using adjacency reduction usually has no backbone neighbors (unless it has neighbors that are using adjacency reduction). so to keep connectivity, that router has to choose a SANS containing the SANS for LSAFullness = 1 😤 which means: if AdjConnectivity is 0 (no adjacency reduction), then LSAFullness must be 1, 2, or 4 🎀

if LSAFullness is 1, the router originates min-cost LSAs 💫 these are partial-topology LSAs that (once flooded) give each router enough info to calculate a shortest (minimum-cost) path to each destination 🗺️ Appendix C describes the algorithm for picking the neighbors to put in the SANS to get min-cost LSAs 🧮 the algorithm's input includes what's learned from each MANET neighbor's Hellos: 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) gets appended to each Hello (unless all link costs are 1) so the link cost to each bidirectional neighbor is advertised 📡

if LSAFullness is 2, the SANS has to be a superset of the SANS for LSAFullness = 1 🫶 this gives you shortest-path routing while letting the router advertise extra neighbors for 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, its router-LSA includes all Full and routable neighbors on each interface where it's an MDR, and only Full neighbors and routable backbone neighbors on its other interfaces. this gives you routing along nearly shortest paths with pretty low overhead 🌷

this document only specifies a few SANS choices (matching different LSAFullness values), but other choices are totally possible 🌍 and different routers don't have to pick the same LSAFullness value 🙌 these choices are interoperable because they all require the router-LSA to include a minimum set of neighbors, and because building the router-LSA (described below) keeps the router-LSAs from different routers consistent 💅✨

9.4. Originating Router-LSAs ✨

okay so bestie, every time a new router-LSA gets originated, it includes a point-to-point (type 1) link for each MANET neighbor that's advertised 🌸 Now, which neighbors get advertised? It depends on whether adjacency reduction is in use. If it is, the router advertises all Full neighbors, plus each routable neighbor j that meets any of the three conditions below. If adjacency reduction is not in use (AdjConnectivity = 0), the router only advertises each Full neighbor j that meets any of those three conditions 💅

(1) The router's SANS (for any interface) includes j.
(2) Neighbor j's SANS includes the router (to ensure symmetry).
(3) Neighbor j is a backbone neighbor.

Okay, the plot twist 🙈 backbone neighbors and neighbors in the SANS don't have to be routable or Full. Only routable and Full neighbors can actually show up in the router-LSA. The reason is that the SANS gets advertised in Hellos, and the SANS shouldn't depend on routability. Iconic design, honestly 🧚

The events that trigger a new router-LSA are the same as in [RFC2328] and [RFC5340], with one twist: a MANET neighbor changing to or from the Full state doesn't always cause a new router-LSA. Instead, a new one gets originated whenever a change makes any of these three things happen 🦋

There's a MANET neighbor j that meets the conditions for inclusion in the router-LSA, but isn't in the current router-LSA yet.
The current router-LSA includes a MANET neighbor that's no longer bidirectional.
The link metric has changed for a MANET neighbor that's already included in the current router-LSA.

You don't have to check these conditions every single time a neighbor set changes. You can check them periodically, just before sending each Hello, which is a whole lot less chaotic 🌈 The implementation that was found to work well goes like this: just before sending each Hello, and whenever a bidirectional neighbor drops to less than 2-Way, the router runs the MDR selection algorithm. Then it updates its adjacencies, routable neighbors, and Selected Advertised Neighbors, and checks the conditions above to see if a new router-LSA should be originated. Also, if a neighbor becomes bidirectional or Full, the router updates its routable neighbors and checks the conditions again ✨

10. Calculating the Routing Table 🗺️

The routing table calculation is the same as what's specified in [RFC2328], except for a few changes to Section 16.1 (Calculating the shortest-path tree for an area). If full-topology adjacencies and full-topology LSAs are in use (AdjConnectivity = 0 and LSAFullness = 4), there's no change to Section 16.1 at all, so you can relax 🫶

If adjacency reduction is used (AdjConnectivity is 1 or 2), then Section 16.1 gets modified. Remember from Section 9 that a router can use any routable neighbor as a next hop to a destination, even if that neighbor isn't advertised in the router-LSA. To make that work, Step 2 gets changed so the router-LSA for the root vertex is replaced with a dummy router-LSA. That dummy includes links to all Full neighbors and all routable MANET neighbors. There's also a special rule for Step 2b (checking for a link from W back to V): it MUST be skipped when V is the root vertex and W is a routable MANET neighbor. But Step 2b still has to run when V isn't the root vertex, which keeps things compatible with OSPFv3 🎀

If LSAFullness is 0 (minimal LSAs), the calculated paths don't need to be shortest paths. The path a packet actually takes can be shorter than the calculated one, because intermediate routers might have routable neighbors that aren't advertised in any router-LSA. Wild, but valid 💀

If full-topology adjacencies and partial-topology LSAs are used, Section 16.1 gets modified a different way. Step 2 is changed so the router-LSA for the root vertex is replaced with a dummy router-LSA that includes links to all Full neighbors. Also, Step 2b MUST be skipped when V is the root vertex and W is a Full MANET neighbor. This is needed because the neighbor's router-LSA doesn't have to contain a link back to the router 🍓

Now, if adjacency reduction is used with partial-topology LSAs, the set of routable neighbors can change without the router-LSA contents changing. For example, a routable neighbor that wasn't included in the router-LSA might move to the Down or Init state. So if the set of routable neighbors changes, the shortest-path tree has to be recalculated, even when the router-LSA itself stays the same 👑

After the shortest-path tree and routing table are calculated, the set of routable neighbors has to be updated, because a route to a non-routable neighbor might have been discovered along the way. If that set changes, the shortest-path tree and routing table must be calculated a second time. The second calculation won't change the set of routable neighbors again, so two calculations are enough. And if the set of routable neighbors gets updated periodically, every HelloInterval seconds, then you don't need to update it right after the routing table changes 💜

11. Security Considerations 🔐

Okay, bestie, this section is seriously important, so pay attention 🥺 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 way AH and ESP get used for OSPFv3 is described in [RFC4552].

Generic threats to routing protocols are described and categorized in [RFC4593]. The mechanisms in [RFC4552] protect against many of these threats, but not all of them. As [RFC5340] points out, these mechanisms do not protect against compromised, malfunctioning, or misconfigured routers (also called Byzantine routers). That's true for both OSPFv3 and OSPF-MDR 😭

Extending OSPFv3 to include MANET routers doesn't introduce any brand-new security threats. BUT 🚨 the wireless medium and the lack of infrastructure that come with MANET routers may make some of the attacks described in [RFC4593] easier to pull off. Depending on the network context, those extra vulnerabilities may increase the need for authentication, integrity, and/or confidentiality, as well as anti-replay service.

For example, sniffing routing information and doing traffic analysis are easier with wireless routers than with wired ones, because the attacker only needs to be within radio range of a router. Confidentiality (encryption) protects against sniffing, but it does not protect against traffic analysis 👀

Interference attacks are also easier to mount against MANET routers because of their wireless nature. These attacks can happen even if OSPF packets are protected by authentication and confidentiality, for instance by transmitting noise or replaying outdated OSPF packets. As discussed below, an anti-replay service (provided by both ESP and AH) can protect against that latter attack 🛡️

The following threat actions are also easier with MANET routers: spoofing (assuming the identity 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 isn't used, or if the attacker takes control of a router or is able to forge legitimacy (for example, 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 means all routers attached to the same MANET must use the same key for multicasting packets. That's required in order to achieve scalability and feasibility, as explained in [RFC4552]. Future specifications can explore automated key management protocols that might be suitable for MANETs 🔑

As discussed in [RFC4552], manual keys can increase vulnerability. For example, manual keys are usually long-lived, which gives an attacker more time to discover them. Also, using the same key on all routers attached to the same MANET leaves every router open to impersonation attacks if any one of them is compromised. Yikes 😱

Now, [RFC4302] and [RFC4303] state that implementations of AH and ESP SHOULD NOT provide anti-replay service in conjunction with manually keyed SAs. It's important to note, though, that this service is allowed if the sequence number counter at the sender is correctly maintained across local reboots until the key is replaced. So it may be possible for MANET routers to use 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, whether from actual topology changes or from malfeasance, could cause instability in the fixed networks. If that's a concern, it is recommended that border routers segregate the MANET networks from the fixed networks, either with separate OSPF areas or, if legacy routers are very sensitive to OSPF update frequency, with separate OSPF instances. With separate OSPF areas, the 5-second MinLSInterval dampens the frequency of changes originated in the MANET networks. OSPF ranges can also be configured to aggregate prefixes for the areas that support MANET networks. With separate OSPF instances, more conservative local policies can limit the volume of updates coming out of 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). ✨

13. Acknowledgments 🫶

Huge 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. Legends 🌟

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 ✨

Okay bestie, time for the bibliography 📚💅 These are the extra reads that back things up, but nothing here is required to implement the spec.

[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.

Appendix A. Packet Formats 🎀

Welcome to the packet closet, where all the bits live 🧚✨

A.1. Options Field

Okay so the L bit in the OSPF options field is the one used for link-local signaling, which you can read more about in [RFC5613]. Routers flip the L bit on in Hello and DD packets to say "hey, this packet has an LLS data block tucked inside" 💌 They also set the L bit in a self-originated router-LSA to say that the LSA is non-ackable 🙈

A.2. Link-Local Signaling

Here's the tea 🍵 OSPF-MDR uses link-local signaling [RFC5613] to stick the MDR-Hello TLV and the MDR-Metric TLV onto Hello packets, and to stick the MDR-DD TLV onto Database Description packets. LLS is basically an extension to OSPFv2 and OSPFv3 that lets you swap arbitrary data using packet types OSPF already has 🦋 Here we're using LLS for OSPFv3, which works by adding an LLS data block at the very end of the OSPFv3 packet. The OSPF packet length field does not count the LLS data block, but the IPv6 packet length does include it. Plot twist 😭

A.2.1. LLS Data Block

The data block used for link-local signaling is laid out like this 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 holds the standard IP checksum of the entire LLS block, start to finish 🧮

The 16-bit LLS Data Length field tells you how long the LLS block is, in 32-bit words, counting the header and the payload both. Heads up: implementations should not use the Length field in the IPv6 packet header to figure out how long the LLS data block is. 🚫

The rest of the block is a bunch of Type/Length/Value (TLV) triplets, which we'll get into in the next part. All TLVs MUST be 32-bit aligned (with padding if needed) 💖

A.2.2. LLS TLV Format

Every LLS data block is built out of TLVs. Check Figure A.2 for the TLV layout ✨

The Type field is the TLV ID, which is unique for each kind of TLV. The Length field is the length of the Value field in bytes. The Value field can hold basically any 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

Quick note 📝 TLVs are always padded out to a 32-bit boundary. The padding bytes do not go in the TLV Length field, but they do count toward the LLS Data Length field in the block header. All unknown TLVs MUST be silently ignored 🙈🫶

A.2.3. MDR-Hello TLV

The MDR-Hello TLV gets appended to each MANET Hello using LLS 🌸 It carries the current Hello sequence number (HSN) for the transmitting interface, plus the number of neighbors of each type listed in the body of the Hello (see Section 4.1). It also tells you whether the Hello is differential (that's the D-bit) and whether the router is using full-topology adjacencies (that's the A-bit) 🦋

     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       |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Type: Set to 14.
Length: Set to 8.
Hello Sequence Number: A circular two-octet unsigned integer telling you the current HSN for the transmitting interface. The HSN goes up by 1 (modulo 2^16) every single time a (differential or full) Hello goes out on that interface 🔁
Reserved: Set to 0. It's reserved for future use, so hands off 🤚
A (1 bit): Set to 1 if AdjConnectivity is 0; otherwise, set to 0.
D (1 bit): Set to 1 for a differential Hello and 0 for a full Hello.
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.
N2 (8 bits): The number of neighbors listed in the Hello that are in state Init.
N3 (8 bits): The number of neighbors listed in the Hello that are Dependent.
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 goes to a neighbor in state ExStart, an MDR-DD TLV gets appended to the packet using LLS 💌 It includes the same two Router IDs that show up in the DR and Backup DR fields of a Hello the router sends. It's used to show the router's MDR Level and Parent(s) 👑

     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                           |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+

Type: Set to 15.
Length: Set to 8.
DR: The same Router ID that's included in the DR field of a Hello sent by the router (see Section A.3).
Backup DR: The same Router ID that's included in the Backup DR field of a Hello sent by the router (see Section A.3).

A.2.5. MDR-Metric TLV

This one's a bit of a lore dump, so get comfy 🛋️ 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. The TLV advertises the link metric for each bidirectional neighbor listed in the body of the Hello. At a minimum it 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 cuts down on overhead when all neighbors share the same link metric, or when only a few neighbors have a link metric that's different from the default. If the I bit is zero, the link metric is included for each bidirectional neighbor listed in the body of the Hello, and the neighbor RIDs get left out of the TLV 🫧

     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)             |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |           ...
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Type: Set to 16.
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.
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.
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.
Metric: The link metric for each bidirectional neighbor. These are 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.

A.3. Hello Packet DR and Backup DR Fields

Last but not least, here's how the DR and Backup DR fields of a Hello packet get set 💅

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. 🌟
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 ✨

okay so the LSA formats are all specified in [RFC5340], Section 4.4 💖 Figure A.3 is a little example network map for a MANET inside one area, and it's giving main character 🗺️

Four MANET routers RT1, RT2, RT3, and RT4 are in area 1. 🧚
RT1's MANET interface has links to RT2 and RT3's MANET interfaces. 🔗
RT2's MANET interface has links to RT1 and RT3's MANET interfaces. 🦋
RT3's MANET interface has links to RT1, RT2, and RT3's MANET interfaces. 💅
RT4's MANET interface has a link to RT3's MANET interface. 🌸
RT1 and RT2 have stub networks attached on broadcast interfaces. 🍓
RT3 has a transit network attached on a broadcast interface. 👑

    ..........................................
    .                                  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
   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

A.4.1. Router-LSAs

bestie, let's look at the router-LSA that node RT3 would originate 🫶 RT3 has 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)

A.4.2. Link-LSAs

next up, 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, plus the ones on its attached networks or stub links 🌈 For an example, we check out 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

Appendix B. Detailed Algorithms for MDR/BMDR Selection ✨

this section gives you the 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 from 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. ⏱️

just so we're on the same page, "bi-neighbor" is shorthand for "bidirectional neighbor" 🫶 Also, node i is the router doing the calculation.

B.1. Detailed Algorithm for Step 2.4 (MDR Selection)

this algorithm performs Step 2.4 of the MDR selection algorithm and assumes Phase 1 and Steps 2.1 through 2.3 have already happened. So 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 uses a FIFO queue, so every node 1 hop from Rmax gets processed first, then 2 hops, and so on. When the BFS finishes, hops(u) for each bi-neighbor node u of node i equals the minimum number of hops from Rmax to 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 works out, for each node u, the tree parent p(u) and the second node r(u) on the tree path from Rmax to u, which Step 3.2 will use 💅

(a) Compute a matrix of link costs c(u,v) for each pair of bi-neighbors u and v, like this 🌸 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. (Heads up, 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 and 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. ✨

B.2. Detailed Algorithm for Step 3.2 (BMDR Selection) ✨

Okay so bestie, this is the part where the router figures out whether it should be a BMDR, and it's giving serious graph-theory energy 🧠💅. Step 3.2 of the MDR selection algorithm needs the router to check whether there are two node-disjoint paths from Rmax to each other bi-neighbor u, going only through bi-neighbors with a bigger (RtrPri, MDR Level, RID) than the router itself 🦋. That info is what decides if the router picks itself as a BMDR. No cap, it's a big deal 💖.

You could check each bi-neighbor u one at a time using the well-known augmenting path algorithm [Lawler], which runs in O(n^2) time 😭. But you'd have to do that for every single bi-neighbor, so the total run time is O(n^3) 💀. The algorithm below makes the same call for all bi-neighbors at once, and the total run time drops to O(n^2) ✨🔥. It's a simplified version of the Suurballe-Tarjan algorithm [Suurballe] for finding pairs of disjoint paths 👑.

The algorithm uses the output of Phase 2: the tree parent p(u) of each node (which defines the BFS tree from Phase 2), and the second node r(u) on the tree path from Rmax to u 🌸.

Here's the vocab. For any node u on the BFS tree other than Rmax, g(u) is the first labeled node on the reverse tree path from u to Rmax, as long as it isn't Rmax itself. (The reverse tree path is u, p(u), p(p(u)), ..., Rmax.) If there's no such labeled node, then g(u) is r(u) 🧚. So if u is labeled, g(u) = u, obviously 🙈. Also, g(u) either has to be labeled or be a neighbor of Rmax, no exceptions 💅.

For any node k that's either labeled or a neighbor of Rmax, the unlabeled subtree rooted at k, written S(k), is the set of nodes u where g(u) = k. So S(k) includes k itself plus all the unlabeled nodes downstream of k on the BFS tree that you can reach without going through any labeled nodes 🎀. You can grab this set in linear time with a depth-first search that starts at k and uses labeled nodes as the boundaries 🍓. g(u) and S(k) aren't stored as variables in the algorithm, they just refer to the definitions above, so no need to track them separately 🫶.

The BMDR algorithm keeps a set B, which starts out empty. A node u gets added to B once we know two node-disjoint paths exist from Rmax to u via nodes with a bigger (RtrPri, MDR Level, RID) than the router itself 🌈. When the algorithm finishes, B holds every node with that property. Main character energy 👑✨.

The algorithm has two steps.

(a) Mark Rmax as labeled. Then, for each pair of nodes u, v on the BFS tree other than Rmax where r(u) is not equal to r(v) (so u and v have different second nodes), with NCM(u,v) = 1, and where u has a greater (RtrPri, MDR level, RID) than the router itself, add v to B. (Obviously there are two disjoint paths from Rmax to v, periodt 💜.)

(b) While there's a node in B that isn't labeled yet, do the following 🔥. Pick any unlabeled node k in B, and let j = g(k). Now mark k as labeled. (This creates a new unlabeled subtree S(k), and shrinks S(j) by removing S(k) from it 😭.) Then, for each pair of nodes u, v where u is in S(k), v is in S(j), and NCM(u,v) = 1:

If u has a larger (RtrPri, MDR level, RID) than the router itself, and v isn't in B yet, add v to B 🦋.
If v has a larger (RtrPri, MDR level, RID) than the router itself, and u isn't in B yet, add u to B 💖.

A simplified version of the algorithm MAY be done by skipping step (b) 🌸. But the simplified version gives you more BMDRs, and it's NOT RECOMMENDED if AdjConnectivity = 2, because it'll end up creating more adjacencies 🙈💀.

The whole thing runs in O(n^2) time, where n is the number of neighbors ✨. Step (a) is O(n^2) because it checks every pair of nodes u and v 😭. Step (b) is also O(n^2), since each pair of nodes gets considered at most once. Labeling nodes splits unlabeled subtrees into smaller ones, and a given pair u, v only gets considered the first time u and v land in different unlabeled subtrees 🧚💅.

Appendix C. Min-Cost LSA Algorithm ✨

okay bestie, this section is about deciding which MANET neighbors go into the router-LSA when LSAFullness is 1 🦋 The min-cost LSA algorithm makes sure the link-state database has enough info to work out at least one shortest (minimum-cost) path to every destination 💖 It assumes a router might have multiple interfaces, at least one of which is a MANET interface. It gets way simpler if the router only has a single (MANET) interface 🫶

The inputs come from the Hellos received from each neighbor on each MANET interface. That includes 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 is the router's SANS for each MANET interface. The SANS is used to build 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 these events happens:

The state or routability of a neighbor changes.
A Hello received from a neighbor indicates a change in its MDR Level, Router Priority, FullHelloRcvd, BNS, DNS, SANS, Parent(s), or link metrics.
An LSA originated by a non-MANET neighbor is received.

Even though the algorithm 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 🔥 More on that after the algorithm description.

Quick note: in the following, the term "bi-neighbor" is short for "bidirectional neighbor" 💅 Also, router i is the router doing the calculation. To perform the min-cost LSA algorithm, the following steps happen.

(1) Create the neighbor connectivity matrix (NCM) for each MANET interface, as described in Section 5.1. Then 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 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 shows 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 skip straight to Step 4.

Here's the deal: if a link exists from router j to router k on more than one interface, we only look at interfaces where the cost from j to k equals COST(j,k). Those interfaces get 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. In other words, 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 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 gets set to 1 if j is selected.) Then, for each MANET bi-neighbor j:

(a) If j is a bi-neighbor on more than one interface, only consider candidate interfaces (the ones where 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:

BNM(u,j) = 1, or
(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 ✨

(7) With the SANS updated, a new router-LSA may need to be originated, as described in Section 9.4 🎀

The lexicographical comparison in Step 5d gives preference to links that are already advertised, which helps improve LSA stability 🫶

Now for the speedy version 🏎️ The above algorithm can run in O(d^2) time if a single link change occurs. For example, say 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 only needs to be performed for pairs j, k where either j or k is equal to x or y. Iconic, right? 👑

Appendix D. Non-Ackable LSAs for Periodic Flooding ✨

okay so picture a super mobile network where a router is basically always originating a new router-LSA every MinLSInterval seconds 😭 In that situation, it shouldn't really be necessary to send Acks for that LSA, retransmit it as a unicast, or describe it in a DD packet. So the originator of an LSA MAY mark its router-LSA as "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 figures out (e.g., based on an exponential moving average) that a new LSA gets 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, never retransmitted as a unicast, and never described in a DD packet, which saves a ton of overhead 💖 Even so, 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). Each MDR must also 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 gets retransmitted.

Note that receiving a retransmitted (duplicate) LSA doesn't cause the LSA to be forwarded right away. Only a new LSA (with a larger sequence number) may be forwarded immediately, according to the flooding procedure of Section 8 🫶

Appendix E. Simulation Results ✨

okay so this appendix is the receipts 🧾💅 the simulation numbers that back up how OSPF-MDR behaves at scale. it's giving science experiment, but make it iconic 🦋

The sim used the GTNetS simulator with OSPF-MDR version 1.01, which you can grab at http://hipserver.mct.phantomworks.org/ietf/ospf. bestie, that link is in the original, not me 🫶

Here's the setup they ran. radio range was 200 m and 250 m, grid length was 500 m, wireless alpha was 0.5, (maximum) velocity was 10 m/s, pause time was 0, packet rate was 10 pkts/s, packet size was 40 bytes, random seed was 8, and the start time for gathering statistics was 1800 s. the stop time was 3600 s for up to 80 nodes and 2700 s for more than 80 nodes. source and destination got picked at random for every generated UDP packet 🎲 and the simulated MAC protocol was 802.11b 📡

The default config got used for Tables 4 and 6, except differential Hellos were on (2HopRefresh = 3), since they're recommended when the neighbor count is large 🌸 Tables 5 and 7 match that setup, except they used minimal LSAs instead of min-cost LSAs. The tables show total OSPF overhead in kb/s, total OSPF packets per second, the UDP delivery ratio, and the average number of hops for UDP packets that actually reach their destination 📊

Tables 5 and 7 also track a few extra stats: the average number of bidirectional neighbors per node, the average number of fully adjacent neighbors per node, and how many times per second the set of bidirectional neighbors and the set of fully adjacent neighbors changed per node. these stats don't change much when you swap min-cost LSAs for minimal ones 🙈

The big takeaway? OSPF-MDR stays solid up to at least 160 nodes with min-cost LSAs, and up to at least 200 nodes with minimal LSAs 👑 Also, routes built with minimal LSAs are only 2.3% to 4.5% longer than min-cost ones at 250 m range, and 3.5% to 7.4% longer at 200 m 🧚

Adjacencies per node and adjacency changes per node per second don't climb as the node count grows. they stay dramatically smaller than the neighbor counts and neighbor changes, and that's a huge reason the overhead stays low 💖 For example, Table 5 says that with 200 nodes at range 250 m, there are 2.136/.039 = 55 times as many adjacency formations with full-topology adjacencies as with uniconnected adjacencies. mind = blown 🤯 More simulation results live at http://www.manet-routing.org.

Here are the tables, straight from the source 💜

                                      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    120    160    200
   ------------------------------------------------------------------
   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

                                      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 🫶

📦 where this page comes from

ietf: rfc5614 2009-08
💖 girlified by claude-haiku-5-5 on 2026-10-17: a language model's rewrite of the original, under its terms