RPF eliminates the loop in the flooding process in Software

Creation Code 39 Extended in Software RPF eliminates the loop in the flooding process

Reverse path forwarding (RPF)

Reverse Path Broadcasting (RPB) RPF guarantees that each network receives a copy of the multicast packet without formation of loops However, RPF does not

guarantee that each network receives only one copy; a network may receive two or more copies The reason is that RPF is not based on the destination address (a group address); forwarding is based on the source address To visualize the problem, let us look at Figure 2241

Net3 in this figure receives two copies of the packet even though each router just sends out one copy from each interface There is duplication because a tree has not been made; instead of a tree we have a graph Net3 has two parents: routers R2 andR4 To eliminate duplication, we must define only one parent router for each network We must have this restriction: A network can receive a multicast packet from a particular source only through a designated parent router Now the policy is clear For each source, the router sends the packet only out of those interfaces for which it is the designated parent This policy is called reverse path broadcasting (RPB) RPB guarantees that the packet reaches every network and that every network receives only one copy Figure 2242 shows the difference between RPF and RPB

The reader may ask how the designated parent is determined The designated parent router can be the router with the shortest path to the source Because routers periodically

send updating packets to each other (in RIP), they can easily determine which router in the neighborhood has the shortest path to the source (when interpreting the source as the destination), If more than one router qualifies, the router with the smallest IP address is selected

Reverse Path Multicasting (RPM) As you may have noticed, RPB does not multicast the packet, it broadcasts it This is not efficient To increase efficiency, the multicast packet must reach only those networks that have active members for that particular group This is called reverse path multicasting (RPM) To convert broadcasting to multicasting, the protocol uses two procedures, pruning and grafting Figure 2243 shows the idea of pruning and grafting

~ CNet32)

c RPM (after pruning) d RPM (after grafting)

' Pruned route,

The designated parent router of each network is responsible for holding the membership information This is done through the IGMP protocol described in 21 The process starts when a router connected to a network finds that there is no interest in a multicast packet The router sends a prune message to the upstream router so that it can exclude the corresponding interface That is, the upstream router can stop sending multicast messages for this group through that interface Now if this router receives prune messages from all downstream routers, it, in turn, sends a prune message to its upstream router What if a leaf router (a router at the bottom of the tree) has sent a prune message but suddenly realizes, through IGMP, that one of its networks is again interested in receiving the multicast packet It can send a graft message The graft message forces the upstream router to resume sending the multicast messages

RPM adds pruning and grafting to RPB to create a multicast shortest path tree that supports dynamic membership changes DVMRP The Distance Vector Multicast Routing Protocol (DVMRP) is an implementation of multicast distance vector routing It is a source-based routing protocol, based on RIP

The Core-Based Tree (CBT) protocol is a group-shared protocol that uses a core as the root of the tree The autonomous system is divided into regions, and a core (center router or rendezvous router) is chosen for each region Formation of the Tree After the rendezvous point is selected, every router is infonned of the unicast address of the selected router Each router then sends a unicast join message (similar to a grafting message) to show that it wants to join the group This message passes through all routers that are located between the sender and the rendezvous router Each intermediate router extracts the necessary infonnation from the message, such as the unicast address of the sender and the interface through which the packet has arrived, and forwards the message to the next router in the path When the rendezvous router has received all join messages from every member of the group, the tree is formed Now every router knows its upstream router (the router that leads to the root) and the downstream router (the router that leads to the leaf) If a router wants to leave the group, it sends a leave message to its upstream router The upstream router removes the link to that router from the tree and forwards the message to its upstream router, and so on Figure 2244 shows a group-shared tree with its rendezvous router Figure 2244 Group-shared tree with rendezvous router