Multicast
Routing
JITHU JOY
1
Optimal Routing :shortest path trees
The process of optimal interdomain routing eventually results in the finding of
the shortest path tree . The root of the tree is the source, and the leaves are
the potential destinations. The path from the root to each destination is the
shortest path , where the goal is to find the route with the least distance or
cost between two points in a network..
2
Unicast Routing
Unicast routing in a network refers to the process of sending data from one
source to one specific destination. It’s a one-to-one form of communication.
When a router receives a packet to forward, it needs to fond the shortest path
to the destination of the packet. The router consults its routing table for that
particular destination. The next-hop entry corresponding to the destination is
the start of the shortest path. The router knows the shortest path for each
destination, which means that the router has a shortest path tree to optimally
reach all destinations. In other words, each line of the routing table is a
shortest path. the whole routing table is a shortest path tree.
3
Multicast Routing
Multicast routing refers to the process of delivering data from one source to multiple
specific destinations simultaneously, without sending separate copies to each recipient.
Multicast is a one-to-many or many-to-many form of communication. When a router
receives a multicast packet, it is different from receiving unicast packet. A multicast
packet have destination in more than one network. Forwarding a single packet to
destination requires a shortest path tree. For example, if we have n packets, we need n
shortest path trees. It increases the complexity in multicast routing. To solve this
problem two methods are used:
• Source based trees
• Group shared trees
4
5
6
7
8
THANK YOU
9
ROUTING PROTOCOLS
By
Niranjana R Nair
Bcs computer science
WHAT IS ROUTING?
• Routing is the process if selecting a path in a
network along which the packet shall be sent to a
destination.
MULTICAST ROUTING
• In multicast routing there is one source and a group of destination.
• In Multicasting the router may forward the received packet through
several interfaces.
T A X O N O M Y OF C O M M O N
MULTICAST ROUTING PROTOCOLS
MOSPF : MULTICAST OPEN SHORTEST
PATH FIRST
• This protocol is an extension of OSPF protocol.
• It used multicast link state routing to create source based trees
• It calculates trees on demand
• The protocol requires a new link state update packet to
associate the unicast address of a host with the group address
or the address the host is sponsoring.
• This packet is called the group-membership L SA
• We make a tree that contains all the host belonging to a
group, but we use the unicast address of the host in
calculations
• For efficiency the router calculates the shortest path trees
on demand.
MULTICAST DISTANCE VECTOR
ROUTING
• Multicast distance vector routing uses source based trees, but,the router
never actually makes a routing table.
• When a router receive a multicast packet,it forwards the packet as through it
is consulting a routing table
• We can say that the shortest path tree is evanescent.
• After it’s use the table is destroyed.
• To accomplish the routing, multicast distance vector algorithm uses a process based on
one of the four decision making strategy:
1) Flooding
2) Reverse Path Forwarding (RPF)
3) Reverse Path Broadcasting (RPB)
4) Reverse Path Multicasting (RPM)
1) Flooding:
• A router receives a packet and without even looking at the destination group
address, sends it out from every interface except the one from which it was
received
• It creates loop in systems:
A packet that has left the router may come back again from another interface or the
same interface and be forwarded again.
• Some forwarding protocols keep a copy of packet for a while and discard any
duplicate to avoid loops.
2) Reverse Path Forwarding (RPF) :
• RPF eliminates the loop in flooding process.
• The router forward only one copy of a packet that has travelled the shortest path from
source to router.
• To checkout if the packet has come through its shortest path RPF uses unicast routing
table.
• The router receive a packet and extract the source address. It consults the unicast
routing table as though it wants to send a packet to the source address.
• The routing table tells the router the next hop.
• If the multicast Packet has just come from the hip defined in the table, the packet has
travelled the shortest path from the source to the router because the shortest path is
the reciprocal in unicast distance vector routing protocols.
• If the path from A to B is shortest then it is also the shortest from B to A.
• The router forwards the packet if it has travelled from the shortest path or it
discards otherwise
REVERSE PATH
FORWARDING
• RPF is not based on destination address
PRO BL EM W I T H RPF because forwarding is based on source
address.
• Net 3 in this figure receives two copies of
the packet even though each router just
send one copy from each [Link]
is a duplication because a tree has not
been made,instead of a tree we have a
graph.
Net 3 has two parents :R2 and R4
• To eliminate duplication we must define
only one parent router for each network
• But a network can receive a multicast
packet from a particular source only
through a designated parent router
RPF Versus RPB
RPF RPB
Now the policy is [Link] each source the router send the packet only out of those
interfaces for which it is the designated [Link] is called as reverse path
broadcasting.
3) Reverse Path Broadcasting (RPB) :
• Each network receives a copy of the multicast packet without formation of loops.
• A network may receive two or more copies.
• Packet reaches every network and that every network receives only one copy.
• The designated parent router can be the router with the shortest path to the source.
Because router periodically sent updating packet to each other , they can easily
determine which router in the neighbourhood has the shortest path to the source.
• Is more then one router qualifies ,the router with the smallest IP address is selected
• 4) Reverse Path Multicasting (RPM) :
• RPB does not Multicast the packet it broadcast [Link] is not
[Link] increase the efficiency the multicast packet must
reach only those network that has active member for that
particular group . This is called as reverse path multicasting.
• To convert broadcasting to multicasting the protocol uses to
procedures: Pruning and grafting
• Pruning:
The router send a prune message to the upstream router so
that the upstream router can stop sending Multicast message for
this group through that Interface.
• Grafting:
The graft message force the upstream router to resume
sending the multicast messages.
DVMRP: D I S T A NC E V E C T OR MULTI C A S T
ROUTING PROTOCOL
• Distance vector multicast routing protocol is an
implementation of multicast distance vector routing. It is a
source based routing protocol.
Core-Based Tree (CBT)
• CBT is a group-shared protocol that uses a core as the
root of the tree • AS is divided into regions, and core
(rendezvous router) is chosen for each region
• Each router sends a unicast join message to rendezvous
router
• When the rendezvous router has received all join
messages from every member of the group, the tree is
formed
Sending Multiple Packets:The source sends the multicast packet to the core
router. The core router decapsulates the packet and forwards it to all
interested hosts. Each router that receives the multicast packet, in turn,
forwards it to all interested ports Computer Networks
Protocol Independent Multicast (PIM) • PIM-DM (Dense Mode) and PIM-SM
(Sparse Mode)
• PIM-DM is used when each router is involved in multicasting • PIM-DM is a
source-based routing
• PIM-DM uses RPF and pruning and grafting strategies to handle
multicasting. However, it is independent of the underlying unicast protocol.
• PIM-SM is used when each router is involved in multicasting with slight
possibility
• PIM-SM is a group-shared routing protocol that has a rendezvous point as
the source of the tree • PIM-SM is similar to CBT but uses a simpler
procedure.