Transcript Recitation_DVMRP

Internet Networking
recitation #7
DVMRP
Spring Semester 2009, Dept. of Computer Science, Technion
1
2
Introduction
 When we discuss multicast routing protocols 3
issues should be addressed:



How hosts can join a multicast group (usually performed
by IGMP).
How routers distribute between them information about
registered multicast subscriptions.
How a router performs routing of a multicast packet.
Internet Networking
3
A simple solution
 Consider the following solution: multicast packets are
flooded from a source to all the routers in the AS.
 Advantages:

Simplicity.

Packets are unnecessarily received by all routers.
Routers receive duplicate packets.
• A filtering mechanism should be employed. Each router
should remember what packets it already forwarded.
 Disadvantages:

Internet Networking
4
Avoiding the need to remember
 To avoid the need to remember, a packet is accepted
only if it arrives on the port that corresponds to the
shortest path from S.

Can it be done in Distance Vector routing?
• Symmetric paths are assumed.
 Duplicate packets are not avoided.
A
An accepted packet
B
C
D
Sent but not accepted packet
E
Internet Networking
F
5
Reverse Path Forwarding
 To avoid duplications, a packet is sent to a
neighbor only if it will be accepted.
 A router sends a packet to a neighbor only if it is on
the shortest path from it to the source.


The router needs to know which of its neighbors use it as
a “next hop” to the source.
This information is advertised to the router as a regular
route report having a cost of infinity.
• This technique is called “Poison Reverse”.
 RPF guarantees that every router receives every
packet exactly once.
Internet Networking
6
Reverse Path Forwarding
A
B
C
E
D
F
Internet Networking
7
Pruning
 Problem: Flooding still occurs throughout the AS.
 Solution: Flood & Prune method.



The first multicast packet from a source S is propagated to
all the network nodes (flooding).
When a leaf router (at the specific tree) receives a multicast
message and doesn’t have group members for it, it sends
PRUNE message to its father node.
When an intermediate router gets PRUNE messages from
all its children then it sends PRUNE message to its father
node.
Internet Networking
8
Pruning example
Only C and E are group members.
before pruning
after pruning
A
B
A
C
E
D
B
F
C
E
Internet Networking
D
F
9
Re-joining the Tree
 After a period of time the PRUNE effect vanishes and
the messages are flooded again.



Provides robustness to topology changes.
Each PRUNE message has a lifetime value associated with it.
The lifetime of a PRUNE message sent by a node to an
upstream node must be no more than the minimum of the
remaining lifetimes of the PRUNE messages received from its
downstream nodes.
 Send an explicit JOIN request, which will propagate
upwards.


A JOIN message must be acknowledged to ensure the
reception of the message.
Used only to undo the effect of a PRUNE message.
Internet Networking
10
RPF with pruning - summary
 Advantages:


Simplicity
Robustness
 Disadvantages:




Packets are flooded to the whole AS on a periodic basis.
All routers must keep state on a per-group and per-source
basis.
In principle each JOIN and PRUNE message for a group
must be sent per-source.
Does not scale for large multicast network.
Internet Networking
11
DVMRP Protocol

Protocol for multicast routing inside of ASs that use
Distance Vector Routing (e.g. RIP).






Defined in RFC 1075.
Revised by Internet Draft: draft-ietf-idmr-dvmrp-v3-11.
• May become an RFC in the future.
Uses IGMP-like messages for exchanging multicast
information between routers.
Based on RPF and flood & prune algorithms.
Suitable for dense multicast trees.
Uses its own routing tables.

Allows the multicast routes to be independent of the unicast
routes.
Internet Networking
12
DVMRP Forwarding Table
 Represents the local router’s understanding of the
shortest path delivery tree for each (source, group) pair.
 Example:
a prune message has been
sent to the upstream router
the router has received a
prune message from a
downstream router.
Internet Networking
13
Tunneling
 A method for sending datagram between routers
separated by gateways that do not support multicast.
 Acts as a virtual network between two routers.
 Example: Host on net 1 wants to send a multicast
message to a host on net 2
net 1
net 2
Internet
R1
with no support
for multicast
Internet Networking
R2
14
Tunneling
 Tunneling is done by encapsulating the original
multicast datagram with an unicast IP datagram.
 The source and the destination of the unicast IP
packets are the end point of the tunnel.
 The encapsulation of the datagram is done by the
source.
 The destination address in the unicast header is
the address of the next router which supports
multicast (it is considered the egress of the tunnel).
Internet Networking
15
Tunneling
 Example:
Source:R1 Dest:R2
Protocol: IP in IP
Source:S Dest:G
Protocol: UDP
UDP header and
data
member of G
Internet
S
R1
with no support
for multicast
Internet Networking
R2