Transcript pptx

CMPT 471
Networking II
Multicasting protocols
1
State machine for an entry in
host's multicast route table
© Janice Regan, 2006
Comer 2000: fig 17.4
2
IGMP states: 1

Consider a router with at least one host on a connected network
that is a member of a particular multicast group
 Every 125 seconds the router will generate a query and send it
to the multicast group..
 When the host receives the query it moves from member state
to delaying member state, it builds its report and sets its
random delay timer (random in a specified interval which
defaults to 10 sec)
 If it hears another report before it is due to send its own it will
drop the report without sending an moves back to idle member
state. (v2 only)
 When its timer expires it sends its report and moves back to
idle member state.
© Janice Regan, 2006
3
IGMP states: 2
 Consider a router with a connected network. No host on
that connected network is a member of the multicast
group. Then consider that one host on the connected
network wishes to join the multicast group






The host will be in the nonmember state.
The host builds a membership report packet.
The host starts a timer and sends the membership report packet
The host moves into the delaying member state.
When the timer expires the host resends the member report
packet and moves into the member state.
Sending the membership report twice (each time in a best effort
UDP packet) provides a measure of security that the
membership report will reach the server
© Janice Regan, 2006
4
Need for dynamic routing
 Membership in groups changes not only when
topology changes, but also when new
hosts/application programs join/leave a group
or update filtering information.
 Routing requires knowledge of both source and
destination to avoid loops (router A-B-C-A)
 Senders need not be members of the multicast
group and multicast messages may be routed
across networks with no members in the
multicast group. Routing must adapt to any
sender.
© Janice Regan, 2006
5
Reverse path forwarding
 When a source wishes to flood a message
across the network to reach all routers
 Determine which interface the packet should arrive
through


Extract the source address
Consult the routing table to determine which interface the
packet would be sent through in if was to be forwarded to the
source address. This is the reverse path interface
 If the packet arrives on the reverse path interface flood
it through all other interfaces
 If the packet arrives on any interface other than the
reverse path interface drop it
© Janice Regan, 2006
6
Reverse path forwarding
 Using the RPF algorithm the packet will be
flooding throughout the internet reaching all
potential group members
 Multiple copies of each packet may reach any
given network.
 Copies of the packet are sent to networks that
are not part of the path from source to receiver
and have no members in the multicast group
© Janice Regan, 2006
7
Source based tree for source x
Group has members only on networks with hosts illustrated
Comer
fig 2006
17.9
©
Janice2000:
Regan,
8
Source based tree for source z
Group has members only on networks with hosts illustrated
©
Janice2000:
Regan,
Comer
fig 2006
17.9
9
Truncated RPF (1)
 Reverse path forwarding with an added step
 Each router keeps both a conventional routing
table and a multicast routing table which is a list
of multicast groups reachable through each
interface
 On a network with more than one directly
connected multicast router TRPF may still result
in multiple copies of a multicast packet reaching
a multicast group member
© Janice Regan, 2006
10
Truncated RPF (2)
 If RPF indicates the message should be
dropped, it is.
OTHERWISE
 If a router has no members on any of its
attached networks it will check an additional list
of reachable multicast groups and forward the
packet through interfaces that lead to members
of the group. The router truncates forwarding
(does not flood the packet through the
interface) when no group members are
reachable through that interface.
© Janice Regan, 2006
11
Source based tree for source x
Group has members only on networks with hosts illustrated
zz
©
Janice2000:
Regan,
Comer
fig 2006
17.9
12
Source based tree for source z
Group has members only on networks with hosts illustrated
zz
©
Janice2000:
Regan,
Comer
fig 2006
17.9
13
reverse path multicasting (RPM):
 TRPF + Any router that has no members attached and
no paths to multicast group members will be ‘pruned’. A
prune message will be sent back to the previous router
for the flooded message telling it to stop sending
messages to the originating router of the prune
message.
 The flood and prune process results in the gradual
development of a source based tree for multicast
routing.
 A router that has previously sent a prune message may
