Transcript slides - University of California, Berkeley

Multicast
EECS 122: Lecture 16
Department of Electrical Engineering and Computer Sciences
University of California
Berkeley
Broadcasting to Groups

Many applications are not one-one





Webcasts
Radio/TV
Push/IE Channels
Packets must reach a Group rather than a
single destination



Broadcast
Group collaboration
Proxy/Cache updates
Resource Discovery
Chats
Video Conferencing
Audio Conferencing
Group membership may be dynamic
More than one group member might be a
source
Idea: After a group is established



Caches and
Proxies
Interested receivers join the group
The network takes care of group
management
Recall RSVP
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
2
The Multicast service Model

Membership access control

R0
S
[G, data]
Net
R1


.
.
.
Sender access control


Rn-1


March 18, 2003
open group: anyone can
join
closed group: restrictions on
joining
anyone can send to group
anyone in group can send
to group
only one host can send to
group
Packet delivery is best effort
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
3
Multicast and Layering

Multicast can be implemented at different
layers

data link layer


network layer


e.g. IP multicast
application layer


e.g. Ethernet multicast
e.g. as an overlay network like Kazaa
Which layer is best?
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
4
Multicast Implementation Issues
How are multicast packets addressed?
 How is join implemented?
 How is send implemented?


How does multicast traffic get routed?


This is easy at the link layer and hardest at the network
layer
How much state is kept and who keeps it?
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
5
Ethernet Multicast


Reserve some Ethernet MAC addresses for multicast
To join group G




To send to group G



network interface card (NIC) normally only listens for packets
sent to unicast address A and broadcast address B
to join group G, NIC also listens for packets sent to multicast
address G (NIC limits number of groups joined)
implemented in hardware, so efficient
packet is flooded on all LAN segments, like broadcast
can waste bandwidth, but LANs should not be very large
Only host NICs keep state about who has joined  scalable to
large number of receivers, groups
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
6
Limitations of Data Link Layer Multicast

Single LAN
limited to small number of hosts
 limited to low diameter latency
 essentially all the limitations of LANs compared to
internetworks


Broadcast doesn’t cut it in larger networks
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
7
IP Multicast: Interconnecting LANS




Interconnected LANs
LANs support link-level
multicast
Map globally unique
multicast address to LANbased multicast address
(LAN-specific algorithm)
IP Group addresses are
class D addresses

1110/28 or 224.0.0.0 to
239.255.255.255
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
8
Internet Group Management Protocol
IGMP

Operates between Router and local Hosts,
typically attached via a LAN (e.g., Ethernet)

1.
Router periodically queries the local Hosts for
group membership information

2.
3.
4.

Can be specific or general
Hosts receiving query set a random timer
before responding
First host to respond sends membership
reports
All the other hosts observe the query and
suppress their own repots.
To Join send a group send an unsolicited Join


Query response architecture
Start a group by joining it
To leave don’t have to do anything

Report
Query to
224.0.0.1
Suppresses
Report
Soft state
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
9
Naïve Routing Option: Don’t change
anything
Point-to point routing
[R0, data]
S
[R1, data]
R0
Net
[Rn-1, data]
R1
.
.
.
Rn-1
Group abstraction not implemented in
the network
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
10
This approach does not scale…
Broadcast
Center
March 18, 2003
Backbone
ISP
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
11
Instead build trees
Copy data at routers
At most one copy of a data packet per link
Broadcast
Center
Backbone
ISP
•Routers keep track of
groups in real-time
•“Path” computation is Tree
computation
March 18, 2003
•LANs implement layer 2
multicast by broadcasting
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
12
Routing: Approaches

Kinds of Trees




Tree Computation Methods
Intradomain Update methods




Shared Tree
Source Specific Trees
Build on unicast Link State: MOSPF
Build on unicast Distance Vector: DVMRP
Protocol Independent: PIM
Interdomain routing: BGMP

