RFC 2189

Core Based Trees (CBT version 2) Multicast Routing -- Protocol Specification --

📅 published September 1997, from ietf

RFC 2189: Core Based Trees (CBT version 2) Multicast Routing, Protocol Specification 🎀✨

Okay bestie, this is Part 1 of 5 of RFC 2189, so hold tight, more is coming 💅

This one is by A. Ballardie (Consultant), dated September 1997, and it's an Experimental doc 🧪 It's also a Network Working Group document. It doesn't obsolete or update anything.

Status of This Memo 🌸

Okay so this memo defines an Experimental Protocol for the Internet community, and it is NOT an Internet standard of any kind 🙈 The authors are asking for discussion and suggestions for improvement, and distribution of this memo is unlimited 💖

Abstract 🦋

This doc describes the Core Based Tree (CBT version 2) network layer multicast routing protocol. CBT builds a shared multicast distribution tree per group, and it's suited to both inter- and intra-domain multicast routing. It's giving versatile 👑

CBT can use its own separate multicast routing table, or it can borrow the one from the underlying unicast routing to set up paths between senders and receivers. The CBT architecture is described in [1].

This doc is moving through the IDMR working group of the IETF. The CBT related documents are [1, 5, 6]. For all the IDMR stuff, check http://www.cs.ucl.ac.uk/ietf/idmr 🧚

Table of Contents 📋

  1. Changes Since Previous version............................. 2
  2. Introduction & Terminology................................. 3
  3. CBT Functional Overview.................................... 3
  4. CBT Protocol Specificiation Details........................ 6
     4.1 CBT HELLO Protocol..................................... 6
         4.1.1 Sending HELLOs................................... 7
         4.1.2 Receiving HELLOs................................. 7
     4.2 JOIN_REQUEST Processing................................ 8
         4.2.1 Sending JOIN_REQUESTs............................ 8
         4.2.2 Receiving JOIN_REQUESTs.......................... 8
     4.3 JOIN_ACK Processing.................................... 9
         4.3.1 Sending JOIN_ACKs................................ 9
         4.3.2 Receiving JOIN_ACKs.............................. 9

     4.4 QUIT_NOTIFICATION Processing........................... 10
         4.4.1 Sending QUIT_NOTIFICATIONs....................... 10
         4.4.2 Receiving QUIT_NOTIFICATIONs..................... 10
     4.5 CBT ECHO_REQUEST Processing............................ 11
         4.5.1 Sending ECHO_REQUESTs............................ 11
         4.5.2 Receiving ECHO_REQUESTs.......................... 12
     4.6 ECHO_REPLY Processing.................................. 12
         4.6.1 Sending ECHO_REPLYs.............................. 12
         4.6.2 Receiving ECHO_REPLYs............................ 12
     4.7 FLUSH_TREE Processing.................................. 13
         4.7.1 Sending FLUSH_TREE Messages...................... 13
         4.7.2 Receiving FLUSH_TREE Messages.................... 13
  5. Non-Member Sending......................................... 13
  6. Timers and Default Values.................................. 13
  7. CBT Packet Formats and Message Types....................... 14
     7.1 CBT Common Control Packet Header....................... 14
     7.2 HELLO Packet Format.................................... 15
     7.3 JOIN_REQUEST Packet Format............................. 16
     7.4 JOIN_ACK Packet Format................................. 16
     7.5 QUIT_NOTIFICATION Packet Format........................ 17
     7.6 ECHO_REQUEST Packet Format............................. 18
     7.7 ECHO_REPLY Packet Format............................... 18
     7.8 FLUSH_TREE Packet Format............................... 19
  8. Core Router Discovery...................................... 19
     8.1  "Bootstrap" Mechanism Overview........................ 20
     8.2  Bootstrap Message Format.............................. 21
     8.3  Candidate Core Advertisement Message Format........... 21
  9. Interoperability Issues.................................... 21
  10.  Security Considerations.................................. 21
  Acknowledgements.............................................. 22
  References.................................................... 22
  Author Information............................................ 23

1. Changes from CBT version 1 🔥

Okay, so this version of the CBT protocol spec is a big glow-up from the previous one ✨ That's why it's officially version 2 💅

CBT version 2 is not, and was not, meant to be backwards compatible with version 1 🙈 The authors don't expect this to cause a ton of compatibility drama, because they don't think CBT is widely deployed at this stage. But any future versions of CBT can be expected to be backwards compatible with this one 🫶

The biggest changes in version 2 compared to version 1 are:

  • new LAN mechanisms, including a HELLO protocol getting folded in 🎀
  • new simplified packet formats, with a common CBT control packet header defined 🧚
  • each group shared tree has only one active core router 👑

This spec revision is a complete re-write of the previous revision. No cap, a full rebrand 💖