later send a graft message to ask for the resumption of
exchange of multicast messages (for example if one of
the hosts on its connected networks decides to join the
multicast group)
© Janice Regan, 2006
14
RPM: routing
 When a new member (receiver) joins the group, the tree
may need to be updated.
 By flooding an announcement of the new member
 By having each router remember how to contact the
rest of the multicast group.
 Distance Vector Multicast Routing Protocol (DVMRP) is
an extension of distance vector routing protocols used
for unicast (works with RIP). DVMRP implements RPM
 DVRMP is (like RIP) an IRP, it is used for hosts and
routers within a single AS. Parts of that AS may be at
different physical locations and be connected by
tunnels.
© Janice Regan, 2006
15
RPM: routing
 Like RIP, DVMRP is not very scalable, larger
amounts of data are exchanged as the network
grows, a small value for infinity is used, and
information on prune messages must be kept
so graft messages can be executed
© Janice Regan, 2006
16
When DVMRP message are sent
 Periodically a router should send out DVMRP




messages with all of its routing information to all of its
virtual interfaces (physical interfaces and tunnels).
Whenever a route is changed, a routing update should
be sent for that route. These triggered updates should
have added random delays.
To supply information about some or all routes in
response to a request.
A request for all routes should be sent on all virtual
interfaces when an DVMRP router is restarted.
If possible, on termination a DVMRP router should send
out DVMRP messages with metrics equal to infinity for
all of its routes, on all virtual interfaces.
© Janice Regan, 2006
17
What is a DVMRP message
 DVMRP uses the Internet Group Management
Protocol (IGMP) to exchange routing
datagrams.
 DVMRP datagrams are composed of two
portions: an IGMP header, and a stream of
tagged data. The fixed length IGMP header of
DVMRP messages is:
Version
Type
4
Subtype
8
CHECKSUM
16
32
 The version is 1. The type for DVMRP is 3.
© Janice Regan, 2006
18
What is a DVMRP message
 Subtypes
 1 = Response; provides routes to some destination(s).
 2 = Request; requests routes to some destination(s).
 3 = Non-membership report;
 4 = Non-membership cancellation; the message
cancels previous non-membership report(s).
 Checksum is calculated over entire message
 Tagged Data, each containing a command. Each
command includes a tag and necessary data
 A DVMRP message is limited to 512 bytes
© Janice Regan, 2006
19
Implementing DVMRP
 There are multiple ways to implement DVMRP
routing on a UNIX system
 mrouted is can be used to support DVMRP and
multicast forwarding and tunnelling
 quagga (or zebra) routing suite can be used not
only to implement DVMRP distance vector
routing protocol but also link state multicast
routing protocols (more later) and unicast
routing protocols.
© Janice Regan, 2006
20
mrouted
 Uses DVMRP (RFC 1075) to propagate
multicast routing information between routers.
(in version 3 only). A pruned routing tree is
determined for each multicast group with routes
that have no members pruned from the
multicast tree
 A router running mrouted is a multicast router
and maintains a multicast routing table
 mrouted does not replace conventional unicast
routing processes, they work in parallel
© Janice Regan, 2006
21
mrouted
 mrouted provides multicast tunnels
 Propagate multicast packets between
network segments or AS’s that support
multicasting through parts of the internet that
do not support multicasting
 Multicast IP packet is encapsulated in a
unicast IP packet then unicast to the next
router that supports multicasting
© Janice Regan, 2006
22
Tunneling
© Janice
Regan,
2006
Comer
2000:
fig 17.10
23
Tunneling:
IP in IP encapsulation
© Janice
Regan,
2006
Comer
2000:
fig 17.11
24
MBONE
 RFC 1458, 1889
 Multicast backbone: a virtual network of
multicast routers that form a backbone for
multicast routing over the internet
 Growing exponentially just like the
internet
© Janice Regan, 2006
25
A DVMRP example
 Network to consider
F
s
A
mrouted
C
mrouted
mrouted
B
D
P
mrouted
A
mrouted
mrouted
E
mrouted
© Janice Regan, 2006
Q
A
mrouted
26
A DVMRP example: RPF
 STEP 1: Send packet from s to A (hops between
routers all have cost 1). Reaches multicastF router A
s
A
mrouted
C
mrouted
mrouted
B
D
P
mrouted
A
mrouted
mrouted
E
mrouted
© Janice Regan, 2006
Q
A
mrouted
27
A DVMRP example: RPF
 STEP 1: RPF at A
