RFC 1075
Distance Vector Multicast Routing Protocol
Distance Vector Multicast Routing Protocol 🎀
RFC 1075 · Network Working Group · November 1988 📅
Authors: D. Waitzman, C. Partridge (BBN STC), and S. Deering (Stanford University) 👩💻
Status: This is an experimental protocol, and the title block doesn't list anything it obsoletes or updates 🧪
1. Status of this Memo ✨
okay so this RFC describes a distance-vector-style routing protocol for routing multicast datagrams through an internet 🌐 it's derived from the Routing Information Protocol (RIP) [1] and implements multicasting as described in RFC-1054 💅 this is an experimental protocol, and its implementation is not recommended at this time 🧪 distribution of this memo is unlimited 🦋
2. Introduction 🌸
so there's a draft standard for multicasting over IP networks now [2], but there weren't any routing protocols to support internetwork multicasting 😭 this memo describes an experimental routing protocol called DVMRP that does exactly that ✨ DVMRP mixes a bunch of RIP's features [1] with the Truncated Reverse Path Broadcasting (TRPB) algorithm Deering described in [3] 🧚
DVMRP is an "interior gateway protocol" 🏠 it's suitable inside an autonomous system but not between different autonomous systems 🙅♀️ it isn't currently developed for routing non-multicast datagrams, so a router that handles both multicast and unicast datagrams has to run two separate routing processes 🥲 it's designed to be easily extensible, though, and could be extended to route unicast datagrams 💜
DVMRP was built to experiment with the algorithms in [3] 🔬 RIP was the starting point because an implementation was already available, and distance vector algorithms are simple compared to link-state algorithms [4] 👑 also, to let experiments cross networks that don't support multicasting, a mechanism called "tunneling" was developed 🚇
the multicast forwarding algorithm needs trees built from routing information 🌳 building those trees needs more state information than RIP is designed to provide, so DVMRP is way more complicated in some places than RIP 😅 a link-state algorithm already keeps much of the state needed, so it might prove a better basis for Internet multicast routing and forwarding 🤔
here's the big difference 💅 RIP thinks in terms of routing and forwarding datagrams to a particular destination 📦 DVMRP's whole purpose is to keep track of the return paths to the source of multicast datagrams 🔁 to keep the explanation consistent with RIP, this memo uses the word "destination" instead of the more proper "source", but you have to remember that datagrams aren't forwarded to these destinations; they originate from them 🫶
this memo is organized like this:
- A description of DVMRP is presented.
- Tunnels are explained.
- The routing algorithm is shown.
- The forwarding algorithm is shown.
- The various time values are listed.
- Configuration information is specified.
this memo doesn't analyze distance-vector routing or fully explain the distance-vector algorithm, so check [1] for more on those topics 📚 the processes that do the routing and forwarding are called "routers" in this memo 🖥️
3. Protocol Description 💖
DVMRP uses the Internet Group Management Protocol (IGMP) to exchange routing datagrams [2] 📨
DVMRP datagrams have two parts: a small, fixed length IGMP header, and a stream of tagged data 🎁
the fixed length IGMP header of DVMRP messages looks like this:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version| Type | Subtype | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+the version is 1 🔢
the type for DVMRP is 3 🏷️
the subtype is one of these 🎯
1= Response; the message provides routes to some destination(s). 📬2= Request; the message requests routes to some destination(s). 🙋♀️3= Non-membership report; the message provides non-membership report(s). 🚫4= Non-membership cancellation; the message cancels previous non-membership report(s). ❌
the checksum is the 16-bit one's complement of the one's complement sum of the entire message, excluding the IP header 🧮 when computing it, the checksum field is zeroed 0️⃣
the rest of the DVMRP message is a stream of tagged data 🎀 the reason for using tagged data is easy extensibility (new commands can be made by adding new tags) and less redundant data in a message ✨ the elements in the stream, called commands, are multiples of 16 bits, so they line up nicely 📏 each command is an eight bit command numeric code with at least an eight bit data portion 💜 sixteen-bit alignment of all commands is required 🧱
if a message has an error in it, it gets discarded at the point where the error is detected 🗑️ any state changed by the message contents before the error will not be restored to its previous values 😬
some commands have default values defined in their specification 🧸 since the defaults may change as the protocol develops, a cautious implementation should not send out messages that depend on defaults 🛡️
DVMRP messages are limited to 512 bytes, excluding the IP header 📏
3.1 NULL Command 🫧
Format:
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| 0 | | Ignored |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+the NULL command can be used to provide extra alignment or padding to 32 bits 🧩
3.2 Address Family Indicator (AFI) Command 🏡
Format:
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| 2 | | family |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+values for family:
2= IP address family, in which addresses are 32 bits long. 🌟
Default: Family = 2.
the AFI command gives the address family for the addresses that come after it in the stream (until a different AFI command shows up) 🔮
it is an error if the receiver does not support the address family 🙅♀️
3.3 Subnetmask Command 🎭
Format:
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| 3 | | count |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+additional argument, with AFI = IP:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Subnet mask |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+count is 0 or 1 🔢
Default: assume that the following routes are to networks, and use a mask of the network mask of each route's destination. 🧭
the subnetmask command gives the subnet mask to use for the routes that come next 🎀 there are some requirements on the bits in the subnetmask: bits 0 through 7 must be 1, and all of the bits must not be 1 🧐
if the count is 0, no subnet mask applies: assume the following routes are to networks, and use a mask of the network mask of each route's destination 🌐 if the count is 1, then a subnet mask should be in the data stream, sized right for the address family 📐
it is an error for count not to equal 0 or 1 🚨
subnetmasks should not be sent outside of the appropriate network 🏠
see [6] for more about IP subnetting 📖
3.4 Metric Command 📏
Format:
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| 4 | | value |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+value is the metric, as an unsigned value ranging from 1 to 255 🔢
Default: None.
the metric command gives the metric for the destinations that follow 🚀 the metric is relative to the router that sent this DVMRP routing update 📡
it is an error for metric to equal 0 🙅♀️
3.5 Flags0 Command 🚩
Format:
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| 5 | | value |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+meaning of bits in value:
Bit 7: Destination is unreachable.
Bit 6: Split Horizon concealed route.Default: all bits zero.
the flags0 command is a way to set a bunch of flags 🏳️🌈 the only defined flags are bits 6 and 7, and they give more info about a route with a metric of infinity 🌈 a router that gets a flag it doesn't support should ignore it 🙈 the command is called flags0 so that more flag commands (flags1, etc.) can be defined later 🧚
this is an experimental command, and it may change in the future 🧪
3.6 Infinity Command ♾️
Format:
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| 6 | | value |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+value is the infinity, as an unsigned value ranging from 1 to 255 🔢
Default: Value = 16.
the infinity command defines the infinity for the metrics that come after it in the stream 🌌
it is an error for infinity to be zero, or less than the current metric 🚫
3.7 Destination Address (DA) Command 📍
Format:
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| 7 | | count |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+array of count additional arguments, with AFI = IP:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+count is the number of addresses supplied, from 1 to 255 🔢 the length of the addresses depends on the current address family 📏 the number of addresses supplied is subject to the 512 byte message length limitation 🧮
Default: None.
the DA command gives a list of destinations 📋 this format can express routes to hosts, but the routing algorithm only supports network and subnetwork routing 🏘️ the current metric, infinity, flags0 and subnetmask, when combined with a single destination address, define a route 🛣️ the current metric must be less than or equal to the current infinity 💅
it is an error for count to equal 0 🙅♀️
That's the end of part 1 of 5, bestie! 🌈✨ More is coming, so stay tuned 💜
3.8 Requested Destination Address (RDA) Command ✨
Okay so the RDA command is basically the "hey, can you tell me the routes to these destinations?" message 💅 Here's the layout:
Format: 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| 8 | | count |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
Array of 'count' additional arguments, with AFI = IP:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Requested Destination Address1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Requested Destination Address2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+count is the number of addresses supplied, from 0 to 255 🫶 The length of each address depends on the current address family, and the number of addresses you pack in is capped by the 512-byte message length limitation 🙈
Default: None.
Description: The RDA command gives a list of destinations that you want routes for. If you want routes for everything, you send count = 0 💖
3.9 Non Membership Report (NMR) Command 🦋
Format of the NMR command, where count is the number of pairs:
Format: 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| 9 | | count |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
Array of 'count' additional arguments, with AFI = IP:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multicast Address1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Hold Down Time1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multicast Address2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Hold Down Time2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+count is the number of Multicast Address and Hold Down Time pairs supplied, from 1 to 255. The address length depends on the current address family, and the number of pairs is subject to the 512-byte message length limitation.
Default: None.
Description: The NMR command is experimental and has not been tested in an implementation 🧪 Each multicast address and hold down time pair is called a non-membership report. The non-membership report tells the receiving router that the sending router has no descendent group members in the given group. Based on that, the receiving router can stop forwarding datagrams to the sending router for the particular multicast address(es) listed. The hold down time tells you, in seconds, how long the NMR is valid ⏳
It is an error for count to equal 0 🚫
The only other commands allowed in a message with NMR commands are the AFI, flags0, and NULL commands. No relevant flags for the flags0 command are defined right now, but that may change in the future 👀
3.10 Non Membership Report Cancel (NMR Cancel) Command 🌸
Format of the NMR Cancel command, where count is the number of addresses:
Format: 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| 10 | | count |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
Array of 'count' additional arguments, with AFI = IP:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multicast Address1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multicast Address2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+count is the number of Multicast Addresses supplied, from 1 to 255. The address length depends on the current address family, and the number of addresses is subject to the 512-byte message length limitation.
Default: None.
Description: The NMR Cancel command is experimental and has not been tested in an implementation 🧪 For each multicast address listed, any previous corresponding non-membership reports get canceled. If there's no corresponding non-membership report for a given multicast address, the Cancel command should be ignored for that multicast address 🤷♀️
It is an error for count to equal 0 🚫
The only other commands allowed in a message with NMR Cancel commands are the AFI, flags0, and NULL commands. No relevant flags for the flags0 command are defined right now, but that may change in the future 💜
3.12 Examples (with bytes in '{}'), not including the message header 🎀
3.12.1 Supplying a single route to the IP address 128.2.251.231 with a metric of 2, an infinity of 16, a subnetmask of 255.255.255.0 🍓
Subtype 1,
AFI 2, Metric 2, Infinity 16, Subnet Mask 255.255.255.0
{2} {2} {4} {2} {6} {16} {3} {1} {255} {255} {255} {0}
DA Count=1 [128.2.251.231]
{7} {1} {128} {2} {251} {231}3.12.2 Supplying a route to the IP addresses 128.2.251.231 and 128.2.236.2 with a metric of 2, an infinity of 16, a subnetmask of 255.255.255.0 👑
Subtype 1,
AFI 2, Metric 2, Infinity 16, Subnet Mask 255.255.255.0
{2} {2} {4} {2} {6} {16} {3} {1} 255} {255} {255} {0}
DA Count=2 [128.2.251.231] [128.2.236.2]
{7} {1} {128} {2} {251} {231} {128} {2} {236} {2}3.12.3 Request for all routes to IP destinations 🧚
Subtype 2, AFI 2, RDA Count = 0
{2} {2} {8} {0}3.12.4 Non Membership Report for groups 224.2.3.1 and 224.5.4.6 with a hold down time of 20 seconds, and group 224.7.8.5 with a hold down time of 40 seconds 💅
Subtype 3,
AFI 2, NMR Count = 3 [224.2.3.1, 20]
{2} {2} {10} {3} {224} {2} {3} {1} {0} {0} {0} {20}
[224.5.4.6, 20] [224.7.8.5, 40]
{224} {5} {4} {6} {0} {0} {0} {20} {224} {7} {8} {5} {0} {0} {0} {40}3.13 Summary of Commands 📋
Here's the whole cheat sheet of which commands can ride together in one message 🦋
Value Name Other commands allowed in same message
----- ---- ---------------------------------------
0 Null Null, AFI, Subnetmask, Metric, Flags0,
Infinity, DA, RDA, NMR, NMR-cancel
2 AFI Null, AFI, Subnetmask, Metric, Flags0,
Infinity, DA, RDA, NMR, NMR-cancel
3 Subnetmask Null, AFI, Subnetmask, Metric, Flags0,
Infinity, DA, RDA
4 Metric Null, AFI, Subnetmask, Metric, Flags0,
Infinity, DA
5 Flags0 Null, AFI, Subnetmask, Metric, Flags0,
Infinity, DA
6 Infinity Null, AFI, Subnetmask, Metric, Flags0,
Infinity, DA
7 DA Null, AFI, Subnetmask, Metric, Flags0,
Infinity, DA
8 RDA Null, AFI, Subnetmask, Flags0, RDA
9 NMR Null, AFI, Flags0, NMR
10 NMR-cancel Null, AFI, Flags0, NMR-cancel4. Tunnels 🎀
okay so a tunnel is how routers send datagrams to each other when the gateways in between don't do multicast routing 🦋 it's basically a virtual network between two routers. like, a router at Stanford and a router at BBN could be linked with a tunnel so multicast datagrams can cross the Internet 🌐 ngl, the authors call tunnels a "transitional hack," and honestly? iconic honesty 💅
Tunneling uses a weakly encapsulated normal multicast datagram. The weak encapsulation is a special two element IP loose source route [5]. 🧚 This is better than "strong" encapsulation (prepending a whole new IP header) because the tunnel end-points don't need to know each other's maximum reassembly buffer size. It also keeps the originator's time-to-live value and any other IP options working correctly ✨
A tunnel has a local end-point, a remote end-point, a metric, and a threshold. The routers at each end only need to agree on the local and remote end-points. See section 8 for how tunnels get configured 🍓 Since the number of intermediate gateways between the end-points is unknown, more research is needed to figure out good metrics and thresholds 🤔
To send a datagram on a tunnel, the following happens:
- A null IP option is inserted into the datagram. This gives the loose source route IP option preferred alignment 🫶
- A two element loose source route IP option is inserted into the datagram.
- The source route pointer is set to point to the second element in the source route.
- The first element in the source route is replaced with the address of the originating host (the original IP source address).
- The second element in the source route is replaced with the multicast destination address given by the originating host (the original IP destination address).
- The IP source address is replaced with the address of the router's appropriate outgoing physical interface (the local tunnel end-point).
- The IP destination address is replaced with an address of the remote router (the remote tunnel end-point).
- The datagram is transmitted to the remote router using non-multicast routing algorithms.
Intermediate, non-multicast gateways route the tunneled datagram to the remote tunnel end-point 🚀 Because the IP source address was swapped for the local tunnel end-point, ICMP error messages go back to the originating multicast router 💜 This is the desired behavior! A host that sends a multicast datagram, which a multicast router decides to tunnel, should not be aware of the tunnel at all. If the source address weren't changed, any ICMP errors would go straight to the originating host, and that would be a whole mess 🙈
When the remote tunnel end-point receives the tunneled datagram, the following happens:
- The IP source address is replaced with the first element in the loose source route.
- The IP destination address is replaced with the second element in the loose source route.
- The null option and the loose source route option are removed from the datagram. This is needed because a host should not be able to tell that it received a datagram that went through a tunnel 🥹
Because no specific network is associated with a tunnel, there are no local group memberships to track for it 🌸 The only neighbor on a tunnel can be the remote end-point. Routing messages should be exchanged through tunnels, but a route is not created for the tunnel itself. The routing messages should be sent as unicast datagrams directly to the remote tunnel end-point, and they should not use an IP loose source route 💅
Justification for using the loose source route and record option for tunneling
the authors were honestly considering making their own IP option for tunneling, but they were worried that intermediate gateways don't transparently pass along IP options they don't recognize. datagrams using a brand new option wouldn't make it across the Internet 😭 it would be better if they could create a new IP option, but it won't work right now. remember, this is a transition design so they can experiment in the current environment 🧪
The tunneled packet containing the LSRR option has these features:
Field Value
----- --------------------
src address = src gateway address
dst address = dst gateway address
LSRR pointer = points to LSRR address 2
LSRR address 1 = src host
LSRR address 2 = multicast destinationTwo questions came up about using the LSRR option for tunnels: "Can intermediate gateways ignore the option?" and "Can the destination gateway properly detect that the LSRR is used for a tunnel?" 🤔
Okay so when an intermediate gateway gets a datagram, it looks at the destination address. For a tunneled datagram, the destination address won't match any address of the receiving gateway. That means the LSRR option doesn't get examined, and the intermediate gateway forwards the datagram to its next hop for the destination address. Easy peasy 🦋
When the destination gateway gets a datagram, it notices the destination address matches one of its own addresses. It then looks at the next LSRR option address, since the source route isn't exhausted yet. That address is a multicast address. Hosts are forbidden from putting multicast addresses into source routes, so the gateway can infer that the LSRR is for tunneling 🧠 The weakness here is that the multicast address in the LSRR might have some other meaning. No other meaning is currently defined, though 🤷♀️
If a tunneled datagram is accidentally addressed to a destination gateway that doesn't support multicasting, that gateway tries to find a route to the multicast address. This fails, and an ICMP destination unreachable error message is sent to the tunneled datagram's source. Since the source address in the tunneled datagram was adjusted to be the address of the source multicast gateway, the ICMP errors won't go to the originating host, which has no idea tunnels exist 🫣
5. Routing Algorithm 🌈
This section gives a terse description of the distance-vector routing algorithm. See [1] for more information 📚
While DVMRP can express routes to individual hosts, the forwarding and routing algorithms only support network and subnetwork routing 🙅♀️
In the discussion below, the term "virtual interface" refers to a physical interface or a tunnel local end-point. A physical interface is a network interface, like an Ethernet card 🔌 A route to a destination goes through a virtual interface. The term "virtual network" refers to a physical network or a tunnel, with the qualification that routes only reference physical networks 💜
The TRPB algorithm forwards multicast datagrams by computing the shortest (reverse) path tree from the source (physical) network to all possible recipients of the datagram 🌳 Each multicast router has to figure out its place in the tree, relative to the particular source. Then it determines which of its virtual interfaces are in the shortest path tree. The datagram is forwarded out those virtual interfaces. Excluding virtual interfaces that aren't in the shortest path tree is called "pruning" ✂️
Consider a virtual network. Using Deering's terminology [3], a router is called the "parent" of the virtual network if it's responsible for forwarding datagrams onto that virtual network through its connecting virtual interface. The virtual network can also be considered a "child" virtual network of the router. Using the child information, routers can do Reverse Path Broadcasting (RPB) 👑
Unnecessary datagrams may still be sent onto some networks, because there might not be any recipients for them on those networks 😬 There are two kinds of recipients: hosts that are members of a particular multicast group, and multicast routers. If no multicast routers on a virtual network consider that virtual network uptree to a given source, then that virtual network is a "leaf" network. If a network is a leaf for a given source, and there are no members of a particular group on it, then there are no recipients for datagrams from the source to the group on that network. That network's parent router can skip sending those datagrams on that network, or "truncate" the shortest path tree. The algorithm that tracks and uses this information is the Truncated Reverse Path Broadcasting (TRPB) algorithm ✨
Figuring out which virtual networks are leaves is not simple 🥴 If any neighboring router considers a given virtual network in the path to a given destination, then the virtual network is not a leaf. Otherwise, it is a leaf. This is a voting function. If a route, with a metric poisoned by split horizon processing, is sent by some router, then that router uses that virtual network as the uptree path for that route (i.e. that router votes that the virtual network is not a leaf relative to the route's destination). Since the number of routers on a virtual network is dynamic, and since routers don't keep all received routing updates, a heuristic is needed to decide when a network is a leaf. DVMRP samples the routing updates on a virtual interface while a hold down timer is running, for a time period of LEAF_TIMEOUT seconds. There is one hold down timer per virtual interface. If a route is received with a metric poisoned by split horizon processing while the hold down timer is running, or at any other time, then the appropriate virtual interface for that route is "spoiled" (it is not a leaf). For every route, any virtual interface that wasn't spoiled by the time the hold down timer expires is considered a leaf 🦋
For a description of an even better forwarding algorithm, the Reverse Path Multicasting algorithm, see [3] 🚀
A route entry should have the following in it:
- Destination address (a source of multicast datagrams) *
- Subnet mask of the destination address *
- Next-hop router to the destination address
- Virtual interface to the next-hop router *
- List of child virtual interfaces *
- List of leaf virtual interfaces *
- A dominant router address for each virtual interface
- A subordinate router address for each virtual interface
- Timer
- Set of flags that indicate the state of the entry
- Metric
- InfinityThe lines marked with '*' are fields that the forwarding algorithm uses directly 💖
The lists of child and leaf interfaces can be implemented as bitmaps 🫶
5.1. Sending Routing Messages 📨
okay so DVMRP routing messages do three jobs 💅: they periodically dump ALL the routing info, they gratuitously share routes that just changed, or they answer a request for some or all routes 🦋
Routing messages sent to physical interfaces should have an IP TTL of 1. 🎀
A bunch of timeouts and rates keep the routing and forwarding algorithms in check. Check section 6 for the actual values 🧚
Here are the rules for when to send routing messages 👑
- Every FULL_UPDATE_RATE seconds a router should send out DVMRP messages with all of its routing information to all of its virtual interfaces. To stop routers from syncing up when they send updates, a real-time timer must be used 🫶
- Whenever a route changes, a routing update should go out for that route. There has to be some delay between triggered updates so the network doesn't get flooded 😭 intervals of TRIGGERED_UPDATE_RATE seconds is suggested.
- A request for all routes should be sent on all virtual interfaces when an DVMRP router is restarted 🌸
- If possible, when a DVMRP router is about to terminate execution, it should send out DVMRP messages with metrics equal to infinity for all of its routes, on all virtual interfaces 💀
When routers are connected through networks that support multicasting, the messages should be multicast to address 224.0.0.4. So routers must listen to multicast address 224.0.0.4 on every physical interface that supports multicasting 🦋 If multicasting isn't supported, broadcasting can be used. And like we already mentioned, routing updates to tunnels should be sent as unicast datagrams to the remote end-point of the tunnel 💜
When you're sending routing messages (except in response to a specific route request, which is an RDA command with a non-zero count), poisoned split horizon processing must be done. This means that for a route that uses network X, routing updates sent to network X must include that route with the metric equal to the infinity, and should include the appropriate flag set in a FLAGS0 command 🔥
Poisoned split horizon is one way to make routing loops less likely 🌈 Another method, which RIP doesn't have, is picking a better infinity for a route ✨ For routes spread across a small but well connected network, an infinity smaller than 16 might be better. The smaller the infinity, the less time a counting-to-infinity event takes. But when you're traversing a wide internet, an infinity of 16 might be too small. The infinity can be increased, at the cost of a longer counting-to-infinity event 🍓
Now the multicast thresholds, which are so cool 🧚 The idea is you use "thresholds" to restrict which multicast datagrams exit a network. Multicast routers on the edge of a subnetted network or autonomous system may require a datagram to have a large TTL to exit a network. This keeps most multicast datagrams inside the network, which cuts down external traffic 🫧 An application that wants to multicast outside its network would need to give its datagrams at least a TTL equal to the sum of the threshold and the distance to the edge of the network (assuming TTL is used as a hop count within the network). A configuration option should allow specifying the threshold for both physical interfaces and tunnels ⭐
When a router starts up, it must send out a request for all routes on each of its virtual interfaces. The request is a message with an RDA command in it, and that command has a count equal to 0 🎀
5.2. Receiving Routing Messages 📥
A router must know which virtual interface a routing message arrived on 👀 Because the routing message may be addressed to the all-multicast-routers IP address, and because of tunnels, the incoming interface can not be identified just by looking at the message's IP destination address 🙈
For each route in a routing message, the following must occur. Here's the exact logic, so read it like it's a recipe 💅
IF a metric was given for the route:
THEN add in the metric of the virtual interface that the message
arrived on.
Lookup the route's destination address in the routing tables.
IF the route doesn't exist in the tables:
THEN try to find a route to the same network in the routing
tables.
IF that route exists in the tables:
THEN IF this route came from the same router as the router
that the found route came from:
THEN CONTINUE with next route.
IF route doesn't have a metric of infinity:
THEN add the route to the routing tables.
CONTINUE with next route.
IF this route came from the same router as the router that the found
route came from:
THEN clear the route timer.
IF a metric was received, and it is different than the found
route's metric:
THEN change the found route to use the new metric and
infinity.
IF the metric is equal to the infinity:
THEN set the route timer to the
EXPIRATION_TIMEOUT.
CONTINUE with next route.
IF the received infinity does not equal the found route's
infinity:
THEN change the found route's infinity to be the received
infinity.
change the found route's metric to be the minimum of
the received infinity and the found route's metric.
ELSE IF a metric was received, and (it is less than the found
route's metric or (the route timer is at least halfway to the
EXPIRATION_TIMEOUT and the found route's metric equals the
received metric, and the metric is less than the received
infinity)):
THEN change the routing tables to use the received route.
clear the route timer.
CONTINUE with next route.5.3. Neighbors 🫂
A list should be kept of the neighboring multicast routers on every attached network 📋 That info can be derived from the DVMRP routing messages that get received. A neighbor that hasn't been heard from in NEIGHBOR_TIMEOUT seconds should be considered to be down 💔
5.4. Local Group Memberships 👯♀️
As required by [2], a multicast router must keep track of group memberships on the multicast-capable networks attached to it. Every QUERY_RATE seconds, an IGMP membership request should be sent to the All Hosts multicast address (224.0.0.1) on each network, by a designated router on that network 🧚 The IGMP membership request will make hosts respond with IGMP membership reports after a small delay. Hosts will send the report for a group to that group's multicast address 🎀
The membership requests should have an IP TTL of 1 🌈
The routers on a network elect (or "designate") a single router to do the queries. The designated router is the router with the lowest IP address on that network. When it starts up, a router considers itself the designated router until it learns (presumably through routing messages) of a router with a lower address 👑 To find out about the group members on a network at startup, a router should multicast a number of membership requests, separated by a small delay. We suggest sending three requests separated by four seconds ⏰
The multicast router must receive all datagrams sent to all multicast addresses 🦋 When it gets an IGMP membership report for a group from an interface, it must either record that the group exists on the interface along with the time, or update the time if the group is already recorded ✨ Recorded group memberships must be timed-out. If a group member report isn't received for a recorded group after MEMBERSHIP_TIMEOUT seconds, the recorded group should be deleted 💅
6. Forwarding Algorithm ✨
okay so this section is all about how a router decides what to do with a multicast datagram that shows up on a physical interface or a tunnel 🧚. the state it has to keep is part of the deal too 💅
bestie, imagine flooding everything. a datagram comes in on one virtual interface and gets copied out every other virtual interface. with redundant paths all over the internet, you'd get duplicates everywhere 😭 that's the chaos this algorithm prevents. it uses the child and leaf info from the routing algorithm to prune the branches of the tree to every destination. main character pruning energy 🌿
the route entries track a couple of things for each virtual interface:
- a dominant router address 👑: the router that has a route with a lower metric (not infinity) to the destination on that virtual interface. the next-hop virtual interface doesn't get one.
- a subordinate router address 🫶: the router that considers this router its parent on the virtual network. so a leaf network never has one set.
here's how the child and leaf lists get manipulated 👇
Upon router startup:
Create a route entry for each virtual interface, with:
- all other virtual interfaces in its child list,
- an empty leaf list,
- no dominant router addresses, and
- no subordinate router addresses.
Start a hold down timer for each virtual interface, with
a value of LEAF_TIMEOUT.
Upon receiving a new route:
Create the route entry, with:
- all virtual interfaces, other than the one on which the
new route was received, in its child list,
- empty leaf list,
- no dominant router addresses, and
- no subordinate router addresses.
Start the hold down timer for all virtual interfaces, other
than the one on which the new route was received, with a
value of LEAF_TIMEOUT.
Upon receiving a route on virtual interface V from neighbor N with a
lower metric than the one in the routing table (or the same metric as
the one in the routing table, if N's address is less than my address
for V), for that route:
If V is in the child list, delete V from the child list.
If there is no dominant router for V and if V is not (now) the
next-hop virtual interface, record N as the dominant router.
Upon receiving a route on virtual interface V from neighbor N with a
larger metric than the one in the routing table (or the same metric
as the one in the routing table, if N's address is greater than my
address for V), for that route:
If N is the dominant router for V, delete N as the dominant router
and add V to the child list.
Upon receiving a route from neighbor N on virtual interface V with a
metric equal to infinity (the split horizon flag should also be set),
for that route:
If V is in the leaf list, delete V from the leaf list.
If there is no subordinate router for V, record N as the
subordinate router.
Upon receiving a route from neighbor N on virtual interface V with a
metric other than infinity (and no split horizon flag), for that
route:
If N is the subordinate router for V, delete N as the subordinate
router and start the hold down timer for V.
Upon timer expiration for a virtual interface (V), for each route:
If there is no subordinate router for V, add V to the leaf list.
Upon failure of neighbor N on virtual interface V, for each route:
If N is the dominant router for V, delete N as the dominant router
and add V to the child list.
If N is the subordinate router for V, delete N as the subordinate
router and start the hold down timer for V.and the actual forwarding decision is this flow 💖
The forwarding algorithm is:
IF the IP TTL is less than 2:
THEN CONTINUE with next datagram.
find the route to the source of the IP datagram.
IF no route exists:
THEN CONTINUE with next datagram.
IF the datagram was not received on the next-hop virtual interface
for the route:
THEN CONTINUE with next datagram.
IF the datagram is tunneled:
THEN replace the datagram's source address with the first address
in the IP loose source route.
replace the datagram's destination address with the second
address in the IP loose source route.
delete the loose source route and the null option from the
datagram and adjust the IP header length fields to reflect
the deletion.
If the datagram destination is group 224.0.0.0 or group 224.0.0.1:
THEN CONTINUE with next datagram.
FOR each virtual interface V
DO IF V is in the child list for the source of the datagram:
THEN IF V is not in the leaf list for the source
OR there are members of the destination group on V:
THEN IF the IP TTL is greater then V's threshold:
THEN subtract 1 from the IP TTL
forward the datagram out Vthe big picture is that a datagram with a TTL under 2 gets dropped, and so does one with no route to its source or one that didn't arrive on the next-hop interface for that route. tunneled datagrams get their addresses swapped back using the loose source route, and group 224.0.0.0 and 224.0.0.1 are skipped entirely. then it only forwards out the interfaces that are children of the source, and leaves are only included if they have members of the destination group. the TTL has to be above that virtual interface's threshold too 🎀
7. Time Values
okay this section is basically the cheat sheet of every rate and timeout, what they mean, and their values. everything is in seconds ⏰
how dynamic the routing environment is changes these rates. a lower rate means you adapt faster to changes, but you waste more bandwidth doing it 🦋
FULL_UPDATE_RATE = 60: how often routing messages with complete routing tables get sent 📦TRIGGERED_UPDATE_RATE = 5: how often triggered routing messages are allowed to go out ⚡
raising these next rates and timeouts can make packets get forwarded to a virtual interface when they don't need to be 💀
QUERY_RATE = 120: how often local group membership gets queried 🔍MEMBERSHIP_TIMEOUT = 2 * QUERY_RATE + 20: how long a local group membership stays valid without being confirmed 🕰️LEAF_TIMEOUT = 2 * FULL_UPDATE_RATE + 5: how long the hold down timer lasts for a virtual interface 🌸
then increasing these timeouts makes the routing algorithm more stable, but it reacts more slowly to changes 🐢
NEIGHBOR_TIMEOUT = 4 * FULL_UPDATE_RATE: how long a neighbor is considered up without confirmation. this one matters for timing out routes and for setting the children and leaf flags 🫧EXPIRATION_TIMEOUT = 2 * FULL_UPDATE_RATE: how long a route is considered valid without confirmation. once this expires, packets stop being forwarded on that route, and routing updates treat it as having a metric of infinity 🚫GARBAGE_TIMEOUT = 4 * FULL_UPDATE_RATE: how long a route exists without confirmation. once this expires, routing updates stop including anything about the route, and the route gets deleted 🗑️
8. Configuration options
a router needs to be configured with the following info, no cap 📝
- tunnel descriptions 🚇: local end-point, remote end-point, metric, and threshold. if there's no threshold, the metric should be used as the default threshold.
- physical interface settings 🔌: metric, infinity, threshold, and subnetwork mask. same deal, if there's no threshold, the metric should be used as the default threshold.
9. Conclusion
so this memo covered DVMRP, which is an extensible distance-vector-style routing protocol, plus the TRPB routing algorithm 🎀 an implementation of these ideas was done and was being tested 🧪
the extra features in DVMRP compared to RIP make it more flexible, but the processing gets more complicated 🤯 and it still has the downsides of being a distance-vector algorithm. link-state algorithms keep much of the state info that DVMRP has to maintain beyond what RIP needs, so the conclusion is that a multicast link-state routing protocol should be developed 🌈
the TRPB algorithm can send datagrams that nobody needed 😭 the Reverse Path Multicasting algorithm (RPM) [3] might be the better choice. the NMR and NMR-cancel DVMRP messages were designed to support RPM. more research is needed here 🔬
10. Acknowledgements
big thanks to Robb Foster, Alan Dahlbom, Ross Callon, and the IETF Host Working Group for their ideas 🫶💜
11. Bibliography
[1] Hedrick, C., "Routing Information Protocol", RFC 1058, Rutgers
University, June 1988.
[2] Deering, S., "Host Extensions for IP Multicasting", RFC 1054,
Stanford University, May 1988.
[3] Deering, S., "Multicast Routing in Internetworks and Extended
LANs", SIGCOMM Summer 1988 Proceedings, August 1988.
[4] Callon, R., "A Comparison of 'Link State' and 'Distance
Vector' Routing Algorithms", DEC, November 1987.
[5] Postel, J., "Internet Protocol", RFC 791, USC/Information
Sciences Institute, September 1981.
[6] Mills, D., "Toward an Internet Standard Scheme for
Subnetting", RFC 940, University of Delaware, April 1985.📦 where this page comes from
- ietf: rfc1075 1988-11
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms