Multicast Routing

Link-State Multicast

·         Multicasting is added to the existing link-state routing.

o   Each router knows entire topology by way of update messages.

o   Dijkstra's algorithm is used to compute shortest path spanning tree to reach all destinations.

·         Each router determines which groups have members on which LAN by monitoring the periodical announcements.

o   If a host does not advertise periodically, then it has left the group.

·         Equipped with group and membership knowledge, each router computes shortest path multicast tree from any source to any group using Dijkstra's algorithm.

·         Link-state routing is expensive as each router must store a multicast tree from every source to every group.

Distance-Vector Multicast

·         Multicasting is added to existing distance-vector routing in two stages.

o   Each router maintains a table of (Destination, Cost, NextHop) for all destination through exchange of distance vectors.

o   Reverse Path Broadcast mechanism that floods packets to other networks

o   Reverse Path Multicasting that prunes end networks that do not have hosts belonging to a multicast group.

Reverse-Path Broadcasting

·         A router when it receives a multicast packet from source S to a Destination from NextHop, then it forwards the packet on all out-going links.

·         The drawbacks are:

o   It floods a network, even if it has no members for that group

o   Duplicate flooding, i.e., packets are forwarded over the LAN by each router connected to that LAN.

·         Duplicate flooding is avoided by

o   Designating a router on the shortest path as parent router.

o   Only parent router is allowed to forward multicast packets from source S to that LAN.

Reverse-Path Multicasting

·         Multicasting is achieved by pruning networks that do not have members for a group G.

·         Pruning is achieved by identifying a leaf network, which has only one router (parent).

·         The leaf network is monitored to determine if it has any members for group G.

·         The router then decides whether or not to forward packets addressed to G over that LAN.

·         The information "no members of G here" is propagated up the shortest path tree.

·         Thus routers can come to know for which groups it should forward multicast packets.

·         Including all this information in a routing update is expensive.

Protocol Independent Multicast (PIM)

·         The above two multicast routing did not scale well.

·         PIM divides multicast routing into sparse and dense mode.

·         In PIM sparse mode (PIM-SM), routers leave and join multicast group using PIM Join and Prune messages.

·         PIM designates a rendezvous point (RP) for each group in a domain to receive PIM messages.

·         All routers in the domain know the IP address of RP for each group.

·         A multicast forwarding tree is built as a result of routers sending Join messages to the RP.

·         The tree may be either shared by multiple senders or source-specific to a sender. Shared Tree

·         When a router sends Join message for group G to RP, it goes through a sequence of routers.

·         Each router along the path creates an entry (*, G) in its forwarding table for the shared tree before forwarding the Join message.

·         Eventually, the message arrives at RP. Thus a shared tree with RP as root is formed.

 

 

·         The above figure shows router R4 sending Join message for group G to RP.

·         It goes through R2. R2 makes an entry (*, G) in its table and forwards the message to RP.

·         Later when R5 sends Join message for group G, it shares the tree. Therefore R2 does not forwards the Join message.

·         When a host attached to router R1, sends a message to group G, which is received by R1.

·         R1 does not know about group G, therefore it encapsulates the multicast packet with unicast address and is tunneled along the way to RP.

·         RP decapsulates the packet and sends the multicast packet to R2, which forwards it to routers R4 and R5 that have members for group G.

Source-specific tree.

·         RP has the option of forcing about group G, onto other routers by sending a source specific Join message to sending host, so that tunneling can be avoided.

·         The intermediary routers create an entry (S, G) for source-specific tree.

·         If more packets are sent from source S to group G, then other routers switch to sourcespecific tree with source host as root.

 

Analysis

·          PIM is protocol independent because, tree formation is based on path that Join messages follows  based on shortest path.

·         Shared trees are more scalable than source-specific trees.

·         Source-specific trees enable efficient routing than shared trees.