Transcript Chapter 4.4 (Multicast)

Multicast
Outline
Link-state Multicast
Distance-vector Multicast
Protocol Independent Multicast
Spring 2006
CS 332
1
Multicast
• LANs support hardware multicast (at worst, just
broadcast)
• We’re concerned here with multicast in an
internetwork
• What we don’t want to have to do: have the
source(s) send individual packets to each receiver
Spring 2006
CS 332
2
Multicast
• Source sends packet to a single multicast address
(class D in IPv4) associated with a specific
multicast group
• Internet Group Multicast Protocol (IGMP): used
to join and leave groups
– Informs router on local network of desire to receive
packets addressed for specific multicast group
• How to learn about addresses? Out-of-band
Spring 2006
CS 332
3
Link-state Multicast
• Extend link-state unicast (easy)
– Add the set of groups that have members on a particular
link (LAN) to “state” for that link
– Use Dijkstra as before to create shortest-path multicast
tree
– Local router knows above “state” from IGMP messages
received from local host(s).
• Each host periodically announces group memberships to LAN
• If announcements stop (I.e. group not listed) router assumes
host has left particular group.
• Router keeps cache of all active source/group pairs
Spring 2006
CS 332
4
Spring 2006
CS 332
5
Distance-Vector Multicast
• More involved than link-state, since routers do not
know entire network topology
• Extend DVR in two stages:
– Broadcast method allowing sending of packet to all
networks on Internet
– Prune back above mechanism so that packets don’t get
flooded to networks that have no interest
Spring 2006
CS 332
6
Reverse-Path Broadcast (RPB)
• Recall (Destination, Cost, NextHop) tuples
• If router receives multicast packet from source S:
– Forward packet on all outgoing links (except one on
which packet arrived) if and only if packet arrived on
link that is the shortest path to S (thus the “reverse”)
– Floods packets from S without looping them toward S
• Two problems
– Flooding even to uninterested groups
– Packet forwarded to LAN over each router on LAN
Spring 2006
CS 332
7
A Partial Solution
• “Parent” router for each link (LAN) for each
source
–
–
–
–
Router with shortest path to S is parent for S
Tie goes to router with smallest address
Routers learn about parenthood from LSAs
Routers keep, for each source, a bit for each incident
link (LAN) indicating whether it is parent for that
source/link pair.
Spring 2006
CS 332
8
Reverse-Path Multicast (RPM)
• Goal: exclude packets for group G from networks
that have no members of G
• Again, two stages:
– Recognize when leaf network (I.e. only one router) has
no group members
– Propogate “no group G members here” message up
shortest-path tree.
• Augment (Destination,Cost) pairs leaf sends with the
set of groups for which leaf network is interested in receiving
packets
• Work way back up tree
• Lots of additional info in routing updates, so pruning done only
when source starts sending packets to group (use RPB until
then)
Spring 2006
CS 332
9
The MBone
• Multicast is not supported at present by many
routers in Internet. Multicast made available by
multicast backbone (MBone)
• Logical internet layered over Internet
–
–
–
–
Class D addresses
Tunnelling (to connect multicast supporting routers)
Distance-Vector Multicast Routing Protocol (DVMRP)
Exponential growth: thousands of networks on four
continents
Spring 2006
CS 332
10
Protocol Independent Multicast (PIM)
• Other methods don’t scale well in situations where
relatively small proportion of routers want to
receive traffic for a given group
• PIM has “sparse-mode” and “dense-mode”, we
discuss PIM-SM (sparse mode)
• Explicit Join and Prune messages sent to a router
designated as the rendezvous point (RP) for that
domain (complex protocol to handle network
partitioning,crash of RP, etc.)
• Construct shared or source-specific trees
Spring 2006
CS 332
11
PIM Tree Construction
• Router sends Join message to RP for group using IP
unicast (with sender field “wildcarded”)
• Each router along path sees Join, notes the interface on
which it was received, and makes forwarding table entry
that indicates that packets destined for this group go
through this interface (called an “all senders” entry)
• Router then determines interface on which to forward the
Join. This becomes only interface on which it will receive
packets for this group
• If new Join arrives for same group on different link, router
notes change, but no need to forward the Join.
Spring 2006
CS 332
12
PIM Example
Spring 2006
CS 332
13
Sending with PIM
• Host sends packet with group multicast address to
designated router (DR) on local network
• DR tunnels packet to RP using IP unicast
• RP receives packet, unpacks multicast packet, and
forwards it along the multicast tree
Spring 2006
CS 332
14
PIM Optimizations
• Tunneling is inefficient, so based on data rate, RP
can force group knowledge into intervening routers
– Send Join toward the sending host
– Routers create sender-specific state in routers, creating a
sender-specific tree distinct from the all senders tree
• Replace shared tree with source-specific tree
– Router at downstream end of tree sends Join message
toward source (not necessarily RP). Router must remain
on shared tree (in case new senders show up), but sourcespecific trees may be much shorter than those through RP
Spring 2006
CS 332
15
PIM Final Remarks
• PIM is protocol independent in sense that it can
use any unicast routing protocol (DVR, link-state,
etc), but is not independent of IP
• Note again tradeoff between scalability and
optimality
– Shared tree reduces state in routers to order of number
of groups, so more scalable than source-specific trees,
which provide optimality
Spring 2006
CS 332
16