This is still evolving…
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
13
Source Specific Trees
5
7
Each source is the route of
its own tree.
4
8
6
11
2
1
March 18, 2003
10
3
13
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
12
14
Source Specific Trees
5
7
Each source is the route of
its own tree.
One tree for each source
4
8
6
11
2
1
10
3
13
12
Can pick “good” trees but
lots of state at the routers!
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
15
Shared Tree
5
7
One tree used by all
4
8
6
11
2
1
10
3
13
12
Can’t pick “good” trees but
minimal state at the routers
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
16
Tree Computation
2
4
•A tree which connects all
the group nodes is a
Steiner Tree
•Finding the min cost
Steiner Tree is NP hard
2
5
1
7
2
8
2
12
6
15
2
2
1
1
13
12
March 18, 2003
12
7
11
3
11
10
2
3
2
2
12
2
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
17
Tree Computation
2
4
•A tree which connects all
the group nodes is a
Steiner Tree
•Finding the min cost
Steiner Tree is NP hard
2
5
1
7
2
8
2
12
6
15
2
2
1
1
13
12
March 18, 2003
12
7
11
3
11
10
2
3
2
2
12
2
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
18
Tree Computation
2
4
•A tree which connects all
the group nodes is a
Steiner Tree
•Finding the min cost
Steiner Tree is NP hard
•The tree does not span
the network
•Heuristics are known
2
5
1
7
2
8
2
12
6
15
2
2
1
1
13
12
March 18, 2003
12
7
11
3
11
10
2
3
2
2
12
2
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
19
Tree Computation
2
4
•A tree that connects all
of the nodes in the graph
is a spanning tree
•Finding a minimum
spanning tree is much
easier
2
5
1
7
2
8
2
12
6
15
2
2
1
1
13
12
March 18, 2003
12
7
11
3
11
10
2
3
2
2
12
2
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
20
Tree Computation
2
4
•A tree that connects all
of the nodes in the graph
is a spanning tree
•Finding a minimum
spanning tree is much
easier
2
5
1
7
2
8
2
12
6
15
2
2
1
1
13
12
March 18, 2003
12
7
11
3
11
10
2
3
2
2
12
2
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
21
Tree Computation
2
4
•A tree that connects all
of the nodes in the graph
is a spanning tree
•Finding a minimum
spanning tree is much
easier
•Prune back to get a
multicast tree
2
5
1
7
2
8
2
12
6
15
2
2
1
1
13
12
March 18, 2003
12
7
11
3
11
10
2
3
2
2
12
2
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
22
Tree Computation
2
4
•A tree that connects all
of the nodes in the graph
is a spanning tree
•Finding a minimum
spanning tree is much
easier
•Prune back to get a
multicast tree
2
5
1
7
2
8
2
12
6
15
2
2
1
1
13
12
March 18, 2003
12
7
11
3
11
10
2
3
2
2
12
2
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
23
Link State Protocols e.g. MOSPF





Use in conjunction with a link state protocol
for unicast
Enhance the LSP updates with group
membership
Compute best tree from source
Flood Membership in link state
advertisements
Dynamics are a problem
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
24
Distance Vector Multicast Routing
An elegant extension to DV routing
 Use shortest path DV routes to determine if
link is on the source-rooted spanning tree

March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
25
Distance Vector Multicast


Extension to DV unicast routing
Packet forwarding
 iff incoming link is shortest path to
source
 out all links except incoming
 Reverse Path Flooding (RPF)
 packets always take shortest path


s:2
s:3
s:1
s:2
s
r
assuming delay is symmetric
Issues
 Every link receives each multicast
packet, even if no interested hosts:
Pruning
 Some links (LANs) may receive
multiple copies: Reverse Path
Broadcasting
March 18, 2003
s:3
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
26
Example

Flooding can cause a given packet to be sent multiple times
over the same link
S
x
y
a
duplicate packet
z
b

Solution: Reverse Path Broadcasting
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
27
Reverse Path Broadcasting (RPB)


Extend DV to eliminate
duplicate packets
Choose parent router for each
link
router with shortest path to
source
 lowest address breaks ties
 each router can compute
independently from already
known information
 each router keeps a bitmap with
one bit for each of its links
s:3
C


s:2
s:3
s:1
s:2
s
r
P
Only parent forwards onto link
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
28
Identify Child Links
Routing updates identify parent
 Since distances are known, each router can
easily figure out if it's the parent for a given
link
 In case of tie, lower address wins

March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
29
Reverse Path Broadcasting (RPB)
S
5
x
forward only
to child link
child link of x
for S
6
y
a
z
b
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
30
Don’t really want to flood!



1.
This is still a broadcast algorithm – the
traffic goes everywhere
Need to “Prune” the tree when there are
subtrees with no group members
Strategy
Identify leaf networks with no members

2.
IGMP
Propagate this information up the subtree
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
31
How much to Prune?


Truncated Reverse Path Broadcasting:
Prunes to prevent flooding of all packets
Reverse Path Multicasting: More aggressive.
Scale router state with the number of active
groups

Use on-demand pruning so that router group state
scales with number of active groups (not all
groups)
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
32
Pruning Details

Prune (Source,Group) at leaf if no members


If all children of router R prune (S,G)


Propagate prune for (S,G) to parent R
On timeout:




Send Non-Membership Report (NMR) up tree
Prune dropped
Flow is reinstated
Down stream routers re-prune
Note: again a soft-state approach
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
33
Pruning Details

