Transcript CN-recitation13

Communication Networks
Recitation 13
Multicast Routing
Comnet 2010
1
The Problem
Traditional unicast model does not scale
– Millions of clients
– Server and network meltdown
Comnet 2010
2
Solution: IP Multicast
• Source sends single stream
• Routers split stream towards all clients
• Guarantee only one copy in each link
Comnet 2010
3
Multicast Routing Tree
Multicast Routing Protocol
On tree relay router
IGMP
Router with directly
attached group members
Comnet 2010
4
Internet Group Management
Protocol (IGMP)
• Used by routers to learn about Multicast
Group Memberships on their directly
attached subnets
• Implemented over IP
• Designated Router
– Each network has one Querier
– All routers begin as Queriers
– Router with the lowest IP address chosen
Comnet 2010
5
How IGMP Works
routers:
Q
hosts:
one router is elected the “querier”
querier periodically sends a Membership Query message
to the all-systems group (224.0.0.1), with TTL = 1
on receipt, hosts start random timers (between 0 and 10
seconds) for each multicast
group to which they belong
Comnet 2010
6
How IGMP Works (cont.)
Q
G
G
G
G
when a host’s timer for group G expires, it sends a
Membership Report to group G, with TTL = 1
other members of G hear the report and stop their timers
routers hear all reports, and time out non-responding
groups
Comnet 2010
7
Shortest Path Tree (SPT)
• Source Based Tree: Rooted at the source,
composed of the shortest paths between
the source and each of the receivers in
the multicast group.
• If the routing metric used is the latency
between neighbors, the resulted tree will
minimize delay over the multicast group.
• Example: DVMRP.
Comnet 2010
8
Distance-Vector Multicast
Routing Protocol (DMVRP)
DVMRP consists of two major components:
(1) a conventional distance-vector routing
protocol (like RIP)
(2) a protocol for determining how to forward
multicast packets, based on the routing table
and routing messages of (1)
Comnet 2010
9
Example Topology
g
g
s
g
Comnet 2010
10
Phase 1: Flooding
g
g
s
g
Comnet 2010
11
Phase 2: Pruning
g
g
prune (s,g)
s
prune (s,g)
g
Comnet 2010
12
Steady State
g
g
g
s
g
Comnet 2010
13
Joining on New Receivers
g
g
g
report (g)
graft (s,g)
s
graft (s,g)
g
Comnet 2010
14
Steady State after Joining
g
g
g
s
g
Comnet 2010
15
Steiner Minimal Tree (SMT)
• Shared Tree: All sources use the same
shared tree.
• SMT is defined to be the minimal cost
subgraph (tree) spanning a given
subset of nodes in a graph
• Approximate SMT: KMB
Comnet 2010
16
A Steiner Tree Example
10
10
4
10
3
5
2
1
3
2
1
• Which is the Steiner tree for green and
red nodes?
Comnet 2010
17
A Steiner Tree Example:
Solution
10
10
4
10
3
5
2
1
3
2
1
• Shortest Path tree =/= Steiner Tree
• 14 + 13 =/= 16
Comnet 2010
18
KMB Algorithm
• G=(V,E), terminals R
• Step 1: Construct a complete directed distance
graph of R: G1=(V1,E1,c1).
• Step 2: Find the min spanning tree T1 of G1.
• Step3: Construct a subgraph GS of G by replacing
each edge in T1 by its corresponding shortest path in
G.
• Step 4: Find the min spanning tree TS of GS.
• Step 5: Construct a Steiner tree TH from TS by
deleting leaves that are not in R.
Comnet 2010
19
KMB Algorithm Cont.
Due to [Kou, Markowsky and Berman 81’]
Worst case time complexity O(|S||V|2).
Cost no more than 2(1 - 1/l) *optimal cost
where l = number of leaves in the steiner tree.
Comnet 2010
20
KMB Example
A
Destination Nodes
4
A
B
1
10
I
1/2
1/2
G
1
B
8
1
F
2
C
9
4
4
4
A
C
1
E
2
4
H
D
B
I
1/2
1/2
1
G
4
1
1
4
G1
A
H
D
4
1
4
C
T1
D
B
1
1
F
2
C
E
2
D
Gs
G
Comnet 2010
21
KMB Example Cont.
A
A
1
1
H
1/2
1/2
G
B
1
1
F
2
C
I
I
1
1
E
B
1
1
F
2
2
C
D
Ts
E
2
D
TH
Comnet 2010
22