Transcript Chapter 4

Chapter 4
IP Multicast
Professor Rick Han
University of Colorado at Boulder
[email protected]
Announcements
• Netstat portion of Homework #3 on Web,
due March 12 (two weeks)
• Programming Assignment #2 coming Friday…
• Midterm March 14
• Next, IP multicast
Prof. Rick Han, University of
Colorado at Boulder
Network Topology for
Programming Assignment #2
1
B
7
4
A
3
1
C
4
E
D
2
F
1
1. Distance Vector Routing
2. Link State Routing
Figure 1
Prof. Rick Han, University of
Colorado at Boulder
Recap of Previous Lecture
• More on Hierarchy in the Internet
•
•
•
BGP, IBGP
OSPF
Subnets and CIDR prefixes
•
•
Dynamic IP address
Local client broadcasts to DHCP Relay, which unicasts
to a DHCP Server
• DHCP
• ICMP
•
•
•
•
Reports IP packet delivery errors back to source
Ping: ICMP echo and echo reply, “smurf” attack
Traceroute: ICMP time expired
Router advertisement and solicitation
Prof. Rick Han, University of
Colorado at Boulder
IP Multicast
• Unicast: one source to one destination
• Broadcast: one source to every destination
• Multicast: one source to N destinations
– Variant: N sources to N destinations
• Application Scenarios:
– Video conference
– Audio concert
– Interactive games
• Example:
A
Multicast
Receiver
6
1
3
– C wants to multicast
B
4
to D and F
Multicast
9
CProf. Rick Han, University of
Sender
Colorado at Boulder
2
1
E
1
D
Multicast
Receiver
F
IP Multicast (2)
• How do we multicast 1->N efficiently?
– N unicast connections can waste bandwidth
over shared links
• not scalable: sender would have to send 100,000
copies of the same packet to 100,000 subscribers
– Hint: use the shortest path spanning tree to
efficiently route multicast packets
Prof. Rick Han, University of
Colorado at Boulder
Link-State IP Multicast
• Dijkstra gives us the shortest path
spanning tree
– Root B of multicast tree sends packets only to
nearest neighbors on tree, rather than to
100,000 members
– Neighbors forward to their neighbors along
shortest path tree, and so on…
A
6
– Also called MOSPF
1
3
4
2
1
B
9
CProf. Rick Han, University of D
Colorado at Boulder
E
1
F
Link-State IP Multicast (2)
• How does a router know an IP packet is a
multicast packet, and not a unicast packet?
– IP packets have a special multicast address
– Class D IP addresses: top 4 bits are “1110” followed by
28 bits to identify the multicast “group” address G
• Not all nodes want to be part of the multicast
tree
– Participating nodes announce that they want to be
part of the tree
– A Designated Router on each LAN hears this and
floods Link State Packets that this LAN has a
multicast group member
• All routers learn multicast membership of entire network
Prof. Rick Han, University of
Colorado at Boulder
Link-State IP Multicast (3)
• Forwarding of packets:
– When a router R receives a packet from S
with destination multicast address G, it
• Performs Dijkstra calculation with S as root (not R)
if not already in cache
• Finds itself (R ) in tree
• For each subtree from R with a group member,
– Cache info for this subtree
A
– Forward packet to
subtree
3
– Example: S=B,
R=E
Sender
4
B
9
6
2
1
CProf. Rick Han, University of D
Colorado at Boulder
Member
1
E
1
Member
F
Distance Vector Multicast
(DVMRP)
• How do we use distance vectors to achieve
multicast?
– Dijkstra’s shortest path tree was more intuitive
– Distance vectors tell us next-hop path for shortest
route to destination
– Basic method: Flood, then Prune
• Flood: Reverse-Path Broadcast
– When receiving a multicast packet to group G from
source S
• Does packet arrive from the shortest-hop link to S?
• If yes, then multicast on all other outgoing links
– This efficiently floods the network
• Any source can send
to any node along a shortest hop tree
Prof. Rick Han, University of
Colorado at Boulder
DVMRP (2)
• Flooding Example : Reverse-Path Broadcast
– When E receives a multicast packet to group G from
source S=C,
• Does packet arrive from the shortest-hop link to B?
• Yes, it arrived on B-E link which is next hop using the
spanning tree centered on E
• Since yes, then multicast
on all other outgoing
links
– To A, F, and D
A
– This floods the network
• Compare to LSP’s
reliable flooding
4
6
1
3
2
1
B
9
CProf. Rick Han, University of D
Colorado at Boulder
E
1
F
DVMRP (3)
• Problems with Reverse-Path Broadcast
– Since we’re flooding on all outgoing links, then
multiple routers on same Ethernet send copies
of same packet
• Solution: assign a parent router on each link. For
each source S, the parent router is the one closest
to S.
A
Parent
6
1
3
B-C link is
Ethernet LAN
4
2
1
B
9
CProf. Rick Han, University of D
Colorado at Boulder
E
1
F
DVMRP (4)
• Problems with Reverse-Path Broadcast
– Flooding the network reaches nodes who don’t want to
be part of the multicast group
– Solution: Prune using Reverse-Path Multicast
• Same “parent” router knows it’s a leaf when it is the only
router in a network
• Each host that is a member of G periodically broadcasts its
membership
• Parent router hears this, and will forward multicast packets
to this LAN
• If parent hears no members, then sends “no members” up the
shortest path tree
Prof. Rick Han, University of
Colorado at Boulder
DVMRP (5)
• Pruning Example:
– B sends to multicast group G consisting of F and D
• This message floods
• E sends a request to its leaf nodes: is anyone part of group
G?
– F and D respond, A does not
• E prunes A (remembers not to forward to A when it receives
a multicast dest addr G)
• C is also pruned from B
A
6
Sender
4
3
2
1
B
9
CProf. Rick Han, University of D
Colorado at Boulder
Member
1
E
1
Member
F
Protocol Independent Multicast
(PIM)
• Problems with MOSPF and DVMRP
– Each router has to have state
– Flooding is costly in DVMRP
• Routers not part of multicast group are flooded, then prune
via “No members” messages
– When only a few “sparse” nodes in multicast tree,
then flooding and state storage become excessive
A
6
1
3
4
2
1
B
9
CProf. Rick Han, University of D
Colorado at Boulder
E
1
F
PIM (2)
• PIM “sparse” mode
– Create a Rendezvous Point (RP) for each multicast
group
– From a multicast tree rooted from the well-known RP
• Reverse path tree formed from unicast Joins by leaf nodes
– Senders unicast to RP, which then multicasts along
tree
A
6
1
3
Rendezvous
Point B
2
1
E
4
9
CProf. Rick Han, University of D
Colorado at Boulder
1
F
PIM (3)
• PIM “sparse” mode
– If a particular sender transmits frequently
then
• Receiver sees many packets with
<source IP addr, multicast group addr>
• Then, receiver sends a Join to the source
• Reverse path multicast tree is formed to the
source, rather than to RP
Prof. Rick Han, University of
Colorado at Boulder
Internet Group Management
Protocol (IGMP)
• Used to join and leave multicast groups
• A multicast-enabled router on a LAN sends
membership_query IGMP message
– “Is anyone part of multicast group G?”
• A multicast-enabled host replies with an IGMP
membership_report
– “Yes, I’m part of multicast group G”
– Host can send unsolicited membership_report to
explicitly join a multicast group
– Router only needs to know that one host on LAN is a
member of group G, not which host nor how many
hosts
• Feedback suppression
Prof. Rick Han, University of
Colorado at Boulder
Other Multicasting Issues
• Source doesn’t have to be a member of a
multicast tree!
– Any malicious user can overwhelm a multicast tree
• Source doesn’t have to know in advance who is in
multicast tree
– Clean decoupling of senders and receivers
• Receiver-driven multicast model [Deering, 1990]
– Any host can send an IGMP Join message to its
attached IP multicast-enabled router
• No control over who joins an IP multicast group
– How do you prevent someone from subscribing at the
IP router level?
– Once in a multicast
group, can eavesdrop
Prof. Rick Han, University of
Colorado at Boulder
Other Multicasting Issues (2)
• Multicast is unreliable
– Uses UDP datagrams over IP multicast datagrams
• How do we design a reliable multicast protocol?
– Suppose B reliably multicasts, and F and D are both
members of multicast tree
– F and D both send ACK’s upstream
– Source can get swamped with ACK’s
– Solution: put ACK filters in
A
6
intermediate routers
• Would have to
understand TCP
semantics
• Controversial
1
3
4
2
1
B
9
CProf. Rick Han, University of D
Colorado at Boulder
E
1
F