How to pick prune timers?
Too long  large join time
 Too short  high control overhead


What do you do when a member of a group
(re)joins?

Issue prune-cancellation message (grafts)
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
34
MBONE


What to do if most of the routers in the internet are
not multicast enabled?
Tunnel between multicast enabled routers
IPM
IP


IPM
Creates an “overlay” network but both operate at
Level 3…
This is how multicast was first deployed
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
35
RMP Scaling

State requirements:


O(Sources  Groups) active state
How to get better scaling?
Hierarchical Multicast
 Core-based Trees

March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
36
Core Based Trees (CBT)

Pick a “rendevouz point” for the group called the
core.



Shared tree
Unicast packet to core and bounce it back to
multicast group
Tree construction is receiver-based
Joins can be tunneled if required
 Only nodes on One tree per group tree involved


Reduce routing table state from O(S x G) to O(G)
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
37
Example
Group members: M1, M2, M3
 M1 sends data

root
M1
M2
M3
control (join) messages
data
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
38
Disadvantages
Sub-optimal delay
 Single point of failure



Core goes out and everything lost until error
recovery elects a new core
Small, local groups with non-local core
Need good core selection
 Optimal choice (computing topological center) is
NP complete

March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
39
PIM

Popular intradomain method


Recognizes that most groups are very sparse


UUNET streaming using this
Why have all of the routers participate in keeping
state?
Two modes


Dense mode: flood and prune
Sparse mode: Core-based shared tree approach
with a twist
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
40
PIM Sparse Mode





Routers explicitly issue JOIN and Prune messages to the Core
Recievers typically send a Join message of the form (*,G)
 As it propagates towards the core it establishes a new branch of
the shared tree
To send on the tree, tunnel to the core and then traverse the
shared tree
 This can lead to bad performance
To optimize sending from S, the core can send Join message of
the form (S,G) to S.
 Creates a specific path from S to the core
Receivers can send (S,G) messages as well to S and gradually
replace the shared tree with a source specific tree
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
41
Problems with
Network Layer Multicast

Scales poorly with number of groups
A router must maintain state for every group that
traverses it
 many groups traverse core routers


Supporting higher level functionality is difficult
NLM: best-effort multi-point delivery service
 Reliability and congestion control for NLM
complicated


Deployment is difficult and slow

Difficult to debug problems given the service
model
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
42
NLM Reliability


Assume reliability through retransmission
Sender can not keep state about each receiver
e.g., what receivers have received
 number of receivers unknown and possibly very large


Sender can not retransmit every lost packet


even if only one receiver misses packet, sender must
retransmit, lowering throughput
N(ACK) implosion

described next
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
43
(N)ACK Implosion


(Positive) acknowledgements
 ack every n received packets
 what happens for multicast?
Negative acknowledgements
 only ack when data is lost
 assume packet 2 is lost
R1
S
3
2
1
R2
R3
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
44
NACK Implosion

When a packet is lost all receivers in the subtree originated at the link where the packet is
lost send NACKs
3
R1
2?
S
3
R2
2?
2?
3
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
R3
45
Scalable Reliable Multicast (SRM)





Randomize NACKs (request repairs)
All traffic including request repairs and repairs are
multicast
A repair can be sent by any node that heard the
request
A node suppresses its request repair if another node
has just sent a request repair for the same data item
A node suppresses a repair if another node has just
sent the repair
March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
46
Avoiding NACK Implosions

Every node estimates distance (in time)
from every other node


Information is carried in session reports (< 5%
of bandwidth)
Nodes use randomized function of
distance to decide when to
Send a request repair
 Reply to a request repair

March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
47
ISPs charge by bandwidth
Broadcast
Center
Backbone
ISP
Remember what
interdomain protocols
optimize for….
March 18, 2003
They make more money
without multicast
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
48
Application Layer Multicast



Provide multicast functionality above the IP unicast
Gateway nodes could be the hosts or multicast
gateways in the network
Advantages
No multicast dial-tone needed
 Performance can be optimized to application


Loss, priorities etc.
More control over the topology of the tree
 Easier to monitor and control groups


Disadvantages
Scale
 Performance if just implemented on the hosts (not
gateways)

March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
49
Summary


Large amount of work on multicast routing
Major problems
preventing flooding
 minimizing state in routers
 denial-of-service attacks
 deployment


Multicast can be implemented at different layers
lower layers optimize performance
 higher layers provide more functionality


IP Multicast still not widely deployed
Ethernet multicast is deployed
 application layer multicast systems are promising

March 18, 2003
A. Parekh, EE122 S2003. Revised and
enhanced F'02 Lectures
50