F
s
A
mrouted
C
mrouted
mrouted
B
D
P
mrouted
A
mrouted
mrouted
E
mrouted
© Janice Regan, 2006
Q
A
mrouted
28
A DVMRP example: RPF
 STEP 2: RPF from B, C, and F
F
s
A
mrouted
C
mrouted
mrouted
B
D
P
mrouted
A
mrouted
mrouted
E
mrouted
© Janice Regan, 2006
Q
A
mrouted
29
A DVMRP example: RPF
 STEP 2: RPF from E, P, and Q
F
s
A
mrouted
C
mrouted
mrouted
B
D
P
mrouted
A
mrouted
mrouted
E
mrouted
© Janice Regan, 2006
Q
A
mrouted
30
A DVMRP example: TRPF
 All destination networks without members need not be
part of the broadcast tree
s
A
F
mrouted
C
mrouted
mrouted
B
D
P
mrouted
A
mrouted
mrouted
E
mrouted
© Janice Regan, 2006
Q
A
mrouted
31
A DVMRP example: RPM
 All destination routers that do not have outgoing paths
to any group members send prune messages
F
s
A
mrouted
C
mrouted
mrouted
B
D
mrouted
prune P
mrouted
A
mrouted
prune
prune
E
mrouted
© Janice Regan, 2006
Q
A
mrouted
prune
32
A DVMRP example: RPM
 All routers receiving a prune message send back a
prune ack
s
F
A
mrouted
C
mrouted
mrouted
B
ack
D
mrouted
P
mrouted
A
mrouted
ack
ack
E
mrouted
© Janice Regan, 2006
Q
A
mrouted
ack
33
A DVMRP example: RPM
 Leaf routers have been pruned
F
s
A
mrouted
C
mrouted
mrouted
B
D
P
mrouted
A
mrouted
mrouted
E
mrouted
© Janice Regan, 2006
Q
A
mrouted
34
A DVMRP example: changes
 Change Topology, new member added on network
attached to router Q, sends ICMP report toF join
s
A
mrouted
C
mrouted
mrouted
B
D
P
mrouted
A
mrouted
mrouted
E
mrouted
© Janice Regan, 2006
Q
Join report
A
mrouted
35
A DVMRP example: changes
 Change Topology, new member added on network
attached to router Q, sends ICMP report toF join
s
A
mrouted
C
mrouted
mrouted
B
D
P
mrouted
A
mrouted
mrouted
Graft
E
mrouted
© Janice Regan, 2006
Q
A
mrouted
36
A DVMRP example: changes
 Change Topology, new member added on network
attached to router Q, sends ICMP report toF join
s
A
mrouted
C
mrouted
mrouted
B
D
P
mrouted
A
mrouted
mrouted
E
mrouted
© Janice Regan, 2006
Q
A
mrouted
37
Other multicast protocols
 MOSPF (RFC 1585)
 Multicast extension of OSPF.
 Demand driven
 uses OSPF topology information to compute
a forwarding tree for each multicast source
 Useful in a particular area of an AS.
 Propagate membership information from
each area to the backbone through MABRs
(multicast area border routers)
© Janice Regan, 2006
38
Other multicast protocols
 PIM-SM, PIM-DM Protocol independent
routing for sparse or dense multicast
networks
© Janice Regan, 2006
39
Sparse and dense multicast
 Consider an internet composed of many
network segments. One or more routers is
connected to each segment.
 If you expect most segments to contain
hosts that will be part of a multicasting group
you have a dense multicast network
 If you expect only a few of the segments to
contain hosts that will be a part of the
multicast group you have a sparse multicast
network.
© Janice Regan, 2006
40
Sparse and Dense multicast
 Consider an internet composed of many
network segments. One or more routers is
connected to each segment.
 For PIM (protocol independent multicast) a
