RFC 5820
Extensions to OSPF to Support Mobile Ad Hoc Networking
RFC 5820: Extensions to OSPF to Support Mobile Ad Hoc Networking 🦋
okay bestie, let's get into RFC 5820 ✨ It's titled Extensions to OSPF to Support Mobile Ad Hoc Networking, and it's an Experimental document, so it's not a Standards Track thing 🧪 It came out in March 2010 from the IETF (Internet Engineering Task Force), and its ISSN is 2070-1721 🔢 The authors are A. Roy, Ed. of Cisco Systems and M. Chandra, Ed., whose affiliation isn't listed. "Ed." just means editor 💅 The title block doesn't list any RFCs that it obsoletes or updates, so it's standing on its own 🌸
Abstract 🫧
okay so this doc describes extensions to OSPF so it can work on mobile ad hoc networks (MANETs) 📡 The extensions are called OSPF-OR (OSPF-Overlapping Relay), and they include mechanisms for link-local signaling (LLS), an OSPF-MANET interface, a simple trick to shrink Hello packets by only sending incremental state changes 🪄, and a method for optimized flooding of routing updates 🌊 OSPF-OR also gives you a way to cut down on unnecessary adjacencies so bigger MANETs can actually work 💜
Status of This Memo 📜
the status part is giving "experimental energy" 🧪 This document is not an Internet Standards Track specification. It's published so people can examine it, try out an experimental implementation, and evaluate it 🔬
It does define an Experimental Protocol for the Internet community ✨ It's a product of the IETF and represents the consensus of the IETF community 🫶 It got public review and was approved for publication by the Internet Engineering Steering Group (IESG). Not every IESG-approved document is a candidate for any level of Internet Standard, so check Section 2 of RFC 5741 if you want the details 📚
For the current status, any errata, and how to send feedback, head to http://www.rfc-editor.org/info/rfc5820 🔗
Copyright Notice ©️
Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved 💖
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents, which you can find at http://trustee.ietf.org/license-info in effect on the publication date. Please read these carefully, because they spell out your rights and restrictions 🧾 Code Components pulled out of this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions, and they come without warranty as described in the Simplified BSD License ⚖️
This document may contain material from IETF Documents or IETF Contributions that were published or made publicly available 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 modifications outside the IETF Standards Process 🙈 So unless you get an adequate license from those copyright holders, this document may not be modified outside the IETF Standards Process, and derivative works may not be created outside it either. The one exceptions are formatting it for publication as an RFC or translating it into languages other than English 🌍
Table of Contents 📑
1. Introduction ....................................................4
1.1. Problem Statement ..........................................4
1.2. Motivation for Extending OSPF to Support MANETs ............5
2. Requirements Notation ...........................................5
3. Proposed Enhancements ...........................................5
3.1. OSPF-MANET Interface .......................................7
3.1.1. Interface Operation .................................8
3.1.2. LSA Formats and Examples ............................8
3.2. Incremental OSPF-MANET Hellos .............................12
3.2.1. The I Option Bit ...................................12
3.2.2. State Check Sequence TLV (SCS TLV) .................12
3.2.3. Neighbor Drop TLV ..................................13
3.2.4. Request From TLV (RF TLV) ..........................14
3.2.5. Full State For TLV (FSF TLV) .......................14
3.2.6. Neighbor Adjacencies ...............................15
3.2.7. Sending Hellos .....................................16
3.2.8. Receiving Hellos ...................................17
3.2.9. Interoperability ...................................19
3.2.10. Support for OSPF Graceful Restart .................19
3.3. Optimized Flooding (Overlapping Relays) ...................20
3.3.1. Operation Overview .................................20
3.3.2. Determination of Overlapping Relays ................21
3.3.3. Terminology ........................................21
3.3.4. Overlapping Relay Discovery Process ................22
3.3.5. The F Option Bit ...................................23
3.3.6. Active Overlapping Relay TLV (AOR TLV) .............23
3.3.7. Willingness TLV ....................................24
3.3.8. Flooding and Relay Decisions .......................25
3.3.9. Intelligent Transmission of Link State
Acknowledgments ....................................26
3.3.10. Important Timers ..................................27
3.3.11. Miscellaneous Protocol Considerations .............28
3.3.12. Interoperability ..................................28
3.4. New Bits in LLS Type 1 Extended Options and Flags .........29
3.5. Smart Peering .............................................29
3.5.1. Rationale for Smart Peering ........................29
3.5.2. Previous Related Work ..............................30
3.5.3. Smart Peering Solution .............................30
3.5.4. Advertising 2-Way Links in Router-LSAs .............33
4. Security Considerations ........................................36
5. IANA Considerations ............................................38
6. Contributors ...................................................39
7. Acknowledgments ................................................39
8. References .....................................................39
8.1. Normative References ......................................39
8.2. Informative References ....................................401. Introduction 🌟
okay so MANETs have been a whole topic for a while now 🧠 They've been studied across different working groups and areas within the IETF, by various military branches, and by different government agencies 🏛️ Lately, networks with mobile ad hoc requirements have been proposed and are seriously being considered for deployment in the near term, which means the concepts and research need to get applied to real deployed networks 🚀 So this document takes a lot of the principles and concepts learned from earlier work and applies them to [OSPFv3], plus some new concepts based on current requirements 💅
1.1. Problem Statement 🧩
MANETs are basically synonymous with packet radio networks, which have existed since the 1960s in a limited military capacity 📻 With the boom in mobile devices and wireless comms, MANETs are showing up in both commercial and military settings ✨ The goal is to support robust and efficient communication on a mobile wireless network by building routing functionality right into the mobile nodes 🫧
A MANET is an autonomous set of nodes spread over a wide geographic area that talk to each other over bandwidth-constrained wireless links 🛰️ Each node might be a transmitter, a receiver, or a relay station, and they can have different physical capabilities 🎀 Packets may hop through several intermediate (relay) nodes before they reach their destination 🦋 These networks usually have no infrastructure: the nodes move around, and there's no central hub or controller, so the network topology isn't fixed 🌀 On top of that, MANETs have to deal with a difficult and variable communication environment 😭 Radio transmissions suffer from the usual issues, including propagation path loss, signal multipath and fading, and thermal noise 📉 These effects change as terminals move, and movement also causes Doppler spreading in the frequency of the transmitted signal 🌪️ Finally, there's interference from neighboring terminals (multi-access interference), hostile jammers, and impulsive interference, like ignition systems, generators, and other non-similar in-band communications, which can all add more interference 💀
Because of all that, whether two nodes can communicate depends on their link quality, which changes with things like signal strength and bandwidth 📶 So routing paths keep changing based on the environment and the resulting network topology 🔄 The topology can be stable for a while and then suddenly become unpredictable 🙈 MANETs are typically decentralized, so there are no central controllers or specially designated routers to pick the routing paths when the topology changes 🫠 All routing decisions and forwarding (relaying) of packets have to be handled by the nodes themselves, and they communicate on a peer-to-peer basis 🤝
1.2. Motivation for Extending OSPF to Support MANETs 🎯
the reason for extending OSPF (described in [OSPF] and [OSPFv3]) so it can run on MANETs has two parts 💖 The main one is interoperability: MANET devices need to work when plugged into a wireline network in as many cases as possible 🔌 The junction between a MANET and a wireline network should also be as fluid as possible, so a MANET can "plug in" to just about any spot in a wireline network and find connectivity and so on, as needed 🫶
You could redistribute routes between two routing protocols, one built just for wireline networks and one just for MANETs 🤷♀️ But that adds complexity and overhead to the MANET/wireline interface, raises the odds of an error creeping in between the two domains, and reduces flexibility 😩
The second motivation is that OSPF is a well-understood and widely deployed routing protocol 👑 That gives a strong base of experience and skills to build on ✨ A protocol that's known to work can be extended, instead of inventing a brand-new one that then has to be fully troubleshot, tested, and modified over a number of years 🙌 Working with a well-known protocol lets development effort go into a narrow focus area, instead of rebuilding from scratch a bunch of things that are already known to work 🧚
2. Requirements Notation 📝
the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [KEY]. iykyk, these are the official BCP 14 keywords, so they carry the exact weight the spec gives them 🔥
3. Proposed Enhancements ✨
okay so this is the main event 💅 this section proposes changes to [OSPFv3] so it can work on mobile ad hoc networks (MANETs) 📡 quick heads up: the mechanisms in Sections 3.2 and 3.3 can be used independently of each other, so you don't have to take the whole bundle 🎀
the problems with running standard [OSPFv3] in a MANET fall into two buckets 🧚 bucket one: traditional link-state routing protocols are built for a statically configured environment 🙃 so most of the setup gets done by hand whenever a new router shows up. OSPF just won't work when routers connect and disconnect in kinda random topologies and combos 💀 routers running the same protocol need modifications so they can talk in a heterogeneous and dynamic environment.
bucket two is scalability 📈 a MANET has to transmit more state information to maintain reachability, so OSPF needs scalability enhancements. yes, OSPF already has some flooding optimizations, like designated router (DR) election, but a lot of them were built assuming a true multi-access network. wireless networks aren't true multi-access networks, because you can't assume 2-way connectivity between everyone on the same Layer 2 link 😭 so optimizations like DR election won't perform correctly in MANET networks. even without that, current OSPF can't handle a highly dynamic environment where links are constantly being formed and broken. the amount of info that would need flooding would overload the network 🫠
Hello messages are another scalability issue 🔋 right now, even if a router's neighbor list hasn't changed, its Hello messages still list all the neighbors on a particular link. for a MANET router, where saving bandwidth and transmission power is critical, sending potentially large Hello messages is super wasteful.
last but not least, current routing protocols form a neighbor relationship with any router on a Layer 2 link that's correctly configured 👀 for MANET routers on a wireless network, this can lead to an excessive number of parallel links between two routers if they communicate through multiple interfaces. in a statically configured network that's not a problem, since the physical topology can be built to prevent excessive redundancy. but in a dynamic network, there must exist additional mechanisms to prevent too many redundant links. (fun fact: links between two nodes on different radio types, different antennae, different channels, etc. are considered different links and not redundant links 🌈) in scalability tests, too many redundant links were shown to increase the size of routing updates and cause extra flooding, so even relatively small networks end up not converging 🥲
3.1. OSPF-MANET Interface
interfaces are the connection between a router and one of its attached networks [OSPF] 🔌 four types of interfaces are defined and supported in [OSPF] and [OSPFv3]: broadcast, Non-Broadcast Multi-Access (NBMA), point-to-point, and point-to-multipoint.
the point-to-multipoint model was chosen to represent MANET interfaces 🦋 (the features designed in this document MAY be included on other interface types as appropriate.) the MANET interface allows the following:
- OSPF treats all router-to-router connections over the MANET interface as if they were point-to-point links.
- Link metric can be set on a per-neighbor basis.
- Broadcast and multicast can be accomplished through Layer 2 broadcast or Layer 2 pseudo-broadcast.
- The MANET interface supports Layer 2 broadcast if it is able to address a single physical message to all of the attached neighbors. One such example is 802.11.
- The MANET interface supports Layer 2 pseudo-broadcast if it is able to pick up a packet from the broadcast queue, replicate the packet, and send a copy over each point-to-point link. One such example is Frame Relay.
- An API must be provided for Layer 3 to determine the Layer 2 broadcast capability. Based on the return of the API, OSPF classifies the MANET interfaces into the following three types: MANET broadcast, MANET pseudo-broadcast, and MANET non-broadcast.
- Multicast SHOULD be used for OSPF packets. When the MANET interface supports Layer 2 broadcast or pseudo-broadcast, the multicast process is transparent to OSPF. Otherwise, OSPF MUST replicate multicast packets by itself.
3.1.1. Interface Operation
a MANET node has at least one MANET interface 📶 MANET nodes can communicate with each other through MANET interfaces. MANET nodes can communicate with non-MANET routers only through normal interfaces, such as Ethernet, ATM, etc.
for scalability reasons, it is not required to configure IPv6 global unicast addresses on MANET interfaces 🙌 instead, a management loopback interface with an IPv6 global unicast address MAY be configured on each MANET node.
the link state advertisements (LSAs) associated with a MANET interface SHOULD have the DC-bit set in the OSPFv3 Options Field and the DoNotAge bit set in the LS Age field as described in [OSPFv3]. Demand Circuits are an optional feature, so the DC-bit setting recommendation level is SHOULD. 🎀
3.1.2. LSA Formats and Examples
LSA formats are specified in [OSPFv3].
to display example LSAs, here's a network map 🗺️ router names are prefixed with the letters RT, network names with the letter N, and router interface names with the letter I.
- Four MANET nodes, RT1, RT2, RT3, and RT4, reside in area 2.
- RT1 has one MANET interface, I11. Through the interface, RT1 is full-adjacent to RT2, RT3, and RT4.
- RT2 has two MANET interfaces, I21 and I22, and one Ethernet interface, I23. RT2 is full-adjacent to RT1 and RT4 through the interface I21, and full-adjacent to RT4 through the interface I22. Stub network N1 is attached with RT2 through the interface I23.
- RT3 has one MANET interface, I31, and is full-adjacent to RT1 through the interface.
- RT4 has two MANET interfaces, I41 and I42. It is full-adjacent to RT2 through the interface I41, and full-adjacent to RT1 and RT2 through the interface I42.
- Moreover, each MANET node is configured with a management loopback interface.
+---+I11 I21+---+I23 |
|RT1|-+----------+-|RT2|------|N1
+---+ | | +---+ |
| | VI22
| | +
| | |
| | |
| | |
| | |
| | +
| | ^I41
+---+ | +---+
|RT3|-+ +-|RT4|
+---+I31 I42+---+the assignment of IPv6 global unicast prefixes to network links is shown below 🧁 (Note: No IPv6 global unicast addresses are configured on the MANET interfaces).
-----------------------------------------------------------
RT1 LOOPBACK 2001:DB8:0001::/64
I11 n/a
RT2 LOOPBACK 2001:DB8:0002::/64
I21 n/a
I22 n/a
I23 2001:DB8:0012::/60
RT3 LOOPBACK 2001:DB8:0003::/64
I31 n/a
RT4 LOOPBACK 2001:DB8:0004::/64
I41 n/a
I42 n/athe OSPF interface IDs and the link-local addresses for the router interfaces in the network are shown below 💖 EUIxy represents the 64-bit interface identifier of the interface Ixy, in Modified EUI-64 format [IPV6ADD].
Node Interface Interface ID Link-Local address
-----------------------------------------------------------
RT1 LOOPBACK 1 n/a
I11 2 fe80:0002::EUI11
RT2 LOOPBACK 1 n/a
I21 2 fe80:0002::EUI21
I22 3 fe80:0003::EUI22
I23 4 fe80:0004::EUI23
RT3 LOOPBACK 1 n/a
I31 2 fe80:0002::EUI31
RT4 LOOPBACK 1 n/a
I41 2 fe80:0002::EUI41
I42 3 fe80:0003::EUI423.1.2.1. Router-LSAs
okay so as an example, let's look at the router-LSAs that node RT2 would originate 🧠 two MANET interfaces, made up of 3 point-to-point links, are presented.
RT2's router-LSA
LS age = DoNotAge+0 ;newly originated
LS type = 0x2001 ;router-LSA
Link State ID = 0 ;first fragment
Advertising Router = 192.0.2.2 ;RT2's Router ID
bit E = 0 ;not an AS boundary router
bit B = 0 ;not an area border router
Options = (V6-bit|E-bit|R-bit)
Type = 1 ;p2p link to RT1 over I21
Metric = 10 ;cost to RT1
Interface ID = 2 ;Interface ID of I21
Neighbor Interface ID = 2 ;Interface ID of I11
Neighbor Router ID = 192.0.2.1 ;RT1's Router ID
Type = 1 ;p2p link to RT4 over I21
Metric = 25 ;cost to RT4
Interface ID = 2 ;Interface ID of I21
Neighbor Interface ID = 3 ;Interface ID of I42
Neighbor Router ID = 192.0.2.4 ;RT4's Router ID
Type = 1 ;p2p link to RT4 over I22
Metric = 15 ;cost to RT4
Interface ID = 3 ;Interface ID of I22
Neighbor Interface ID = 2 ;Interface ID of I41
Neighbor Router ID = 192.0.2.4 ;RT4's Router ID3.1.2.2. Link-LSAs
a MANET node originates a separate link-LSA for each attached interface 🔗 as an example, check out the link-LSA that RT3 will build for its MANET interface I31.
RT3's link-LSA for MANET interface I31
LS age = DoNotAge+0 ;newly originated
LS type = 0x0008 ;link-LSA
Link State ID = 2 ;Interface ID of I31
Advertising Router = 192.0.2.3 ;RT3's Router ID
Rtr Pri = 1 ;default priority
Options = (V6-bit|E-bit|R-bit)
Link-local Interface Address = fe80:0002::EUI31
# prefixes = 0 ;no global unicast address3.1.2.3. Intra-Area-Prefix-LSAs ✨
okay so a MANET node makes an intra-area-prefix-LSA 🎀 to advertise its own prefixes and the ones on its attached stub links 🦋 for example, let's look at the one RT2 is about to build 💅
RT2's intra-area-prefix-LSA for its own prefixes
LS age = DoNotAge+0 ;newly originated
LS type = 0x2009 ;intra-area-prefix-LSA
Link State ID = 177 ;or something else
Advertising Router = 192.0.2.2 ;RT2's Router ID
# prefixes = 2
Referenced LS type = 0x2001 ;router-LSA reference
Referenced Link State ID = 0 ;always 0 for router-LSA
;reference
Referenced Advertising Router = 192.0.2.2
;RT2's Router ID
PrefixLength = 64 ;prefix on RT2's LOOPBACK
PrefixOptions = 0
Metric = 0 ;cost of RT2's LOOPBACK
Address Prefix = 2001:DB8:0002::
PrefixLength = 60 ;prefix on I23
PrefixOptions = 0
Metric = 10 ;cost of I23
Address Prefix = 2001:DB8:0012::Note: MANET nodes may originate intra-area-prefix-LSAs for attached transit (broadcast/NBMA) networks. This is normal behavior (defined in [OSPFv3]), which is irrelevant to MANET interfaces. Please consult [OSPFv3] for details. 🙈
3.2. Incremental OSPF-MANET Hellos 🌸
okay so in MANETs, shrinking the size of the packets that get sent over and over is a BIG deal 😭 it cuts down the total overhead for routing ✨ and the trick is to leave the list of neighbors out of Hello packets, unless that info has actually changed 💅 each Hello only saves a little, but over time it adds up to something seriously significant 💖
this doc defines a brand new option bit to help run incremental Hello packets 🦋 it also defines a new State Check Sequence TLV (SCS TLV) and a Neighbor Drop TLV, both sent using LLS [LLS] 🧚
3.2.1. The I Option Bit 🎀
there's a new I-bit in the LLS Type 1 Extended Options and Flags field 🫶 it's defined for Hello packets and tells you that only incremental info is in there 💜 see Section 5 for where the I-bit lives 🌈
3.2.2. State Check Sequence TLV (SCS TLV) 👑
this is a new TLV that shows the current state, which is represented by a State Check Sequence (SCS) number from the router that's sending it 🔥
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SCS Number |R|FS|N | Reserved |
+-----------------------------------------------------------------+- Type: 6
- Length: Set to 4.
- SCS Number: A circular two-octet unsigned integer indicating the current state of the transmitting device. Note that when the incremental Hello mechanism is invoked (or re-started), an initial SCS value of '1' SHOULD be used for the first incremental Hello packet. This sequence number is referred to as InitialSCS. Note that InitialSCS also implies a full state. 🌷
- R: Request bit. If set, this is a request for current state. The list of routers that should respond to this request is indicated in the Request From TLV (RF TLV) (defined below). If the RF TLV is not present, it is assumed that the request is meant for all nodes. 🙋♀️
- FS: Full State bit. If set, the Hello packet contains full state as far as the neighbor(s) in the Full State For TLV (FSF TLV) (defined below) are concerned. If the FSF TLV is not present, the Hello packet contains full state for all neighbors. 💅
- N: Incomplete bit. If NOT set, the complete state associated with the SCS number is included in the Hello packet. If set, this indicates that the appended TLVs are being sent 'persistently', and that there is more state associated with the SCS number that was sent originally, but is not included in this Hello packet. This bit allows any desired TLVs to be sent 'persistently' for a number of Hellos with the same SCS number without requiring all of the TLVs associated with that SCS number to be transmitted. The first time an SCS number is sent, the entire state associated with that SCS number is transmitted, and the N-bit MUST NOT be set. 😭
- Reserved: Set to 0. Reserved for future use. 🫧
A Hello with the SCS TLV appended and with the R-bit set will be referred to as a Hello request. 🍓
3.2.3. Neighbor Drop TLV 💀
this is a new TLV that lists the neighbor(s) that got removed from the list of known neighbors 🌈
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Dropped Neighbor(s) |
+---------------------------------------------------------------+
| ....
+--------------------- Type: 7
- Length: Set to the number of dropped neighbors included in the TLV multiplied by 4.
- Dropped Neighbor(s) - Router ID of the neighbor being dropped. 🥀
3.2.4. Request From TLV (RF TLV) 🙋♀️
this is another new TLV that says which neighbor(s) you're asking for their latest Hello state 🧚
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Request From Neighbor(s) |
+---------------------------------------------------------------+
| ....
+--------------------- Type: 8
- Length: Set to the number of neighbors included in the TLV multiplied by 4.
- Request From Neighbor(s) - Router ID of the neighbor(s) from which Hello state is being requested. 🎀
3.2.5. Full State For TLV (FSF TLV) 🌸
one more new TLV 🫶 this one names the neighbor(s) that the sending node is answering with full state 🦋
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Full State For Neighbor(s) |
+---------------------------------------------------------------+
| ....
+--------------------- Type: 9
- Length: Set to the number of neighbors included in the TLV multiplied by 4.
- Full State For Neighbor(s) - Router ID of the neighbor(s) should process this packet. 💜
3.2.6. Neighbor Adjacencies 🤝
this section covers building neighbor adjacencies and what happens when they fail, using the incremental Hello signaling 🧚
3.2.6.1. Building Neighbor Adjacencies 💖
Hello packets get sent periodically, following [OSPF] and [OSPFv3] 🕰️ an OSPF implementation that can send only partial neighbor info in Hellos SHOULD always set the I-bit in the Hellos it transmits, except where this document says otherwise 🫶 Hello packets MAY be skipped every HelloInterval if the router sends other packets during that time ✨
when a router gets a Hello from a brand new neighbor (here, "new" means a neighbor in less than Init state, as defined in Section 10.1 [OSPF]) and the Hello has the I-bit set, it will:
- Place the new neighbor in the neighbor list described in [OSPFv3], Appendix A.3.2. 🌷
- Increment the router's SCS number that it will use in its next Hello (indicated in the SCS TLV). 🔢
- Remove the neighbor from the neighbor list described in [OSPFv3], Appendix A.3.2, when the neighbor has reached the Exchange state (as described in [OSPF], Section 10.1). 🚪
- Remove the neighbor from the neighbor list described in [OSPFv3], Appendix A.3.2, if the neighbor is not a DR or backup designated router (BDR) on an OSPF broadcast link, and if the neighbor is advertised as connected in the network-LSA advertised by the DR. 🧹
3.2.6.2. Adjacency Failure 💔
when a router spots an adjacency failure (going to a state less than Exchange), a router using I-bit signaling SHOULD:
- Remove the adjacent router from local tables, and take the appropriate actions for a failed adjacency described in [OSPF] and [OSPFv3]. 🗑️
- Add the formerly adjacent router to a Neighbor Drop TLV. 📝
- Increment the router's SCS number that it will transmit in its next Hello. 🔢
- Transmit Hellos with this Neighbor Drop TLV. It may be desirable to send the Neighbor Drop TLV in three consecutive Hellos to increase the probability of reception. In this case, 'persistent' Hello packets would be sent with the same SCS number, the Neighbor Drop TLV, and the N-bit set. Thus, the receiver knows that the Neighbor Drop TLV is being sent persistently, and there is more state associated with the SCS in case it must request missing state presumably transmitted in a previous Hello. 📣✨
3.2.7. Sending Hellos 📨
okay so when a device first shows up on a network (wandering into range of another device, getting powered on, flipping its radio on, etc.), it needs the complete neighbor state from every neighbor before it can use the incremental Hello mechanism 🫶. So upon initialization, a device MAY send a multicast Hello request (and omit the Request From TLV). The neighbors get the request and reply with a Hello containing their complete neighbor state ✨.
If a device is in INIT state with a neighbor and gets a Hello from that neighbor without its router ID in the neighbor list, the device SHOULD request the current state from the neighbor. This is literally to dodge a "race" condition 💀, because that Hello could mean either that the device is NOT SEEN by the neighbor, or that the device is adjacent and just isn't in the incremental list. So when the neighbor gets that Hello request, it responds with its neighbor state for the neighbor 🦋.
The first Hello packet with a particular SCS number MUST contain the full state associated with that SCS number, i.e., all state changes since the last SCS number. The N-bit MUST NOT be set in the State Check Sequence TLV 🎀.
Incremental Hello packets can be sent persistently (sent in k successive Hello packets), with flexibility in how much information actually gets sent. There are three options:
- The entire incremental Hello packet is sent persistently. This is accomplished by simply sending the entire state associated with an SCS number for k successive Hellos. Since the SCS number stays the same, the N-bit is not set in these incremental Hello packets 💅.
- Partial information for a particular SCS number is sent persistently. After the first Hello packet with a particular SCS number is sent, only the TLVs that you want sent persistently go out in subsequent Hellos with the same SCS number, and the N-bit gets set 🌸.
- No information is sent persistently. This is the default behavior, where an incremental Hello packet with a particular SCS number is only sent once 🍓.
3.2.8. Receiving Hellos 👂
Each OSPF device supporting incremental Hello signaling, as described in this document, MUST keep the last known SCS number from each neighbor it has received Hellos from, as long as the neighbor adjacency structure is maintained 💜.
If a device receives a Hello from an adjacent neighbor with an SCS number less than the last known SCS number from that neighbor, it MUST first check whether the SCS number is a wrap around. "Wrap around" is when the last known SCS number is MAX_SCS (65535) and the new SCS number is 1 🔄. If it's not a wrap around, then the device MUST send a Hello request to the neighbor.
If it is a wrap around, or if a device receives a Hello from an adjacent neighbor with an SCS number one greater than the last known SCS number from that neighbor, it MUST:
- Examine the neighbor list described in [OSPFv3], Appendix A.3.2. If any neighbors are contained in this list, increment the SCS number contained in the adjacent neighbor's data structure.
- Examine the Neighbor Drop TLV as described in Section 3.2.6.2. If this list contains a neighbor other than the local router, increment the SCS number contained in the adjacent neighbor's data structure.
- Examine the Neighbor Drop TLV as described in Section 3.2.6.2. If the local router identifier is contained in this list, destroy the transmitting adjacent neighbor's data structures 👑.
- Examine any other TLVs incrementally signaled, as described in documents referring to this RFC. If there are other state changes indicated, increment the SCS number contained in the adjacent neighbor's data structure.
- If no state change information is contained in the received Hello, send a request for current state (by setting the 'R'-bit) in the next Hello 🙈.
If a device receives a Hello from an adjacent neighbor with an SCS number greater than the last known SCS number + 1 from that neighbor, it MUST send a Hello request to the neighbor, since it may be missing some neighbor state 😭.
3.2.8.1. Receiving Hellos with the N-bit Set 🧩
If a device receives a Hello with the SCS TLV included and the N-bit set in this TLV, it MUST verify that it has already received the SCS number with the N-bit NOT set from the neighbor. If the device determines that this is the first receipt of that SCS number from this neighbor, then it MUST send a Hello request to the neighbor, since it missed the initial Hello packet with that SCS number and is therefore missing state 🥺.
3.2.8.2. Receiving Hellos with the R-bit Set 🙋♀️
If a device receives a Hello with the SCS TLV included and the R-bit set, it looks for the RF TLV. If its router ID is listed in the RF TLV, or the TLV is not found, it includes its full state in the next Hello. This MUST include:
- The neighbor ID of the requesting neighbor(s) in the list of neighbors described in [OSPFv3], Appendix A.3.2.
- An SCS TLV with the transmitter's current SCS number and the FS-bit set. Note that the transmitter's SCS number is NOT incremented 🚫.
- Any other TLVs, defined in other documents referencing this RFC, indicating the current state of the local system.
- The neighbor ID of all the neighbors who have requested current state, in the FSF TLV.
If the full state is being sent to a large number of existing neighbors, an implementation could choose to instead generate a full state for all neighbors and omit the FSF TLV 🌈.
3.2.8.3. Receiving Hellos with the FS-bit Set 💖
When a device receives a Hello with the SCS TLV included and the FS-bit set, the Hello packet contains the neighbor's full state for the device. The packet SHOULD be processed as follows:
- If the received SCS number is equal to the last known SCS number, the packet SHOULD be ignored, since the device already has the latest state information 🫠.
- If the received SCS number is different from the last known SCS number, this Hello has new information and MUST be parsed ✨.
- If it is listed in the FSF TLV, or if the FSF TLV is not present, the device MUST save the SCS number, process the Hello as described in Section 3.2.8, and process any other appended TLVs 🎉.
3.2.9. Interoperability 🤝
On receiving a Hello packet from a new neighbor without the I-bit set, the local router will continue to place that router's identifier in transmitted Hellos on this link, as described in [OSPFv3], Appendix A.3.2 🧚.
3.2.10. Support for OSPF Graceful Restart 🔁
OSPF graceful restart, as described in [OSPFREST] and [OSPFGR], relies on the lack of neighbors in the list of neighbors described in [OSPFv3], Appendix A.3.2, to determine that an adjacent router has restarted, and on other signaling to determine that the adjacency should not be torn down. If all Hello packets transmitted by a given router have an empty Hello list, relying on an empty Hello packet to signal a restart (or to reliably tear down an OSPF adjacency) is no longer possible. Hence, this signaling has to be slightly altered 🥹. When a router would like to tear down all adjacencies, or signal that it has restarted:
- On initially restarting, during the first RouterDeadInterval after restart, the router will transmit Hello packets with an empty neighbor list and the I-bit cleared. Any normal restart or other signaling may be included in these initial Hello packets 🌙.
- As adjacencies are learned, these newly learned adjacent routers are included in the multicast Hellos transmitted on the link 🌱.
- After one RouterDeadInterval has passed, the incremental Hello mechanism is invoked. An incremental Hello packet with full state is sent with the I-bit set, the SCS TLV included with the FS-bit set, and the InitialSCS value (e.g., SCS of '1'). Subsequent Hello packets will include only incremental state 🌟.
Routers that are neighboring with a restarting router MUST continue sending their Hello packets with the I-bit set 💅.
3.3. Optimized Flooding (Overlapping Relays) 🌊
A component that can influence the scalability and convergence characteristics of OSPF ([OSPF], [OSPFv3]) in a MANET environment is how much information needs to be flooded. The ideal solution is that a router receives a particular routing update only once. However, there must be a trade-off between protocol complexity and making sure that every speaker in the network receives all of the information. Note that a speaker refers to any node in the network that is running the routing protocol and transmitting routing updates and Hello messages 📣.
Controlling the amount of information on the link matters even more in a MANET environment, because of the potential transmission costs and resource availability in general 💸.
In some environments, a group of speakers that share the same logical segment may not be directly visible to each other. Some possible causes are: low signal strength, long distance separation, environmental disruptions, partial VC (virtual circuit) meshing, etc. 📡 In these networks, a logical segment refers to the local flooding domain, dynamically determined by transmission radius. In these situations, some speakers (the ones not able to directly reach the sender) may never be able to synchronize their databases 😵. To solve these synchronization issues, a mechanism is needed through which all the nodes on the same logical segment can receive the routing information, regardless of the state of their adjacency to the source 🫶.
3.3.1. Operation Overview 🧠
The optimized flooding operation relies on the ability of a speaker to advertise all of its locally connected neighbors. In OSPF, this ability is realized through the use of link state advertisements (LSA)s ([OSPF], [OSPFv3]) 💫.
A speaker receives router-LSAs from its adjacent neighbors. A speaker's router-LSA conveys the list of the adjacent speakers of the originator ("neighbor list"). The local speaker can compare the neighbor list reported by each speaker to its own neighbor list. If the local neighbor list contains adjacent speakers that the originator cannot reach directly (i.e., those speakers that are not in the originator's neighbor list), then these speakers are locally known as non-overlapping neighbors for the originator 🔍.
The local speaker should relay any routing information to non-overlapping neighbors of the sender, based on the algorithm outlined in Section 3.3.8. Because more than one such speaker may exist, the mechanism is called "overlapping relays". The algorithm, however, does select the set of overlapping relays that should transmit first. This set is known as the active set of overlapping relays for a speaker 🦋✨
3.3.2. Determination of Overlapping Relays ✨
okay so step one 💅 is that every speaker builds its neighbor list and shares it in router-LSA packets. Once everyone has those, each speaker can work out its 2-hop neighborhood 🦋, which is basically the nodes that are neighbors of the speaker's 1-hop neighbors.
A bidirectional neighbor counts as an overlapping relay for a speaker if it can reach a node in that 2-hop neighborhood. In other words, it has 1-hop neighbors of its own, not counting the speaker 🫶.
The set of Active Overlapping Relays for a speaker is the minimum set of direct neighbors where every node in the 2-hop neighborhood is a neighbor of at least one relay in that active set. It's the tiniest squad that still covers everybody 🌸
Each speaker SHOULD select a set of Active Overlapping Relays using a selection algorithm. One suggested algorithm is in Section 3.3.4, and it's based on the multipoint relay (MPR) selection algorithm from [OLSR]. Overlapping relays MUST behave as specified in Section 3.3.8 💖
Also, a speaker MUST NOT choose a neighbor as an Active Overlapping Relay if that neighbor set the N-bit in its Active Overlapping Relay TLV (see Section 3.3.6). The one exception is when that neighbor is the only neighbor that can reach a 2-hop neighbor 🙈
Election of Active Overlapping Relays happens across interfaces, so it's node-based and not link-based. ✨
3.3.3. Terminology 🎀
The following heuristic and terminology for Active Overlapping Relay selection is mostly borrowed from [OLSR] 🧚
- FULL: Neighbor state FULL, as defined in [OSPF] and [OSPFv3]. Heads up that every neighbor reference in this document is assumed to be a FULL neighbor 💅
- N: N is the set of FULL neighbors of the node.
- 2-hop FULL neighbors (N2): The list of 2-hop neighbors of the node that are FULL and can be reached from direct neighbors, not counting any directly connected neighbors.
- Active Set: A (sub)set of the neighbors that are selected, so that through these selected nodes, all 2-hop FULL neighbors can be reached.
- D(y): The degree of a 1-hop neighbor node y (where y is a member of N) is the number of FULL neighbors of node y, EXCLUDING all the members of N and EXCLUDING the node doing the computation 🍓
3.3.4. Overlapping Relay Discovery Process 🔍
A possible algorithm for discovering overlapping relays goes like this 👑
- Start with an active set made of all members of N that have set the A-bit in their Active Overlapping Relay TLV (AOR TLV), as defined in Section 3.3.6.
- Calculate D(y), where y is a member of N, for all nodes in N.
- Add to the active set those nodes in N which are the only nodes to provide reachability to a node in N2. For example, if node b in N2 can be reached only through a symmetric link to node a in N, then add node a to the active set. Then remove the nodes from N2 that are now covered by a node in the active set 🫶
- While there are still nodes in N2 that are not covered by at least one node in the active set:
- A. For each node in N, calculate the reachability. That's the number of nodes in N2 that aren't yet covered by at least one node in the active set and that can be reached through this 1-hop neighbor.
- B. Select as an Active Overlapping Relay the node with the highest Willingness value (Section 3.3.7) among the nodes in N with non-zero reachability. If there are multiple choices, pick the node that provides reachability to the maximum number of nodes in N2. If multiple nodes provide the same amount of reachability, pick the one whose D(y) is greater. As a final tie breaker, the node with the highest router ID should be chosen. Then remove the nodes from N2 that are now covered by a node in the active set 🌈
- As an optimization, process each node, y, in the active set in increasing order of Willingness value. If all nodes in N2 are still covered by at least one node in the active set, excluding node y, and if the Willingness of node y is smaller than
MAX_WILLINGNESS, then node y should be removed from the active set 💀
3.3.5. The F Option Bit 🦋
A single new option bit, the F-bit, is defined in the LLS Type 1 Extended Options and Flags field. The F-bit tells everyone that the node supports the optimized flooding mechanism described in this document. Check Section 5 for where the F-bit lives 🧚
3.3.6. Active Overlapping Relay TLV (AOR TLV) 💜
A new TLV is defined so that each speaker can share its set of Active Overlapping Relays in the Hello messages. The TLV is sent using LLS [LLS] ✨
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Relays Added |A|N| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID(s) of Active Overlapping Relay(s) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- Type:
10 - Length: variable. This is the length of the TLV in bytes, NOT including Type and Length.
- Relays Added: variable. This is the number of Active Overlapping Relays that are being added. The number of Active Overlapping Relays being dropped is then given by
[(Length - 4)/4 - Relays Added]🎀 - A-bit: If this bit is set, the node is saying it will always flood routing updates that it receives, regardless of whether it is selected as an Active Overlapping Relay 💅
- N-bit: If this bit is set, the node is saying it most likely will not flood routing updates. The node SHOULD NOT be chosen to be an Active Overlapping Relay unless it is the only neighbor that can reach 2-hop neighbor(s). Also, if the node is selected as an Active Overlapping Relay and it can't do the required duties, the network behavior is not compromised, because it ends up behaving the same as if the node was never chosen 🙈
- Reserved: Reserved for future use. The sender MUST set this to zero, and the receiver MUST ignore it upon receipt. 🔒
- Router ID(s) of Active Overlapping Relay(s): The router IDs of neighbors that are either being chosen to serve as an Active Overlapping Relay or removed from serving as one. The Active Overlapping Relays being added MUST be listed first, and the number of such relays MUST equal Add Length. The remaining listed relays are being dropped as Active Overlapping Relays, and the number of those MUST equal
[(Length - 4)/4 - Relays Added]🍓
Note that the A-bit and N-bit don't depend on any particular selection algorithm for choosing the set of Active Overlapping Relays. However, the bits SHOULD be considered as input into the selection algorithm 🧠
If a node is selected as an Active Overlapping Relay and it does not support the Incremental Hello mechanism defined in Section 3.2, then it SHOULD always be included as an Active Overlapping Relay in the TLV. Also, while a node needs to know whether it is an Active Overlapping Relay, it doesn't necessarily have to know who the other Active Overlapping Relays are 🫶
3.3.7. Willingness TLV 🌟
A new TLV is defined so that each speaker can share its willingness to serve as an Active Overlapping Relay in the Hello message. The TLV is sent using the LLS [LLS] 🦋
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Willingness | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- Type:
11 - Length: 4 bytes. It does not include the Type and Length fields.
- Willingness: 1 byte that indicates how willing the node is to serve as an Active Overlapping Relay for its neighbors.
0:MIN_WILLINGNESS128:DEFAULT_WILLINGNESS255:MAX_WILLINGNESS
The TLV is optional and MUST be silently ignored if it isn't understood. If the Willingness TLV isn't included in the Hello packet, the Willingness value SHOULD be taken as DEFAULT_WILLINGNESS 💖
3.3.8. Flooding and Relay Decisions ✨
okay so this is where the relay drama actually happens 🎀 whether a node relays an LSA, and when it does, depends on the topology and on whether that node is one of the Active Overlapping Relays 💅
Upon receiving an LSA from a bi-directional neighbor, a node makes its flooding decisions using this algorithm 🧚:
- If the node is an Active Overlapping Relay for the adjacent speaker, the router SHOULD immediately relay whatever information it received from the adjacent speaker. Lowkey the easiest case 🔥
- If the node is a non-Active Overlapping Relay for the adjacent speaker, the router SHOULD wait a specified amount of time (PushbackInterval plus jitter (see Section 3.3.10)) before deciding whether to transmit. [Jitter is there so that several non-Active Overlapping Relays don't all propagate the same redundant info at once 🙈] Note that a node with the N-bit set in the 'Active Overlapping Relays' extension will not be chosen as an Active Overlapping Relay unless it is the only node providing reachability to a 2-hop neighbor. However, it MUST perform the duties of a non-Active Overlapping Relay as required. Non-Active Overlapping Relays MUST follow the acknowledgment mechanism outlined in Section 3.3.9.
A. During this time, if the node determines that flooding the LSA will only result in a redundant transmission, the node MUST suppress its transmission. Otherwise, it MUST transmit upon expiration of PushbackInterval plus jitter. Not me suppressing my own transmission for no reason, but this is the vibe 💀
B. If a non-Active Overlapping Relay hears a re-flood from another node that covers its non-overlapping neighbors before its timer to transmit expires, it SHOULD reset its PushbackInterval plus jitter timer. (Note that the implementation should take care to avoid resetting the PushbackInterval timer based on transmissions from Active Overlapping Relays.) During this time, if the node determines that flooding the update will only result in a redundant transmission, the node MUST suppress its transmission. Otherwise, it MUST transmit upon expiration of PushbackInterval plus jitter. Main character energy, but make it efficient 👑
C. If a non-Active Overlapping Relay hears an old instance of the LSA during this time, it SHOULD ignore the LSA, and it SHOULD NOT send a unicast packet to the neighbor with the most recent LSA as specified in [OSPFv3]. 🫶
- For LSAs that are received unicast because of retransmission by the originator, the node MUST determine whether it has already received the LSA from another speaker. If it already has the current instance of the LSA in its database, it MUST do nothing further in terms of flooding the LSA (since it would have taken appropriate action when it first received the LSA). However, if it does not have the current instance of the LSA in its database, it MUST take action according to the rules above, just as if it had received the multicast LSA. The acknowledgment mechanism outlined in Section 3.3.9 MUST be followed, and any timeout mechanism for unicast LSAs MAY be followed.
Note that a node can determine whether further flooding an LSA will only result in a redundant transmission by already having heard link state acknowledgments (ACKs) or floods for that LSA from all of its neighbors. Bestie, that's the whole trick ✨
Because the network is dynamic, the set of Active Overlapping Relays may not be up to date when the relay decision gets made, or it may not be able to do its flooding duties, e.g., because of poor link quality 📉. The non-Active Overlapping Relays are there so this situation doesn't cause database synchronization issues and, thus, packet loss 🛟.
Since the originator of the information, the relay, and the receiver are all in the same dynamically determined local flooding domain, the relay MUST NOT change the routing update information. In general, LSAs SHOULD be sent to a well-known multicast address. In some cases, routing updates MAY be sent using unicast packets. 🦋
3.3.9. Intelligent Transmission of Link State Acknowledgments 🌸
To optimize bandwidth use on the link, a speaker MUST follow these recommendations about ACK transmissions:
- All ACKs MUST be sent via multicast.
- Typically, LSAs are acknowledged by all of the adjacent speakers. In the case of relayed information, the relay MUST only expect either explicit or implicit acknowledgments from neighbors that have not previously acknowledged this LSA. Don't chase the people who already said yes 🙄
- Because routing updates are sent via multicast, the set of overlapping speakers will usually receive the same update more than once. A speaker SHOULD only acknowledge the first update received on the link.
- An Active Overlapping Relay SHOULD NOT explicitly acknowledge information that it is relaying. The relayed information will serve as an acknowledgment to the sender. If no information is being relayed, then an explicit ACK MUST be sent. 🫠
- Several ACKs MAY be bundled into a single packet. The wait (AckInterval) before sending one such packet reduces the number of packet transmissions required to acknowledge multiple LSAs. Efficiency era 🍓
- All ACK packets SHOULD reset the RouterDeadInterval at the receiver. If there is no state waiting to be transmitted in a Hello packet at the sender, then the HelloInterval at the sender SHOULD be reset. Note that an ACK serves as a Hello packet with no state change. So every ACK is basically a little "still here" text 💌
- Any LSA received via unicast MUST be acknowledged. (Note that acknowledgment is via multicast as specified in rule (1) above.)
An ACK received from a non-overlapping neighbor should prevent redundant transmission of the information to it by another overlapping relay. Should, not must, so it's a vibe check, not a rule 🧐
3.3.10. Important Timers ⏰
This section details the timers that were introduced in Sections 3.3.8 and 3.3.9.
- PushbackInterval: The length of time in seconds that a non-Active Overlapping Relay SHOULD wait before further flooding an LSA, if needed. This timer MUST be less than 1/2 of the RxmtInterval ([OSPF], [OSPFv3]) minus propagation delays, i.e.,
(PushbackInterval + propagation delay) < RxmtInterval/2. The PushbackInterval is set by a non-Active Overlapping Relay upon receipt of an LSA. ⏳ - AckInterval: After a node determines that it must transmit an ACK and the AckInterval timer is not already set, the node SHOULD set the AckInterval timer. The AckInterval is the length of time in seconds that a node should wait in order to transmit many ACKs in the acknowledgment packet. This wait reduces the number of packet transmissions required to acknowledge multiple LSAs. The AckInterval MUST be less than the PushbackInterval minus propagation delays, i.e.,
(AckInterval + propagation delay) < PushbackInterval. 🕰️
3.3.11. Miscellaneous Protocol Considerations 🧩
The mechanism described refers to the operation of relays on a common media segment. In other words, an LSA is only relayed out the same interface it was received on. However, the concept of information relay may be extended to flooding all link state advertisements received on any interface (and forwarded on any other interface). OSPF works on the premise that all of the nodes in a flooding domain will receive all of the routing information. One of the important properties here is that the routing information is not altered when relayed. 🎀
If each speaker advertised all of its adjacent neighbors on all interfaces, then the overlap check would determine which speakers are adjacent to both speakers. As a result, link state information should only be flooded to non-overlapping neighbors (taking all of the interfaces into account).
The flooding mechanism in OSPF relies on a designated router to guarantee that any new LSA received by one router attached to the broadcast network will be re-flooded properly to all the other routers attached to that broadcast network. Such designated routers must be able to reach all of the other speakers on the same subnet. A designated router SHOULD NOT be elected if overlapping relays are used. 🙅♀️
If such designated routers already exist, then the relays MUST be capable of differentiating them and then making relaying decisions based on OSPF's normal operation. As a result, there may be groups of neighbors to which some information should not be relayed. This mode of operation is NOT RECOMMENDED, as it adds complexity to the system. Sis, that's a lot of moving parts 😭
The intent of the overlapping relay mechanism is to optimize flooding of routing control information. However, other information (such as data) may also be relayed in some networks using the same mechanism. 💜
3.3.12. Interoperability 🤝
On receiving a Hello packet from a new neighbor without the F-bit set, the local router will assume that the new neighbor will flood normally as described in [OSPFv3]. Thus, the local router SHOULD include the neighbor in its overlapping relay set, since the neighbor will flood by default. This allows the local router to select its entire overlapping relay set more optimally 🌈.
If the F-bit is set and the I-bit as defined in Section 3.2 is not set in the neighbor's Hello, and the neighbor is selected as an overlapping relay by the local router, the local router will continue to include the neighbor's identifier in its active relay set. Old friend, still in the group chat ✨
3.4. New Bits in LLS Type 1 Extended Options and Flags 🎀
Two new option bits are defined in the "LLS Type 1 Extended Options and Flags" Field [LLS] as follows:
- I-bit - defined in Section 3.2.1: The I-bit is only defined for Hello packets and indicates that only incremental information is present. 🍓
- F-bit - defined in Section 3.3.5: The F-bit indicates that the node supports the optimized flooding mechanism as specified in this document. 🫶
3.5. Smart Peering 🦋
There is significant overhead in OSPF when a router has to establish adjacencies with every peer it can verify 2-way connectivity with. OSPF supports the broadcast network type for these scenarios, where you only have to peer with the designated router (DR). However, a full mesh of connectivity is required for proper operation, and this doesn't help in networks with overlapping partial meshes of connectivity. This document proposes a technique to reduce the number of adjacencies based on shortest path tree (SPT) reachability information. Fewer adjacencies, less drama 🌸
3.5.1. Rationale for Smart Peering ✨
okay so in OSPF ([OSPF], [OSPFv3]), nodes set up an adjacency by first checking 2-way connectivity between them 🔗 and then syncing their link state databases. once the peering is done and the adjacency is up, they keep advertising each other in their LSAs 💅 so peers stay in the link state database and get counted in all the SPF (Shortest Path First) calculations. during reliable flooding, a node must ensure that each peer has actually received the flooded routing update, using an acknowledgment and retransmission mechanism 🫶
so basically, keeping an adjacency for a particular peer is a trade-off 🤔 you get more redundancy in routing paths and network reachability, but you pay for it with overhead like memory consumption, SPF computations, routing overhead, and network convergence.
we should consider reducing the number of adjacencies a node maintains without hurting reachability and redundancy. this has direct implications on network scalability and is especially attractive in environments where the topology is dynamic 🦋 for example, in a mobile ad hoc network (MANET), nodes are mobile and the topology is constantly changing, so it seems highly desirable to 'intelligently' become adjacent with only selected peers, and not set up a peering session with every node that comes within transmission range 🌈 selective peering can be particularly useful for avoiding the peering process for unstable nodes, i.e., nodes that come in and out of transmission range 🙈
3.5.2. Previous Related Work 🍓
forming a FULL adjacency requires discovery (2-way relationship) and database synchronization. to avoid reaching the FULL state, others have modified link state protocols to use periodic advertisements (instead of a database exchange). the result is that neighbor discovery is still required, but routing information is learned over time. an example of this approach is:
- OSPFv2 Wireless Interface Type [WINTF]
- where the use of periodic advertisements "eliminates the formation of full adjacencies on wireless interfaces; all neighbor states beyond 2-Way are not reached,and no database synchronization is performed".
what we propose here goes a step further 🚀 by not requiring the formation and maintenance of neighbor state (2-way, or other) and without changing the route distribution mechanisms in the link state protocols. in other words, the mechanism described is completely backward compatible 💖
3.5.3. Smart Peering Solution 👑
two routers are defined as synchronized when they have identical link state databases. to limit the number of neighbors that are formed, an algorithm is needed to select which neighbors to peer with 💅
The algorithm MUST provide reachability to every possible destination in the network, just as when normal adjacency formation processes are used. we should always peer with a neighbor if it provides our only path to currently unreachable destinations ✨
3.5.3.1. SPT Reachability Heuristics 🧚
the peering decision is really a local matter to a router. if a router can ensure that reachability to other nodes is available without bringing up a new adjacency, it can choose not to bring up the new adjacency 🫶
we propose an algorithm that uses the existing information about a new neighbor's reachability in the SPT. if the two routers can already reach each other in the SPT, it is not necessary to form an adjacency between them 🌸
the decision to peer or not is made when a Hello is received. when a Hello is received from a new neighbor or a neighbor in a state lower than Exchange:
- A check is made in the link state database to see if the peer is already reachable in the SPT.
- If the peer is either not known in the SPT or is not reachable, we start the Exchange process.
- If the peer is reachable, then bringing up adjacency with this neighbor does not provide reachability to any new destinations.
let's take an example of a single OSPF area. this check would look for the neighbor's router-LSA. if the LSA is present in the database and is reachable in the SPT, we have a chance to suppress adjacency formation 🔥
it's worth noting that as the number of links and redundancy in the network is reduced, the likelihood of suboptimal routing increases 💀
3.5.3.2. State Machine 🎀
the state machine of a basic implementation of this algorithm is provided below. An implementation MAY use some heuristics (Step (3) below), beyond the SPT reachability, to decide whether or not it considers a new adjacency to be of value 🦋
......................
|Receive a Hello |
(1) |from a new potential|
|neighbor |
'`''''''''''''''''''''
|
|
|
,''''''''''''''''''''''|
|Check to see if there |
(2) |is a router-LSA from |----no--(4)form a
|the new potential | new
|neighbor in the link | neighbor
|state database, which |
|is reachable in SPT |
'`''''''''''''''''''''''
|
|yes
(3) |
,'''''''''''''''''''''''''''''''''''''''''''''''''''''''''|
| (3b)........................ |
|(3a),______________________ |Determine if the | |
| |Determine if the new | |number of redundant | |
| |link cost is better | |paths to the potential| |
| |than the current path| |neighbor is < the | |
| |cost by a configured | |maximum configured | |
| |amount | |value | |
| '`''''''''''''''''''''' '`'''''''''''''''''''''' |
| \ / |
| .....\.........../.... |
| |User configurable | |
| |selection algorithm | |
| '`'''/'''''''\'''''''' |
| / \ |
'`'''''''''''''''''''''/'''''''''''\'''''''''''''''''''''''
/ \
requirements requirements
met not met
/ \
/ \
(4) form a new neighbor (5) do not become
neighbors3.5.4. Advertising 2-Way Links in Router-LSAs 🌈
the technique described in Section 3.5.3 minimizes the number of adjacencies in highly meshed environments. this is especially useful when the network is in motion and the average adjacency lifetime is small 🏎️
however, it has an undesirable side effect 😬 it limits the number of transit links available to forward traffic.
an implementation may choose to allow some (or even all) of these 2-way state neighbors to be announced in the router-LSA. since the state remains 2-way, we don't incur control plane (database sync and flooding) overhead. however, advertising the link in the router-LSA makes the link available to the data plane 💜
this can be safely done if the neighbor is reachable in a special SPT constructed by ignoring any other 2-way links in the network. this optional optimization is described below 🫶
3.5.4.1. Unsynchronized Adjacencies ✨
Okay so if the new neighbor is already reachable in the SPT, there's zero rush to do a full database sync with it 🫶. Here's what we do once a neighbor hits 2-way state. (Quick note: when I say "SPT" in this section, I mean the special SPT built using the rules in Section 3.5.4.2 💅.)
- After a 2-WayReceived event, check whether the neighbor is reachable in the SPT. If it is, mark the neighbor as FULL with respect to link advertisement.
- That means the router-LSA or network-LSA link for that neighbor gets advertised as if the neighbor were FULL 👑.
- The adjacency information is built with the U-bit (more on that below) 🔥.
- Database synchronization gets postponed:
- by a configured amount of time, OR
- until it's absolutely "necessary"
Either way, if a database sync is pending, it kicks off the moment we notice the neighbor is no longer reachable in the SPT. The sync can be done by Out-of-Band Sync [OOB], which keeps the current adjacency alive and syncs in the background ✨. A normal resync also works, but it comes with the drawback of an adjacency flap 😭.
In standard OSPF, we bring up the adjacency first and then announce a transit link. This approach lets the link be used as a forwarding path super fast, and still syncs the database in a timely way when the alternate flooding path was recently broken 🦋.
There's also a circular dependency we have to sort out 🙈. Once you start announcing the link, the shortest path will probably be via this very link. So it's not trivial to detect when the alternate dependent path is gone. What we'd really like is to know the neighbor is reachable via a path that doesn't go through an unsynchronized path.
We've generally solved this kind of problem by running an SPF and pretending the link in question doesn't exist. It doesn't need a full SPF, just enough to see if ANY other path reaches the neighbor. The worst case is when the alternate path is really gone, and we find that out by building a full SPT. This has to happen every time the link state database changes, and for EACH link whose viability depends on the SPT. That raises scalability concerns, so we won't dig into it further here 💀.
We can get the same results with just ONE additional SPF that's capable of ignoring these Unsynchronized links. The result from that SPT can satisfy the reachability condition for ANY number of Unsynchronized Adjacencies. This basically requires being able to tell the difference between a normal FULL adjacency and this new Unsynchronized Adjacency. There are two ways to do that:
(A) Define LD Options and use a bit in it, like this:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | LD Options | Metric |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Interface ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Link Description in a Router-LSALD Options are the Link Description options 🎀. They're used to specify some special capability or state of a link. Here's how they look:
+-+-+-+-+-+-+-+-+
| | | | | | | |U|
+-+-+-+-+-+-+-+-+
LD OptionsThe U-bit is the "Unsynchronized" bit 🦋. It gets set if the adjacency is being announced before the databases are fully synchronized.
This approach is backward compatible, because the only routers looking at this bit are the ones that support the mechanisms specified in this document 🫶.
(B) Introduce a new link type in router-LSA.
This one's a much more complex solution, with backward compatibility concerns, because unknown link type handling isn't defined in the OSPF standard [OSPF]. So this solution isn't considered any further 🙅♀️.
3.5.4.2. Unsynchronized SPT 🌸
Whenever link state changes happen, we need to run ONE additional SPF by ignoring all links with the U-bit set. This SPT is then consulted to see if any of our Unsynchronized Adjacencies need to start database sync. It's also consulted when a new neighbor goes into 2-way state, to decide whether we form the adjacency immediately or defer it for later 🧚.
3.5.4.3. Flooding Considerations 🌈
One of the main goals of delaying database synchronization is cutting down on unnecessary OSPF packets traversing these links 💜. Since the unsynchronized Adjacencies stay in 2-way state, OSPF updates won't be flooded over the corresponding interfaces, which means extra savings ✨.
An option is provided to enable or disable flooding over these Unsynchronized Adjacencies. The upside of allowing flooding is being able to use more links for control plane purposes. We still get the savings of not having to form the adjacency 💅.
3.5.4.4. Overlapping Relay (OR) Election Impact 👑
The overlapping relay election algorithm uses the 2-hop neighborhood it gleans from our neighbor's router-LSAs. Unsynchronized Adjacencies need to be considered in the relay election algorithm 🔥.
If flooding is enabled on unsynchronized Adjacencies, no change is needed in the relay election algorithm 🫶. If flooding is disabled, then the relay election algorithm needs to prune neighbors that are connected via an Unsynchronized Adjacency from our 1-hop and 2-hop neighbor lists 🙈.
4. Security Considerations ✨
Okay bestie, this section is SERIOUS 😭🔥 Read it like your network depends on it, because it kinda does.
In a MANET, security is both harder and more important, because the medium is wireless 📡. Controlling which devices can connect to a MANET at Layer 2 is left to Layer 2 security mechanisms, such as 802.1x, and others 🔐. Controlling which attached devices can transmit traffic needs some kind of security system (outside the scope of this document) that can authenticate, and provide authorization for, individual members of the routing domain 💖.
The other security considerations are similar to any MANET protocol extension. Here's what [MDR] has to say:
As with OSPFv3 [OSPFv3], OSPF-OR can use the IPv6 Authentication Header (AH) [AH] and/or the IPv6 Encapsulation Security Payload (ESP) [ESP] to provide authentication, integrity, and/or confidentiality. The use of AH and ESP for OSPFv3 is described in [OSPFv3-SEC].
Generic threats to routing protocols are described and categorized in [THREATS]. The mechanisms described in [OSPFv3-SEC] protect against many of these threats, but not all of them. In particular, as mentioned in [OSPFv3], these mechanisms do not protect against compromised, malfunctioning, or misconfigured routers (also called Byzantine routers 👀). This is true for both OSPFv3 and OSPF-OR.
Extending OSPFv3 to include MANET routers doesn't introduce any new security threats. However, the wireless medium and the lack of infrastructure that come with MANET routers may make some of the attacks described in [THREATS] easier to pull off 😬. Depending on the network context, these 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, since the attacker only needs to be within radio range of a router 📻. Confidentiality (encryption) protects against sniffing, but not against traffic analysis.
Interference attacks are also easier to mount against MANET routers because of their wireless nature 📶. Such attacks can still happen even if OSPF packets are protected by authentication and confidentiality, for example by transmitting noise or replaying outdated OSPF packets 💀. As discussed below, an anti-replay service (provided by both ESP and AH) can protect against the 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) 🙅♀️.
[OSPFv3-SEC] 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. This is required in order to achieve scalability and feasibility, as explained in [OSPFv3-SEC]. Future specifications can explore automated key management protocols that may be suitable for MANETs ✨.
As discussed in [OSPFv3-SEC], manual keys can increase vulnerability 🚨. For example, manual keys are usually long lived, which gives an attacker more time to discover them. On top of that, 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 😱.
Although [AH] and [ESP] state that implementations of AH and ESP SHOULD NOT provide anti-replay service in conjunction with SAs that are manually keyed, it's important to note that such service is allowed if the sequence number counter at the sender is correctly maintained across local reboots until the key is replaced 🔁. So it may be possible for MANET routers to make use of the anti-replay service provided by AH and ESP 🎀.
When an OSPF routing domain includes both MANETs and fixed networks, the frequency of OSPF updates, whether from actual topology changes or from malfeasance, could cause instability in the fixed networks 🌪️. Where that's a concern, it's recommended that the border routers segregate the MANETs from the fixed networks, either with separate OSPF areas or, where 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 MANETs ⏳. OSPF ranges can also be configured to aggregate prefixes for the areas supporting MANETs 🧩. With separate OSPF instances, more conservative local policies can be used to limit the volume of updates coming out of the MANETs 💅.
5. IANA Considerations ✨
IANA has made the assignments below, following the policies in [IANA] 💅
- I-bit and F-bit from the "LLS Type 1 Extended Options and Flags" registry, as defined below 🎀
+---+---+---+---+---+---+---+- -+---+---+---+---+---+---+---+---+
| * | * | * | * | * | * | * |...| * | * | * | * | F | I | RS| LR|
+---+---+---+---+---+---+---+- -+---+---+---+---+---+---+---+---+
Bits in Extended Options and Flags TLV- New TLV types from the "Link Local Signalling TLV Identifiers (LLS Types)" registry, as defined below 🦋
TLV Name TLV Type
-------- --------
State Check Sequence TLV 6
Neighbor Drop TLV 7
Request From TLV 8
Full State For TLV 9
Active Overlapping Relay TLV 10
Willingness TLV 11- A new registry has been defined for LD Options, as explained in Section 3.5.4.1. The U-bit is allocated by this document. 🌸
All future additions to LD Options are subject to OSPF WG review and require IETF Review. Bestie, that's the rule for any new LD Options, so keep it in mind 🧚
6. Contributors 🫶
The following persons are contributing authors to the document:
Fred Baker Dave Cook
Cisco Systems Cisco Systems
1121 Via Del Rey 7025-4 Kit Creek Road
Santa Barbara, CA 93117 Research Triangle Park, NC 27709
USA USA
EMail: fred@cisco.com EMail: dacook@cisco.com
Alvaro Retana Yi Yang
Cisco Systems Cisco Systems
7025-4 Kit Creek Road 7025-4 Kit Creek Road
Research Triangle Park, NC 27709 Research Triangle Park, NC 27709
USA USA
EMail: aretana@cisco.com EMail: yiya@cisco.com
Russ White
Cisco Systems
7025-4 Kit Creek Road
Research Triangle Park, NC 27709
USA
EMail: riw@cisco.com7. Acknowledgments 💖
The authors and contributors would like to thank Pratap Pellakuru and Stan Ratliff for their feedback and implementation of the document. Thanks to Richard Ogier and John Avery for doing a final review. The whole group chat is so grateful, no cap 🙌
8. References 📚
8.1. Normative References
[OSPF] Moy, J., "OSPF Version 2", STD 54, RFC 2328,
April 1998.
[OSPFv3] Coltun, R., Ferguson, D., Moy, J., and A. Lindem,
"OSPF for IPv6", RFC 5340, July 2008.
[LLS] Zinin, A., Roy, A., Nguyen, L., Friedman, B., and
D. Yeung, "OSPF Link-Local Signaling", RFC 5613,
August 2009.
[IANA] Narten, T. and H. Alvestrand, "Guidelines for Writing
an IANA Considerations Section in RFCs", BCP 26,
RFC 5226, May 2008.
[KEY] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.8.2. Informative References
[IPV6ADD] Hinden, R. and S. Deering, "IP Version 6 Addressing
Architecture", RFC 4291, February 2006.
[OSPFGR] Moy, J., Pillay-Esnault, P., and A. Lindem, "Graceful
OSPF Restart", RFC 3623, November 2003.
[OSPFREST] Nguyen, L., Roy, A., and A. Zinin, "OSPF Restart
Signaling", RFC 4812, March 2007.
[OOB] Nguyen, L., Roy, A., and A. Zinin, "OSPF Out-of-Band
Link State Database (LSDB) Resynchronization",
RFC 4811, March 2007.
[OLSR] Clausen, T., Ed., and P. Jacquet, Ed., "Optimized Link
State Routing Protocol (OLSR)", RFC 3626,
October 2003.
[WINTF] Ahrenholz J., et al., "OSPFv2 Wireless Interface
Type", Work in Progress, May 2004.
[MDR] Ogier, R. and P. Spagnolo, "Mobile Ad Hoc Network
(MANET) Extension of OSPF Using Connected Dominating
Set (CDS) Flooding", RFC 5614, August 2009.
[AH] Kent, S., "IP Authentication Header", RFC 4302,
December 2005.
[ESP] Kent, S., "IP Encapsulating Security Payload (ESP)",
RFC 4303, December 2005.
[OSPFv3-SEC] Gupta, M. and N. Melam,
"Authentication/Confidentiality for OSPFv3", RFC 4552,
June 2006.
[THREATS] Barbir, A., Murphy, S., and Y. Yang, "Generic Threats
to Routing Protocols", RFC 4593, October 2006.Authors' Addresses 🌈
Abhay Roy (Editor)
Cisco Systems
170 W. Tasman Drive
San Jose, CA 95134
USA
EMail: akr@cisco.com
Madhavi W. Chandra (Editor)
113 Holmhurst Court
Cary, NC 27519
EMail: mw.chandra@gmail.com📦 where this page comes from
- ietf: rfc5820 2010-03
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms