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 ( What is
the problem in Distance Vector routing ?)
• RPF algorithm:
– When a multicast packet is received from source (S) on
interface (I) at router R
– If I belongs to the shortest path from R to S, forward it to
all interfaces except I; Otherwise, refuse the packet
– Assumes symmetric routing : distance(R→S) =
distance(S→ R)
3
RPF Properties
• RPF properties:
– Generates 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
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 father 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 (the next node on the
shortest path to S: again symmetry is assumed).
– 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 per-source 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)
R1
S
UDP header and
data
R2
G
10
MBONE
• Experimental Multicast Backbone on the Internet (’92)
• Based on the virtual connection between multicast routers (manually
configured: What problem is caused when joining the net?)
• 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
• A special flag is added in the database for supporting
MOSPF
• Therefore MOSPF routers actually can perform RPF and
prune computation “in memory” (Locally computed: How
can symmetry be broken?)
12
MOSPF – Designated Router: Reminder
• A router responsible for registering and
propagation of multicast group membership
information for a certain network called
Designated Router
• When a host sends a 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 LSP in its area (LSA, Link State Advertisement, in the
RFC)
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 LSP
• The Designated Router for some network
propagates group membership information of its
network with this new type of LSP. Its distribution
intended for all the area.
• The Designated Router propagates information
only about networks assigned to this router
• The LSP includes records. Their structure is: a
network and a multicast group for which it wants
to belong.
16
MOSPF Routing
• MOSPF routing is influenced by source and by the
multicast destination
• When a router receives a multicast packet it generates
Shortest Path Tree with a packet sender as the root 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
• HW2 q 2.
• If Group-Membership-LSP distribution is limited to an
area, then how multicast between different areas of the
same AS is executed ?
• A part of Area-Border-Routers are defined to function
also as a Inter Area Multicast Forwarders
• In this role, they summarize Group-Membership-LSP 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 messages for the
advertised groups from Backbone and forward them to
its area.
18
MOSPF – Inter Area Routing
• To prevent explosion of data external routers don’t
advertise in their areas all the groups that have been
defined in other areas.
• How 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): The Intra-Area routers believe that the
Inter Area router is a part of all the multicast groups.
• These 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