different approach is taken for dense multicast
networks (usually a single enterprise with a
small number of ASs) and for sparse multicast
networks ( ISP’s with varied usage, general
internets)
 DVMRP is the simplest form of Dense Multicast,
 PIM-SM is the most commonly used multicast
protocol
© Janice Regan, 2006
41
PIM
 PIM-DM Uses a broadcast and prune (flood and
prune) process similar to DVRMP.
 Forward multicast datagrams until told not to
(pruned)
 PIM-SM Uses a demand driven approach
 Do not forward multicast datagrams until asked
 End station sends request to its local multicast
router.
 Local multicast router propagates request to other
multicast routers till the request reaches a router that
is currently forwarding multicast packets.
© Janice Regan, 2006
42
PIM-SM: finding active routers
 Designate one or more routers as core routers or
Rendezvous points (RP). Only one should be active
 Each RP maintains a database of all its multicast
groups and their sources.
 Each multicast router must know the addresses of the
RPs. (addresses learned using protocols we will not
cover)
 Each multicast group has one RP
© Janice Regan, 2006
43
PIM-SM: finding active routers
 Designate one or more routers as core routers or
Rendezvous points (RP). Only one should be active
 Each RP maintains a database of multicast groups and
their sources.
 Each multicast router must know the addresses of the
RPs. (addresses learned using protocols we will not
cover)
 A core based tree (CBT) rooted at the RP can then be
generated. The CBT will connect to all active (with
present members) routers


Used to route multicast datagrams to multiple groups
Demand driven, only add to the tree when a new host, which
may be on an unserviced router, requests to become a
member of the group
© Janice Regan, 2006
44
Example:
 Based on material from
ftp://ftp-eng.cisco.com/ipmulticast/training/Module1.pdf
© Janice Regan, 2006
45
Example: Receiver Joining Group
 Uses RPF,
 source is the RP for shared trees (RP to receivers),
 New receivers register with RP then their local
multicast router becomes part of the shared
tree (if it is not already) and traffic flows up the
shared tree to them
© Janice Regan, 2006
46
PIM-SM: adding a receiver to CBT
 The new receiver will send an IGMP report
requesting that it join group G to its local router
 If the local router is not a part of the CBT it will
send a join message to the router one hop closer
to the RP
 If a the local router is already a part of the CBT for
a local RP
 it is already forwarding multicast packets.
 The local multicast router will add the host to the
multicast group and begin forwarding packets to the
host from the RP
© Janice Regan, 2006
47
PIM-SM: adding a receiver to CBT
 If a the local router is not already a part of the CBT
(shared tree) for a local RP
 The local multicast router will send a join request to
the next hop router on the path to the RP (along
the unicast path)
 When the join message reaches the next hop
router that router will
 add an entry in its forwarding table to forward group G
multicast datagrams to the local router
 If it is a member of the CBT for group G it will add the
originating host to its list of member for group G
 If it is not a member of the CBT it will send a join
message to the router one hop closer to the RP
© Janice Regan, 2006
48
PIM-SM: adding a receiver to CBT
 The next hop router will (loops)
 add an entry in its forwarding table to forward
group G multicast datagrams to the originating
router of the join message
 If the next hop router is a member of the CBT
for group G it will add the originating host to its
list of member for group G
 If it is not a member of the CBT it will send a
join message to the router one hop closer to
the RP
 The loop above continues until a router that is a
member of the CBT is reached
© Janice Regan, 2006
49
A PIM-SM example: changes
 New receiver unicasts join to RP. At each router
F
pim-SM
pim-SM
pim-SM
pim-SM
pim-SM
pim-SM
Unicast join
message
Resulting
shared tree New receiver
© Janice Regan, 2006
pim-SM
pim-SM
RP
pim-SM
pim-SM
50
PIM-SM adding a source
 A multicast data sender sends data to a multicast group.
 The sender's local router (DR) takes those data packets,
unicast-encapsulates them, and sends them directly to the
RP.
 The RP receives these encapsulated data packets,
decapsulates them, and forwards them onto the shared
tree.
 The packets then follow the shared multicast tree, being
