Core Based Trees (CBT)

Ballardie, Francis, Crowcroft

multicast internet network routing

@inproceedings{ballardie:sigcomm-1993,
  author={Ballardie, Tony and Francis, Paul and Crowcroft, Jon},
  title={Core Based Trees ({CBT})},
  booktitle={{ACM} Conference on Communications Architectures,
             Protocols and Applications ({SIGCOMM})},
  year={1993},
  pages={85--95},
  publisher={ACM},
} 

Previous established desired properties:

• Conformance to standard host group model
  • Including decoupling source and destinations
• High probability of delivery
• Low delay

New, critical desired properties:

• Scalability
  • Requires information hiding
• Robustness to network dynamics
• Independence from specific underlying unicast routing
• Flexibility to adjust to different multicast group structures
  • Dense, sparse, clustered, diverse, frequent, infrequent, etc

Source based approaches don't scale in general---could have N^2 such pairs

DVMRP requires routers to continually push to stay off the tree

Dependence on specific unicast protocols limits approaches to staying within a single AS

Core Based Trees (CBT)~\cite{ballardie:sigcomm-1993} aims to address scalability and efficiency limitations of previous multicast approaches, particularly DVMRP. It attempts to minimize the number of routers that have to maintain state or traffic regarding the group through a combination of constructing a single tree per group and constructing that tree as necessary. These are in contrast to the source-based trees of many protocols and the constant pruning trafic of DVMRP.

Each multicast group under CBT is associated with one or a small set of core routers. How these are determined is not intrinsically part of the protocol, and it is assumed that they are either known a priori or may be discovered via DNS. When a host joins a group, the request is routed toward the core router via underlying unicast routing, stopping at any intermediate CBT router already in the tree for that group. All CBT routers along the path from that point to the router directly connected to the originating host join the group tree and begin forwarding messages. When a group message is generated, if necessary it is first routed to the tree via unicasting toward the core. After reaching a CBT router in the group it is propagated throughout the group tree.

CBT routers in an active group use missed heartbeat messages to detect the failure of a parent node. Affected nodes then attempt to rejoin the group tree, either by the children of the failed node re-enacting the join process and grafting the tree, or triggering each descendent to individually attempt to rejoin. Core node failure is managed by rollover among a list of alternative cores.