Transcript tutorial7

Internet Networking
Spring 2002
Tutorial 7
Multicast Routing Protocols
DVMRP + MOSPF
1
Introduction
•
When we discuss multicast routing protocols
we should learn 3 things:
1. How hosts can join to a multicast group (IGMP)
2. How routers distribute between them information
about registered multicast subscriptions
3. How a router performs routing of a multicast packet
2
RPF – Reverse Path Forwarding
• Simplest algorithm for multicast routing is flooding packets
from a source to all ASs. Disadvantages:
– Large amount of unnecessary packets sending
– Need to remember already received packets to prevent duplications
• Better idea is to build some kind of spanning tree
• RPF algorithm:
– When a multicast packet is received from source (S) on
interface (I)
– If I belongs to the shortest path from S, forward it to all
interfaces except I; Otherwise, refuse the packet
3
RPF Properties
• RPF properties:
– Generate Shortest Path spanning tree
– Different spanning tree for each source
– But unnecessary forward packets to all networks,
even not subscribed to the multicast group
• RPF+ (improvement - look one step further)
– A router forwards packets only to the neighbors that it
is their “father” on the shortest path from a source
4
RPF Pruning
• Idea:
– There is no sense to forward a packet if there is no a
group member down the tree
• Algorithm Flood & Prune:
– 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 the farther node
– When an intermediate router gets prune messages
through all the outgoing interfaces then it sends
prune message by self to its father node
5
RPF Pruning Properties
– If a router wants to join a group after pruning, it sends
join request to its father node at the tree
– After predefined time exceeding joining to the group is
renewed
• The algorithm is robust for topology changes
• However, it has 2 drawbacks:
– Packets are flooded to the whole network on the
periodic basis
– All routers must keep state on a per-group and persource basis
6
DVMRP Protocol
• Protocol for multicast routing inside of ASs that
use Distance Vector Routing (i.e. RIP), defined
in RFC 1075.
• DVMRP uses IGMP messages of a new type
(not usual QUERY or REPORT messages) for
exchanging multicast information between
routers
• Based on RPF algorithm
• Uses its own routing tables (because of the
tunnels and forward-path metric)
7
DVMRP Protocol
Forwarding algorithm:
– When a router receives a multicast packet from an
interface (or a tunnel) it checks in the DVRMP routing
table whether it is on the shortest path from the source
– If this is not a case the packet is dropped; otherwise, it
is forwarded to all multicast-capable interfaces and
tunnels for which the router is the previous hop from
the source
– 2 additional checks are applied at this stage: a
verification of the packet TTL and a check for group
membership
8
DVMRP Tunneling
net 1
net 2
Internet
R1
with no support
for multicast
R2
Host on net 1 wants to send a multicast message to a host on net 2
Problem: Sometimes, some of intermediate
routers required for sending a multicast message
are not supporting DVMRP
9
DVMRP Tunneling
• Solution: Sending a multicast packet inside of an usual
unicast packet from one DVMRP router R1 to another
DVRMP router R2 through intermediate “usual” routers.
Virtual connection (tunnel) defined between R1 and R2.
Source:R1 Dest:R2
Protocol: IP in IP
Source:S Dest:G
Protocol: UDP
IP header (1)
IP header (2)
UDP header and
data
10
MBONE
• Experimental Multicast Backbone on the Internet
• Based on the virtual connection between multicast routers
• Uses DVMRP as multicast protocol
11
MOSPF
• MOSPF - enhancements to OSPF to support IP
multicast routing (RFC 1584)
• The OSPF link state database provides a
complete description of AS topology.
• MOSPF complements the database with a new
type of link state records – group membership
• Therefore MOSPF routers actually can perform
RPF and prune computation “in memory”
12
MOSPF – Designated Router
• A router responsible for registering and
propagation of multicast group membership
information for a certain network called
Designated Router
• When a host send request to the Designated
Router to be a member of some multicast group
(by IGMP protocol) then the last performs 2 things:
– Update Local Group Database
– Propagate update in the form of Group Membership LSA in its area
13
MOSPF – Local Group Database
• The local group database keeps track of the group
membership of the router's directly attached networks.
• Each entry in the local group database is a pair of:
[group, attached network]
which indicates that the attached network has one or
more hosts belonging to the multicast destination group.
• This information is then used by the router when
deciding which directly attached networks to forward a
received IP multicast datagram onto, in order to
complete delivery of the datagram to local, group
members.
14
Local Group Database - Example
• If Router RT3 has been elected Designated Router for Network N3, then
the Table: lists the local group database for the routers RT1-RT4.
Router
local group database
RT1
RT2
RT3
RT4
[Group B, N1]
[Group A, N2], [Group B, N2]
[Group B, N3]
None
b
b
N1
RT1
N3
b
RT4
RT2
a
N2
N4
RT3
h1
15
Group Membership LSA
• The Designated Router for some network
propagates group membership information of its
network with this new type of LSA. Its
distribution intended for all the area.
• The Designated Router propagates information
only about networks assigned to this router
• The LSA include records. Their structure is: a
network and a multicast group for which it wants
to belong.
16
MOSPF Routing
• MOSPF routing influenced by source and by the
multicast destination
• When a router receive a multicast packet it generates
Shortest Path Tree with a packet sender as the route
and destination networks as the leafs
• After the router computed the tree it finds its place in the
tree and decides about next targets for packet sending
• To prevent repeated generation of the same tree, the
results of the computations are saved in the Forwarding
Cache, including: source address, multicast group,
upstream and downstream interfaces (explained in the
lecture)
17
MOSPF – Inter Area Routing
• If Group-Membership-LSA distribution limited to an area,
how then executed multicast between different areas of
the same AS?
• Define part of Area-Border-Routers to function also as a
Inter Area Multicast Forwarders
• In this role, they summarize Group-Membership-LSA for
their area and advertise it over the Backbone. The
summary will contain all the groups for which at least
one member exists in the area.
• The router will get all outside message for the advertised
groups from Backbone and forward them to its area.
18
MOSPF – Inter Area Routing
• To prevent explosion of data external router don’t
advertise in their areas all the groups that have been
defined in other areas. How then is it possible to send
multicast packets from one area to another?
• For this purpose Multicast Wildcard Receivers are
defined (all Inter Area Multicast Forwarders perform this
functionality)
• This routers get all the multicast traffic of their area and
then through the Backbone, the datagram can be
forwarded to all group members in other areas
19