Transcript tut7 - Webcourse

Internet Networking
Spring 2005
Tutorial 7
DVMRP
1
Introduction

When we discuss multicast routing
protocols 3 issues should be
addressed:



How hosts can join to 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.
2
A simple solution


Consider the following solution: multicast
packets are flooded from a source to all the
routers in the AS.
Advantages:


Simplicity.
Disadvantages:


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.
3
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
F
4
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 more than infinity.


This technique is called “Poison Reverse”.
RPF guarantees that every router receives every
packet exactly once.
5
Reverse Path Forwarding
A
B
C
E
D
F
6
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.
7
Pruning example
Only C and E are group members.
before pruning
after pruning
A
B
A
C
E
D
F
B
C
E
D
F
8
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 to an upstream
node must be no more than the minimum of the
remaining lifetimes of the PRUNE messages received from
the downstream nodes.
This is an example of a soft state concept.
Send an explicit GRAFT (join) request, which will
propagate upwards.


A GRAFT message must be acknowledged to ensure the
reception of the message.
Used only to undo the effect of a PRUNE message.
9
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 GRANT and PRUNE message for
a group must be sent per-source.
Does not scale for large multicast network.
10
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.
11
DVMRP Forwarding Table


Represents the local router’s understanding of the
shortest path delivery tree for each (source, group)
pair.
a prune message has been
sent to the upstream router
Example:
the router has received a
prune message from a
downstream router.
12
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
R2
13
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).
14
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
R2
15
Comparison to CBT & PIM


CBT and PIM are also used by ASs which employ
distance vector routing.
CBT defines a core router from which the multicast
packets are propagated, hence:


There is no need for the routers to keep a state per-source.
Only GRAFT messages are used to join a tree.




Since there is one tree, only one GRAFT message needs to be
sent to accept packets from all possible sources.
The flood & prune method is not needed.
Suitable for sparse multicast trees.
PIM uses a hybrid approach.



For sparse multicast trees a CBT-like protocol is used.
For dense multicast trees a DVMRP-like protocol is used.
PIM is considered the multicast protocol of choice.
16