2. Introduction & Terminology 🦋

So in CBT, a "core router" (or just "core") is a router that acts as a "meeting point" between a sender and group receivers 🌸 Some contexts call this the "rendezvous point (RP)" instead, and that's cited as [2]. A core router doesn't have to be configured to know it's a core router, which is lowkey iconic ✨

A router that's part of a CBT distribution tree is called an "on-tree" router 🌳 An on-tree router keeps active state for the group 💜

We refer to any interface that supports multicast transmission as a broadcast interface 📡

Now the directions 🧭 An "upstream" interface (or router) is one that sits on the path towards the group's core router, looking at it from this interface (or router). A "downstream" interface (or router) is one that sits on the path away from the group's core router, again from this interface's point of view 💅

Other terminology gets introduced in context as we go through the text 🎀

3. CBT Functional Overview ✨

Okay bestie, so the CBT protocol is OBSESSED with building and maintaining one shared multicast distribution tree 🌳 that only stretches across the networks and links where interested receivers actually live. No spreading it everywhere for no reason, it's giving efficiency 💅

Here's how it starts. A host says "I want in!" by sending an IGMP host membership report [3] out across its attached link 🎀. When a local CBT aware router hears that, it kicks off the tree joining process (unless it already did 👀) by generating a JOIN_REQUEST message. That message goes to the next hop on the path toward the group's core router. (How the router figures out which core to join? That's in section 8 🧚.) This join message must be explicitly acknowledged with a JOIN_ACK, either by the core router itself or by another router on the path between the sender and the core that has already successfully joined the tree 🫶.

The join message sets up transient join state in every router it passes through 🦋. That state is the tuple <group, incoming interface, outgoing interface>. The "incoming interface" and "outgoing interface" can be "previous hop" and "next hop" instead, if the links don't support multicast transmission. "Previous hop" comes from the IP source address of the incoming control packet, and "next hop" gets pulled from the routing table, specifically the next hop toward the specified core address 🗺️. This transient state eventually times out unless a JOIN_ACK from upstream "confirms" it ⏳. The JOIN_ACK travels back along the reverse path of the join message, which works because of that transient join state. Once the acknowledgement reaches the router that started the join, the new receiver can finally get traffic sent to the group 🥹✨

Loops can't form in a CBT tree, and the reasons are lowkey genius 🧠. First, there's only one active core per group. Second, the tree building and maintenance scenarios that could create loops are avoided. For example, if a router's upstream neighbour becomes unreachable, that router immediately "flushes" all of its downstream branches, so they can each rejoin individually if they need to 💧. Transient unicast loops aren't a threat either, because a new join message that loops back on itself never gets acknowledged, so it just times out 🙅‍♀️.

The state a router creates when it sends or receives a JOIN_ACK is bi-directional 🔁. Data can flow either way along a tree "branch". This state is group specific, and it holds the group address plus a list of local interfaces over which join messages for that group were previously acknowledged. There's no "incoming" or "outgoing" interface concept here, but the router still needs to tell the upstream interface apart from the downstream ones. In CBT, those are called the "parent" and "child" interfaces 👑. A router is not considered "on-tree" until it has received a JOIN_ACK for a JOIN_REQUEST it previously sent 🌸.

Now the multicast forwarding cache 💜. On link types that don't support native multicast transmission, an on-tree router must store the address of a parent and of any children. On links that do support multicast, though, the parent and child information is represented with local interface addresses (or similar identifying info, like an interface "index") over which the parent or child can be reached 🔍.

Data from non-member senders gets encapsulated (IP-in-IP) by the first-hop router, then unicast to the group's core router 📦. Because of this, no group state is needed in the network between the first-hop router and the core. When the packet arrives at the core, the outer encapsulating header is removed, and the packet is disseminated over the group shared tree as described below 🎁.

When a multicast data packet arrives at a router, the router uses the group address as an index into the multicast forwarding cache 🔑. A copy of the incoming packet is forwarded over each interface (or to each address) listed in that entry, except the incoming interface 💌.

Every router in a CBT multicast tree except the core router is responsible for maintaining its upstream link, as long as it has interested downstream receivers, meaning its child interface list is not NULL 🥰. A child interface is one with a member host directly attached, or one with a downstream on-tree router attached. This "tree maintenance" happens because each downstream router periodically sends a CBT "keepalive" message (ECHO_REQUEST) to its upstream neighbour, which is its parent router on the tree 💓. One keepalive covers all entries that share the same parent, which helps scalability on links shared by lots of groups 📈. On multicast capable links, the keepalive is multicast to the "all-cbt-routers" group (IANA assigned as 224.0.0.15), and that has a suppressing effect on any other router for which that link is its parent link 🤫. If a parent link doesn't support multicast transmission, keepalives get unicast instead.

When a valid child interface receives a keepalive, it prompts a response (ECHO_REPLY), which is either unicast or multicast, depending on what's appropriate 📨. The ECHO_REPLY carries a list of the groups for which that interface is a child interface 📋.

It can't be assumed that all routers on a multi-access link have the same view of unicast routing 🙃. That's especially true when the multi-access link spans two or more unicast routing domains. This could lead to multiple upstream tree branches forming, which is an error condition, unless steps are taken to make sure all routers on the link agree on which router is upstream for a given group. So CBT routers on a multi-access link go through an explicit election mechanism that picks one router, the designated router (DR), as the link's upstream router for all groups 🗳️. The DR might not be the link's best next hop for a particular core router, so a join message can end up getting redirected back across the multi-access link. When that happens, the DR unicasts the redirected join message across the link to the best next hop, which prevents a looping scenario 🔄. This redirection only ever applies to join messages. It's suboptimal for join messages, sure, but they're generated infrequently, and multicast data never crosses a link more than once (either natively or encapsulated) 🙌.

Except in the exception case described above, all CBT control messages are multicast over multicast supporting links to the "all-cbt-routers" group, with IP TTL 1 📡. The IP source address of a CBT control message is the sending router's outgoing interface. The IP destination address is either the "all-cbt-routers" group address or a unicast address, depending on what's appropriate. On-tree routers pick up all the addressing info they need during tree setup 🧩.

If CBT runs over a tunnelled topology, a router sending a CBT control packet over a tunnel interface uses its local tunnel end point address as the packet's IP source address, and the remote tunnel end point address as the IP destination address 🚇.

4. Protocol Specification Details 📜

Details of the CBT protocol are presented in the context of a single router implementation 🖥️.

4.1. CBT HELLO Protocol 👋

The HELLO protocol elects a designated router (DR) on broadcast-type links 🏆. It's also used to elect a designated border router (BR) when a CBT domain interconnects with other domains (see [5]). Alternatively, the designated BR can be elected as a matter of local policy 📋.

A router shows that it's the link's DR by setting the DR-flag on that interface. Each of a router's broadcast interfaces has a DR flag associated with it 🚩. The flag can only be one of two values, TRUE or FALSE, and by default it's FALSE 🙅‍♀️.

A network manager can adjust a router's DR eligibility by optionally configuring a HELLO preference, which goes into the router's HELLO messages 🎛️. Valid configuration values run from 1 to 254 (decimal), with 1 meaning "most eligible" 🥇. If nothing is configured, a router uses the default HELLO preference of 255. The elected DR uses HELLO preference zero (0) in its HELLO advertisements, no matter what it was configured with, and it keeps using preference zero for as long as it's running 👑.

HELLO messages are multicast periodically to the all-cbt-routers group, 224.0.0.15, using IP TTL 1 ⏰. The advertisement period is [HELLO_INTERVAL] seconds.

HELLO messages have a suppressing effect on routers that would advertise a "lesser preference" in their own HELLO messages. A router resets its [HELLO_INTERVAL] if the received HELLO is "better" than its own 🤫. So in steady state, the HELLO protocol generates very little traffic overhead 🌿.

The DR election winner is the router advertising the lowest HELLO preference, or the lowest-addressed router if there's a tie 🏅.

Two or more routers on the same broadcast link advertising HELLO preference 0 should never happen 😳. But if it does, every zero-advertising router except the lowest-addressed one gives up its DR claim right away by unsetting the DR flag on the corresponding interface. The routers that gave up subsequently advertise their previously used preference value in their HELLO advertisements 🫠.

4.1.1. Sending HELLOs 📣

When a router starts up, it multicasts two HELLO messages over each of its broadcast interfaces in succession 🚀. The DR flag starts out unset (FALSE) on each broadcast interface. This avoids the situation where every router on a multi-access subnet thinks it's the DR, which would stop join-requests from being forwarded multiple times if they arrive during this startup period 🙅‍♀️. If no "better" HELLO message arrives within HOLDTIME seconds, the router takes on the DR role on the corresponding interface 👑.

A router sends a HELLO message whenever its [HELLO_INTERVAL] expires. Every time it sends one, it resets its hello timer ⏱️.

4.1.2. Receiving HELLOs 👂

A router does not respond to a HELLO message if the received HELLO is "better" than its own, or equally preferenced but lower addressed 🙈.

A router must respond to a HELLO message if the received one is lesser preferenced (or equally preferenced but higher addressed) than what this router would send over the same interface 💁‍♀️. The response goes out when an interval timer expires. That timer is set to somewhere between zero (0) and [HOLDTIME] seconds when the lesser preferenced HELLO message comes in ⏳💖.

4.2. JOIN_REQUEST Processing 🎀

A JOIN_REQUEST is the CBT control message used to register a member host's interest in joining the distribution tree for the group 🦋✨.

4.2.1. Sending JOIN_REQUESTs ✨

okay bestie, a JOIN_REQUEST can only ever be originated by a leaf router 🌸, i.e. a router with directly attached member hosts. this join message gets sent hop-by-hop towards the core router for the group (see section 8) 🦋. the originating router caches <group, NULL, upstream interface> for each join it originates, and that's called "transient join state" 💅. the absence of a "downstream interface" (NULL) tells you this router is the join message originator, so it's the one responsible for any retransmissions of this message if a response isn't received within [RTX_INTERVAL] 🫶. it's an error if no response comes in after [JOIN_TIMEOUT] seconds 😭. if that happens, the joining process may be re-invoked when the next IGMP host membership report comes in from a locally attached member host.

note that if the interface the JOIN_REQUEST is going out over supports multicast, the JOIN_REQUEST is multicast to the all-cbt-routers group, using IP TTL 1 🎀. if the link doesn't support multicast, the JOIN_REQUEST is unicast to the next hop on the unicast path to the group's core 🧚.

4.2.2. Receiving JOIN_REQUESTs 🌈

on broadcast links, JOIN_REQUESTs that are multicast may only be forwarded by the link's DR 👑. other routers attached to the link may still process the join (see below) 💜. JOIN_REQUESTs that are multicast over a point-to-point link are only processed by the router on the link that does not have a local interface matching the join's network layer (IP) source address. unicast JOIN_REQUESTs may only be processed by the router that has a local interface matching the join's network layer (IP) destination address.

now, forwarding. if the receiving router is not on-tree for the group, isn't the group's core router, and hasn't already forwarded a join for the same group, the join gets forwarded to the next hop on the path towards the core ✨. it's multicast or unicast depending on whether the outgoing interface supports multicast. the router caches <group, downstream interface, upstream interface> for the forwarded join. any later JOIN_REQUESTs for the same group get cached until this router has received a JOIN_ACK for the join it already sent, and then those cached joins can also be acknowledged 🍓.

if this transient join state isn't "confirmed" with a join acknowledgement (JOIN_ACK) from upstream, the state times out after [TRANSIENT_TIMEOUT] seconds ⭐.

if the receiving router is the group's core router, the join is "terminated" and acknowledged with a JOIN_ACK 👑. same deal if the router is on-tree and the JOIN_REQUEST arrives over an interface that isn't the group's upstream interface: the join gets acknowledged 🌸.

if a JOIN_REQUEST for the same group is scheduled to go out over the corresponding interface (basically, waiting for a timer to expire), that JOIN_REQUEST gets unscheduled 🙈.

and if this router has a cache-deletion-timer [CACHE_DEL_TIMER] running on the arrival interface for the group in a multicast join, the timer gets cancelled 💖.

4.3. JOIN_ACK Processing 🎀

a JOIN_ACK is how an interface gets added to a router's multicast forwarding cache 🦋. once it's in there, that interface becomes part of the group distribution tree 🌳.

4.3.1. Sending JOIN_ACKs ✨

the JOIN_ACK goes out over the same interface the corresponding JOIN_REQUEST came in on 💅. sending the acknowledgement makes the router add that interface to its child interface list in its forwarding cache for the group, if it isn't on there already 🫶.

a JOIN_ACK is multicast or unicast depending on whether the outgoing interface supports multicast transmission 🧚.

4.3.2. Receiving JOIN_ACKs 🌈

the group and arrival interface have to match a <group, ...., upstream interface> in the router's cached transient state. if there's no match, the JOIN_ACK gets discarded 😭. if there is a match, a CBT forwarding cache entry for the group gets created, with the "upstream interface" marked as the group's parent interface 👑.

if "downstream interface" in the cached transient state is NULL, the JOIN_ACK has reached the originator of the corresponding JOIN_REQUEST, so it isn't forwarded downstream 🌸. if "downstream interface" is non-NULL, a JOIN_ACK for the group gets sent over that "downstream interface" (multicast or unicast, accordingly) 🦋. that interface then gets installed in the child interface list of the group's forwarding cache entry 💜.

once the transient state has been confirmed by moving it into the forwarding cache, the transient state gets deleted 🍓.

4.4. QUIT_NOTIFICATION Processing 💅

a CBT tree gets "pruned" in the downstream-to-upstream direction whenever a CBT router's child interface list for a group becomes NULL 🥀.

4.4.1. Sending QUIT_NOTIFICATIONs ✨

a QUIT_NOTIFICATION gets sent to a router's parent router on the tree whenever the router's child interface list becomes NULL 🌸. if the link the quit is going over supports multicast transmission, the quit is unicast when the sending router is the link's DR; otherwise, it's multicast 🧚.

a QUIT_NOTIFICATION is not acknowledged. once it's sent, all information about the group it represents is deleted from the forwarding cache immediately 💀.

to help keep a child and parent router consistent, since a QUIT_NOTIFICATION could get lost, a total of [MAX_RTX] QUIT_NOTIFICATIONs are sent, each one HOLDTIME seconds after the previous one 🫶.

sending the first quit also triggers a FLUSH_TREE message going out over each downstream interface for the corresponding group 🔥.

4.4.2. Receiving QUIT_NOTIFICATIONs 🌈

the group reported in the QUIT_NOTIFICATION has to match a forwarding cache entry. if no match is found, the QUIT_NOTIFICATION is ignored and discarded 🙈. if there is a match and the arrival interface is a valid child interface in the group entry, what the router does next depends on whether the QUIT_NOTIFICATION was multicast or unicast 💖.

if the QUIT_NOTIFICATION was unicast, the corresponding child interface is deleted from the group's forwarding cache entry, and no further processing is needed 🦋.

if the QUIT_NOTIFICATION was multicast, and the arrival interface is a valid child interface for the specified group, the router sets a cache-deletion-timer [CACHE_DEL_TIMER] ⏳.

this is where it gets clever 🧠. this router might be a parent router for several downstream routers attached to the arrival link. so the [CACHE_DEL_TIMER] interval gives the routers that didn't send the QUIT_NOTIFICATION, but did receive it over their parent interface, a chance to make sure the parent router doesn't remove the link from its child interface list 👑. so when a router gets a multicast QUIT_NOTIFICATION over a parent interface, it schedules a JOIN_REQUEST for the group to go out at a random interval between 0 (zero) and HOLDTIME seconds 🎲. if a multicast JOIN_REQUEST shows up over the corresponding interface (the parent) for the same group before this router sends its own scheduled JOIN_REQUEST, it unschedules its own multicast JOIN_REQUEST 💅.

4.5. ECHO_REQUEST Processing 🦋

the ECHO_REQUEST message lets a child keep an eye on reachability to its parent router for a group (or a range of groups, if the parent router is the parent for multiple groups) 👀. group information isn't carried in ECHO_REQUEST messages 🌸.

4.5.1. Sending ECHO_REQUESTs ✨

whenever a router creates a forwarding cache entry because it got a JOIN_ACK, it starts periodically sending ECHO_REQUEST messages over its parent interface 🫶. the ECHO_REQUEST is multicast to the all-cbt-routers group over multicast-capable interfaces. the one exception is when the sending router is the DR on the interface the ECHO_REQUEST goes over, in which case it's unicast (and so is the corresponding ECHO_REPLY) 👑.

ECHO_REQUEST messages go out at [ECHO_INTERVAL] second intervals ⏰.

whenever an ECHO_REQUEST is sent, [ECHO_INTERVAL] gets reset 🔄.

if no response shows up, any groups present on the parent interface will eventually expire after [GROUP_EXPIRE_TIME] 💀. that results in a QUIT_NOTIFICATION going upstream, and a FLUSH_TREE message going downstream for each group whose parent interface was the upstream interface 😭.

4.5.2. Receiving ECHO_REQUESTs 🌈

if an ECHO_REQUEST arrives over any valid child interface, the receiving router schedules an ECHO_REPLY to go out over that same interface. the scheduled interval is between 0 (zero) and HOLDTIME seconds 🎲. this message is multicast to the all-cbt-routers group over multicast-capable interfaces, and unicast otherwise 🧚.

if a multicast ECHO_REQUEST arrives via any valid parent interface, the router resets its [ECHO_INTERVAL] timer for that upstream interface. that suppresses the router's own ECHO_REQUEST over that upstream interface 🙈.

4.6. ECHO_REPLY Processing 💖

ECHO_REPLY messages let a child monitor its parent's reachability, and they help keep the group state information consistent between the two 🫶.

4.6.1. Sending ECHO_REPLY messages ✨

an ECHO_REPLY message is sent in response to an ECHO_REQUEST, as long as the ECHO_REQUEST was received over one of this router's valid child interfaces 🌸. an ECHO_REPLY reports all groups for which that link is its child 💅.

ECHO_REPLY messages are unicast or multicast, as appropriate 🦋.

4.6.2. Receiving ECHO_REPLY messages 🌈

an ECHO_REPLY message must be received via a valid parent interface 👑.

for each group reported in an ECHO_REPLY, the downstream router tries to match that group with one in its forwarding cache whose parent interface is the arrival interface. every successful match gets "refreshed" ✨. but if a group hasn't been "refreshed" after [GROUP_EXPIRE_TIME] seconds, a QUIT_NOTIFICATION is sent upstream and a FLUSH_TREE message is sent downstream for that group 😭.

if this router has directly attached members for any of the flushed groups, then receiving an IGMP host membership report for any of those groups will prompt the router to rejoin the corresponding tree(s) 🔄.

4.7. FLUSH_TREE Processing 🔥

the FLUSH_TREE (flush) message is how a router tears down all of its downstream branches for a particular group 💥. when it's sent over multicast-capable interfaces, the flush message is multicast to the all-cbt-routers group, and unicast otherwise 🧚.

4.7.1. Sending FLUSH_TREE messages ✨

a FLUSH_TREE message is sent over each downstream (child) interface when a router has lost reachability with its parent router for the group (detected via ECHO_REQUEST and ECHO_REPLY messages) 💀. all group state gets removed from any interface a flush message is sent over 🧹. a flush can specify a single group, or all groups (INADDR_ANY) 🌍.

4.7.2. Receiving FLUSH_TREE messages 🌈

a FLUSH_TREE message must be received over the parent interface for the specified group. otherwise, the message is discarded 🙈.

the flush message must be forwarded over each child interface for the specified group 🦋.

once the flush message has been forwarded, all state for the group is removed from the router's forwarding cache 💅.

5. Non-Member Sending 🦋

okay so bestie, what if the sender isn't even in the group tree?? 👀 Totally allowed! 💅 The host just blasts out normal native multicast data, and a local router picks it up in promiscuous mode. That router must be CBT capable, btw 🙈 It's assumed the local CBT router already knows the relevant <core, group> mapping, so it wraps the packet up (IP-in-IP ✨) and unicasts it to the matching core router. When the core gets it, it unwraps the packet and spreads it over the group tree like we already talked about 🌸 iconic, honestly.

6. Timers and Default Values 💖

this section is basically the cheat sheet for every timer we've mentioned, plus the recommended defaults 📝 You're totally free to configure other values, but if you do, make sure they're consistent across all CBT routers on the same network. otherwise everyone's out of sync and it's chaos 💀

  • [HELLO_INTERVAL]: the interval between sending a HELLO message. Default: 60 seconds.
  • [HELLO_PREFERENCE]: Default: 255.
  • [HOLDTIME]: generic response interval. Default: 3 seconds.
  • [MAX_RTX]: default maximum number of retransmissions. Default 3.
  • [RTX_INTERVAL]: message retransmission time. Default: 5 seconds.
  • [JOIN_TIMEOUT]: raise exception due to tree join failure. Default: 3.5 times [RTX_INTERVAL].
  • [TRANSIENT_TIMEOUT]: delete (unconfirmed) transient state. Default: (1.5*RTX_INTERVAL) seconds.
  • [CACHE_DEL_TIMER]: remove child interface from forwarding cache. Default: (1.5*HOLDTIME) seconds.
  • [GROUP_EXPIRE_TIME]: time to send a QUIT_NOTIFICATION to our non-responding parent. Default: (1.5*ECHO_INTERVAL).
  • [ECHO_INTERVAL]: interval between sending ECHO_REQUEST to parent routers. Default: 60 seconds.
  • [EXPECTED_REPLY_TIME]: consider parent unreachable. Default: 70 seconds.

7. CBT Packet Formats and Message Types 🎀

okay the packet formats are where it gets really fun 🧚 CBT control packets ride inside IP, and IANA gave CBT IP protocol number 7 [4] 🔥

7.1. CBT Common Control Packet Header 💅

every CBT control message starts with the same fixed-length header, so that's the first thing to know 🌈

       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |  vers | type  |  addr len     |         checksum              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


                  Figure 1. CBT Common Control Packet Header

this spec is version 2 ✨ and here are the packet types you'll be seeing:

  • type 0: HELLO
  • type 1: JOIN_REQUEST
  • type 2: JOIN_ACK
  • type 3: QUIT_NOTIFICATION
  • type 4: ECHO_REQUEST
  • type 5: ECHO_REPLY
  • type 6: FLUSH_TREE
  • type 7: Bootstrap Message (optional)
  • type 8: Candidate Core Advertisement (optional)
  • Addr Length: address length in bytes of unicast or multicast addresses carried in the control packet.
  • Checksum: the 16-bit one's complement of the one's complement sum of the entire CBT control packet.

7.2. HELLO Packet Format 🦋

    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    CBT Control Packet Header                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Preference   |  option type  |  option len   |  option value |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                     Figure 2. HELLO Packet Format

HELLO Packet Field Definitions:

  • preference: sender's HELLO preference.
  • option type: the type of option present in the option value field. One option type is currently defined: option type 0 (zero) = BR_HELLO; option value 0 (zero); option length 0 (zero). This option type is used with HELLO messages sent by a border router (BR) as part of designated BR election (see [5]).
  • option len: length of the option value field in bytes.
  • option value: variable length field carrying the option value.

7.3. JOIN_REQUEST Packet Format 🌸

       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    CBT Control Packet Header                  |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                          group address                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                          target router                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                        originating router                     |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |  option type  |  option len   |        option value           |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                     Figure 3. JOIN_REQUEST Packet Format

JOIN_REQUEST Field Definitions

  • group address: multicast group address of the group being joined. For a "wildcard" join (see [5]), this field contains the value of INADDR_ANY.
  • target router: target (core) router for the group.
  • originating router: router that originated this JOIN_REQUEST.
  • option type, option len, option value: see HELLO packet format, section 7.2.

7.4. JOIN_ACK Packet Format 💜

JOIN_ACK Field Definitions

  • group address: multicast group address of the group being joined.
  • target router: router (DR) that originated the corresponding JOIN_REQUEST.
       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    CBT Control Packet Header                  |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                          group address                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                           target router                       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |  option type  |  option len   |         option value          |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                       Figure 4. JOIN_ACK Packet Format
  • option type, option len, option value: see HELLO packet format, section 7.2.

7.5. QUIT_NOTIFICATION Packet Format 🍓

       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    CBT Control Packet Header                  |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                          group address                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    originating child router                   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                  Figure 5. QUIT_NOTIFICATION Packet Format

QUIT_NOTIFICATION Field Definitions

  • group address: multicast group address of the group being joined.
  • originating child router: address of the router that originates the QUIT_NOTIFICATION.

7.6. ECHO_REQUEST Packet Format 🧚

       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    CBT Control Packet Header                  |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    originating child router                   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                     Figure 6. ECHO_REQUEST Packet Format

ECHO_REQUEST Field Definitions

  • originating child router: address of the router that originates the ECHO_REQUEST.

7.7. ECHO_REPLY Packet Format ⭐

       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    CBT Control Packet Header                  |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    originating parent router                  |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                       group address #1                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                       group address #2                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                           ......                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                       group address #n                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                      Figure 7. ECHO_REPLY Packet Format

ECHO_REPLY Field Definitions

  • oringinating parent router: address of the router originating this ECHO_REPLY.
  • group address: a list of multicast group addresses for which this router considers itself a parent router w.r.t. the link over which this message is sent.

7.8. FLUSH_TREE Packet Format 🌈

       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    CBT Control Packet Header                  |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         group address                         |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                           ......                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                       group address #n                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                      Figure 8. FLUSH_TREE Packet Format

FLUSH_TREE Field Definitions

  • group address(es): multicast group address(es) of the group(s) being "flushed".

8. Core Router Discovery 🗺️✨

okay so there are two options for CBTv2 core discovery 💅. the "bootstrap" mechanism (as it's currently specified with the PIM sparse mode protocol [2]) only works for intra-domain core discovery, but it gives you a "plug & play" vibe with minimal configuration 🎀. the downside is that it's way harder to shape the distribution tree, which means it's harder to make it optimal 🙈. also, for it to work, every CBT router in the domain has to implement the bootstrap mechanism. no cap, that's a lot to ask 💀.

the other option is to manually configure leaf routers with <core, group> mappings (leaf routers only! 🍃). this creates a bit of admin burden, because the mapping for a particular group has to be coordinated across all leaf routers so everything stays consistent 😭. so yeah, this method does not scale particularly well. BUT, it's likely that "better" trees will come out of it, and it's also the only option available right now for inter-domain core discovery 👑.

8.1. "Bootstrap" Mechanism Overview 🧚

it's unlikely that the bootstrap mechanism will get attached to a well-known network layer protocol like IGMP [3], even though that would make intra-domain deployment super ubiquitous 🌈. so each multicast routing protocol that needs the bootstrap mechanism has to implement it as part of the multicast routing protocol itself 🔥.

here's the quick summary of how the bootstrap mechanism works (the full details are in [7] 📚). it's assumed that all routers in the domain implement the "bootstrap" protocol, or at the very least forward bootstrap protocol messages 💜.

a subset of the domain's routers are set up as CBT candidate core routers ⭐. each candidate core router periodically (default every 60 secs) advertises itself to the domain's Bootstrap Router (BSR), using "Core Advertisement" messages 📣. the BSR itself gets elected dynamically from all (or participating) routers in the domain 🗳️. the elected BSR collects those "Core Advertisement" messages from the candidate core routers and periodically advertises a candidate core set (CC-set) to every other router in the domain, using traditional hop-by-hop unicast forwarding 🦋. the BSR uses "Bootstrap Messages" to advertise the CC-set. together, "Core Advertisements" and "Bootstrap Messages" make up the "bootstrap" protocol 🫶.

when a router gets an IGMP host membership report from one of its directly attached hosts, the local router runs a hash function on the reported group address 🔢. the result of that hash is used as an index into the CC-set 🎯. this is how local routers figure out which core to use for a particular group ✨.

ooh, and the hash function is specifically tailored so that a small number of consecutive groups always hash to the same core 🤌. bootstrap messages can also carry a "group mask", which can potentially limit a CC-set to a particular range of groups 🧱. this helps cut down on traffic concentration at the core 💖.

if a BSR detects that a particular core is unreachable (meaning it hasn't announced its availability within some period), it deletes that core from the CC-set it sends in its next bootstrap message 🗑️. this is how a local router finds out that a group's core is unreachable 😱. the router then has to re-hash for each affected group and join the new core, after removing the old state 🔄. the removal of the "old" state follows the sending of a QUIT_NOTIFICATION upstream, and a FLUSH_TREE message downstream 🌸.

8.2. Bootstrap Message Format 📦

     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
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |             CBT common control packet header                  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |      For full Bootstrap Message specification, see [7]        |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 9. Bootstrap Message Format 🎀

8.3. Candidate Core Advertisement Message Format 📣

     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
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |              CBT common control packet header                 |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |   For full Candidate Core Adv. Message specification, see [7] |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 10. Candidate Core Advertisement Message Format 🌈

9. Interoperability Issues 🤝

interop between CBT and DVMRP is specified in [5] 💕.

interop with other multicast protocols will be fully specified as the need arises 🔜.

10. Security Considerations 🔐

⚠️ security considerations are not addressed in this memo. 😭 bestie, this part is serious, so read carefully.

whilst multicast security is a topic of ongoing research, multicast applications (users) can still take advantage of security services like encryption and/or authentication 🔒, as long as the applications actually support those services 💅.

RFCs 1949 and 2093/2094 talk about different ways of distributing multicast key material 🗝️. that can result in network layer access control being provided to a multicast distribution tree 🛡️.

[9] gives a synopsis of multicast security threats and proposes some possible counter measures 🕵️.

beyond these, there's not much published work on multicast security 🥲.

Acknowledgements 🫶🌸

special thanks to Paul Francis, NTT Japan, for the original brainstorming sessions that brought this work to life ✨.

the emergence of CBTv2 owes a lot to Clay Shields and his work on Ordered CBT (OCBT) [8] 👑. Clay identified and proved several failure modes of CBT as it was originally specified with multiple cores 😱. he also suggested using an unreliable quit mechanism, which shows up in this specification as the QUIT_NOTIFICATION 💖. Clay has also offered more general constructive comments on the CBT architecture and specification 🧠.

others who contributed to the progress of CBT include Ken Carlberg, Eric Crawley, Jon Crowcroft, Mark Handley, Ahmed Helmy, Nitin Jain, Alan O'Neill, Steven Ostrowsksi, Radia Perlman, Scott Reeve, Benny Rodrig, Martin Tatham, Dave Thaler, Sue Thompson, Paul White, and other participants of the IETF IDMR working group 🌟.

thanks also to 3Com Corporation and British Telecom Plc for funding this work 💜.

References 📚

[1] Core Based Trees (CBT) Multicast Routing Architecture; A. Ballardie; RFC 2201, September 1997.

[2] Protocol Independent Multicast (PIM) Sparse Mode/Dense Mode; D. Estrin et al; ftp://netweb.usc.edu/pim Working drafts, 1996.

[3] Internet Group Management Protocol, version 2 (IGMPv2); W. Fenner; ftp://ds.internic.net/internet-drafts/draft-ietf-idmr-igmp-v2-**.txt. Working draft, 1996.

[4] Reynolds, J., and J. Postel, "Assigned Numbers", STD 2, RFC 1700, October 1994.

[5] CBT Border Router Specification for Interconnecting a CBT Stub Region to a DVMRP Backbone; A. Ballardie; ftp://ds.internic.net/internet-drafts/draft-ietf-idmr-cbt-dm-interop-**.txt. Working draft, March 1997.

[6] Ballardie, A., "Scalable Multicast Key Distribution", RFC 1949, July 1996.

[7] A Dynamic Bootstrap Mechanism for Rendezvous-based Multicast Routing; D. Estrin et al.; Technical Report; ftp://catarina.usc.edu/pim

[8] The Ordered Core Based Tree Protocol; C. Shields and J.J. Garcia-Luna-Aceves; In Proceedings of IEEE Infocom'97, Kobe, Japan, April 1997; http://www.cse.ucsc.edu/research/ccrg/publications/infocomm97ocbt.ps.gz

[9] Multicast-Specific Security Threats and Counter-Measures; A. Ballardie and J. Crowcroft; In Proceedings "Symposium on Network and Distributed System Security", February 1995, pp.2-16.

Author Information 👩‍💻💖

Tony Ballardie, Research Consultant

EMail: ABallardie@acm.org 📬

📦 where this page comes from