replicated wherever the RP Tree branches, and eventually
reaching all the receivers for that multicast group.
 The process of encapsulating data packets to the RP is
called registering, and the encapsulation packets are
known as PIM Register packets
© Janice Regan, 2006
51
A PIM-SM example: changes
 Unicast encapsulated data from local router to RP
New source
F
pim-SM
pim-SM
pim-SM
pim-SM
pim-SM
Multicast
data to group
pim-SM
Unicast encapsulated
multicast data
shared tree
pim-SM
RP
pim-SM
pim-SM
receiver
© Janice Regan, 2006
pim-SM
52
A PIM-SM example: changes
 Continue to unicast encapsulated data directly to RP
New source
while building a source based
tree
F
pim-SM
pim-SM
pim-SM
pim-SM
pim-SM
Data distribution down
shared tree
Source tree join
messages
receiver
shared tree
© Janice Regan, 2006
pim-SM
pim-SM
pim-SM
RP
pim-SM
pim-SM
53
A PIM-SM example: changes
 Multicast data can now travel through the source based
tree. Send register stop message to stop encapsulated
delivery
New source
F
pim-SM
pim-SM
pim-SM
pim-SM
pim-SM
pim-SM
RP
pim-SM
source tree
shared tree
pim-SM
pim-SM
pim-SM
54
receiver
© Janice Regan, 2006
Where are we now





The new receiver joined the shared tree
A new source has sent data to the multicast group.
It’s local router registered it with the RP
A source tree from the RP to the source has been built.
After building the source tree and initiating data transfer
through the source tree the RP sent a register stop
message to cease encapsulated delivery to RP
 When the source sends data it now passes through the
source tree to the RP
 The data passes from the RP through the source tree
then throught the shared tree to all the members of the
multicast group
© Janice Regan, 2006
55
What next?
 This may be inefficient,
 Taking a longer path to the RP and then the
destination
 May be a shorter path from the source to the
receiver
 May want to add the new source as a SBT (source
based tree), a shortest path tree from the source to the
receiver
 Source based trees are built only for source-receiver
paths carrying significant traffic. When a specific traffic
level is attained between a source and receiver then the
SBT will be determined.
© Janice Regan, 2006
56
Building the SBT
 The routers serving the receiver’s network
will directly unicast a source join message
to the router serving the destination’s
network
 The source join message travels through
the network at each hop another link in
the source based tree is established
© Janice Regan, 2006
57
A PIM-SM example: changes
 source join messages are sent to build a shortest path
source based tree. Traffic still travels along the original
source tree
New source
F
pim-SM
pim-SM
pim-SM
pim-SM
pim-SM
Source join
messages
source tree
shared tree
pim-SM
RP
pim-SM
pim-SM
pim-SM
pim-SM
58
receiver
© Janice Regan, 2006
A PIM-SM example: changes
 source prune messages are sent to switch over from
the old source tree. Traffic now travels along the new
source tree
New source
F
pim-SM
pim-SM
pim-SM
pim-SM
pim-SM
Source prune
messages
source tree
shared tree
pim-SM
RP
pim-SM
pim-SM
pim-SM
pim-SM
59
receiver
© Janice Regan, 2006
A PIM-SM example: changes
 RP prunes uneccessary link in shared tree
New source
F
pim-SM
pim-SM
pim-SM
pim-SM
pim-SM
Source prune
messages
source tree
shared tree
pim-SM
RP
pim-SM
pim-SM
pim-SM
pim-SM
60
receiver
© Janice Regan, 2006
A PIM-SM example:
 RP prunes additional uneccessary link in shared tree
New source
F
pim-SM
pim-SM
pim-SM
pim-SM
pim-SM
prune
pim-SM
RP
pim-SM
source tree
shared tree
pim-SM
pim-SM
pim-SM
61
receiver
© Janice Regan, 2006
A PIM-SM example: final
 RP prunes uneccessary link in shared tree
New source
F
pim-SM
pim-SM
pim-SM
pim-SM
pim-SM
traffic
pim-SM
RP
pim-SM
source tree
shared tree
pim-SM
pim-SM
pim-SM
62
receiver
© Janice Regan, 2006