An Architecture for Wide Area Multicast Routing

One-line summary: Mcast routing that can dynamically switch between core-based trees and shortest-path trees to provide efficient behavior for both sparse and dense mcast groups, using explicit joins (rather than explicit prunes) and periodic refreshes of soft state in routers.

Overview/Main Points

• Motivation:
  • link-state and distance-vector mcast routing scale poorly for large but sparse groups.
  • Explicit pruning scales terribly for large but sparse groups.
  • core-based trees trade less router state for longer delivery paths and traffic concentration; shortest-path delivery trees trade more router state for shorter paths and traffic dispersal.
  • CBT's work well for sparse groups, SPT's for dense groups. Want a way to flexibly choose between them without breaking compatibility/interoperability or tearing down the group and recomputing its routes.
• Requirements:
  • efficient sparse group support
  • high quality data distribution (application can choose low delay delivery if needed)
  • unicast routing protocol independence (why?)
  • interoperability w/existing mcast routing
  • robustness: no single point of failure or hard state
• Sparse group support: designate some routers as RP's (rendezvous points) for subtree below them.
• To join an mcast group RP-tree:
  • receiver sends PIM-join upstream to nearest RP (may be 1 or more router hops away)
  • RP is in the mcast tree of an upstream source. When the source starts sending, RP will receive a PIM-register message.
  • At that point it forwards the original PIM-join towards the source.
  • Note that the RP is now acting as the forwarding agent for packets going to the receiver.
• To switch from RP-tree to shortest-path tree:
  • PIM-join-SPT message sent upstream towards RP.
  • RP propagates message up to mcast source S.
  • S then starts forwarding multicast directly on a shortest-path tree to the receiver (which probably circumvents RP).
  • Once receiver starts receiving mcast packets that were not sent through RP, it sends RP a PIM-prune message, which (a) is forwarded to S, and (b) causes the RP to set up a "negative cache" entry for the receiver (i.e. no longer forward mcast packets for that receiver).
• Fault tolerance:
  • Reachability beacons periodically broadcast downstream from RP's. If receivers detect an RP has gone away, they can target some other RP.
  • Since PIM messages are periodically refreshed, they don't need to be positively acked.
  • Therefore all state in routers is effectively soft state, though a few mcast packets may be missed if an RP reboots.

Relevance

Flaws

• No discussion of how policy (when to switch) might be implemented.
• Might the intermediate routers want to control this policy (i.e. "Please switch from RP to SP because I am running out of routing table entries!") There seems to be no way for them to do this since everything is strictly receiver-driven (all messages originate at receivers).