RFC 1584
Multicast Extensions to OSPF
RFC 1584: Multicast Extensions to OSPF 🦋
Okay bestie, let's start with the title block 📋 This is RFC 1584, "Multicast Extensions to OSPF," from the Network Working Group ✨ It was written by J. Moy of Proteon, Inc. 💖 The category is Standards Track, and the date is March 1994 🌸 The title block doesn't list any RFCs that this one obsoletes or updates, so there's nothing else to track there 🫶
Status of This Memo
Okay so this document is an Internet standards track protocol for the whole Internet community 🌈 It also asks everyone to share discussion and suggestions for improvements, so bring your ideas 💅 For where this protocol stands right now, check the current edition of the "Internet Official Protocol Standards" (STD 1) ✨ And distribution is unlimited, so share it with your whole group chat 🎀
Abstract
Okay, main character energy alert 🚨 This memo is all about enhancements to OSPF that let it route IP multicast datagrams 🦋 The twist is that a multicast packet gets routed based on both its source and its multicast destination. That's called source/destination routing, and it's giving precision 💅 As it travels, the packet follows a shortest path to each multicast destination ✨
Here's the part that's lowkey genius 🧠 When multiple hosts are in the same multicast group, the packet only gets replicated when the paths to those hosts diverge. So any shared stretch of path gets reused instead of duplicated 🌸 Iconic efficiency, no cap 💖
OSPF is a link-state routing protocol, and it keeps a database that describes the Autonomous System's topology 🗺️ This memo adds a new OSPF link state advertisement that describes where the multicast destinations are 📍 Then a multicast packet's path gets calculated by building a pruned shortest-path tree rooted at the packet's IP source 🌳 These trees get built on demand, and the results get cached so later packets can reuse them ⭐
These multicast extensions are built on top of OSPF Version 2 💜 They've been implemented so multicast routing can be rolled out piecemeal into an OSPF Version 2 routing domain 🧚 Some routers can run the multicast extensions while others keep forwarding only regular IP traffic (unicasts) 🫶 That's a whole vibe for gradual rollouts 🎀
Please send comments to mospf@gated.cornell.edu 💌
Table of Contents
1 Introduction ........................................... 4
1.1 Terminology ............................................ 5
1.2 Acknowledgments ........................................ 6
2 Multicast routing in MOSPF ............................. 6
2.1 Routing characteristics ................................ 6
2.2 Sample path of a multicast datagram .................... 8
2.3 MOSPF forwarding mechanism ............................ 10
2.3.1 IGMP interface: the local group database .............. 10
2.3.2 A datagram's shortest-path tree ....................... 14
2.3.3 Support for Non-broadcast networks .................... 16
2.3.4 Details concerning forwarding cache entries ........... 16
3 Inter-area multicasting ............................... 18
3.1 Extent of group-membership-LSAs ....................... 19
3.2 Building inter-area datagram shortest-path trees ...... 22
4 Inter-AS multicasting ................................. 27
4.1 Building inter-AS datagram shortest-path trees ........ 28
4.2 Stub area behavior .................................... 30
4.3 Inter-AS multicasting in a core Autonomous System ..... 31
5 Modelling internal group membership ................... 31
6 Additional capabilities ............................... 33
6.1 Mixing with non-multicast routers ..................... 34
6.2 TOS-based multicast ................................... 35
6.3 Assigning multiple IP networks to a physical network .. 36
6.4 Networks on Autonomous System boundaries .............. 37
6.5 Recommended system configuration ...................... 38
7 Basic implementation requirements ..................... 40
8 Protocol data structures .............................. 40
8.1 Additions to the OSPF area structure .................. 41
8.2 Additions to the OSPF interface structure ............. 42
8.3 Additions to the OSPF neighbor structure .............. 43
8.4 The local group database .............................. 43
8.5 The forwarding cache .................................. 44
9 Interaction with the IGMP protocol .................... 45
9.1 Sending IGMP Host Membership Queries .................. 46
9.2 Receiving IGMP Host Membership Reports ................ 46
9.3 Aging local group database entries .................... 47
9.4 Receiving IGMP Host Membership Queries ................ 47
10 Group-membership-LSAs ................................. 48
10.1 Constructing group-membership-LSAs .................... 49
10.2 Flooding group-membership-LSAs ........................ 52
11 Detailed description of multicast datagram forwarding . 52
11.1 Associating a MOSPF interface with a received datagram 55
11.2 Locating the source network ........................... 55
11.3 Forwarding locally originated multicasts .............. 57
12 Construction of forwarding cache entries .............. 58
12.1 The Vertex data structure ............................. 59
12.2 The SPF calculation ................................... 60
12.2.1 Candidate list Initialization: Case SourceIntraArea ... 65
12.2.2 Candidate list Initialization: Case SourceInterArea1 .. 66
12.2.3 Candidate list Initialization: Case SourceInterArea2 .. 66
12.2.4 Candidate list Initialization: Case SourceExternal .... 67
12.2.5 Candidate list Initialization: Case SourceStubExternal 70
12.2.6 Processing labelled vertices .......................... 70
12.2.7 Merging datagram shortest-path trees .................. 71
12.2.8 TOS considerations .................................... 72
12.2.9 Comparison to the unicast SPF calculation ............. 74
12.3 Adding local database entries to the forwarding cache 75
13 Maintaining the forwarding cache ...................... 76
14 Other additions to the OSPF specification ............. 77
14.1 The Designated Router ................................. 77
14.2 Sending Hello packets ................................. 78
14.3 The Neighbor state machine ............................ 78
14.4 Receiving Database Description packets ................ 78
14.5 Sending Database Description packets .................. 79
14.6 Originating Router-LSAs ............................... 79
14.7 Originating Network-LSAs .............................. 79
14.8 Originating Summary-link-LSAs ......................... 80
14.9 Originating AS external-link-LSAs ..................... 80
14.10 Next step in the flooding procedure ................... 81
14.11 Virtual links ......................................... 81
15 References ............................................ 83
Footnotes ............................................. 84
A Data Formats .......................................... 88
A.1 The Options field ..................................... 89
A.2 Router-LSA ............................................ 91
A.3 Group-membership-LSA .................................. 93
B Configurable Constants ................................ 95
B.1 Global parameters ..................................... 95
B.2 Router interface parameters ........................... 95
C Sample datagram shortest-path trees ................... 97
C.1 An intra-area tree .................................... 98
C.2 The effect of areas .................................. 100
C.3 The effect of virtual links .......................... 101
Security Considerations .............................. 102
Author's Address ..................................... 102Okay that's the front matter, bestie 💖 Next up is Section 1, Introduction, so stay tuned 🦋✨
1. Introduction ✨
okay so this memo is all about upgrading OSPF Version 2 so it can handle IP multicast routing 🦋 the upgrade is backward-compatible, which is so important bestie. routers running the multicast additions still interoperate with non-multicast OSPF routers when they forward regular (unicast) IP data traffic 🫶 the protocol you get after adding the multicast enhancements to OSPF is called the MOSPF protocol 💜
IP multicasting is basically LAN multicasting but stretched across a whole TCP/IP internet 🌈 host multicasting support is specified in [RFC 1112]. there, multicast groups are represented by IP class D addresses 🎀 hosts join and leave groups using the Internet Group Management Protocol (IGMP, also specified in [RFC 1112]) 🧚 a host doesn't have to be a member of a group to send datagrams to it, which is lowkey wild 😭 and multicast datagrams get delivered to each group member with the same "best-effort" delivery that regular (unicast) IP traffic gets 💅
MOSPF can forward multicast datagrams from one IP network to another (aka through internet routers) 🔥 it decides where a multicast datagram goes based on both its source and its destination, which is sometimes called source/destination routing 👑 the OSPF link state database gives a full picture of the Autonomous System's topology 🍓 then the new group-membership-LSA type gets added, so the location of every multicast group member is pinpointed right in the database ✨ from there, the path of a multicast datagram gets calculated by building a shortest-path tree rooted at the datagram's source 🌸 any branches without multicast members get pruned off 💀 these pruned trees are built the first time a datagram shows up (on demand!) and then the results are cached for later datagrams with the same source and destination 🙈
here's the catch: OSPF lets an Autonomous System be split into areas, and when that happens you lose complete knowledge of the topology 😭 so when multicasts go between areas, only incomplete shortest-path trees can be built, which can lead to some routing inefficiency 🥺 a similar situation happens when the source lives in a different Autonomous System 💔 in both cases the neighborhood right around the source is unknown, so it gets approximated using OSPF summary link advertisements (different area) or OSPF AS external link advertisements (different Autonomous System) 🦋
MOSPF routers and non-multicast OSPF routers can totally live together 🫶 both types interoperate when forwarding regular (unicast) IP data traffic ✨ the one limit is that the forwarding reach of IP multicasts is capped by how many MOSPF routers are in the Autonomous System (and how they're interconnected) 🥀 there's no way to "tunnel" multicast datagrams through non-multicast routers, sorry bestie 🙅♀️ and just like base OSPF, datagrams (multicast or unicast) are routed "as is", meaning they don't get further encapsulated or decapsulated as they travel through the Autonomous System 🎀
1.1. Terminology
this memo uses the terminology from section 1.2 of [OSPF] 📖 so terms like "Network", "Autonomous System" and "link state advertisement" are assumed to be understood already 💖 we also use LSA as the abbreviation for "link state advertisement" 🌸 so router links advertisements are called router-LSAs, and the brand new link state advertisement describing where multicast group members are is called a group-membership-LSA 🧚
[RFC 1112] talks about how IP multicast datagrams get encapsulated at the data-link layer 🦋 and here's the twist: on a broadcast network, the IP multicast destination isn't mapped to a data-link address with ARP like unicast does ✨ instead, there are static mappings from IP multicast destinations to data-link addresses 🌈 those mappings depend on the network type: some networks algorithmically map IP multicasts to data-link multicast addresses, and others map every IP multicast destination onto the data-link broadcast address 💅 this document loosely calls both of these "data-link multicast" 🫶
the following terms also show up all over this document 🎀
- Non-multicast router. A router running OSPF Version 2 but not the multicast extensions 🥺 these routers don't forward multicast datagrams, but they can still work with MOSPF routers when forwarding unicast packets 🌸 routers running the MOSPF protocol are called either multicast-capable routers or MOSPF routers 👑
- Non-broadcast networks. A network that supports attaching more than two stations, but can't deliver a single physical datagram to multiple destinations (aka it doesn't support data-link multicast) 🔥 [OSPF] calls these non-broadcast, multi-access networks 💜 an X.25 PDN is an example 🍓
- Transit network. A network with two or more OSPF routers attached 🦋 these networks can forward data traffic that's neither locally-originated nor locally-destined ✨ in OSPF, except for point-to-point networks and virtual links, the neighborhood of each transit network is described by a network links advertisement (network-LSA) 🫶
- Stub network. A network with only a single OSPF router attached 🧚 every network in an OSPF system is either a transit or a stub network, but never both 💀
1.2. Acknowledgments
the multicast extensions to OSPF are based on the Link-State Multicast Routing algorithm presented in [Deering] 👑 the [Deering] paper also has a section on Hierarchical Multicast Routing (which gave MOSPF's inter-area multicasting scheme its ideas) 🌈 plus it covers several Distance Vector (also called Bellman-Ford) multicast algorithms 🤓 one of those, Truncated Reverse Path Broadcasting, has actually been implemented in the Internet (see [RFC 1075]) 🎀
the MOSPF protocol was developed by the MOSPF Working Group of the Internet Engineering Task Force 🫶 parts of this work were supported by DARPA under NASA contract NAG 2-650 💖
2. Multicast routing in MOSPF
okay now we get into the actual algorithm 🔥 this section describes MOSPF's basic multicast routing algorithm 🦋 the basic version runs inside a single OSPF area and covers the case where the multicast datagram's source is inside that same area ✨ within the area, the datagram's path forms a tree rooted at the source 🌳
2.1. Routing characteristics
as a multicast datagram gets forwarded along its shortest-path tree, it's delivered to each member of the destination multicast group 💅 here's the vibe for how MOSPF forwards it 👑
- The path a multicast datagram takes depends on both its source and its multicast destination 🫶 this is called source/destination routing, which is different from most unicast forwarding algorithms (like OSPF) that route based only on destination 🌸
- The path between the datagram's source and any particular group member is the least cost path available 💖 cost is expressed in terms of the OSPF link-state metric 🍓 so if the OSPF metric represents delay, a minimum delay path gets chosen 🧚 OSPF metrics are configurable 🦋 each outbound router interface gets a metric, representing the cost of sending a packet on that interface 💜 the cost of a path is the sum of its constituent (outbound) router interfaces[1] 🔥
- MOSPF takes advantage of any commonality among least cost paths to destination group members ✨ but when group members are spread across multiple networks, the datagram sometimes has to be replicated 🌈 this replication happens as few times as possible (at the tree branches), so common path segments get maximum advantage 💅
- For a given multicast datagram, all routers calculate an identical shortest-path tree 🎀 there's a single path between the datagram's source and any particular group member 🥺 that means, unlike OSPF's handling of regular (unicast) IP traffic, there's no equal-cost multipath 🙅♀️
- On each packet hop, MOSPF normally forwards IP multicast datagrams as data-link multicasts 🫶 there are two exceptions 👀 first, on non-broadcast networks there are no data-link multicast or broadcast services, so the datagram has to be forwarded to specific MOSPF neighbors (see Section 2.3.3) 🌸 second, a MOSPF router can be configured to forward IP multicasts on specific networks as data-link unicasts, to avoid datagram replication in certain anomalous situations (see Section 6.4) 🧚
while MOSPF optimizes the path to any given group member, it doesn't necessarily optimize the use of the internetwork as a whole 🥹 to do that, instead of source-based shortest-path trees, you'd need to calculate something like a minimal spanning tree (containing only the group members) 🤓 this type of minimal spanning tree is called a Steiner tree in the literature 💜 for a comparison of shortest-path tree routing to routing with Steiner trees, see [Deering2] and [Bharath-Kumar] 📚
2.2. Sample path of a multicast datagram
let's do an example 🎀 we'll look at the sample Autonomous System pictured in Figure 1 🦋 this figure is taken from the OSPF specification (see [OSPF]) ✨ bigger rectangles are routers, smaller rectangles are hosts 🌸 oblongs and circles represent multi-access networks[2] 🫶 lines joining routers are point-to-point serial connections 🔥 and a cost has been assigned to each outbound router interface 💅
Okay so the setup is this: every router in Figure 1 is running MOSPF 💅. Then we add a bunch of hosts. The ones labelled Ma have joined a multicast group called Group A through IGMP 🦋. They live on networks N2, N6 and N11. The hosts labelled Mb joined a different group, Group B, and they're on N1, N2 and N3 🎀. Quick tea: hosts can join more than one group at a time. This example keeps it to one each only so it's easier to follow 🫶. Hosts H2 through H5 are there as senders of multicast datagrams. Their sources are separate from the group members just for clarity ✨.
Now let's watch a multicast datagram move. Say Host H2 (on Network N4) sends a datagram to Group B 💖. It starts out as a data-link layer multicast on N4. Router RT3 is a multicast router, so it has "opened up" its interface data-link multicast filters, and it catches the datagram. RT3 wants to get it to every Group B member on N1, N2 and N3, so it sends one single copy onto Network N3, again as a data-link multicast[3]. Once RT1 and RT2 get that datagram from RT3, they multicast it onto their own stub networks, N1 and N2 respectively 🌸. Here's the fun part: because the copy went out on N3 as a data-link multicast, RT4 gets a copy too. But RT4 won't forward it, since it isn't on a shortest path between the source (Host H2) and any Group B members 🙈.
The path depends on where the datagram comes from, bestie 🧚. If Host H3 sent that same datagram, the path would be exactly the same, because H2 and H3 are on the same network (N4). But if Host H4 sent it, the route would be different. In that case, when Router RT3 gets the datagram, RT3 drops it instead of forwarding it, because RT3 is no longer on the shortest path to any Group B member 💀.
Here's the whole map so you can see what I'm talking about 🗺️:
+
| 3+---+ +--+ +--+ N12 N14 |
N1|--|RT1|\1 |Mb| |H4| \ N13 / _| +---+ \ +--+ /+--+ 8\ |8/8
| + \ _ | __/ \ | / |
+--+ +--+ / \ 1+---+8 8+---+6
| Mb | Mb | * N3 *--- | RT4 | ------ | RT5 | --------+ |
+--+ /+--+ ____/ +---+ +---+ |
- / | |7 |
| 3+---+ / |
N2|--|RT2|/1 |1 |6 | __| +---+ +---+8 6+---+ |
| + | RT3 | -------------- | RT6 |
+--+ +--+ +---+ +--+ +---+ |
| Ma | H3 | _ | 2 _ | H2 | Ia | 7 |
+--+ +--+ \ | / +--+ | | +---------+ | | N4 | |
N11 | | +---------+ | |
| \ | N12 | |
|---|---|---|
| 3 +--+ | 6 2/ |
+---+ |Ma| | +---+/
| RT9 | +--+ | RT7 | ---N15 |
+---+ | +---+ 9
| 1 + | 1 |
_|__ | Ib|5 __|_ +--+ / \ 1+----+2 | 3+----+1 / --|Ma|
- N9 ------|RT11|----|---|RT10|--- N6 * +--+ ____/ +----+ | +----+ ____/
| 1 + | 1 |
+--+ 10+----+ N8 +---+
| H1 | ----- | RT12 | RT8 |
+--+SLIP +----+ +---+ +--+
| 2 | 4 _ | H5 |
|---|---|---|
| / +--+ |
+---------+ +--------+ N10 N7
Figure 1: A sample MOSPF configuration
Okay, so back to RT3 and that H4 case. Totally different vibe from the H2 path, and it's giving "the path is about the source, not the receiver" 🔥.
Now the destination matters too 💅. If Host H2 sends to Group A instead, the route changes. It starts as a multicast on N4, and RT3 catches it and makes two copies 👯. One goes onto N3, and RT2 forwards it onto N2. The other goes to RT10 (through RT6), where it splits again and finally lands on N6 and N11. Even though the datagram gets copied a bunch, it isn't changed (except its IP TTL) as it's forwarded. There's no encapsulation either. The destination stays listed as the multicast group A 🦋✨.
2.3. MOSPF forwarding mechanism ✨
Every MOSPF router on the path of a multicast datagram makes its forwarding decision from a data cache 🧠. That cache is called the forwarding cache. There's a separate forwarding cache entry for every source/destination combination[4]. Each entry says, for datagrams with matching source and destination, which neighboring node (a router or a network) the datagram has to be received from (that's the upstream node), and which interfaces it should be sent out of next (the downstream interfaces) 🌈.
A forwarding cache entry is built from two pieces 🧩. The first one is the local group database. It's built by IGMP and tells the router which groups have members on its directly attached networks, so the router can deliver datagrams locally. The second piece is the datagram's shortest path tree. It's built on demand and rooted at the datagram's source. This tree is what gets datagrams to group members that are farther away (not directly attached) 🌸.
2.3.1. IGMP interface: the local group database 🎀
The local group database keeps track of which groups have members on the router's directly attached networks 💜. Each entry is a [group, attached network] pair. It means that network has one or more IP hosts in that IP multicast destination group. The router uses these entries to decide which directly attached networks get a received datagram, so local members get delivered to ✨.
This database is built through IGMP (see [RFC 1112]). When a MOSPF router becomes Designated Router on an attached network (let's call it N1), it starts sending periodic IGMP Host Membership Queries on that network 📣. Hosts answer with IGMP Host Membership Reports, one for each multicast group they belong to. When the router hears a Host Membership Report for Group A, it adds or refreshes the entry [Group A, N1] in its local group database. If Reports for Group A stop showing up on the network later, the entry is deleted 🫧.
Important tea: on any given network, only the Designated Router sends IGMP Host Membership Queries and listens for IGMP Host Membership Reports 👑. A MOSPF router ignores Host Membership Reports on networks where it wasn't elected Designated Router[5]. So at most one router does these IGMP jobs on a network, and that network shows up in the local group database of at most one router. That stops datagrams from being copied over and over as they get delivered to local members 🙌. The result is that each router in the Autonomous System has a different local group database 😭. Compare that to the MOSPF link state database and the datagram shortest-path trees (see Section 2.3.2), which are identical on every router in the Autonomous System 💖.
Other routers also have to know about local group members, or a datagram from far away would never get forwarded to the router that serves them 🚀. That's done with a group-membership-LSA. Like other link state advertisements, it gets flooded throughout the Autonomous System. The router makes a separate group-membership-LSA for each multicast group that has one or more entries in its local group database. A router's group-membership-LSA (say, for Group A) lists the local transit vertices (the router itself and/or any directly connected transit networks) that should not be pruned from Group A's datagram shortest-path trees 🌳. The router lists itself if either 1) one or more of its attached stub networks have Group A members, or 2) the router itself is a Group A member. The router lists a directly connected transit network if both 1) the router is Designated Router on that network and 2) the network has one or more Group A members 🫶.
Let's go back to Figure 1 for this one 🎀. If Router RT3 has been elected Designated Router for Network N3, then Table 1: lists the local group database for the routers RT1-RT4 💅.
In this case, each of the routers RT1, RT2 and RT3 will originate a group-membership-LSA for Group B, and RT2 will also originate one for Group A 🎀. RT1 and RT2's group-membership-LSAs list only the routers themselves, since N1 and N2 are stub networks. RT3's group-membership-LSA lists the transit Network N3 🌸.
Figure 2 shows the Autonomous System's link state database 🦋. A router or transit network gets labelled with a multicast group if and only if it has been mentioned in a group-membership-LSA for that group ✨. When building the shortest-path tree for a multicast datagram, these labels let the router prune away any branches with no group members 💅. How that tree gets built is covered in Section 2.3.2.
Lowkey, none of the hosts in Figure 1 that belong to groups A and B show up by name in the link state database (see Figure 2) 🙈. You literally can't tell which stub networks have group members just by looking at it. The link state database only tells you which routers and transit networks have attached group members, and that's all you need for forwarding multicast datagrams to work 💜.
Router local group database
_____________________________________
RT1 [Group B, N1]
RT2 [Group A, N2], [Group B, N2]
RT3 [Group B, N3]
RT4 None
Table 1: Sample local group databases
**FROM**
|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|
|1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|N3|N6|N8|N9|
----- ---------------------------------------------
RT1| | | | | | | | | | | | |0 | | | |
RT2| | | | | | | | | | | | |0 | | | |
RT3| | | | | |6 | | | | | | |0 | | | |
RT4| | | | |8 | | | | | | | |0 | | | |
RT5| | | |8 | |6 |6 | | | | | | | | | |
RT6| | |8 | |7 | | | | |5 | | | | | | |
RT7| | | | |6 | | | | | | | | |0 | | |
* RT8| | | | | | | | | | | | | |0 | | |
* RT9| | | | | | | | | | | | | | | |0 |
T RT10| | | | | |7 | | | | | | | |0 |0 | |
O RT11| | | | | | | | | | | | | | |0 |0 |
* RT12| | | | | | | | | | | | | | | |0 |
* N1|3 | | | | | | | | | | | | | | | |
N2| |3 | | | | | | | | | | | | | | |
N3|1 |1 |1 |1 | | | | | | | | | | | | |
N4| | |2 | | | | | | | | | | | | | |
N6| | | | | | |1 |1 | |1 | | | | | | |
N7| | | | | | | |4 | | | | | | | | |
N8| | | | | | | | | |3 |2 | | | | | |
N9| | | | | | | | |1 | |1 |1 | | | | |
N10| | | | | | | | | | | |2 | | | | |
N11| | | | | | | | |3 | | | | | | | |
N12| | | | |8 | |2 | | | | | | | | | |
N13| | | | |8 | | | | | | | | | | | |
N14| | | | |8 | | | | | | | | | | | |
N15| | | | | | |9 | | | | | | | | | |
H1| | | | | | | | | | |12| | | | | |
Figure 2: The MOSPF database.
Networks and routers are represented by vertices.
An edge of cost X connects Vertex A to Vertex B iff
the intersection of Column A and Row B is marked
with an X. In addition, RT1, RT2 and N3 are labelled
with multicast group A and RT1, N6 and RT9 are
labelled with multicast group B.Those labelled leaves are what make the pruning possible, so the database still does its job even without naming every host 🧚.
2.3.2. A datagram's shortest-path tree ✨
While the local group database makes local delivery of multicast datagrams work, a datagram's shortest-path tree shows the intermediate hops a multicast datagram takes from its source to each group member 🗺️. As mentioned above, that tree is a pruned shortest-path tree rooted at the datagram's source. Two datagrams with different [source net, multicast destination] pairs may have, and honestly probably will have, different pruned shortest-path trees 👑.
A datagram's shortest-path tree gets built "on demand"[6], meaning the first time a multicast datagram arrives with a particular [source net, multicast destination] combination 🔥. To build it, the router does the following. First, it finds the datagram's source IP network in the link state database. Then, using the router-LSAs and network-LSAs in that database, it builds a shortest-path tree with the source network as the root. Last, it prunes away any branches that don't contain routers or transit networks labelled with that multicast destination (via a group-membership-LSA) 🌈.
Let's walk through an example of building one, using the Autonomous System in Figure 1 🦋. Its link state database is pictured in Figure 2. When a router first receives a multicast datagram sent by Host H2 to multicast group A, these steps happen: Host H2 is first determined to be on Network N4. Then the shortest path tree rooted at net N4 is calculated[7], pruning branches that don't contain routers or transit networks labelled with multicast group A. That gives the pruned shortest-path tree in Figure 3 💅. At this point, every leaf of the tree is a router or transit network labelled with multicast group A: routers RT2 and RT9 and transit Network N6 🎀.
To forward the multicast datagram, each router has to find its own spot in the datagram's shortest-path tree 💖.
o RT3 (N4, origin)
/ \
1/ \8
/ \
N3 (Mb) o o RT6
/ \
0/ \7
/ \
RT2 (Ma,Mb) o o RT10
/ \
3/ \1
/ \
N8 o o N6 (Ma)
/
0/
/
RT11 o
/
1/
/
N9 o
/
0/
/
RT9 (Ma) o
Figure 3: Sample datagram's shortest-path tree,
source N4, destination Group AA router's position in the datagram's pruned shortest-path tree (call it Router RTX) has two parts 🧚. First is RTX's parent in the tree, which becomes the forwarding cache entry's upstream node. Second is the list of RTX's interfaces that lead to downstream routers or transit networks labelled with the datagram's destination, and these get added to the forwarding cache entry as downstream interfaces 🫶. Also, after calculating the tree, a router might find that it isn't on the tree at all. You'd spot that as a forwarding cache entry with no upstream node or an empty list of downstream interfaces 🙈.
Here's an example of a router describing its spot, using Router RT10 in Figure 3 💜. Router RT10's upstream node for the datagram is Router RT6, and it has two downstream interfaces: one connecting to Network N6 and the other connecting to Network N8 ✨.
2.3.3. Support for Non-broadcast networks 🌸
When forwarding multicast datagrams over non-broadcast networks, you can't send the datagram as a link-level multicast, because neither link-level multicast nor broadcast is supported on those networks 🙅. Instead, it has to be forwarded separately to specific neighbors. To make that work, forwarding cache entries can hold downstream neighbors as well as downstream interfaces 🦋.
The IGMP protocol isn't defined over non-broadcast networks. So there can't be group members directly attached to non-broadcast networks, and non-broadcast networks never show up in local group database entries 😭.
Say Network N3 in Figure 1 is an X.25 PDN 🍓. Look at Router RT3's forwarding cache entry for datagrams with source Network N4 and multicast destination Group B. Instead of showing the interface to Network N3 as the downstream interface, that entry would list the neighboring routers RT1 and RT2 as separate downstream neighbors 🫶. And in this case, there couldn't be a Group B member directly attached to Network N3 💅.
2.3.4. Details concerning forwarding cache entries 💖
Okay, but here's the bit that matters 🫖: forwarding cache entries can be freely deleted after some period of inactivity (aka garbage collected) if router memory resources are running low 🧹✨
3. Inter-area multicasting 🌍
Okay so up until now this memo has been about multicast forwarding when the whole Autonomous System is one single OSPF area 🏠. If the datagram's source and all its group members live in the same area, the logic is exactly the same. This section is about what happens when the source and (at least some of) the group members sit in different OSPF areas 🗺️. That's called inter-area multicast, and it's giving main character energy 💅
Inter-area multicast brings up a few questions, and the next sections answer them:
- Are group-membership-LSAs specific to a single area? And if they are, how does group membership info get passed from one area to the next? 🤔
- How do you build the datagram shortest-path trees in the inter-area case, when routers in other areas don't have the full picture of the datagram source's neighborhood? 🫣
- An area border router builds multiple datagram shortest-path trees, one for each attached area. So how do you squish those separate trees into a single forwarding cache entry? 🧩
Here's the lowkey reassuring part 🫶: the basic mechanisms are the same in the inter-area case as in the intra-area case. Forwarding is still driven by the contents of the forwarding cache. The cache is still built from the same two ingredients, the local group database and the datagram shortest-path trees 🍓. The shortest-path tree calculation is different in the inter-area case (see Section 3.2), but the local group database is built exactly the same way. MOSPF's interface with IGMP doesn't change just because there are areas 🙌. And finally, the forwarding algorithm in Section 11 is the same for both intra-area and inter-area cases. Iconic consistency 👑
The following discussion uses the area configuration in Figure 4 as an example 🖼️. That figure comes from the OSPF specification and shows an Autonomous System split into three areas (Area 1, Area 2 and Area 3). There's a single backbone area too (everything outside the shading). Because the backbone area has to be contiguous, a single virtual link is configured between the area border routers RT10 and RT11 🔗. Also, an area address range is configured in Router RT11 so that Networks N9-N11 and Host H1 get reported as a single route outside of Area 3 (via summary-link-LSAs). Very efficient, very slay 💖
3.1. Extent of group-membership-LSAs
Group-membership-LSAs are specific to a single OSPF area 🔒. Just like OSPF router-LSAs, network-LSAs and summary-link-LSAs, a group-membership-LSA only gets flooded throughout its own area[9]. A router attached to multiple areas (aka an area border router) can end up originating several group-membership-LSAs for one multicast destination, one for each attached area. But, as we'll see, the contents of those group-membership-LSAs vary depending on their associated areas 👀
Just like in OSPF, each MOSPF area has its own link state database 🗄️. The MOSPF database is basically the OSPF link state database, just enhanced with group-membership-LSAs. Let's look at the area configuration in Figure 4 again. Adding the group-membership-LSAs to the area databases gives you the databases pictured in Figures 6 and 7. Figure 6 is Area 1's MOSPF database, and Figure 7 is the backbone's MOSPF database. Superscripts show which transit vertices have been advertised as requesting particular multicast destinations. A superscript of "w" means the router is advertising itself as a wild-card multicast receiver (see below) 🃏. The dashed lines are OSPF summary-link-LSAs or AS external-link-LSAs. And notice in Figure 7 that Router RT11 has condensed its routes to Networks N9-N11 and Host H1 into a single summary-link-LSA. Condensing that is so neat 🧹💕
..................................
. + .
. | 3+---+ +--+ +--+ . N12 N14
. N1|--|RT1|\1 |Mb| |H4| . \ N13 /
. _| +---+ \ +--+ /+--+ . 8\ |8/8
. | + \ _|__/ . \|/
. +--+ +--+ / \ 1+---+8. 8+---+6
. |Mb| |Mb| * N3 *---|RT4|------|RT5|--------+
. +--+ /+--+ \____/ +---+ . +---+ |
. + / | . |7 |
. | 3+---+ / | . | |
. N2|--|RT2|/1 |1 . |6 |
. __| +---+ +---+8 . 6+---+ |
. | + |RT3|--------------|RT6| |
. +--+ +--+ +---+ +--+. +---+ |
. |Ma| |H3|_ |2 _|H2|. Ia|7 |
. +--+ +--+ \ | / +--+. | |
. +---------+ . | |
.Area 1 N4 . | |
.................................. | |
................................ | |
. N11 . | |
. +---------+ . | |
. | \ . | | N12
. |3 +--+ . | |6 2/
. +---+ |Ma| . | +---+/
. |RT9| +--+ . | |RT7|---N15
. +---+ ....... | +---+ 9
. |1 .. + ...|..........|1........
. _|__ .. | Ib|5 __|_ +--+.
. / \ 1+----+2.. | 3+----+1 / \--|Ma|.
. * N9 *------|RT11|----|---|RT10|---* N6 * +--+.
. \____/ +----+ .. | +----+ \____/ .
. | !*******|*****! | .
. |1 Virtual + Link |1 .
. +--+ 10+----+ ..N8 +---+ .
. |H1|-----|RT12| .. |RT8| .
. +--+SLIP +----+ .. +---+ +--+.
. |2 .. |4 _|H5|.
. | .. | / +--+.
. +---------+ .. +--------+ .
. N10 Area 3..Area 2 N7 .
.............................................................
Figure 4: A sample MOSPF area configuration3.1. Inter-area multicast ✨
So picture this 💖 an OSPF router has a local group database entry for [Group Y, Network X]. It then originates a group-membership-LSA for Group Y into the area that contains Network X. In the Figure 4 setup, Router RT1 does exactly this for Group B 🎀. That LSA gets flooded throughout Area 1 and literally goes no further 🙈. Same energy with RT3: once it's elected Designated Router for Network N3, it originates a group-membership-LSA into Area 1 listing the transit Network N3 as having group members. Check out Figure 6 and you'll see both Router RT1 and Network N3 labelled with Group B 🦋.
Okay so in OSPF, the area border routers are the ones forwarding routing info and data traffic between areas 🌸. In MOSPF, it's a bit more selective. A subset of the area border routers, called the inter-area multicast forwarders, forward group membership info and multicast datagrams between areas 💅. Whether a given OSPF area border router is also a MOSPF inter-area multicast forwarder is configuration dependent (see Section B.1) ⭐. In Figure 4 we assume that all area border routers are also inter-area multicast forwarders.
To share group membership between areas, inter-area multicast forwarders "summarize" their attached areas' group membership to the backbone 🧚. It's giving the same vibe as the summary-link-LSAs in base OSPF. An inter-area multicast forwarder works out which groups have members in its attached non-backbone areas. Then, for each of those groups, it injects a group-membership-LSA into the backbone area. In Figure 4, Area 1 has two groups with members: Group A and Group B. So both of Area 1's inter-area multicast forwarders (Routers RT3 and RT4) inject group-membership-LSAs for these two groups into the backbone. As a result, both of these routers end up labelled with Groups A and B in the backbone link state database (see Figure 7) 💜.
membership +------------------+ datagrams
+ > > > >>| Backbone |< < < < +
^ +------------------+ ^
^ / | \ ^
^ / | \ ^
+----^-----+/ +----------+ \+----^-----+
| Area 1 | | Area 2 | | Area 3 |
+----------+ +----------+ +----------+
Figure 5: Inter-area routing architectureHere's the twist though 👀. Unlike unicast summarization in base OSPF, MOSPF's group membership summarization is asymmetric. A non-backbone area's group membership gets summarized to the backbone, but that info is not then readvertised into other non-backbone areas. The backbone's group membership isn't summarized for the non-backbone areas either. Back to Figure 4: Area 3's group (Group A) is advertised to the backbone, but it doesn't get redistributed to Area 1. So routers inside Area 1 have no idea about Area 3's group membership 😭.
So if nothing extra was added to MOSPF, multicast traffic starting in Area 1 for Multicast Group A would never reach the Group A members in Area 3 💀. Enter the wild-card multicast receiver 🔥. This is a router that gets all multicast traffic, no matter the multicast destination. A router's wild-card multicast reception status is per-area. In non-backbone areas, all inter-area multicast forwarders[10] are wild-card multicast receivers. That way, all multicast traffic from a non-backbone area gets forwarded to its inter-area multicast forwarders, and from there to the backbone. The backbone knows every area's group membership, so it can forward the datagram to all the group members. Also, the backbone itself doesn't need any wild-card multicast receivers[11]. For example, Routers RT3 and RT4 are wild-card multicast receivers in Area 1 (see Figure 6), while there are none in the backbone (see Figure 7) ✨.
This gives us the inter-area routing architecture in Figure 5 🌈. All group membership gets advertised from the non-backbone areas into the backbone. All IP multicast traffic from the non-backbone areas gets forwarded to the backbone too. Once group membership info meets the multicast datagram traffic, delivering the datagrams becomes possible 🎉.
3.2. Building inter-area datagram shortest-path trees 🌸
When you're building datagram shortest-path trees with areas in the mix, the datagram's source and (at least some of) the destination group members are often in separate areas 🫶. Since detailed topological information concerning one
**FROM**
|RT|RT|RT|RT|RT|RT|
|1 |2 |3 |4 |5 |7 |N3|
----- -------------------
RT1| | | | | | |0 |
RT2| | | | | | |0 |
RT3| | | | | | |0 |
* RT4| | | | | | |0 |
* RT5| | |14|8 | | | |
T RT7| | |20|14| | | |
O N1|3 | | | | | | |
* N2| |3 | | | | | |
* N3|1 |1 |1 |1 | | | |
N4| | |2 | | | | |
Ia,Ib| | |15|22| | | |
N6| | |16|15| | | |
N7| | |20|19| | | |
N8| | |18|18| | | |
N9-N11,H1| | |19|16| | | |
N12| | | | |8 |2 | |
N13| | | | |8 | | |
N14| | | | |8 | | |
N15| | | | | |9 | |
Figure 6: Area 1's MOSPF database.
Networks and routers are represented by vertices.
An edge of cost X connects Vertex A to Vertex B iff
the intersection of Column A and Row B is marked
with an X. In addition, RT1, RT2 and N3 are labelled
with multicast group A, RT1 is labelled with multicast
group B, and both RT3 and RT4 are labelled as
wild-card multicast receivers.
**FROM**
|RT|RT|RT|RT|RT|RT|RT
|3 |4 |5 |6 |7 |10|11|
------------------------
RT3| | | |6 | | | |
RT4| | |8 | | | | |
RT5| |8 | |6 |6 | | |
RT6|8 | |7 | | |5 | |
RT7| | |6 | | | | |
* RT10| | | |7 | | |2 |
* RT11| | | | | |3 | |
T N1|4 |4 | | | | | |
O N2|4 |4 | | | | | |
* N3|1 |1 | | | | | |
* N4|2 |3 | | | | | |
Ia| | | | | |5 | |
Ib| | | |7 | | | |
N6| | | | |1 |1 |3 |
N7| | | | |5 |5 |7 |
N8| | | | |4 |3 |2 |
N9-N11,H1| | | | | | |1 |
N12| | |8 | |2 | | |
N13| | |8 | | | | |
N14| | |8 | | | | |
N15| | | | |9 | | |
Figure 7: The backbone's MOSPF database.
Networks and routers are represented by vertices.
An edge of cost X connects Vertex A to Vertex B iff
the intersection of Column A and Row B is marked
with an X. In addition, RT3 and RT4 are labelled
with both multicast groups A and B, and RT7, RT10,
and RT11 are labelled with multicast group A.OSPF area is not distributed to other OSPF areas (the flooding of router-LSAs, network-LSAs and group-membership-LSAs is restricted to a single OSPF area only) 😤. So building complete datagram shortest-path trees is often impossible in the inter-area case. To compensate, we use approximations, built from wild-card multicast receivers and OSPF summary-link-LSAs 🧠.
When a router first receives a datagram for a particular [source net, destination group] pair, it calculates a separate datagram shortest-path tree for each of its attached areas 🌷. Each tree is built solely from LSAs in that area's link state database. Say a router is calculating a datagram shortest-path tree for Area A. It helps to separate out two cases 💅.
The first case, Case 1: The source of the datagram belongs to Area A, has already been described in Section 2.3.2. But with OSPF areas, pruning the tree needs some care so the branches leading to other areas stay put, since it's unknown whether there are group members in those (remote) areas 👀. So only branches with no group members and no wild-card multicast receivers get pruned when producing the datagram shortest-path tree.
For example, say in Figure 4 Host H2 sends a multicast datagram to Group A 🦋. Then the datagram's shortest-path tree for Area 1, built the same way by every router in Area 1 that receives the datagram, is shown in Figure 8. Notice that both inter-area multicast forwarders (RT3 and RT4) are on that tree. That's what makes sure the datagram reaches the backbone and then Areas 2 and 3 🫶.
- Case 2: The source of the datagram belongs to an area other than Area A. In this case, when building the datagram shortest-path tree for Area A, the immediate neighborhood of the datagram's source is unknown 🤷♀️. But the summary-link-LSAs in the Area A link state database show the cost of the paths between each of Area A's inter-area multicast forwarders and the datagram source. Those summary links are used to approximate the neighborhood of the datagram's source, and the tree begins with links directly connecting the source to each of the inter-area multicast forwarders. These links point in the reverse
okay so picture this 🦋 the datagram's shortest-path tree for Area 1, with the source at N4 and the destination Group A:
o RT3 (W, origin=N4)
|
1|
|
N3 (Mb) o
/ \
0/ \0
/ \
RT2 (Ma,Mb) o o RT4 (W)
Figure 8: Datagram's shortest-path tree,
Area 1, source N4, destination Group Abestie, the tree is pointing the other way now 🙈 Remember the links from Case 1 above? Same vibe, just reversed: every link pointing towards the datagram source instead of away from it 💅. Any extra links that get added to the tree also point in that reverse direction ✨. Then, same as before, you prune every branch that has no group members and no wild-card multicast receivers, and boom, you've got the final datagram shortest-path tree 🌸
Let's run it back with Host H2 from Figure 4 sending a multicast datagram to Group A 🎀 The backbone's datagram shortest-path tree looks like Figure 9. The neighborhood around the source (Network N4) is approximated by the summary links that RT3 and RT4 advertise, and yes, every single link in Figure 9 has its arrow pointing back at N4 🔥
o N4
/ \
2/ \3
/ \
RT3 (Ma,Mb) o o RT4 (Ma,Mb)
/ \
6/ \8
/ \
RT6 o o RT5
| |
5| |6
| |
RT10 (Ma) o o RT7 (Ma)
|
2|
|
RT11 (Ma) o
Figure 9: Datagram shortest-path tree: Backbone,
source N4, destination Group A. Note that
reverse costs (i.e., toward origin) are
used throughout.ngl this is the part that gets a little messy 😭 In Case 2, the reverse costs get used for the entire tree, and that's not a choice, it's forced. Why? Because summary-link-LSAs only tell you the cost towards the datagram source, so that's all you've got to work with 🥺 If your link costs are asymmetric (different going each way), this can lead to less efficient routes when multicasts are forwarded between areas. So it's not always the most glow-up path, periodt 💀
Now for the routers sitting on more than one area. They have to calculate multiple trees and then merge them into one single forwarding cache entry 🧚 Back in Section 2.3.2, we saw that when a router is connected to just one area, its spot on the datagram shortest-path tree pretty much decides (mostly) what its forwarding cache entry looks like 👑 When a router is attached to several areas, it's calculating several datagram shortest-path trees, and each one adds to the forwarding cache entry's list of downstream interfaces/neighbors ✨
but here's the twist only one of those trees gets to pick the forwarding cache entry's upstream node 🫶 If one of the attached areas actually contains the datagram source, that area is the one that gets to decide the upstream node, no debate. Otherwise, the tiebreaking rules of Section 12.2.7 get invoked 🦋
Let's make it concrete with Host H2 in Figure 4 again, sending a multicast datagram to Group A 🌈 Router RT3 calculates two datagram shortest-path trees: one for Area 1 and one for the backbone. Since the datagram's source (Host H2) lives in Area 1, the Area 1 tree decides RT3's upstream node, which is Network N4 💖 RT3 ends up with two downstream interfaces: the interface to Network N3 (that one comes from the Area 1 tree) and the serial line to Router RT6 (that one comes from the backbone tree) 🍓
Router RT10 is calculating two trees too. Its upstream node comes from the backbone tree, and its two downstream interfaces come from the Area 2 tree 🌸 And then there's Router RT11, the overachiever 😤 It calculates three trees: its upstream node comes from the Area 2 tree, and its downstream interface comes from the Area 3 tree. Three trees, one forwarding entry, main character energy 👑💅
4. Inter-AS multicasting ✨
okay so this section is about how MOSPF handles multicast datagrams moving between Autonomous Systems 🌐. Some AS boundary routers in a MOSPF system get configured as inter-AS multicast forwarders, and they're also running an inter-AS multicast routing protocol 💅. This spec doesn't dictate how that protocol works, but MOSPF does assume a few things about how the two interact:
- MOSPF guarantees that the inter-AS multicast forwarders receive every multicast datagram 🫶, but each designated router decides for itself whether a datagram should be forwarded on to other Autonomous Systems. That call will probably be made through the inter-AS routing protocol.
- MOSPF assumes the inter-AS routing protocol forwards multicast datagrams in an RPF (reverse path forwarding; see [Deering] for an explanation of this terminology) way 🔁. So if a multicast datagram's source (call it X) lives outside the MOSPF domain, the datagram enters the MOSPF domain at the points advertising (into OSPF) the best routes back to X. MOSPF works out the datagram's path through the domain based on this assumption.
MOSPF treats an inter-AS multicast forwarder as a wild-card multicast receiver in all of its attached areas 🃏. Just like in the inter-area case, this keeps those routers on all the pruned shortest-path trees, so they receive every multicast datagram no matter the destination 🦋.
Let's look at an example 👀. Say RT5 and RT7 in Figure 1 were both configured as inter-AS multicast forwarders. The link state database would then look like Figure 2, with two extras: a) RT5 and RT7 get wild-card status (they show up with superscript "w"s), and b) the external links RT5 and RT7 originate get labelled as multicast-capable[12]. Iconic 💖.
Another one: check out the area configuration in Figure 4. Again, RT5 and RT7 are inter-AS multicast forwarders. In Area 1's link state database (Figure 6), the external links from RT5 and RT7 get labelled as multicast-capable too. But RT5 and RT7 are not labelled as wild-cards in Area 1's database, and that's on purpose 🙈. It isn't needed, since Area 1's inter-area multicast forwarders (RT3 and RT4) are wild-cards, so every multicast datagram gets forwarded to the backbone anyway. Then, in the backbone's link state database (Figure 7), RT5 and RT7 do get labelled as wild-cards 🌸.
4.1. Building inter-AS datagram shortest-path trees 🌳
When multicast datagrams need to go between Autonomous Systems, the datagram shortest-path tree gets built like this 🧚. Remember, a router builds a separate tree for each area it's attached to, and then those trees get merged into one forwarding cache entry. Say the router is building the tree for Area A. There are three cases. The first two were already covered earlier in this memo: Case 1 (the datagram's source is in Area A) in Section 2.3.2, and Case 2 (the source is in another OSPF area) in Section 3.2. The only change to those two is that inter-AS multicast forwarders, along with group members and inter-area multicast forwarders, have to stay on the pruned trees. The new one is Case 3 💜:
- Case 3: The source of the datagram belongs to another Autonomous System. The source's immediate neighborhood is unknown, so the multicast-capable AS external links stand in to approximate it 🕵️. The tree starts with links directly attaching the source to one or more inter-AS multicast forwarders. Those approximating AS external links point in reverse (towards the source), same as the approximating summary links in Case 2. And, like Case 2, every link in the tree has to point in the reverse direction. The final datagram shortest-path tree is produced as usual, by pruning any branches that have no group members and no wild-card multicast receivers ✂️.
As an example, say a host on Network N12 (see Figure 4) sends a multicast datagram to Destination Group B 📨. Assume all the external costs pictured are OSPF external type 1 metrics. Any routers in Area 1 that receive the datagram would build the datagram shortest-path tree in Figure 10. Notice that every link points in reverse, towards the source 👈. The tree shows the routers expect the datagram to enter the Autonomous System at Router RT7, and then enter the area at Router RT4.
Quick note 📝: when the "best" inter-AS multicast forwarder isn't directly attached to the area, the source's neighborhood gets approximated by a summary link and a multicast-capable AS external link chained together. That's exactly what's happening in Figure 10.
In Case 3 (datagram source in another AS), the rule that every tree link points in reverse (towards the source) fits right in, since summary links and AS external links already point that way 🙌. This also means the inter-AS multicast routing protocol has to operate in a reverse path forwarding fashion (see condition 2 of Section 4). Heads up though: reverse path forwarding can give sub-optimal routing when costs are configured asymmetrically 😬. It can even mean multicast datagrams never get delivered when reachability is asymmetric 💀.
Inter-AS multicast forwarders might end up calculating a forwarding cache entry's upstream node as being outside the AS 🌀. For example, Router RT7 in Figure 10 will end up calculating an external router (via its external link to Network
o N12
|
2|
|
o RT7
|
14|
|
o RT4 (W)
|
0|
|
o N3 (Mb)
/|\
/ | \
1/ | 1\
/ 1| \
/ | \
RT1 (Mb) o | o RT3 (W)
o
RT2 (Ma,Mb)
Figure 10: Datagram shortest-path tree: Area 1,
source N12, destination Group B. Note that
reverse costs (i.e., toward origin) are
used throughout.N12) as the upstream node for the datagram. That means RT7 has to receive the datagram from a router in another AS before it injects the datagram into the MOSPF system 📬.
4.2. Stub area behavior 🏡
AS external links don't get imported into stub areas 🚫. Suppose the source of a datagram is outside the Autonomous System, and the datagram gets forwarded into a stub area. In that stub area's datagram shortest-path tree, the source's neighborhood can't be approximated with AS external links. Instead, it's approximated by the default summary links (see Section 3.6 of [OSPF]) originated by the stub area's intra-area multicast forwarders 🧩.
Other than that one small change to how a stub area's datagram shortest-path trees are built, every other MOSPF algorithm (like merging with other areas' trees to form the forwarding cache) works the same for stub areas as it does for non-stub areas 🎀.
4.3. Inter-AS multicasting in a core Autonomous System 👑
Sometimes the MOSPF routing domain connects lots of different Autonomous Systems and acts as a "core Autonomous System" (e.g., the old NSFNet backbone) 🏛️. In that case, most of the MOSPF routers might be inter-AS multicast forwarders too. If every one of them declared itself a wild-card multicast receiver, that could waste a ton of network bandwidth 😭. So, as an alternative, the inter-AS multicast routers can explicitly advertise every group they're interested in forwarding (to other "client" Autonomous Systems) in group-membership-LSAs 📣. Those groups would have to be learned through an inter-AS multicast routing protocol (or possibly even statically configured).
This basically lets the clients of the core Autonomous System advertise their group membership into the core 🫧. But here's the twist: any client MOSPF domains still have their inter-AS multicast forwarders configured as wild-card multicast receivers, so the advertising is asymmetric. The core won't advertise its own or anyone else's group membership to the clients 🙃. This gets the same inter-AS multicast routing architecture MOSPF uses for inter-area multicast routing (see Figure 5) 🌈.
5. Modelling internal group membership ✨
okay so a MOSPF router can also have multicast apps running on it 👀 like a UNIX workstation that doubles as a multicast router 💻 this section is about two different ways to represent the group membership of those internal apps. both have their perks 🫶 for maximum flexibility, the MOSPF forwarding algorithm (see Section 11) is specified so that either representation can be used in a MOSPF router. and honestly, both can be used at once, depending on the app 💅
Representation one is based on the paradigm from RFC 1112 🎀 here an app joins a multicast group on one or more specific physical interfaces. then it only gets a multicast datagram if the datagram is received on one of those specified interfaces. if it's received on multiple specified interfaces, the app gets multiple copies 👯 Figure 11 shows this algorithm the way it's implemented in (modified) BSD UNIX kernels. the figure follows a multicast datagram from the moment it's received on a particular interface. first, copies go to the apps that joined on the receiving interface. then the forwarding decision (the box with the question mark) gets made, and the packet is (possibly) forwarded out certain interfaces. if those interfaces can't receive their own multicasts, a copy of the datagram has to be looped back internally to the appropriately joined apps 🔁
The advantages of the RFC 1112 representation are:
- It's the standard way an IP host joins multicast groups. it's simplest to use the same membership model for hosts and routers, because most people would say an IP router is a special case of an IP host anyway 🧚
- It's how group membership has been implemented in BSD UNIX. existing multicast apps are written to join multicast groups on specific interfaces 💾
- The possibility of receiving multiple datagram copies may improve fault tolerance. If the datagram is dropped due to an
+-------+
|receive|
+-------+
|
|---> To application
|
+-------------------+
|forwarding decision|
+-------------------+
|
/ \
/---\----> To application
/ \------> To application
/ \
/ \
+--------+ +--------+
|transmit| |transmit|
+--------+ +--------+
Figure 11: RFC 1112 representation of internal
group membershiperror on the path to some interface, another interface may still receive a copy 🛟
- The ability to specify a particular receiving interface may improve the accuracy of IP multicast's expanding ring search mechanism (see Section 2.3.4) 🎯
- Membership in the non-routable multicast groups (224.0.0.1 - 224.0.0.255) must be on a per-interface basis. An OSPF router always belongs to 224.0.0.5 (AllSPFRouters) on its OSPF interfaces, and may belong to 224.0.0.6 (AllDRouters) on one or more of its OSPF interfaces 🌸
Representation two is MOSPF-specific 🦋 here an app joins a multicast group on an interface-independent basis. in other words, group membership is tied to the router as a whole, not separately on each interface. the app gets a copy of a multicast datagram if and only if the datagram would actually be forwarded by the MOSPF router. Figure 12 shows how this algorithm would be implemented. the datagram is received on a particular interface. if the datagram is validated for forwarding (i.e., the receiving interface connects to the matching forwarding cache entry's upstream node), a copy of the datagram is also given to the appropriately joined apps. note that this model of group membership isn't as general as the RFC 1112 model, because it can only be implemented in MOSPF routers and not in arbitrary IP hosts. BUT it has these advantages 👑
- The app doesn't need to know about the router interfaces. it doesn't need to know what kind or how many interfaces there are, because the MOSPF protocol itself takes care of that 🫶
- As long as any interface is operational, the app keeps receiving multicast datagrams. this happens automatically, without the app modifying its group membership 🙌
- The app receives only one copy of the datagram. with the RFC1112 representation, whenever an app joins on more than one interface (which must be done if the app doesn't want to rely on a single interface), multiple datagram copies get received during normal operation 😵💫
6. Additional capabilities ⭐
this section describes the MOSPF configuration options that let routers with different capabilities be mixed together in the same
+-------+
|receive|
+-------+
|
|
|
+-------------------+
|forwarding decision|---> to application
+-------------------+
|
/ \
/ \
/ \
/ \
/ \
+--------+ +--------+
|transmit| |transmit|
+--------+ +--------+
Figure 12: MOSPF-specific representation of internal
group membershiprouting domain. note that these options handle special circumstances that may not come up in normal operation. default values for the configuration settings are specified in Appendix B 📋
6.1. Mixing with non-multicast routers 🧩
MOSPF routers can be mixed freely with routers that are running only the base OSPF algorithm (called non-multicast routers in the following). this lets MOSPF get deployed piece by piece, which speeds up deployment and allows experimenting with multicast routing on a limited scale 🌱
When a MOSPF router builds a datagram shortest-path tree, it leaves out all non-multicast routers. for example, in Figure 1, if Router RT6 wasn't a multicast router, the datagram shortest-path tree in Figure 3 would be built with a more circuitous branch through Router RT5, instead of through Router RT6 🗺️ also, non-multicast routers don't take part in flooding the new group-membership-LSAs. this follows the general principle that a router shouldn't have to handle link state advertisements whose format (or contents) it doesn't understand 🙅♀️
Mixing MOSPF routers with non-multicast routers creates a number of potential problems 😬 certain mixes can make multicast datagrams take suboptimal paths, or in other cases lead to multicast datagrams not being delivered at all. on top of that, mixing MOSPF and non-multicast routers can make the paths of multicast datagrams diverge radically from the path of unicast datagrams. those divergences can make routing problems harder to debug 🪲
here are the specific difficulties that may come up when mixing MOSPF routers with non-multicast routers:
- Even though there's unicast connectivity to a destination, there may not be multicast connectivity. For example, if Router RT10 in Figure 1 becomes a non-multicast router, the group member connected to Network N11 will no longer be able to receive multicasts sourced by Host H2. But the two hosts will still be able to exchange unicasts (e.g., ICMP pings) 💔
- When the Designated Router for a multi-access network is a non-multicast router, the network won't be used for forwarding multicast datagrams. For example, if in Figure 1 Router RT4 is Designated Router for Network N3, and RT4 is non-multicast, Network N3 won't be used to forward IP multicasts. This would mean that multicast datagrams originated by Hosts H2 and H3 wouldn't be forwarded beyond their local network (N4), even though it seems like the needed multicast connectivity exists 🫠
- When forwarding multicast datagrams between areas, mixing MOSPF routers and non-multicast routers in the source area may cause unexpected loss of multicast connectivity. This is because in inter-area routing of multicast datagrams, the neighborhood of the datagram's source is approximated by OSPF summary links, and OSPF summary-link-LSAs don't carry indications/guarantees of the summarized path's multicast routing capability 🧐
6.2. TOS-based multicast 🎀
MOSPF lets a separate datagram shortest-path tree get built for each IP Type of Service. this means the path of a multicast datagram can vary depending on the datagram's TOS classification, as well as its source and destination 🌈
For each router interface, OSPF lets you configure a separate metric for each IP TOS. When building the shortest path tree for TOS X, the cost of a path is the sum of the component interfaces' TOS X metrics. note that OSPF requires a TOS 0 metric to be specified for each interface. but as a form of data compression, metrics only need to be specified for non-zero TOS if they're different from the TOS 0 metric 🗜️
OSPF routers can also be configured to ignore TOS when forwarding packets. Such routers, called TOS-incapable, build only the TOS 0 portion of the routing table. TOS-incapable routers can be mixed freely with TOS-capable routers when forwarding unicast packets. for unicast, the packet gets forwarded along the TOS 0 route whenever the TOS X route doesn't exist. however, MOSPF has to handle this situation a bit differently, since each router must build the exact same tree rooted at the datagram's source 🌳✨
Okay so, the TOS stuff is genily optional, bestie 💅 TOS-capable and TOS-incapable multicast routers can be mixed freely in the same routing domain 🦋. The TOS-incapable ones will only ever build TOS 0 datagram shortest-path trees. The TOS-capable ones build TOS 0 trees first 🌸. If those trees only have TOS-capable routers in them, then they go ahead and build separate datagram shortest-path trees for the non-zero TOS values ✨. If not, the TOS 0 tree gets used to forward all traffic, no matter what TOS it's marked with 😭. So ngl, every router ends up using the same datagram shortest-path trees, which is so iconic 👑. See Section 12.2.8 for more details 🫶.
6.3. Assigning multiple IP networks to a physical network 🎀
Okay, putting multiple IP networks or subnets on one physical wire is literally where things get messy in MOSPF 🙈. OSPF treats each of those IP networks as its own separate entity. It makes a separate network-LSA for each one and forms a separate adjacency for each one. Meanwhile IGMP only sees the one underlying physical network 💀. Then the real problem shows up: when a multicast datagram comes in off that multiply-addressed wire, there's no good way to pick its upstream node. You need that node to make the forwarding decision, see Section 11 for the details 🧚. So unless someone sorts this out with configuration, you can get unwanted replication of multicast datagrams when they get forwarded over those multiply-addressed wires 😩.
The fix is that MOSPF lets you turn off multicast forwarding on certain IP networks or subnets 🌈. When forwarding is disabled on the wire's "extra" subnets (that's all but one of them), those extra subnets won't show up in datagram shortest-path trees. They also won't show up in the local group database or the forwarding cache entries 💖. So unwanted datagram replication is totally eliminated ✨. To actually disable multicast forwarding on a subnet, you set the IPMulticastForwarding parameter to disabled on every router interface that connects to that subnet. See Section B.2 🍓.
6.4. Networks on Autonomous System boundaries 🌸
Another plot twist can happen on IP networks or subnets that sit on the boundary of a MOSPF Autonomous System 👀. It's kind of like unicast, where these networks might be running multiple IGPs (Interior Gateway Protocols). These networks can also be running multiple multicast routing protocols 🔥. In that case it can become impossible for a MOSPF router to tell whether a multicast datagram is coming in along the datagram shortest-path tree, or whether it snuck in from the other Autonomous System 😵. Guessing wrong can lead to either unwanted replication or non-delivery of the multicast datagram 💀. Also, to avoid getting duplicate multicast datagrams, group members on these boundary networks will probably want to declare their membership to one Autonomous System and not the other 🙈.
Let's look at the example in Figure 13 🦋. Network X is on the boundary of both ASes. One possible multicast datagram path is shown: the datagram starts in a third Autonomous System, then gets delivered to both AS #1 and AS #2 separately. The paths through the two Autonomous Systems can end up sharing certain boundary networks as common segments 🧩. In Figure 13, Network X is common to both paths. So if both Autonomous Systems were running their own (separate copies of) MOSPF, the same datagram would show up twice on Network X as a data-link multicast 😱. That would make any group members on Network X, or downstream from it, receive duplicate datagrams 💔.
<-Datagram path->*
* *
* *
* .....*.........
.........*..... | . * AS #2
AS #1 * . |*****+---+
+---+*****|*----|RTC|
|RTA|----*|* . +---+
+---+ . *|* .
. *|* .
. *|* . +---+
+---+ . *|*----|RTD|
|RTB|----*|*****+---+
+---+*****| .....*..........
.........*.... | *
* | *
* Network X *
*
Figure 13: Networks on AS boundariesMOSPF has two mechanisms to kill this replication 🔪. The first one: a system administrator can set certain networks to forward multicast datagrams as data-link unicasts instead of data-link multicasts 💌. You do this by setting the IPMulticastForwarding parameter to data-link unicast on those router interfaces attached to the network (see Section B.2). For example, in Figure 13, the routers in AS #2 could be configured so that Router C sends the multicast datagram out onto Network X as a data-link unicast addressed directly to Router D 🫶. Router D accepts that data-link unicast, but it would reject any data-link multicast forwarded by Router A 🙅♀️. That eliminates replication of multicast datagrams downstream from Network X 🎉. Also, if IPMulticastForwarding is set to data-link unicast on Network X, group membership won't be monitored on that network 👀. That stops group members attached directly to Network X from receiving multiple datagram copies, because group membership on the boundary network is only monitored from one AS (AS #1 in our example) 🌟.
Now, forwarding IP multicasts as data-link unicasts has some downsides when three or more MOSPF routers are attached to the network 😬. First of all, it's more work for a router to send multiple unicasts than a single multicast. Second, the multiple unicasts eat up more network bandwidth than one multicast would. And last, it increases the delay for some group members, since multiple unicasts also take longer to send than a single multicast 🐢.
6.5. Recommended system configuration 💜
So to make MOSPF's route selection more predictable 🔮, it is recommended that all routers in any particular OSPF area have the same multicast and TOS capabilities. Keeping areas homogeneous means IP multicast packets follow relatively the same path as IP unicasts 🛣️. On the flip side, heterogeneous areas will work, and will probably be necessary at least during the initial introduction of multicast routing 🥲. But those areas may produce seemingly sub-optimal and unexpected routes 🤨. For example, see Section 6.1 above for a detailed rundown of the possible pitfalls when you mix multicast and non-multicast routers ⚠️.
As for the other options above, to get the most predictable results, it is recommended that a router interface's IPMulticastForwarding parameter be set to a value other than data-link multicast only when either a) multiple IP networks have been assigned to a single physical wire, or b) multiple multicast routing protocols are running on the attached network 🎯.
7. Basic implementation requirements ✨
An implementation of MOSPF needs the following pieces of system support 🧰. This support is on top of what's required for the base OSPF implementation, as outlined in Section 4.4 of [OSPF] 📚.
- Promiscuous multicast reception. In a multicast router, it's necessary to receive all IP multicasts at the data-link level 👂. On interfaces where IP multicast datagrams are encapsulated by a wide range of data-link multicast destination addresses (e.g, ethernet and FDDI), the easiest way to do this is to disable any hardware filtering of multicast destinations (i.e., by "opening up" the interface's multicast filter) 🔓.
- Data-link multicast/broadcast detection. To avoid unwanted replication of multicast datagrams in certain exceptional conditions, the multicast router needs to figure out whether a datagram was received as a data-link multicast/broadcast or as a data-link unicast 🕵️♀️. It uses that info later in the MOSPF forwarding mechanism. See Section 6.4 for more details 💅.
- An implementation of IGMP. MOSPF uses the Internet Group Management Protocol (IGMP, documented in [RFC 1112]) to monitor multicast group membership 👯♀️. See Section 9 for details 🌷.
8. Protocol data structures 💅
The MOSPF protocol is described here in terms of its operation on various protocol data structures 🧩. These data structures are included for explanatory uses only, and are not intended to constrain a MOSPF implementation 🫶. Besides the data structures listed below, this specification also references the various data structures (e.g., OSPF interfaces and neighbors) defined in [OSPF] 📖.
In a MOSPF router, the following items get added to the list of global OSPF data structures described in Section 5 of [OSPF] 🎀:
- Local group database. This database describes the group membership on all attached networks for which the router is either Designated Router or Backup Designated Router. This in turn determines the group-membership-LSAs that the router will originate, and the local delivery of multicast datagrams (see Sections 2.3.1 and 10) 🍓.
- Forwarding cache. Each entry in the forwarding cache describes the path of a multicast datagram having a particular [source net, multicast destination, TOS] combination 🌈. These cache entries are calculated when building the datagram shortest-path trees. See Sections 2.3.4 and 11 for more details ⭐.
- Multicast routing capability. Indicates whether the router is running the multicast extensions defined in this memo 🔥. A router running the multicast extensions must still run the base OSPF algorithm as set forth in [OSPF] 🧠. Such a router will continue to interoperate with non-multicast-capable OSPF routers when forwarding IP unicast traffic 🤝.
Okay so this part is where the router-property list wraps up, and then section 8 gets properly detailed 🎀
- Inter-area multicast forwarder 🦋 This one says whether the router will forward IP multicasts from one OSPF area to another. Such a router declares itself a wild-card multicast receiver in its non-backbone area router-LSAs (see Section 14.6), and also summarizes its attached areas' group membership to the backbone in group-membership-LSAs. When building inter-area datagram shortest-path trees, these are the routers sitting right next to the datagram source at the root of the tree (see Section 3.2). Not every multicast-capable area border router needs to be set up as an inter-area multicast forwarder 💅 However, whenever both ends of a virtual link are multicast-capable, they must both be configured as inter-area multicast forwarders (see Section 14.11).
- Inter-AS multicast forwarder 🌈 This one says whether the router will forward IP multicasts between Autonomous Systems. Such a router declares itself a wild-card multicast receiver in its router-LSAs (see Section 14.6). These routers are also assumed to be running some kind of inter-AS multicast protocol. They mark every external route they import into the OSPF domain with whether it provides multicast connectivity (see Section 14.9). When building inter-AS multicast datagram trees, these are the routers that sit right next to the datagram source at the root of the tree.
8.1. Additions to the OSPF area structure ✨
The OSPF area data structure is described in Section 6 of [OSPF]. In a MOSPF router, the following item gets added to the OSPF area structure, and it's giving organized 🗂️
- List of group-membership-LSAs 💖 These link state advertisements describe where the area's multicast group members are. Group-membership-LSAs are flooded throughout a single area only. Area border routers also summarize their attached areas' membership by originating group-membership-LSAs into the backbone area. For more information, see Sections 3.1 and 10.
8.2. Additions to the OSPF interface structure 🍓
The OSPF interface structure is described in Section 9 of [OSPF]. In a MOSPF router, the following items get added to the OSPF interface structure. Quick heads up: the IPMulticastForwarding parameter is really a description of the attached network 🙈 So it should be configured identically on all routers attached to a common network. Otherwise, incorrect routing of multicast datagrams may result[13].
IPMulticastForwarding🔥 This configurable parameter indicates whether IP multicasts should be forwarded over the attached network, and if so, how. It can take one of three values:disabled,data-link multicastanddata-link unicast. When set todisabled, IP multicast datagrams will not be forwarded out the interface. When set todata-link multicast, IP multicast datagrams will be forwarded as data-link multicasts. When set todata-link unicast, IP multicast datagrams will be forwarded as data-link unicasts. The default value isdata-link multicast. The other two settings are for the special circumstances described in Sections 6.3 and 6.4. When set todisabledor todata-link unicast, IGMP group membership is not monitored on the attached network.IGMPPollingInterval🧚 When the router is actively monitoring group membership on the attached network, it periodically sends IGMP Host Membership Queries.IGMPPollingIntervalis a configurable parameter giving the number of seconds between IGMP Host Membership Queries. The router actively monitors group membership on the attached network when both a) the interface'sIPMulticastForwardingparameter is set todata-link multicastand b) the router has been elected Designated Router on the attached network. See Section 9 for details.IGMPTimeout⏳ This configurable parameter indicates how long (in seconds) a local group database entry associated with this interface will persist without another matching IGMP Host Membership Report being received. See Section 9 for details.- IGMP polling timer 💜 When this interval timer fires, an IGMP Host Membership Query gets sent out the interface. The length of this timer is the configurable parameter
IGMPPollingInterval. See Section 9 for details.
8.3. Additions to the OSPF neighbor structure 🦋
The OSPF neighbor structure is defined in Section 10 of [OSPF]. In a MOSPF router, the following items get added to the OSPF neighbor structure:
- Neighbor Options 🌸 This field was already defined in the OSPF specification. However, in MOSPF there's a new option that indicates the neighbor's multicast capability. This new option is learned during the Database Exchange process, through reception of the neighbor's Database Description packets. It determines whether group-membership-LSAs are flooded to the neighbor. See the items concerning flooding in Section 14 for a more detailed explanation.
8.4. The local group database 📚
The local group database was already introduced in Section 2.3.1. This section attempts a more precise definition. The local group database tracks the group membership of the router's directly attached networks. Database entries are created and maintained by the IGMP protocol. Database entries can cause group-membership-LSAs to be originated, which in turn enable the pruning of datagram shortest-path trees. The local group database also dictates the router's responsibility for delivering multicast datagrams to directly attached group members.
Each entry in the local group database has three components: the multicast group, the attached network and the entry's age. A database entry is indexed by the first two components: multicast group and attached network. A database lookup function is assumed to exist, so that given a [Group A, Network N1] pair, the matching database entry (if any) can be discovered. A database entry for [Group A, Network N1] exists if and only if there are Group A members currently located on Network N1. 🫶
The three components of a local group database entry are defined as follows:
- MulticastGroup 💅 The multicast group whose members are being tracked by this entry. Each multicast group is represented as a class D IP address. For the semantics of multicast group membership, see [RFC 1112].
- AttachedNetwork 🎀 Each database entry is concerned with the group members belonging to a single attached network. To get a complete picture of local group membership (for example, when building a group-membership-LSA), it may be necessary to consult multiple database entries, one for each attached network. Note that a router is only required to maintain entries for those attached networks on which it has been elected Designated Router or Backup Designated Router (see Section 9).
- Age ⏰ Indicates the number of seconds since an IGMP Host Membership Report for multicast Group A has been seen on Network N1. If the age field hits Network N1's configured
IGMPTimeoutvalue, the local group database entry is removed (i.e., the entry has "aged out"). See Sections 9.2 and 9.3 for more information.
8.5. The forwarding cache 🔮
The forwarding cache was already defined in Section 2.3. This section attempts a more precise definition. Each entry in the forwarding cache indicates how a multicast datagram having a particular [source network, destination multicast group, IP TOS] will be forwarded. A forwarding cache entry is built on demand from the local group database and the datagram's shortest-path tree. For more details, check Sections 2.3.4 and 12.
Each entry in the forwarding cache has six components: the multicast datagram's source network, the destination multicast group, the IP TOS, the upstream node, the list of downstream interfaces and (possibly) a list of downstream neighbors. A forwarding cache entry is indexed by source network, destination multicast group and IP TOS. A lookup function is assumed to exist, so that given a multicast datagram with a particular [IP source, destination multicast group, IP TOS], a matching cache entry (if any) can be found. 🧠
The six components of a forwarding cache entry are defined as follows:
- Source network 🌈 The datagram's source network is described by a network/subnet/supernet number and its corresponding mask. The source network for a datagram is discovered via a routing table or database lookup of the datagram's IP source address, as described in Section 11.2.
- Destination multicast group 💖 The destination group to which matching datagrams are being forwarded. For the semantics of multicast group membership, see [RFC 1112].
- IP TOS 👑 The IP Type of Service specified by matching datagrams. This means the path of the multicast datagram depends on its TOS classification, which is a whole thing ngl ✨
- Upstream node 🚦 The attached network or neighboring router from which the datagram must be received. If it's received from a different attached network or neighboring router, the matching datagram is dropped instead of forwarded. This prevents unwanted replication of multicast datagrams. The upstream node may be unspecified (i.e., set to
NULL). In this case, matching datagrams will always be dropped, no matter where they're received from. The upstream node may also be specified as the placeholderEXTERNAL. This means the datagram must be received on a non-MOSPF interface in order to be forwarded. - List of downstream interfaces 🍓 These are the router interfaces that the matching datagram should be forwarded out of (assuming the datagram was received from the upstream node). Each interface is also listed with a TTL value. The TTL value is the minimum number of hops necessary to reach the closest (in terms of router hops) group member. This lets the router drop datagrams that have no chance of reaching a destination group member 🫶
- List of downstream neighbors. 💅 When the datagram is to be forwarded out a non-broadcast multi-access network, or if the interface's
IPMulticastForwardingparameter is set todata-link unicast, the datagram must be forwarded separately to each downstream neighbor (see Sections 2.3.3 and 6.4). As done for downstream interfaces, each downstream neighbor is specified together with the smallest TTL that will actually reach a group member. 🦋
9. Interaction with the IGMP protocol ✨
okay so MOSPF uses the IGMP protocol (see [RFC 1112]) to keep track of who's in which multicast group 👀 basically the Designated Router on a network periodically sends IGMP Host Membership Queries (see Section 9.1), and those queries prompt the group members on the network to send back IGMP Host Membership Reports. 🫶 Those Reports then get recorded in the local group databases of the Designated Router and the Backup Designated Router (see Section 9.2). main character energy for the DR and BDR, honestly 👑
9.1. Sending IGMP Host Membership Queries
Only the network's Designated Router sends Host Membership Queries. 🙈 This minimizes the amount of group membership information on the network, both in terms of queries and responses. less chatter, less noise, iconic 🌸
When a MOSPF router becomes Designated Router on a network, it checks to see that the network's IPMulticastForwarding parameter is set to data-link multicast (see Section B.2). If so, it starts the interface's IGMP polling timer. ⏰ Then, whenever the timer fires (every IGMPPollingInterval seconds), the MOSPF router sends a Host Membership Query out the interface. The destination of the query is the IP address 224.0.0.1. For the format of the query, see [RFC 1112]. If/when the MOSPF router ceases to be the network's Designated Router, the IGMP polling timer is disabled and no more Hosts Membership Queries are sent. 🛑
Heads up bestie: when multiple IP networks are assigned to a single physical network, things can get a little chaotic 💀 MOSPF treats each such IP network separately, electing (possibly) a different Designated Router for each network. However, IGMP operates on a physical network basis only: when a Host Membership Query is sent, all group members on the physical network respond, regardless of their IP addresses. So unless theIPMulticastForwardingparameter is set to a value other thandata-link multicaston all but one of the physical network's IP networks, excess multicast membership reporting will result. 😭
9.2. Receiving IGMP Host Membership Reports
Received Host Membership Reports are processed by both the network's Designated Router and Backup Designated Router. 🧚 It is the Designated Router's responsibility to distribute the network's group membership information throughout the routing domain, by originating group-membership-LSAs (see Section 10). The Backup Designated Router processes Reports so that it too has a complete picture of the network's group membership, enabling a quick cutover upon Designated Router failure. the BDR is literally the friend who keeps receipts just in case 🧾💜
An IGMP Host Membership Report concerns membership in a single IP multicast group (call it Group A). The Report is sent to the Group A address so that other group members may see the Report and avoid sending duplicates (see [RFC 1112] for details). When an IGMP Host Membership Report, sent on Network N[14], is received by a MOSPF router, the following steps are executed:
(1) If the router is neither the Designated Router nor the Backup Designated Router on the network, the Report is discarded and processing stops. 🚫
(2) If the Report concerns a multicast group in the range 224.0.0.1 - 224.0.0.255, the Report is discarded and processing stops. This range of multicast groups are for local use (single hop) only, and datagrams sent to these destinations are never forwarded by multicast routers. 🙅♀️
(3) Locate the entry for [Group A, Network N] in the local group database. If no such entry exists, create one. In any case, set the age of the entry to 0. Note that even if multiple hosts attached to Network N report membership in the same group, only a single local group database entry will be formed. See Section 8.4 for more details concerning the local group database. 📒✨
(4) If the router is the network's Designated Router, and a local group database entry was created in the previous step, it may be necessary to originate a new group-membership-LSA. See Section 10 for details. 🔥
9.3. Aging local group database entries
Every local database entry has an age field. ⏳ Suppose that there is a database entry for [Group A, Network N1]. The age field then indicates the length of time (in seconds) since the last Host Membership Report for Group A was received on Network N1. If the age of the entry reaches Network N1's configured IGMPTimeout value (see Section B.2), the entry is considered invalid and is removed from the database. 🗑️
Note that when a router, after having been either Network N1's Designated Router or Backup Designated Router, but now being neither, will (after IGMPTimeout seconds) automatically age out all of its local group database entries associated with Network N1. 🦋 For this reason, it is not necessary to purge local group database entries on OSPF interface state changes. it ages out on its own, so no drama, no manual cleanup, periodt 💅
9.4. Receiving IGMP Host Membership Queries
If a MOSPF router has internal multicast applications, and if the applications have bound themselves to certain interfaces (using the RFC 1112 representation described in Section 5), then the MOSPF router responds to received Host Membership Queries by issuing Host Membership Reports. 🎀 Identical to the operation of any IP host supporting multicast applications, the exact procedure for issuing these Host Membership Reports is specified in [RFC 1112]. Note that in this case, if the router has been elected Designated Router on a network, it must receive its own Host Membership Reports and Host Membership Queries. 🪞
If instead all of its applications have joined groups in an interface-independent fashion (using the MOSPF-specific representation described in Section 5), the MOSPF router does not respond to Host Membership Queries. 🙃 Instead, the MOSPF router communicates this membership information by originating appropriate group-membership-LSAs (see Section 10.1). no replies needed when it's all interface-independent, the LSAs do the talking 📣🍓
10. Group-membership-LSAs ✨
Okay bestie, group-membership-LSAs are how MOSPF spreads the "who wants this multicast group" info around the whole routing domain 💌. Each one is scoped to a single OSPF area (see Section 3.1) and covers exactly one multicast group 🦋. Basically, it lists the networks directly connected to whoever originated it that have at least one group member on them. For the deets on how it slots into the OSPF link state database, see Section 2.3.1 💅.
The creation of group-membership-LSAs is discussed in Section 10.1, and the format is in Section A.3 🎀. A router will originate a group membership-LSA for multicast group A when one or more of these conditions hold:
- The router is Designated Router on a network (call it Network X), the interface to Network X has its IPMulticastForwarding parameter set to data-link multicast (see Section B.2), and Network X contains one or more members of Group A. 🌸
- The router is an inter-area multicast forwarder (see Section B.1), and one or more of the router's attached non-backbone areas contain Group A members. In this case, the router will originate a group-membership-LSA for Group A into the backbone. This is how group membership gets conveyed between areas (see Section 3.1) 🧚
- The router itself has applications that are requesting membership in Group A, in an interface-independent fashion (see Section 5) ✨
Now, group-membership-LSAs get aged like every other OSPF link state advertisement (router-LSAs, network-LSAs, etc.) while they sit in a router's link state database. So to keep valid advertisements from "aging out", a router MUST refresh its self-originated group-membership-LSAs every LSRefreshTime interval, by incrementing their LS sequence numbers and reissuing them 🔥. Whenever something changes one of the router's self-originated group-membership-LSAs, a new instance gets issued with an LS sequence number incremented by 1 💖. Heads up though: a router is not allowed to originate two new instances of the same advertisement within MinLSInterval seconds. That means some originations have to get deferred sometimes 🙈. And if an event makes it inappropriate for the router to keep originating a particular LSA, the router flushes it from the routing domain by "premature aging" 💀. For more on LSA maintenance, see Sections 12, 12.4, 14 and 14.1 of [OSPF] 📚.
When one of these events happens, a router MAY need to (re)issue one or more group-membership-LSAs 👑:
- One of the router's interfaces changes state. For example, the router may have become Designated Router on a particular network, so it starts advertising that network's group membership to the rest of the MOSPF system in group-membership-LSAs 🦋.
- The router receives an IGMP Host Membership Report, which causes a new local group database entry to be formed (see Section 9.2) 🌈.
- One of the router's local group database entries "ages out", because it's no longer being refreshed by received IGMP Host Membership Reports (see Section 9.3) 😭.
- The router is an inter-area multicast forwarder, and the group membership of one of its attached non-backbone areas changes. The router spots this when a new group-membership-LSA shows up in that non-backbone area's link state database, or when an old one gets flushed out of it 🫶.
- The group membership of one of the router's internal applications changes 🍓.
10.1. Constructing group-membership-LSAs 🧁
This section walks through how to build a group-membership-LSA. The format is in Section A.3, and each LSA concerns a single multicast group. The body is a list of the local transit nodes (the router itself and its directly attached transit networks) that contain group members. Section 10 covered the conditions that call for (re)originating one. Also, if the router is an area border router, it MAY need to originate a separate group-membership-LSA for each attached area 🎀.
Here's what a group-membership-LSA looks like when Router X originates it into Area A, assuming it's reporting membership in multicast group G:
- The advertisement fields that aren't type-specific (LS age, LS sequence number, LS checksum and length) are set according to Section 12.1 of [OSPF] ✨.
- The Options field of a group-membership-LSA doesn't get processed on receipt. Still, for consistency, the Options field in these advertisements SHOULD have its MC-bit set, T-bit clear, and the E-bit should match the configuration of Area A (so set if and only if Area A is not a stub area). The rest of the Options field is set to 0 💅.
- The Link State ID is set to the group whose membership is being reported (Group G) 💜.
- The Advertising Router is set to the OSPF Router ID of the router originating the advertisement (Router X) 🌸.
- The body is a list of local transit vertices that should be labelled with Group G membership (see Section 2.3.1). This list MAY include the advertising router itself and any transit networks directly attached to it. The steps below figure out which of those transit vertices actually make it into the LSA. Each vertex should be listed at most once, even if several reasons point to the same one. And if no transit vertices get listed, the advertisement SHOULD NOT be (re)originated. If an instance already exists, it SHOULD then be flushed from the link state database using the premature aging procedure in Section 14.1 of [OSPF] 🙈.
a. Look at the entries in the local group database that describe Group G membership (see Section 8.4), one at a time. Each entry references one of Router X's attached networks (call it Network N). If Network N doesn't belong to Area A, or if Router X isn't Network N's Designated Router[15], then Network N SHOULD NOT be added to the group-membership-LSA, and you move on to the next entry. Otherwise, if N is a stub network (e.g., Router X is the only OSPF router attached to N), Router X adds itself by adding a vertex with Vertex type set to 1 (router) and Vertex ID set to Router X's OSPF Router ID. Otherwise, N is a transit network. In that case, Network N SHOULD be added by adding a vertex with Vertex type set to 2 (network) and Vertex ID set to the IP address of Network N's Designated Router (i.e., Router X's IP interface address on Network N) 🦋.
b. If Router X itself has applications requesting Group G membership on an interface-independent basis (see Section 5), it SHOULD add itself by adding a vertex with Vertex type set to 1 (router) and Vertex ID set to Router X's OSPF Router ID 🌈.
c. If Router X is an inter-area multicast forwarder (see Section 3.1), Area A is the backbone area (Area ID 0.0.0.0), and at least one of Router X's attached non-backbone areas has Group G members (shown by one or more advertisements in those areas' link state databases with Link State ID set to Group G and LS age set to a value other than MaxAge[16]), then Router X SHOULD add itself by adding a vertex with Vertex type set to 1 (router) and Vertex ID set to Router X's OSPF Router ID 🧚.
Let's look at an example, the network configuration in Figure 4 🌟. Say Router RT2 has been elected Designated Router for Network N3. RT2 would then originate (into Area 1) the following group-membership-LSA for Group B:
; RT2's group-membership-LSA for Group B
LS age = 0 ;always true on origination
Options = (E-bit|MC-bit)
LS type = 6 ;group-membership-LSA
Link State ID = Group B
Advertising Router = RT2's Router ID
Vertex type = 1 ;RT2 itself (for stub N2)
Vertex ID = RT2's Router ID
Vertex type = 2 ;Network N3 (since RT2 is DR)
Vertex ID = RT2's IP interface address on N310.2. Flooding group-membership-LSAs 🦄
When MOSPF routers and non-multicast OSPF routers live together in one routing domain, group-membership-LSAs don't get flooded to the non-multicast routers[17] 🙅♀️. As a general design principle, optional OSPF advertisements only get flooded to routers that understand them 💜.
A MOSPF router finds out about a neighbor's multicast-capability right at the start of the "Database Exchange Process" (see Section 10.6 of [OSPF]). That's when it receives Database Description packets from a neighbor in state Exstart. A neighbor is multicast-capable if and only if it sets the MC-bit in the Options field of its Database Description packets. Then, in the next step of Database Exchange, group-membership-LSAs go into the Database summary list sent to the neighbor (see Sections 7.2 and 10.3 of [OSPF]), but only if that neighbor is multicast-capable 🎀.
When flooding group-membership-LSAs to adjacent neighbors, a MOSPF router checks each neighbor's multicast-capability. Group-membership-LSAs only get flooded to multicast-capable neighbors. To be more precise, in Section 13.3 of [OSPF], group-membership-LSAs only get placed on the Link state retransmission lists of multicast-capable neighbors[18] 🌸. Heads up, though: when Link State Update packets are sent as multicasts, a non-multicast neighbor MAY (inadvertently) receive group-membership-LSAs. When that happens, the non-multicast router simply discards the LSA (see Section 13 of [OSPF], receiving LSAs having unknown LS types) 🙃.
11. Detailed description of multicast datagram forwarding 🦋
Okay so this is the big finale of MOSPF forwarding, bestie 🦋 It's a whole chain of steps, and it's where all those sneaky config options finally show up together. The forwarding process got a casual intro back in Section 2.2, but some super obscure settings, like the IPMulticastForwarding interface parameter, were mentioned elsewhere and can totally change what happens. This section puts every single influencer into one algorithm 💅
We're assuming the datagram actually arrived on one of the router's interfaces. Locally generated datagrams (aka ones made by the router's own internal apps) get handled by the algorithm in Section 11.3 instead 🙈
Say the datagram's IP destination is Group G. The forwarding process goes like this:
Step 1. When the datagram shows up, the MOSPF router notes these parameters. Later steps look at them to decide whether the datagram gets forwarded 👀
- a. The receiving MOSPF interface linked to the datagram. It gets picked from the receiving physical interface, using the algorithm in Section 11.1.
- b. Whether the datagram came in as a link-level multicast/broadcast or as a link-level unicast. Step 7 uses this to help decide if it gets forwarded.
Step 2. Pass a copy of the datagram to each internal application that has joined Group G on the receiving MOSPF interface (see Section 5). 🎀
Step 3. If the datagram's IP source address matches the receiving MOSPF interface's IP address, don't forward it. Discard it instead, and the forwarding process is done. This stops the router's own locally originated datagrams from getting copied by mistake, which can happen when the receiving MOSPF interface picks up its own multicast transmissions 🙃
Step 4. If Group G falls in the range 224.0.0.1 through 224.0.0.255 inclusive, don't forward it any further. That range is dedicated to use on a local network segment only 🌸
Step 5. Associate a source network (SourceNet) with the multicast datagram, as described in Section 11.2. If SourceNet can't be determined (aka there's no available unicast route back to the datagram source), don't forward the datagram any further 🚫
Step 6. Look up the forwarding cache entry (see Section 8.5) matching the datagram's [SourceNet, Group G, TOS] combination. If that cache entry doesn't exist yet, the calculation in Section 12 builds one. For the datagram to be forwarded, the forwarding cache entry's contents must be double-checked against the received datagram's characteristics, like so:
- a. If the forwarding cache entry's upstream node is unspecified (i.e.,
NULL), don't forward the datagram any further. - b. Otherwise, suppose the forwarding cache entry's upstream node is set to
EXTERNAL. In that case the datagram gets forwarded if and only if the receiving MOSPF interface is set toNULL(i.e., if and only if the datagram was received on a non-MOSPF interface). This one is kinda plot-twisty ngl ✨ - c. Otherwise, if the datagram's receiving MOSPF interface doesn't attach to the forwarding cache entry's upstream node, don't forward it any further.
Step 7. If the receiving MOSPF interface's IPMulticastForwarding parameter is set to data-link unicast, only forward the datagram if it was received as a data-link unicast.
Step 8. At this point the datagram is eligible for further forwarding 🥳 Before forwarding, the router checks whether it has any internal applications that have joined Group G on an interface-independent basis. If so, pass a copy of the datagram to each of those requesting application processes.
Step 9. Check each downstream interface listed in the forwarding cache entry. If the TTL in the datagram is greater than or equal to the TTL specified for that downstream interface, forward a copy of the datagram out that interface. Before forwarding the copy, decrement the copy's TTL by 1. On most interfaces the datagram goes out as a data-link multicast/broadcast. The exact data-link encapsulation depends on the attached network's type:
- On ethernet and IEEE 802.3 networks, the datagram is forwarded as a data-link multicast. The destination data-link multicast address is picked by an algorithmic translation of the IP multicast destination. See [RFC 1112] for details.
- On FDDI networks, the datagram is forwarded as a data-link multicast. The destination data-link multicast address is picked by an algorithmic translation of the IP multicast destination. See [RFC 1390] for details.
- On SMDS networks, the datagram is forwarded using the same SMDS address that IP broadcast datagrams use. See [RFC 1209] for details.
- On networks that support broadcast but not multicast (e.g., the Experimental Ethernet), the datagram is forwarded as a data-link broadcast. See [RFC 1112] for details.
- On point-to-point networks, the datagram is forwarded the same way unicast datagrams are forwarded. See [RFC 1112] for details.
Step 10. Check each downstream neighbor listed in the forwarding cache entry. If the TTL in the datagram is greater than or equal to the TTL specified for that downstream neighbor, forward a copy of the datagram to the downstream neighbor (as a data-link unicast). Before forwarding the copy, decrement the copy's TTL by 1.
ICMP error messages are never generated in response to received IP multicasts. In particular, ICMP destination unreachables and ICMP TTL expired messages are not generated by the above procedure if the router refuses to forward a multicast datagram.
11.1. Associating a MOSPF interface with a received datagram ✨
A MOSPF interface has to be associated with a received multicast datagram before it gets forwarded (see Step 1a of Section 11), and with received IGMP Host Membership Reports before they get processed (see Section 9.2).
When only a single IP network is assigned to the physical interface that received the datagram, picking the receiving MOSPF interface is clear-cut. When there are multiple logical IP networks attached to the receiving physical interface, the receiving MOSPF interface gets picked like this. Look at all the MOSPF interfaces associated with the receiving physical interface. Toss out any whose IPMulticastForwarding parameter has been set to disabled. The receiving MOSPF interface is then the remaining interface with the highest IP interface address (or NULL if there are no remaining interfaces)[19] 🎯
11.2. Locating the source network ✨
MOSPF forwarding cache entries are indexed by the datagram's source IP network/subnet/supernet. That's why, whenever an IP multicast datagram arrives, the IP network belonging to the datagram's IP source address has to be found. Here's the algorithm that does it:
Look up the OSPF TOS 0 routing table entry[20] corresponding to the datagram's IP source address, as described in Section 11.1 of [OSPF]. If this routing table entry describes an OSPF intra-area or inter-area route, the source network is set to the network defined by the routing table entry's Destination ID and Address Mask (see Section 11 of [OSPF]). Otherwise (i.e., the routing table entry specifies an external route, or there's no matching routing table entry), the list of matching AS external-link-LSAs gets examined. A matching AS external-link-LSA is one that describes a network which contains the datagram's IP source address. That list gets pruned in the following steps to determine the source network:
- Those AS external-link-LSAs with MC-bit clear (see Section A.1), or with LS age set to
MaxAge, or which were originated by unreachable AS boundary routers, get discarded. - AS external-link-LSAs specifying Type 1 external metrics are always preferred over those specifying Type 2 external metrics.
- If there are still multiple AS external-link-LSAs remaining, the ones specifying the best matching (i.e., most specific) network get selected. The source network is then set to the network/subnet/supernet (possibly even the default route) described by the best matching AS external-link-LSAs. Note that AS external-link-LSAs specifying a cost of
LSInfinityare eligible for this best match, as long as their MC-bit is set.[21]
It's possible that two different MOSPF routers calculate the same multicast datagram's source network differently. For example, check out the network configuration shown in Figure 4. When calculating the source network for a datagram whose source is Network N10 and destination is Group Ma, Router RT11 would calculate the source network as Network N10 itself, while Router RT10 would calculate the source network as the aggregate of Networks N9-N11 and Host H1 (advertised in a single summary-link-LSA by Router RT11). But here's the good part: even if routers pick different source networks, all routers will still agree on the datagram's shortest-path tree 🌈
External sources get treated differently in the above calculation, since the Internet is likely to have separate multicast and unicast topologies for some time to come. Once the multicast and unicast topologies do merge, the MC-bit will be set on all AS external-link-LSAs, and the above use of the LSInfinity metric (to indicate a route meant for multicast traffic but not unicast traffic) won't be necessary anymore. At that point, the determination of source network for external sources goes back to the same simple routing table lookup used for internal sources 💜
As an example of the logic for external sources, suppose a multicast datagram is received having the IP source address 10.1.1.1. Suppose also that the three AS external-link-LSAs shown in Table 3 are in the router's OSPF database. The OSPF routing table lookup would yield the network 10.1.1.0 with a mask of 255.255.255.0, however the above calculation would choose a source network of 10.1.0.0 with a mask of 255.255.0.0, despite the fact that its matching LSA has a cost of LSInfinity.
11.3. Forwarding locally originated multicasts ✨
Okay bestie, so this is where a MOSPF router handles a multicast datagram that one of its own apps just sent out 📦✨
This section describes how a MOSPF router forwards a multicast datagram that was originated by one of its own internal applications. The app formats and addresses the datagram first, and then forwarding the locally originated multicast goes like this:
(1) Find the router interface whose IP address matches the datagram's source address. Multicast the datagram out that interface, following the Host extensions for IP multicasting in [RFC 1112].
(2) If the router interface from the previous step has been configured for MOSPF, and its IPMulticastForwarding parameter is not equal to disabled, set the receiving MOSPF interface to that interface. Otherwise, set the receiving MOSPF interface to NULL.
(3) Run the MOSPF forwarding process from Section 11, starting at its Step 4.
Here's the sample table, which is giving real "example" energy 🎀
Network Mask Cost MC-bit
______________________________________________________
10.1.1.0 255.255.255.0 Type 1: 10 clear
10.1.0.0 255.255.0.0 Type 2: LSInfinity set
10.0.0.0 255.0.0.0 Type 2: 1 set
Table 3: Sample AS external-link-LSAsSo the algorithm basically means the router always multicasts the datagram out the source interface, then runs the basic forwarding algorithm from Section 11 as if the datagram had come in on that source interface 🦋 If the router ends up receiving its own multicast transmissions, Step 3 of Section 11 stops the duplicates from getting copied over and over, so no unwanted replication 🙅♀️ The spec was written on purpose so the right forwarding actions happen whether or not the router hears its own transmissions. That's some serious main character planning 👑
12. Construction of forwarding cache entries ✨
This section breaks down how a MOSPF forwarding cache entry gets built 🧁 We already talked about the high-level version in Sections 2.3, 2.3.1, 2.3.2, 3.2, and 4.1. These entries are built on demand: when a multicast datagram shows up and there's no matching forwarding cache entry, the build kicks off (see Step 6 of Section 11). The inputs to the build are the datagram's source network (see Section 11.2) and its destination group address. In the algorithm below, those two are called SourceNet and Group G. The main steps are:
(1) Allocate the forwarding cache entry. Set its Source network to SourceNet, its Destination multicast group to Group G, and its IP TOS field to match the multicast datagram's TOS. Set its upstream node and its list of downstream interfaces to NULL 💖
(2) For each Area A that the calculating router is attached to:
- a. Calculate Area A's datagram shortest-path tree. This calculation is described in Section 12.2 below. It's kind of similar to how OSPF's intra-area routes get calculated, which is described in Section 16.1 of [OSPF]. The main differences between the multicast datagram shortest-path tree calculation and OSPF's intra-area unicast calculation are listed in Section 12.2.9 below. As a result of each area's datagram shortest-path tree, the forwarding cache entry's list of outgoing interfaces is (possibly) updated. Area A's datagram shortest-path tree depends on the datagram's IP TOS. Section 12.2 covers the TOS 0 datagram shortest-path tree, and the changes needed for non-zero TOS values are in Section 12.2.8 🌈
- b. Possibly set the forwarding cache entry's upstream node. Only one of the calculating router's attached areas decides the upstream node. That area is called the datagram's RootArea. The RootArea starts out as
NULL. After Area A's datagram shortest-path tree is finished, the calculation in Section 12.2.7 decides whether Area A is the datagram's RootArea 🔥
(3) Update the forwarding cache entry's list of outgoing interfaces based on the local group database. This makes sure multicast gets delivered to group members on the calculating router's directly attached networks. Section 12.3 explains this process 🫶
These main steps are explained in more detail below. The detailed part starts with the big data structure the datagram shortest-path tree calculation uses: the Vertex data structure 🧚
12.1. The Vertex data structure
A datagram shortest-path tree gets built with the Dijkstra or SPF algorithm. The algorithm is written in graph language: vertices and links. Vertices are the area's routers and transit networks, and links are the router interfaces and point-to-point lines that connect them. Every vertex has the following state info attached. Basically, this info says what the current best path from the SourceNet to the vertex is, and where the vertex sits relative to the calculating router. Each datagram shortest-path tree is built separately for each area, and the vertices below are also specific to one area (called Area A) 🍓
- Vertex type. Set to 1 for routers, 2 for transit networks. This coding matches the coding for vertices listed in the group-membership-LSA (see Section A.3).
- Vertex ID. A 32-bit identifier for the vertex. For routers, set it to the router's OSPF Router ID. For transit networks, set it to the IP address of the network's Designated Router. This coding matches the coding for vertices listed in the group-membership-LSA (see Section A.3).
- LSA. The link state advertisement describing the vertex' immediate neighborhood. You can find it with a database lookup in Area A's link state database (see Section 12.2 of [OSPF]), with LS type set to Vertex type and Link State ID set to Vertex ID.
- Parent. In the current best path from SourceNet to the vertex, the router or transit network right before the vertex. The parent can change as better paths get found, right up until the vertex is installed on the shortest-path tree 💅
- IncomingLinkType. Set to the type of link that got the vertex onto the shortest-path tree. In order of decreasing preference[22], the possible types are: ILVirtual (virtual links), ILDirect (vertex is directly attached to SourceNet), ILNormal (either router-to-router or router-to-network links), ILSummary (OSPF summary links), ILExternal (OSPF AS external links), or ILNone (the vertex is not on the shortest-path tree).
- AssociatedInterface/Neighbor. If the current best path from SourceNet to the vertex goes through the calculating router, this shows the calculating router's interface (or neighbor) that leads to the vertex.
- Cost. The cost, in OSPF link state metric terms, of the current best path from SourceNet to the vertex. If the path cost is a mix of external type 2 and internal OSPF metrics, the vertex' cost parameter reflects both parts. Remember that the type 2 part always matters more than the type 1 part 🙈
- TTL. If the current best path from SourceNet to the vertex goes through the calculating router, TTL is set to the number of routers between the calculating router and the vertex. That includes the calculating router, but not the vertex itself.
12.2. The SPF calculation
This section explains how datagram shortest-path trees get built 🌸 The tree describes the path a multicast datagram takes as it moves through an OSPF area. For a given datagram, every router in an OSPF area builds an identical tree. A router attached to multiple areas builds a separate datagram shortest-path tree for each area 💜
The datagram shortest-path tree is built with the Dijkstra or SPF algorithm, the same one used to find OSPF's intra-area unicast routes (see Section 16.1 of [OSPF]). The algorithm is explained here and in [OSPF] using graph language: vertices and links. Vertices are the area's routers and transit networks, and links are the router interfaces and point-to-point lines that connect them. The algorithm mainly juggles two lists of vertices: the candidate list and the forming shortest-path tree. The candidate list has the vertices that paths have been found to, but whose paths might not be optimal yet. Each cycle, the vertex closest to the tree's root that's still on the candidate list moves over to the shortest-path tree. Then the neighbors of that just-processed vertex get checked for being added to, or changed on, the candidate list. The algorithm stops when the candidate list is empty ⭐
The datagram shortest-path tree for Area A gets built in these steps. The datagram's SourceNet and its destination group G are the inputs to the calculation (see Step 6 of Section 11). The tree also depends on the IP Type of service in the datagram's IP Header. But we'll put off the TOS talk until Section 12.2.8, so every calculation and cost in this section is for TOS 0 only. The router doing the calculation is called Router RTX. At each step (and in the sub-sections 12.2.1 through 12.2.8), LSAs from Area A's link state database get checked. In every case, any LSA with LS age equal to MaxAge is ignored. The main part of the calculation is Steps 4 and 5, which repeat until the candidate list is empty:
(1) Set up the algorithm's data structures. Clear the shortest-path tree. Set each vertex in Area A (the area's routers and transit networks) to: Parent NULL, IncomingLinkType ILNone, and AssociatedInterface/Neighbor NULL ✨
(2) Set up the candidate list. One or more vertices get placed on the candidate list first, depending on where SourceNet is relative to Area A and Router RTX. This breaks into the following cases (which get named so we can refer back to them later):
- Case
SourceIntraArea:SourceNetbelongs to Area A. In this case, the candidate list is initialized as in Section 12.2.1. - Case
SourceInterArea1:SourceNetbelongs to an OSPF area that is not directly attached to Router RTX. In this case, the candidate list is initialized as in Section 12.2.2. - Case
SourceInterArea2:SourceNetdoes not belong to Area A, but it still belongs to an OSPF area that is directly attached to Router RTX. In this case, the candidate list is initialized as in Section 12.2.3. - Case
SourceExternal:SourceNetis external to the OSPF routing domain, and Area A is not an OSPF stub area. In this case, the candidate list is initialized as in Section 12.2.4. - Case
SourceStubExternal:SourceNetis external to the OSPF routing domain, and Area A is an OSPF stub area. In this case, the candidate list is initialized as in Section 12.2.5.
Two different routers in Area A may select different initialization cases above. 🦋 For example, consider the network configuration shown in Figure 4. When calculating the Area 3 datagram shortest-path tree for a datagram whose source is Network N7 (e.g., from Host H5) and destination is Group Ma, Router RT11 would initialize the candidate list using Case SourceInterArea2 while Router RT9 would use Case SourceInterArea1. Likewise, if Area 3 were configured as an OSPF stub area and the datagram source was the external Network N12, Router RT11 would use Case SourceStubExternal while Router RT9 would use Case SourceInterArea1! 💀 However, despite the possibility of routers selecting different cases, all routers in an area will still initialize the candidate list (and in fact, run the rest of the SPF calculation) identically. 🫶
(3) If the candidate list is empty, the algorithm terminates. 🌸
(4) Move the closest candidate vertex to the shortest-path tree. Select the vertex on the candidate list that is closest to SourceNet (i.e., has the smallest Cost value). If there are multiple possibilities, select transit networks over routers. If there are still multiple possibilities remaining, select the vertex having the highest Vertex ID. Call the chosen vertex Vertex V. Remove Vertex V from the candidate list, and install it on the shortest-path tree.
Next, determine whether Vertex V has been labelled with the Destination multicast Group G. If so, it may cause the forwarding cache entry's list of outgoing interfaces/neighbors to be updated. See Section 12.2.6 for details. ✨
(5) Examine Vertex V's neighbors for possible inclusion in the candidate list. Consider Vertex V's LSA. Each link in the LSA describes a connection to a neighboring router/network. If the link connects to a stub network, examine the next link in the LSA. Otherwise, the link (Link L) connects to a neighboring transit node. Call this node Vertex W. Perform the following steps on Vertex W:
a. If W is already on the shortest-path tree, or if W's LSA does not contain a link back to vertex V, or if W's LSA has LS age of MaxAge, or if W is not multicast-capable (indicated by the MC-bit in the LSA's Options field), examine the next link in V's LSA.
b. Otherwise determine the cost to associate with the link from V to W. If SourceNet belongs to Area A (Case SourceIntraArea in Step 2), use the cost listed for Link L in V's LSA. Otherwise, use the link's reverse cost: Examine W's LSA, and find the cost listed for the link connecting back to V. Actually, when V and W are both routers, there may be multiple links between them. In this case, use the smallest cost listed in W's LSA for any of the links connecting back to V and having the same Type (as specified in the Router-LSA; must be either: point-to-point connection or virtual link) as Link L[23].
c. Calculate the cost from SourceNet to W, when using Link L. It is the sum of the cost of SourceNet to V (i.e., V's Cost parameter) plus the link cost calculated in Step 5b. Let this sum be Cost C. If W is not yet on the candidate list, install W on the candidate list, modifying its parameters as specified below (Step 5d). Otherwise, W is on the candidate list already. In this case, if:
- C is less than W's current Cost, update W's parameters on the candidate list as specified below (Step 5d).
- C is equal to W's current Cost, then the following tiebreakers are invoked. The type of Link L is compared to W's current
IncomingLinkType, and whichever link has the preferred type is chosen (the preference order of link types is listed in Section 12.1's definition ofIncomingLinkType). If the link types are the same, then a link whose Parent is a transit network is preferred over one whose Parent is a router. If the links are still equivalent, the link whose Parent has the higher Vertex ID is chosen. Whenever Link L is chosen, W's parameters are modified as below (Step 5d). Whenever the previously discovered link is chosen, the next link in V's LSA is examined instead. tiebreakers are where the drama lives 🔥 - C is greater than W's current Cost, examine the next link in V's LSA.
d. At this point, a better candidate path has been found to Vertex W, using Link L. Modify Vertex W's parameters accordingly. W's Parent is set to Vertex V. W's IncomingLinkType is set to ILVirtual if Link L is a virtual link, otherwise IncomingLinkType is set to ILNormal. W's Cost parameter is set to C. W's TTL and AssociatedInterface/Neighbor parameters are set according to one of the following cases:
- Vertex V is the calculating router itself. In this case, W's
TTLparameter is set to 1. If Link L is a virtual link, W'sAssociatedInterface/Neighboris set to NULL. Otherwise, W'sAssociatedInterface/Neighboris set to the non-virtual interface connecting the calculating router to W which has the smallest cost value. Note that, in the reverse cost (inter-area and inter-AS multicast) cases, this may not be the interface corresponding to Link L. However, since W is only concerned with the node it is receiving the datagram from (the upstream node; see Section 11), and not with the particular interface the datagram is received on, the calculating router is free to pick the sending interface when there are multiple connecting links. - Vertex V is upstream of the calculating router (i.e., V's
AssociatedInterface/Neighboris equal to NULL). In this case, Vertex W'sTTLparameter is set to 0, and itsAssociatedInterface/Neighboris set to NULL. - V is a transit network, and is directly downstream from the calculating router (i.e., V's
AssociatedInterface/Neighboris non-NULL and V'sTTLis set to 1). W is then one of the calculating router's neighbors. In this case, W'sTTLparameter is also set to 1. If network V has been configured for data-link unicasting (see Section B.2) or if V is a non-broadcast network, W'sAssociatedInterface/Neighboris set to W itself (a neighbor of the calculating router). Otherwise, W'sAssociatedInterface/Neighboris set to the calculating router's interface to Network V. - Vertex V is downstream from the calculating router (i.e., V's
AssociatedInterface/Neighboris non-NULL), and either a) V is a router or b) V'sTTLparameter is greater than 1. In these cases, W'sAssociatedInterface/Neighborparameter is copied directly from V. If V is a router, W'sTTLparameter is set to V'sTTLparameter incremented by one. If V is a transit network, W'sTTLparameter is set directly to V'sTTLparameter.
(6) If the candidate list is non-empty, go to Step 4. Otherwise, the algorithm terminates. 🌈
After the datagram shortest-path tree for Area A is complete, the calculating router (RTX) must decide whether Area A, out of all of RTX's attached areas, determines the forwarding cache entry's upstream node. This determination is described in Section 12.2.7.
Examples of the above SPF calculation, with particular emphasis on the tiebreaking rules, are given in Appendix C. 🧚
12.2.1. Candidate list Initialization: Case SourceIntraArea ✨
In this case, SourceNet belongs to Area A. The candidate list is then initialized as follows. Start with the LSA listed as Link State Origin in the matching OSPF routing table entry. If this LSA is not multicast-capable (i.e, its Options field has the MC-bit clear) the candidate list should be set to NULL. Otherwise, the vertex identified by the LSA is installed on the candidate list, setting its vertex parameters as follows: IncomingLinkType set to ILDirect, Cost set to 0, Parent to NULL and AssociatedInterface/Neighbor to NULL.
As a consequence of this initialization, note that if SourceNet is a stub network, then the datagram shortest-path tree will not actually be rooted at the datagram source, but will instead be rooted at the MOSPF router that attaches the stub network to the rest of the MOSPF system. 🙈 For example, consider the network configuration shown in Figure 4. When calculating the Area 2 datagram shortest-path tree for a datagram whose source is Network N7 (e.g., from Host H5) and destination is Group Ma, Router RT11 (and all other routers attached to Area 2) will begin with the candidate list set to Router RT8. As another example, the datagram shortest-path tree pictured in Figure 3 is really rooted at Router RT3 instead of Network N4. 👑
12.2.2. Candidate list Initialization: Case SourceInterArea1 🦋
Okay so this case is for when SourceNet lives in an OSPF area that is not directly attached to the calculating router (RTX) 🌸. Here's how the candidate list gets set up. Look at the Area A summary-link-LSAs that advertise SourceNet. For each one, if the MC-bit is set in the LSA's Options field and the advertised cost is not LSInfinity, then the vertex for that LSA's advertising area border router gets added to the candidate list 💖. Each added vertex starts out with IncomingLinkType set to ILSummary, Cost set to whatever is advertised in the LSA, Parent set to NULL, and AssociatedInterface/Neighbor set to NULL ✨.
For example, check out the network in Figure 4 🧚. When RT2 calculates the Area 1 datagram shortest-path tree for a datagram from Network N7 (say, from Host H5) to Group Ma, it initializes the candidate list with two area border routers: RT3 (cost 20) and RT4 (cost 19). See Figure 6 for the full picture 👑.
12.2.3. Candidate list Initialization: Case SourceInterArea2 🎀
This one is for when SourceNet belongs to an OSPF area that is not Area A, but that area is still directly attached to the calculating router (RTX) 🦋. The candidate list gets initialized in two steps.
- Find the Area A summary-link-LSA that best matches SourceNet 🔍. Skip any summary-link-LSAs that specify cost
LSInfinityor have unreachable Advertising Routers[24]. A matching summary-link-LSA is one that advertises a range of addresses containing SourceNet, and the best match is, as usual, the most specific one. Let SourceRange be the network described by that best matching summary-link-LSA. - This is similar to the logic in the SourceInterArea1 case 🌈. Examine all the Area A summary-link-LSAs that advertise SourceRange. For each one, if a) the MC-bit is set in the LSA's
Optionsfield, b) the advertised cost is notLSInfinity, and c) the Advertising Router is reachable, then the vertex for that LSA's Advertising Router gets added to the candidate list 💅. Each added vertex starts out withIncomingLinkTypeset toILSummary,Costset to whatever is advertised in the LSA,Parentset to NULL, andAssociatedInterface/Neighborset to NULL.
So why SourceRange and not just SourceNet, like in SourceInterArea1? 🙈 Because routing info can get collapsed at area boundaries. For Area A's area border routers and its internal routers to build the same Area A datagram shortest-path tree, they both have to start at SourceRange, since Area A's internal routers know nothing about SourceNet 💀. Also, SourceRange isn't found by looking at the calculating router's configured set of area address ranges. That's on purpose, so nothing depends on the configured area address ranges being synchronized across every area border router 🫶.
Here's the example from Figure 4 🌸. When RT11 calculates the Area 2 datagram shortest-path tree for a datagram from Network N11 to Group Ma, it works out SourceRange as the collection of Networks N9-N11 and Host H1. Then it initializes the candidate list with just itself (RT11), with a cost of 1, since RT11 advertises Networks N9-N11 and Host H1 in a summary-link-LSA with a cost of 1 🦋.
12.2.4. Candidate list Initialization: Case SourceExternal 👑
Here SourceNet is external to the OSPF routing domain, and Area A is not an OSPF stub area 🧚. The candidate list is initialized as follows. Heads up: a Vertex W might get added to the candidate list when W is already on it 😭. When that happens, W's vertex parameters get updated if the Cost it would be added with is better[25] (closer to SourceNet) than its previous value. If the costs are the same, W's parameters still get modified if the IncomingLinkType it would be added with is better (see the definition of IncomingLinkType in Section 12.1) than its previous value 🌈.
For each AS external-link-LSA advertising SourceNet, do the following steps 💖.
- If the AS external-link-LSA's MC-bit is clear, or if its advertising router is not reachable, then that AS external-link-LSA is not used 🙈. AS external-link-LSAs that have their MC-bit set and advertise a cost of
LSInfinitycan be used, though. These describe paths that work for multicast but not unicast data traffic (see Section 11.2) ✨. - If the AS external-link-LSA's
Forwarding addressfield is0.0.0.0, these vertices get added to the candidate list 🫶. If the Advertising AS boundary router (call it ASBR) belongs to Area A, its vertex is added withIncomingLinkTypeset toILExternal,Costset to whatever is advertised in the LSA,Parentset to NULL, andAssociatedInterface/Neighborset to NULL. Then, whether or not ASBR belongs to Area A, every Area A area border router that is advertising a reachable, multicast-capable (MC-bit set) type 4 summary-link-LSA for ASBR gets added too 🔥. Each of those is added withIncomingLinkTypeset toILSummary,Costset to the sum of what's advertised in that type 4 summary-link-LSA plus the value in the original AS external-link-LSA,Parentset to NULL, andAssociatedInterface/Neighborset to NULL. - If the AS external-link-LSA's
Forwarding addressfield is non-zero, look that address up in the OSPF routing table 🔍. Then it splits into one of these cases:- The Forwarding address is not usable 💀. In that case, nothing gets added to the candidate list. It's not usable if it has no matching routing table entry, or if the matching routing table entry is neither intra-area nor inter-area.
- The Forwarding address belongs to Area A[26] 🦋. Its matching routing table entry has Path-type of intra-area, and its Associated area is Area A. The vertex represented by that entry's Link State Origin field gets added to the candidate list (assuming the vertex is multicast-capable) 🌸. It's added with
IncomingLinkTypeset toILExternal,Costset to whatever was advertised in the original AS external-link-LSA,Parentset to NULL, andAssociatedInterface/Neighborset to NULL. - The Forwarding address belongs to an area that is not attached to Router RTX[27] 🌍. Its matching routing table entry has Path-type of inter-area. Call the network that entry represents ForwardNet. For each reachable, multicast-capable summary-link-LSA (in Area A) advertising ForwardNet, add that LSA's advertising area border router to the candidate list 💖. Each one is added with
IncomingLinkTypeset toILSummary,Costset to the sum of what's advertised in the summary-link-LSA plus the value in the original AS external-link-LSA,Parentset to NULL, andAssociatedInterface/Neighborset to NULL. - The Forwarding address belongs to another one of Router RTX's attached areas[28] 🧚. Its matching routing table entry has Path-type of intra-area, and its associated Area is something other than Area A. Call the network that entry represents ForwardNet. First, find the Area A summary-link-LSA that best matches ForwardNet, skipping any summary-link-LSAs that specify cost
LSInfinityor have unreachable Advertising Routers. Let ForwardRange be the network described by that best matching summary-link-LSA. Then, for each reachable, multicast-capable summary-link-LSA (in Area A) advertising ForwardRange, add that LSA's advertising area border router to the candidate list 👑. Each one is added withIncomingLinkTypeset toILSummary,Costset to the sum of what's advertised in the summary-link-LSA plus the value in the original AS external-link-LSA,Parentset to NULL, andAssociatedInterface/Neighborset to NULL.
Okay, here's the whole thing in one go 🎀. Each of Area A's inter-area multicast forwarders and inter-AS multicast forwarders gets examined. The ones that have multicast-capable paths to SourceNet (represented either as a multicast-capable AS external link or as a Type 4 summary link concatenated with a multicast-capable AS external link) get added to the candidate list as router vertices 🦋. It's possible that a router that is both an inter-area multicast forwarder and an inter-AS multicast forwarder has two equal-cost paths to SourceNet: one an AS external link, and the other a Type 4 summary link concatenated with an AS external link. In that case, the concatenation is preferred 🌈. The added vertex's state is set like this: IncomingLinkType is set to ILSummary if the path is represented as a concatenation of a Type 4 summary link and an AS external link, and to ILExternal otherwise. Cost is set to the cost of the shortest path from the vertex to SourceNet. Parent is set to NULL, and AssociatedInterface/Neighbor is set to NULL ✨.
For example, consider the network configuration shown in Figure 4 🗺️. When calculating the Area 2 datagram shortest-path tree for a datagram whose source is Network N14 and destination is Group Ma, the candidate list would be initialized to the two routers RT7 at a cost of 14 and RT10 at a cost of 19. This assumes that the external costs pictured in Figure 4 are external type 1s 🧠.
12.2.5. Candidate list Initialization: Case SourceStubExternal
Okay so in this case, SourceNet is external to the OSPF routing domain, and Area A is an OSPF stub area 🌸. The candidate list is then initialized similarly to case SourceInterArea1. The Area A summary-link-LSAs advertising DefaultDestination are examined. For each such summary-link-LSA having both its MC-bit set and its advertised cost not equal to LSInfinity, the vertex representing the LSA's advertising area border router is added to the candidate list. An added vertex' state is initialized as: IncomingLinkType set to ILSummary, Cost to whatever is advertised in the LSA, Parent to NULL and AssociatedInterface/Neighbor to NULL ✨.
The most likely outcome of the above is that all of stub Area A's inter-area multicast forwarders will be installed on the candidate list, with appropriate costs 💖.
12.2.6. Processing labelled vertices
Bestie, this is where things get labelled 🏷️. When encountered during the SPF calculation, vertices labelled with the destination multicast group (Group G) may cause the forwarding cache entry's list of downstream interfaces/neighbors to be modified. A Vertex V in Area A is labelled with Group G if and only if at least one of the following holds:
(1) V is a router, and its router-LSA indicates that it is a wild-card multicast receiver (i.e., bit W in its router-LSA is set). This may be true when V is an inter-area or inter-AS multicast forwarder.
(2) V is listed in the body of a group membership-LSA. In particular, find the originator of Vertex V's LSA; call it Router Y. Then find the group-membership-LSA in Area A's link state database which has Link State ID = Group G and Advertising Router = Router Y (see Section A.3). If this group-membership-LSA exists, and if Vertex V is listed in the body of the LSA (see Sections 10 and A.3), then Vertex V is labelled with Group G 🎀.
When Vertex V is added to the shortest-path tree in Step 4 of Section 12.2, and if Vertex V is both downstream from the calculating router (i.e., Vertex V's AssociatedInterface/Neighbor is non-NULL) and labelled with Group G, then Vertex V's AssociatedInterface/Neighbor is added to the forwarding cache entry's list of downstream interfaces/neighbors. In addition, Vertex V's TTL value is attached to the added downstream interface/neighbor. If the particular interface/neighbor had already been added to the list of downstream interfaces/neighbors, the list is simply modified by setting the downstream interface/neighbor's TTL value to the minimum of its existing TTL value and Vertex V's TTL value 🦋.
12.2.7. Merging datagram shortest-path trees
After the datagram shortest-path tree for Area A is complete, the calculating router (RTX) must decide whether Area A, out of all of its attached areas, determines the forwarding cache entry's upstream node. This is done by examining RTX's position on the Area A datagram shortest-path tree, which is in turn described by RTX's Area A Vertex data structure. If RTX's Vertex parameter IncomingLinkType is either ILNone (RTX is not on the tree), ILVirtual or ILSummary, then some area other than Area A will determine the upstream node. Otherwise, Area A might possibly determine the upstream node (i.e., may be selected the RootArea), depending on the following tiebreakers[29]:
- If RootArea has not been set, then set RootArea to Area A. Otherwise, compare the present RootArea to Area A in the following:
- Choose the area that is "nearest to the source". Nearest to the source depends on each area's candidate list initialization case, as it occurs in Step 2 of Section 12.2. The initialization cases, listed in order of decreasing preference (or nearest to farthest) are:
SourceIntraArea,SourceInterArea1,SourceExternalandSourceStubExternal. Areas whose candidate list initialization falls into caseSourceInterArea2are never used as the RootArea. As an example, consider the network configuration shown in Figure 4. When calculating the datagram shortest-path tree for a datagram whose source is Network N7 (e.g., from Host H5) and destination is Group Ma, Router RT11 would set its RootArea to Area 2 (CaseSourceIntraArea) instead of Area 3 (CaseSourceInterArea2) or the backbone Area 0 (CaseSourceInterArea) 🏆. - If there are still two equally good areas, and one of them is the backbone, set RootArea to the backbone (Area 0).
- If there are still two equally good areas, set RootArea to the area whose datagram shortest-path tree provides the shortest path from SourceNet to RTX. This is a comparison of RTX's Vertex parameter Cost in the two areas.
- If there are still two equally good areas, set RootArea to one with the highest OSPF Area ID.
If the above has set the RootArea to be Area A, the forwarding cache entry's upstream node must be set accordingly. This setting depends on the IncomingLinkType in RTX's Area A Vertex structure. If IncomingLinkType is equal to ILDirect, the upstream node is set to the appropriate directly-connected stub network. If equal to ILNormal, the upstream node is set to the Parent field in RTX's Area A Vertex structure. If equal to ILExternal, the upstream node is set to the placeholder EXTERNAL 🫶.
12.2.8. TOS considerations
The previous sections 12.2 through 12.2.7 described the construction of a TOS 0 (default TOS) datagram shortest-path tree. However, in a TOS-capable router, a separate tree may be built for each TOS. If a TOS-capable router receives a multicast datagram that specifies a non-zero TOS X, it first builds the TOS 0 datagram shortest-path tree. Then, if all the routers on the pruned tree are TOS-capable, a separate TOS X datagram shortest-path tree is calculated[30]. Otherwise, the TOS 0 tree is used for all datagrams, regardless of their specified TOS 🌈.
To determine whether there are any TOS-incapable routers on the pruned TOS 0 tree, the following additions are made to Section 12.2's tree calculation:
- A new piece of state information is added to each vertex: TOS-capable path. This indicates whether the present path from SourceNet to vertex, as represented on the datagram shortest-path tree, contains only TOS-capable routers.
- The TOS-capable path parameter is calculated when the vertex is first added to the candidate list and recalculated when/if the vertex' position on the candidate list is modified (see Section 12.2's Step 2 and Step 5d). The parameter is set to
TRUEif both the vertex itself is TOS-capable and the vertex' parent has its TOS-capable path parameter set toTRUE; otherwise, TOS-capable path is set toFALSE. - All routers on the TOS 0 datagram shortest-path tree are TOS-capable if and only if, whenever a vertex labelled with Group G is added to the shortest-path tree (Section 12.2.6), the value of the vertex' TOS-capable path parameter is
TRUE.
The source of the multicast datagram is always located using a TOS 0 routing table lookup, regardless of the datagram's TOS classification (see Section 11.2). If the calculating router is not capable of TOS-based routing, it calculates only TOS 0 datagram shortest-path trees, and uses them to route datagrams independent of TOS value. Otherwise, when calculating the TOS X datagram shortest-path tree, the algorithm in Section 12.2 is used, with the modifications listed below.
- When calculating RangeNet and ForwardRange in Sections 12.2.3 and 12.2.4 respectively, only summary-link-LSAs having TOS 0 cost of
LSInfinityare excluded (no change from the TOS 0 case). However, when adding vertices to the candidate list in Sections 12.2.2 through 12.2.5, the TOS X cost of the summary links and/or AS external links (and not the TOS 0 cost) are reflected in the added vertices' Cost parameter. - In Step 5 of Section 12.2, the TOS X cost of Link L (in the appropriate direction) is used, not the TOS 0 cost.
- Non-TOS-routers are not added to the candidate list, and are thus excluded from the trees 🙈.
12.2.9. Comparison to the unicast SPF calculation
Okay, there are so many similarities between building a multicast datagram's shortest-path trees in Section 12.2 and OSPF's intra-area route calculation for unicast traffic (Section 16.1 of [OSPF]). Both have been described in terms of Dijkstra's algorithm 🤓. But there are some differences, and the major ones are below 👑:
- In the multicast case, the datagram SPF calculation is rooted at the datagram's source. In the unicast case, each router is the root of its own unicast intra-area SPF calculation.
- In the multicast case, the datagram shortest-path tree is a true tree; i.e., between any two nodes on the tree there is one path. However, due to the provision for equal-cost multipath in [OSPF], the unicast SPF calculation may add additional links to the shortest-path tree 💜.
12.3. Adding local database entries to the forwarding cache ✨
Okay bestie, once the datagram shortest-path trees are built for each attached area, the forwarding cache has an upstream node and a list of downstream interfaces 🌸 But wait, there's one more step! To make sure the datagram actually reaches group members on directly attached networks 🫶, the local group database (Section 8.4) has to get scanned so it can add stuff to the list of downstream interfaces 💖 Every local group database entry with Group G as MulticastGroup gets checked 🔍 Say we have [Group G, Network N] 🎀 If the calculating router (RTX) is Network N's Designated Router, then RTX's Network N interface gets added to the list of outgoing interfaces with a TTL of 1 ✨ And if the Network N interface was already on that list? Its TTL just gets set to 1 💅
Here's a cute example 🦋 Picture the network configuration in Figure 4, where we're calculating the forwarding cache entry for a datagram whose source is Network N4 (say, from Host H2) and whose destination is Group Mb 🍓 After the datagram shortest-path tree for Area 1 is calculated, Router RT2 has its upstream node set to Network N3 and its list of downstream interfaces set to NULL 🥹 But then RT2 looks at its local group database, sees the entry, and adds its Network N2 interface with a TTL of 1 to the downstream list. Main character energy for RT2 fr fr 👑
13. Maintaining the forwarding cache 🧚
Okay, so a MOSPF router might need to limit how big its forwarding cache gets, because resources are finite 🥺 Cache entries can be purged at any time to make room for newer ones, and that's totally fine because purged entries can always be rebuilt when needed 🌈 This memo doesn't specify an algorithm for picking which entries to purge, though 🤷♀️ What it does say is that you should take care not to keep rebuilding an entry and then purging it again over and over. That's called thrashing, and it should be avoided 💀
The forwarding cache building stuff was covered in Section 12 💜 There are also events that force one or more forwarding cache entries to get deleted, and we're going through those right now. Deleted cache entries just get rebuilt on an as-needed basis, so no panic 🫶
- When the internal topology of the MOSPF system changes, all forwarding cache entries must be deleted 😭 This is because internal topology changes can make the previously calculated datagram shortest-path trees invalid 🙈 Since the multicast routing calculation depends on the results of the unicast routing calculations, the forwarding cache should be cleared after the unicast routing table has been rebuilt ✨ Internal topology changes are flagged when both a) a new instance of either a router-LSA or a network-LSA is received and b) the contents of the new advertisement (other than the LS age, LS sequence number and LS checksum fields) are different from the previous instance 🦋 This covers routers and links going up or down, routers switching from multicast-incapable to multicast-capable, and so on, etc. 🔥
- When a Type 3 summary-link-LSA (network summary) changes, the forwarding cache entries that specify datagram sources inside the range of addresses described by the updated summary-link-LSA must be deleted 💅 See Sections 12.2.3 and 12.2.5 🎀
- Suppose the content of an AS external-link-LSA changes 👀 If that AS external-link-LSA describes an external network N, then every forwarding cache entry specifying an external source network that is contained in N or that contains N (i.e., external sources that are a subset or a superset of N) must be deleted 💜
- When membership in a multicast group changes, all forwarding cache entries for that particular group must be deleted 🍓 Group membership changes are flagged when either a) the content of a group-membership-LSA changes or b) an entry in the local group database (see Section 8.4) changes ✨
- When the cost to an AS boundary router or to a forwarding address specified by one or more AS external-link-LSAs changes, all forwarding cache entries specifying an external network as datagram source must be deleted 😱 In this case, potentially all inter-AS datagram shortest-path trees have been invalidated, so it's a big moment 🌸 The forwarding cache entries should be deleted after the new best cost to the AS boundary router/forwarding address has been calculated 🫶
Quick reminder, bestie: the cache is always rebuildable, so deleting entries is a normal part of life, not a disaster 💖
14. Other additions to the OSPF specification ✨
MOSPF needs a few tweaks to base OSPF, and they're all backward-compatible 💖 A MOSPF router still gets along perfectly with a plain OSPF router when it's forwarding unicast traffic. Most of these changes already came up earlier in this doc, so this section just gathers up the leftovers. They're organized by the OSPF section they affect.
14.1. The Designated Router
This is all in Section 7.3 of [OSPF]. In OSPF, a network's Designated Router has two big jobs 👑 First, it originates the network's network-LSA. Second, it controls flooding on the network, because every router on that network only syncs with the Designated Router (and the Backup Designated Router). For these reasons[32], when one or more of the network's routers are running MOSPF, the Designated Router should be running MOSPF too. The easy way to make that happen is to give every non-multicast router a Router Priority of 0 🎀
In MOSPF, the Designated Router also keeps an eye on the network's multicast group membership. It does this by periodically sending Host Membership Queries and collecting the Host Membership Reports that come back (see Section 9). This is yet another reason why the Designated Router must be multicast-capable. 🦋
14.2. Sending Hello packets
This one's in Section 9.5 of [OSPF]. A MOSPF router sets the MC-bit in the Options field of its Hello packets. That just says "hey, I'm multicast-capable" 🌸 It doesn't necessarily mean the sending interface's IPMulticastForwarding parameter is turned on (see Section B.2). Setting the MC-bit in Hellos is strictly for informational purposes, so neighbors receiving those Hellos don't act on it at all. A neighbor's multicast-capability gets learned later, during the Database Exchange Process (see Section 14.4).
14.3. The Neighbor state machine
This is covered in Section 10.3 of [OSPF]. When a neighbor enters state Exchange, its neighbor Database summary list gets initialized (check the OSPF neighbor FSM entry for State: ExStart and Event: NegotiationDone) ✨ That list describes the portion of the router's link state database that still needs to be synced with the neighbor. Group-membership-LSAs are included in the neighbor Database summary list if and only if the neighbor is multicast-capable. To figure that out, the router looks at the neighbor's Database Description packets (see Section 14.4).
14.4. Receiving Database Description packets
This is in Section 10.6 of [OSPF]. A neighbor's multicast-capability gets learned from the Database Description packets it sends. When the Database Description packet that moves the neighbor from ExStart to Exchange arrives, the router checks the state of the MC-bit in that packet's Options field. The neighbor is multicast-capable if and only if the MC-bit is set 💜
That neighbor capability then decides two things. First, whether group-membership-LSAs get summarized to the neighbor during Database Exchange (see Section 14.3). Second, whether group-membership-LSAs get flooded to the neighbor during the flooding process (see Section 10.2). Main character energy, honestly 💅
14.5. Sending Database Description packets
Section 10.8 of [OSPF] is the one for this. A MOSPF router sets the MC-bit in the Options field of its Database Description packets. This tells its adjacent neighbors that the router is multicast-capable 🍓 It doesn't necessarily reflect the state of the sending interface's IPMulticastForwarding parameter (see Section B.2) either.
When a router goes from being multicast-capable to multicast-incapable, or vice-versa, it must tell its adjacent neighbors about it by restarting the Database Description process (i.e., rolling every adjacent neighbor's state back to Exstart). Bestie, that's a whole restart, so don't flip this casually 😭
14.6. Originating Router-LSAs
This is in Section 12.4.1 of [OSPF]. A MOSPF router sets the MC-bit in the Options field of its router-LSA. That lets the router be included in datagram shortest-path trees (see Step 5a of Section 12.2) 🧚
MOSPF also adds a brand-new flag to the router-LSA's rtype field: the W-bit ✨ When the W-bit is set, the router gets included on all datagram shortest-path trees, no matter which multicast group we're talking about (see Section 12.2.6). This is called a wild-card multicast receiver. A router sets the W-bit when it wants to receive all multicast datagrams, regardless of destination. That'll sometimes be true for inter-area multicast forwarders (see Section 3.1) and inter-AS multicast forwarders (see Section 4) 🌈
A router must originate a new instance of its router-LSA whenever something happens that would invalidate the LSA's current contents. In particular, if the router's multicast capability changes, or its ability to act as an inter-area or inter-AS multicast forwarder changes, its router-LSA must be reoriginated. No skipping this, periodt 💀
14.7. Originating Network-LSAs
This is in Section 12.4.2 of [OSPF]. In OSPF, a transit network's network-LSA is originated by the network's Designated Router. The Designated Router sets the MC-bit in the Options field of the network-LSA if and only if both of these are true: a) the Designated Router is multicast-capable (in other words, it's running MOSPF), and b) the Designated Router's interface's IPMulticastForwarding parameter has been set to a value other than disabled (see Section B.2) 💖 When the network-LSA has the MC-bit set, the network can be included in datagram shortest-path trees (see Section 12.2.6).
It's intended that all routers attached to a common network agree on that network's IPMulticastForwarding capability. Here's the tea though: this agreement isn't enforced 🙈 When there are disagreements, incorrect routing of multicast datagrams can result, so please don't leave your routers out of sync.
14.8. Originating Summary-link-LSAs
This is in Section 12.4.3 of [OSPF]. Inter-area multicast forwarders always set the MC-bit in the Options field of their summary-link-LSAs, even if the path that the summary-link-LSA describes isn't actually multicast-capable. It's possible there's no multicast-capable path to the described destination at all, and that's okay 🦋 All other area border routers (the ones that aren't inter-area multicast forwarders) clear the MC-bit in the Options field of their summary-link-LSAs.
If its MC-bit is clear, the summary-link-LSA won't be used when initializing the candidate list in Sections 12.2.2, 12.2.3 and 12.2.5 🫶
14.9. Originating AS external-link-LSAs
This is in Section 12.4.4 of [OSPF]. Unlike summary-link-LSAs, an inter-AS multicast forwarder should clear the MC-bit in the Options field of one of its AS external-link-LSAs if it's known that there's no multicast-capable path from the described destination to the router itself. That knowledge might come from, for example, an inter-AS multicast routing algorithm (see Section 4) 🔥 If the inter-AS multicast forwarder is unsure whether a multicast-capable path exists between the described destination and the router itself, the MC-bit should be set in the AS external-link-LSA instead. All other AS boundary routers (the ones that aren't inter-AS multicast forwarders) clear the MC-bit in the Options field of their AS external-link-LSAs.
If its MC-bit is clear, the AS external-link-LSA won't be used when initializing the candidate list in Section 12.2.4 🌸
Here's a spicy case: when multicast connectivity to an external destination exists but unicast connectivity doesn't, an AS external-link-LSA can be originated with its MC-bit set and a cost of LSInfinity. That kind of LSA still gets used by the multicast routing calculation (see Section 12.2.4) ✨ So when a MOSPF router wants to stop advertising an AS external destination, it must use the premature aging procedure specified in Section 14.1 of [OSPF]. Just setting the AS external-link-LSA's cost to LSInfinity won't cut it 🙅♀️
14.10. Next step in the flooding procedure
This is in Section 13.3 of [OSPF]. Group-membership-LSAs are specific to a single OSPF area, and they're only flooded to multicast-capable routers 🧚 When flooding a group-membership-LSA, Section 13.3 of the OSPF specification gets modified like this. 1) The list of interfaces examined during flooding (called the eligible interfaces in Section 13.3 of [OSPF]) is the set of all interfaces attaching to Area A (the area that the group-membership-LSA is received from), just like for router-LSAs, network-LSAs and summary-link-LSAs. 2) When each interface is examined, a group-membership-LSA is added to a neighbor's link state retransmission list if and only if both a) Step 1d of [OSPF]'s Section 13.3 is reached for the neighbor and b) the neighbor is multicast-capable. The neighbor's multicast capability is discovered during the Database Exchange process (see Section 14.4) 💜
Now, on broadcast networks, Link State Update packets go out as multicasts at first, so non-multicast routers might still receive group-membership-LSAs. No drama though: they'll just drop them, because they don't recognize that LS type (see Step 2 of [OSPF]'s Section 13) 🙈 No Link State acknowledgments for group-membership-LSAs are expected from non-multicast routers, and group-membership-LSAs will never get retransmitted to them, since the LSAs never go on those routers' link state retransmission lists (see the paragraph above) 💅
For more on flooding group-membership-LSAs, check out Section 10.2 🎀
14.11. Virtual links
This is in Section 15 of [OSPF] 🦋 When a MOSPF router (in other words, a multicast-capable router) is both an area border router and an endpoint of a virtual link whose other endpoint is also multicast-capable, the router must also be an inter-area multicast forwarder. This is necessary so that multicast datagrams can flow through the virtual link's transit area, from one endpoint to the other 🌈 When the backbone's datagram shortest-path tree is constructed in Section 12.1, it's assumed that virtual links can forward multicast datagrams whenever both endpoints are multicast-capable. Iconic behaviour from the backbone, no notes 👑
15. References 📚
Okay bestie, here's the reading list, kept exactly as written so nobody gets confused 🎀
[Bharath-Kumar] Bharath-Kumar, K. and J. Jaffe, "Routing to Multiple
Destinations in Computer Networks", IEEE
Transactions on Communications, COM-31[3], March
1983.
[Deering] Deering, S., "Multicast Routing in Internetworks and
Extended LANs", SIGCOMM Summer 1988 Proceedings,
August 1988.
[Deering2] Deering, S., "Multicast Routing in a Datagram
Internetwork", Stanford Technical Report, STAN-CS-
92-1415, Department of Computer Science, Stanford
University, December 1991.
[OSPF] Moy, J., "OSPF Version 2", RFC 1583, Proteon, Inc.,
March 1994.
[RFC 1075] Waitzman, D., Partridge, C., and S. Deering,
"Distance Vector Multicast Routing Protocol", RFC
1075, BBN STC, Stanford University, November 1988.
[RFC 1112] Deering, S., "Host Extensions for IP Multicasting",
STD 5, RFC 1112, Stanford University, May 1988.
[RFC 1209] Piscitello, D., and J. Lawrence, "Transmission of IP
Datagrams over the SMDS Service", RFC 1209, Bell
Communications Research, March 1991.
[RFC 1340] Reynolds, J. and J. Postel, "Assigned Numbers", STD
2, RFC 1340, USC/Information Sciences Institute,
July 1992.
[RFC 1390] Katz, D., "Transmission of IP and ARP over FDDI
Networks", STD 36, RFC 1390, cisco Systems, Inc.,
January 1993.Footnotes 🧚
[1] Okay so, OSPF actually lets you configure a separate link cost for each TOS 💅 That means MOSPF can end up calculating separate paths for each TOS. See Section 6.2 for the deets.
[2] We also assume in this section that the pictured multi-access networks provide data-link multicast/broadcast services 🌸
[3] Note that if N3 were a non-broadcast network, RT3 would send separate copies of the datagram to RT1 and RT2 😭 And since IGMP isn't defined on non-broadcast networks, there could be no Group B member attached to N3 in that case. Still, the multicast datagram would get delivered to the Group B members on N1 and N2 💖
[4] Actually, MOSPF keeps a separate forwarding cache entry for each combination of source, destination and TOS 🦋 For a discussion of TOS-based multicast routing, see Section 6.2.
[5] Okay, this one's a little plot twist 🙈 The discussion in this section skips the Backup Designated Router's role in IGMP. The BDR doesn't send IGMP Host Membership Queries, but it does listen to IGMP Host Membership Reports and builds "shadow" local group database entries along the way. Those entries don't lead to group-membership-LSAs, and they don't influence delivery of multicast datagrams. They're just kept around to make the handoff from BDR to Designated Router smooth if the DR fails. See Sections 2.3.4, 9 and 10 for details 🫶
[6] One could imagine building every possible datagram shortest-path tree up front, but that might be expensive, both in router CPU time and in router memory 💀 The hope is that building the trees on demand and caching the results spreads the calculations out over a longer period, which eases the pressure on router resources ✨
[7] It's possible that, thanks to alternate paths, several different shortest-path trees are available. MOSPF depends on every router building the exact same tree, so tie-breaking schemes get used during tree construction to make sure identical trees come out 👑 See Section 12 for more details.
[8] Note that the expanding ring search finds the nearest server in terms of hop count, but not necessarily in terms of the OSPF metric 🧭
[9] This means that in MOSPF, just like in OSPF, the only kind of link state advertisement that can be flooded between areas is the AS external-link-LSA 🌈
[10] A router says it's a wild-card multicast receiver by setting the appropriate flag in its router-LSA. See Section 14.6 for details 🎀
[11] This is not quite true, bestie 🙃 As we'll see, any inter-AS multicast forwarders that belong to the backbone are designated as wild-card multicast receivers. See Section 4.
[12] It's possible that, through an inter-AS multicast routing protocol, Router RT7 knows it doesn't have multicast connectivity to Network N15, even though it has unicast connectivity 😤 In that case, RT7 would not advertise the external link to N15 as multicast capable.
[13] Synchronization of the IPMulticastForwarding interface parameter isn't enforced by the MOSPF protocol, since it isn't included in the contents of a MOSPF router's Hello packets 🤷♀️
[14] Actually, when multiple IP networks have been assigned to the same physical network, the very first thing to do is associate an IP network with the received Host Membership Report. That's done the same way a receiving interface gets associated with a received multicast datagram. See Section 11.1 🧩
[15] For this reason, when a transit network has both MOSPF routers and non-multicast OSPF routers attached, be careful to make sure a MOSPF router gets elected Designated Router 👀 You can do that by setting the routers' configured Router Priority properly.
[16] Note that just because these advertisements exist in the link state database, it doesn't mean the Group G members are reachable 😬 Reachability doesn't enter into building the transit vertex list, which keeps the calculation simple. It's a trade-off, though. As a result, some multicast datagrams may get forwarded further than necessary when the described Group G members are actually unreachable.
[17] Since the Designated Router controls flooding on the network, this is yet another reason to make sure a MOSPF router is the Designated Router 🫶
[18] In other words, group-membership-LSAs will never be retransmitted to non-multicast routers 🙅♀️
[19] This last step won't be necessary if the configuration guidelines in Section 6.5 are followed ✨
[20] The TOS 0 routing table entry gets examined regardless of the TOS specified by the multicast datagram 💅
[21] It's assumed that a MOSPF router wanting to stop advertising a route to an external destination will use the premature aging procedure in Section 14.1 of [OSPF], rather than setting the AS external-link-LSA's cost to LSInfinity 🌷
[22] This preference ordering is used in Step 5c of Section 12.2 🧁
[23] No attempt is made to match the links' two halves. See Step 5d 🪞
[24] Okay, but a summary-link-LSA is still eligible for matching even if the MC-bit in its Options field is clear 🦋
[25] Costs may have both a Type 2 and a Type 1 component, and the Type 2 component is always the most significant one 📏
[26] This case mirrors the SourceIntraArea candidate list initialization in Section 12.2.1 🪄
[27] This case mirrors the SourceInterArea1 candidate list initialization in Section 12.2.2 🪄
[28] This case mirrors the SourceInterArea2 candidate list initialization in Section 12.2.3 🪄
[29] Note that picking the upstream node this way enforces the inter-area routing architecture from Section 3.1. The multicast datagram goes from the source area, over the backbone, and then into the non-backbone areas 🌍 It's kind of like the "hub and spoke" architecture for unicast forwarding described in Section 3.2 of [OSPF].
[30] Okay, this procedure looks backwards at first 🙃 You'd expect the TOS X datagram tree to be built first. But the SPF calculation has to make sure that all routers participating in forwarding that datagram, both TOS-capable and non-TOS-capable, build the same tree. Since we know the non-TOS-capable routers will use the TOS 0 tree, the only safe way to use the TOS X tree is when you're guaranteed the non-TOS-capable routers will decline to forward the datagram. That guarantee is clearly met when only TOS-capable routers sit on the TOS 0 datagram tree 💖
[31] Indeed, there are also cases where a router that isn't on a particular datagram shortest-path tree never has to calculate that tree, since it won't receive the datagram in the first place 🌙
[32] Group-membership-LSAs aren't processed by non-multicast routers (see Section 10.2) 🙈 Also, if the Designated Router wasn't running the multicast extensions, multicast datagrams wouldn't get forwarded over the network, because its network-LSA would have its MC-bit clear (see Step 5a in Section 12.2).
A. Data Formats 💅
Here's where we get into the packet and LSA formats ✨ This section documents the format of MOSPF protocol packets and link state advertisements (LSAs). Every change and addition to the OSPF Version 2 data formats was made in a backward-compatible way 🫶 So multicast routers running MOSPF can interoperate with (non-multicast) OSPF Version 2 routers when forwarding regular (unicast) IP data traffic. Iconic, right? 🌈
The MOSPF packet formats are the same as for OSPF Version 2, which is described in Appendix A of [OSPF] 🎀 One extra option got added to the Options field that shows up in OSPF Hello packets, Database Description packets and all link state advertisements. This new option indicates a router's or network's multicast capability, and it's documented in Section A.1. The presence of this new option is ignored by all non-multicast routers 🦋
To support MOSPF, one of OSPF's link state advertisements got modified, and a brand new one got added 🔥 The format of the router-LSA was modified (see Section A.2) to include a new flag that says whether the router is a wild-card multicast receiver. The new link state advertisement, called the group-membership-LSA, was added to pinpoint multicast group members in the link state database 💜 This new advertisement is neither flooded nor processed by non-multicast routers. The group-membership-LSA is documented in Section A.3.
A.1 The Options field ✨
okay so the OSPF Options field shows up in Hello packets, Database Description packets, and every link state advertisement 💖 It's how routers say what they can and can't do, so routers with different levels of capability can all hang out in the same OSPF routing domain 🫶
In Hello packets, it lets a router turn away a neighbor when the capabilities don't match 🙅♀️ In Database Description packets, a router can decide not to forward certain LSA types to a neighbor that has reduced functionality. And when capabilities are listed inside LSAs, routers can route traffic around the reduced-functionality routers by leaving them out of parts of the routing table calculation. main character routing behavior 👑
There are three capabilities defined so far. For each one, the effect of it showing up (or not showing up) in Hello packets, Database Description packets, and link state advertisements is spelled out below. Heads up: the E-bit (ExternalRoutingCapability) only means something in Hello packets 🦋
+---+---+---+---+---+---+---+---+
| * | * | * | * | * |MC | E | T |
+---+---+---+---+---+---+---+-+-+
The OSPF Options field- T-bit 🌸 This tells you the router's TOS capability. If the T-bit is reset, the router only supports a single TOS (TOS 0), and it's also called incapable of TOS-routing. If a router links advertisement doesn't have the T-bit, that router gets skipped when building a non-zero TOS shortest-path tree. So routers that can't do TOS routing get avoided as much as possible when forwarding data traffic that asks for a non-zero TOS 🙈 The same goes for summary link advertisements and AS external link advertisements: if the T-bit is missing, that advertisement is only describing a TOS 0 route (not routes for non-zero TOS).
- E-bit 🍓 AS external link advertisements don't get flooded into or through OSPF stub areas. The E-bit makes sure all the members of a stub area agree on how that area is set up. It only matters in Hello packets. When the E-bit is reset in a Hello packet sent out a particular interface, the router won't send or receive AS external link state advertisements on that interface (so basically, that interface connects to a stub area). Two routers won't become neighbors unless they agree on the E-bit. no cap, that's a dealbreaker 💅
- MC-bit 🧚 This one describes the multicast capability of the different pieces of the OSPF routing domain. When figuring out the path for multicast datagrams, only the link state advertisements with the MC-bit set get used. A router also uses the MC-bit in its Database Description packets to tell its adjacent neighbors whether it's going to take part in flooding the new group-membership-LSAs ✨
A.2 Router-LSA 💜
okay so an OSPF router creates a router-LSA for each of its attached areas. The router-LSA describes the state and cost of the router's interfaces to that area. The full details of the router-LSA are in Section A.4.2 of [OSPF] 🫶 The router-LSA already has flags that say whether the router is a) an area border router, b) an AS boundary router, or c) the endpoint of a virtual link. MOSPF added one more flag, called bit W below 🔥 It shows whether the router wants to receive all multicast datagrams no matter the destination. Basically, a wild-card multicast receiver 🎀
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LS age | Options | 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link State ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Advertising Router |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LS sequence number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LS checksum | length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| rtype | 0 | # links |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
| Link ID | P
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ E
| Link Data | R
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | # TOS | TOS 0 metric | #
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ L
# | TOS | 0 | metric | I
T +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ N
O | ... | K
S +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ S
| | TOS | 0 | metric | |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
| ... |
The router LSA
+---+---+---+---+---+---+---+---+
| * | * | * | * | W | V | E | B |
+---+---+---+---+---+---+---+-+-+
The rtype fieldThe rtype field has flags that classify the router by what it does 🌈 Here's what each one means:
- bit B 🦋 When this is set, the router is an area border router (B is for border). These routers forward unicast data traffic between OSPF areas.
- bit E 💅 When this is set, the router is an AS boundary router (E is for external). These routers forward unicast data traffic between Autonomous Systems.
- bit V 🌸 When this is set, the router is an endpoint of an active virtual link (V is for virtual), and that link uses the described area as its Transit area.
- bit W 👑 When this is set, the router is a wild-card multicast receiver. These routers receive all multicast datagrams no matter the destination. Inter-area multicast forwarders and inter-AS multicast forwarders are sometimes wild-card multicast receivers too (see Sections 3 and 4) ✨
A.3 Group-membership-LSA 🧚
okay so group-membership-LSAs are the Type 6 link state advertisements 💖 They belong to one specific OSPF area and never get flooded past the area they came from. A router's group-membership-LSA for Area A shows the directly attached networks that are in Area A and have members of a particular multicast group 🫶
A router makes a group-membership-LSA for multicast group D when both of these are true for at least one directly attached network: 1) the router has been elected Designated Router for that network, and 2) at least one host on the network has joined Group D through the IGMP protocol 🙌
A router can also make a group-membership-LSA for Group D if the router itself runs internal applications that belong to Group D. Area border routers also originate group-membership-LSAs into the backbone area when there are group members in their attached non-backbone areas. For more on when these get originated, see Section 10 🔥
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LS age | Options | 6 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link State ID = Destination Group |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Advertising Router |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LS sequence number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LS checksum | length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Vertex type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Vertex ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
The group-membership-LSASo the group-membership-LSA is the standard 20-byte link state header (see Section A.4.1 of [OSPF]) followed by a list of transit vertices to label with the multicast destination 🎀 The advertisement's Link State ID is set to the destination multicast group address. There's no metric associated with it. Each transit vertex is identified by its Vertex type and Vertex ID (see Section 12.1 for an explanation of this terminology) 🦋
- Vertex type 💖 This is set equal to 1 for a router, and 2 for a transit network. Note that the only router that may be included in the list is the Advertising Router itself 💅
- Vertex ID 🫶 For router vertices, this field holds the router's OSPF Router ID. For transit network vertices, it holds the IP address of the network's Designated Router. Also, the link state advertisement tied to the transit vertex is the one where
LS type= Vertex type,Link State ID= Vertex ID, andAdvertising Router= the group-membership-LSA's Advertising Router 🌸
B. Configurable Constants ✨
okay so this section is the settings list for OSPF's multicast extensions 🎀 These parameters are in addition to the configurable constants that base OSPF already has (check Appendix C of [OSPF] for those). Every MOSPF implementation must provide a way to set these, whether through network management or some other means 💅
B.1 Global parameters
These apply to the whole router 🌸
- Multicast capability. This tells you whether the router is running MOSPF. If it is, it will follow the algorithms in this specification. If it isn't, the router can still run basic OSPF (as set out in [OSPF]) and will be able to interoperate with multicast capable routers (see Section 6.1) when forwarding regular (unicast) IP data traffic 🦋
- Inter-area multicast forwarder. This decides whether the router forwards multicast datagrams between OSPF areas. Such a router summarizes group membership information to the backbone, and acts as a wild-card multicast receiver in all its attached non-backbone areas (see Section 3.1). Not every multicast-capable area border router has to be set up as an inter-area multicast forwarder. BUT whenever both ends of a virtual link are multicast-capable, they must both be configured as inter-area multicast forwarders (see Section 14.11) 👑 By default, all multicast-capable area border routers are configured as inter-area multicast forwarders ✨
- Inter-AS multicast forwarder. This decides whether the router forwards multicast datagrams between Autonomous Systems. Such a router acts as a wild-card multicast receiver in all attached areas (see Section 4). It is also assumed that an inter-AS multicast forwarder runs some kind of inter-AS multicast routing algorithm 🧚
B.2 Router interface parameters
These can be set separately for each of the router's OSPF interfaces. Quick reminder: an OSPF interface is the connection between the router and one of its attached IP networks 🍓 Also, IPMulticastForwarding is really a description of the attached network, so it should be configured identically on all routers attached to a common network. Otherwise, incorrect routing of multicast datagrams may result 😭
IPMulticastForwarding. This decides whether IP multicasts get forwarded over the attached network, and if so, how. It can be one of three values:disabled,data-link multicastordata-link unicast. When it'sdisabled, IP multicast datagrams will not be forwarded out the interface. When it'sdata-link multicast, they get forwarded as data-link multicasts. When it'sdata-link unicast, they get forwarded as data-link unicasts. The default isdata-link multicast. The other two settings are for the special circumstances described in Sections 6.3 and 6.4. When it's set todisabledordata-link unicast, IGMP group membership is not monitored on the attached network 🙈IGMPPollingInterval. The number of seconds between IGMP Host Membership Queries sent out this interface. A multicast-capable router only sends IGMP Host Membership Queries when it has been elected Designated Router for the attached network. See [RFC 1112] for a discussion of this parameter's value 💖- IGMP timeout. If no IGMP Host Membership Reports have been heard on an attached network for a particular multicast group A after this period of time, the entry [Group A, attached network] is deleted from the router's local group database. See Section 9 for more information 🥀
C. Sample datagram shortest-path trees
okay this part is my favorite because it's basically a drama between routers 🎭 In MOSPF, all routers must calculate exactly the same datagram shortest-path trees. Like, no exceptions. To make sure that happens in internetworks with redundant links, a bunch of tie-breakers were defined in the MOSPF routing table calculation (see Steps 4 and 5c of Section 12.2, and Sections 12.2.4 and 12.2.7). This section shows those tie-breakers in action on one sample topology 👑
There are three examples, all using the same physical topology and the same set of OSPF interface costs (check the left side of Figure 14). The source is always Host H1 on the network at the top of the figure (192.9.1.0), and the destination group members are the two hosts labelled Group Ma at the bottom. The first case is intra-area multicast, and the other two show how OSPF areas change the path of a multicast datagram 🌈
C.1 An intra-area tree
The datagram shortest-path tree for the intra-area case is on the right of Figure 14. The root is the source network (192.9.1.0), and the leaves are the two routers (RT4 and RT3) directly attached to the stub networks with Group Ma members 🦋
There are equal-cost paths to both group members. For the member on the left, the path could go either through network 10.1.0.0 or through network 10.2.0.0. By the tie-breaking rules, the path through 10.2.0.0 wins, since it has the larger IP network number (see Step 5c of Section 12.2) 💅
For the member on the right, the path could go either over Network 10.2.0.0 or over the serial line connecting routers RT2 and RT3. The path over Network 10.2.0.0 is chosen after two tie-breaking rules. First, Network 10.2.0.0 goes on the shortest-path tree before Router RT3, since networks are always chosen over routers (see Step 4 of Section 12.2). Then, here's the figure:
+--+
|H1|
+--+
Net 192.9.1.0 |
+------------------+
| |
+----------+ |1 |1
| Network | 8+---+ +---+ o 192.9.1.0
| 10.1.0.0 |------|RT1| |RT2| |
+----------+ +---+ +---+ 0|
| |8 8| |
8| +----------+ |8 o RT1
+---+10 | Network | 10+---+ |
|RT4|-------| 10.2.0.0 |----|RT3| 8|
+---+ +----------+ +---+ |
|3 |3 o 10.2.0.0
| | / \
+---------+ +-------+ 0/ \0
| | / \
+--+ +--+ o o
|Ma| |Ma| RT4 RT3
+--+ +--+
Figure 14: An intra-area treechoice of either Network 10.2.0.0 or Router RT2 for RT3's parent on the tree, Net 10.2.0.0 is again preferred since it is a network (see Step 5c of Section 12.2)
C.2 The effect of areas
In Figure 15 below, the previous diagram has been modified by adding OSPF areas 🧚 The datagram source is now part of the OSPF backbone (Area 0), while the rest of the topology is in Area 1. Since the source and the group members are in different areas, reverse costs are used when building the tree (see Step 5b of Section 12.2). This actually eliminates the equal cost paths from the diagram, and leads to the Area 1 datagram shortest-path tree on the right of Figure 15 ✨
+--+
|H1|
+--+
Net 192.9.1.0 |
+------------------+
..................... | |
. +----------+ . |1 |1 192.9.1.0
. | Network | 8+---+ +---+ o
. | 10.1.0.0 |------|RT1|........|RT2|... / \
. +----------+ +---+ +---+ . 1/ \1
. | |8 8| . / \
. 8| +----------+ |8 . o RT1 o RT2
. +---+10 | Network | 10+---+ . | \
. |RT4|-------| 10.2.0.0 |----|RT3| . 0| \8
. +---+ +----------+ +---+ . | \
. |3 |3 . o 10.1.0.0 o
. | | . | RT3
. +---------+ +-------+. 8|
. | | . |
. +--+ +--+ . o
. |Ma| |Ma| . RT4
. +--+ Area 1 +--+ .
.........................................
Figure 15: The effect of areasC.3 The effect of virtual links
In Figure 16 below, Network 10.1.0.0 has been set up as its own area (Area 1), while everything else belongs to the OSPF backbone (Area 0). On top of that, a virtual link runs through Area 1, boosting the backbone connectivity 🌸 Here, the source and the group members are in the same area, so forward costs are used. However, since virtual links are preferred over regular links (see Step 5c of Section 12.2), the backbone datagram shortest-path tree uses Network 10.1.0.0 instead of 10.2.0.0 on the path to the left group member. That gives the tree on the right of Figure 16 🦋
+--+
|H1|
+--+
Net 192.9.1.0 |
................ +------------------+
. +----------+ . /1 |
. | Network |8. / |1
. | 10.1.0.0 |-+---+ +---+ o 192.9.1.0
. +----------+*|RT1| |RT2| |
. 8|*******+---+ +---+ 0|
.Area1 |*VL . \8 8| |
.....+---+...... +----------+ |8 o RT1
|RT4|10 | Network | 10+---+ / \
+---+-------| 10.2.0.0 |----|RT3| /8 \8
| +----------+ +---+ / \
|3 |3 o 10.1 o 10.2.0.0
| | | |
+---------+ +-------+ |0 |0
| | | |
+--+ +--+ o o
|Ma| |Ma| RT4 RT3
+--+ +--+
Figure 16: The effect of virtual linksSecurity Considerations
Security issues are not discussed in this memo. 🔒 Plot twist: that's the whole section, so no hidden drama here, bestie 🫶
Author's Address ✨
okay bestie, this is where we find the human behind all of it 🫶 John Moy was the author, and here's how to reach him. He was at Proteon, Inc. 💅
John Moy
Proteon, Inc.
9 Technology Drive
Westborough, MA 01581
Phone: (508) 898-2800
Email: jmoy@proteon.comthat's the whole RFC, babe 🦋 every spec, every section, every little detail is now yours to read and enjoy 💜
📦 where this page comes from
- ietf: rfc1584 1994-03
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms