Transcript IP Multicast

Multicast on the Internet
CSE 6590
Fall 2009
4/5/2016
1
Addressing
• Class D address
• Ethernet broadcast address (all 1’s)
• IP multicast using
– Link-layer (Ethernet) broadcast
– Link-layer (Ethernet) multicast
Both cases need filtering at IP layer.
• Source: unicast IP address S
Receivers: multicast group ID G
• Each group is identified by (S, G)
2
IPv4 Address Formats
3
Mapping from Class D IP adress to
Ethernet multicast adress
4
Reverse Path Forwarding
 rely on router’s knowledge of unicast
shortest path from it to sender
 each router has simple forwarding behavior:
if (multicast datagram received on incoming link on
shortest path back to center)
then flood datagram onto all outgoing links
else ignore datagram
Reverse Path Forwarding (2)
• Building a loop-free broadcast tree
• No knowledge of group membership
6
Reverse Path Forwarding
A
B
c
F
E
D
G
7
Spanning-Tree Broadcast
A
B
c
F
A
E
B
c
D
F
G
(a) Broadcast initiated at A
E
D
G
(b) Broadcast initiated at D
8
Internet Multicast Service Model
128.59.16.12
128.119.40.186
multicast
group
226.17.30.197
128.34.108.63
128.34.108.60
Multicast group concept: use of indirection
• a host “sends” IP datagrams to multicast group
• routers forward multicast datagrams to hosts that have
“joined” that multicast group
9
Multicast groups
 Class D Internet addresses reserved for multicast:
 Host group semantics:
o anyone can “join” (receive from) multicast group
o anyone can send to multicast group
o no network-layer identification to hosts of members
 Needed: infrastructure to deliver multicast-addressed
datagrams to all hosts that have joined that multicast
group
10
Multicast Protocols
Transport layer
• UDP
• Real-time Transport Protocol (RTP): for
multimedia content
• ReSerVation Protocol (RSVP): for bandwidth
reservation in a multicast distribution
11
Multicast Protocols (2)
Routing, delivery
• On a local network:
– Internet Group Management Protocol (IGMP)
– Multicast Listener Discovery (MLD): similar to IGMP
but for IPv6
• Intra-domain:
– MOSPF, PIM, DVMRP
• Inter-domain:
– Multicast Border Gateway Protocol (MBGP)
12
Joining a multicast group: 2-step process
• Local: host informs local multicast router of desire to join
group: IGMP (Internet Group Management Protocol)
• Wide area: local router interacts with other routers to
receive multicast datagram flow
– many protocols (e.g., DVMRP, MOSPF, PIM)
IGMP
IGMP
wide-area
multicast
routing
IGMP
13
IGMP: Internet Group Management Protocol
• Host: sends IGMP report when application joins
multicast group
– IP_ADD_MEMBERSHIP socket option
– hosts need not explicitly “unjoin” group when leaving
• Router: sends IGMP query at regular intervals
– hosts belonging to a multicast group must reply to
query
query
report
14
IGMP
• Router: Host
Membership Query
message broadcast on
LAN to all hosts.
• Host: Host Membership
Report message to
indicate group
membership
– randomized delay
before responding
– implicit leave via no
reply to Query
• Group-specific Query
• Leave Group message
– Last host replying to
Query can send explicit
Leave Group message
– Router performs groupspecific query to see if
any hosts left in group
– Introduced in RFC 2236
IGMP v3: current version
15
IGMP: Summary
• For membership management.
• Between a host on a subnet (Ethernet) and the router for
the subnet.
• The router periodically broadcast an IGMP hostmembership query message on its subnet.
• A host subscribes to a group replies by multicasting a
host-membership report message.
– Note: feedback implosion  uses a random timer.
• The report is sent 3 times (for reliability).
• IGMP-1: hosts send no report  leaving the group
IGMP-2: hosts send explicit host-membership leave
messages to reduce leave latency.
16
Truncated Broadcasting
• Extension of Reverse Path Forwarding
• No members of a group on a subnet  leaf router will
not forward packets of this group to the subnet (pruning).
• But does not reduce traffic in the core network
• More efficient multicast routing is needed!!!
17
Multicast Routing Approaches
• Minimum cost trees
– Minimum Steiner trees
• Shortest path trees
– Source-based trees
– Core-based trees
…we first look at basic approaches, then specific protocols
adopting these approaches
18
Minimum Steiner Trees
• Steiner Tree: minimum cost tree connecting all routers
with attached group members.
• Problem is NP-complete.
• Excellent heuristics exist.
• Not used in practice:
– computational complexity.
– information about entire network needed.
– monolithic: rerun whenever a router needs to
join/leave.
Shortest Path Tree
• Multicast cast forwarding tree: tree of shortest path
routes from source to all receivers.
– Dijkstra’s algorithm.
S: source
LEGEND
R1
1
2
R4
R2
3
R3
router with attached
group member
5
4
R6
router with no attached
group member
R5
6
R7
i
link used for forwarding,
i indicates order link
added by algorithm
Internet Multicasting Routing: DVMRP
• DVMRP: distance vector multicast routing
protocol, RFC1075.
• Flood and prune: reverse path forwarding,
source-based tree.
– initial datagram to multicast group flooded
everywhere via RPF
– routers not wanting the multicast data: send
prune messages to upstream neighbors
DVMRP Example
S: source
LEGEND
R1
1
2
R4
R2
3
R3
router with attached
group member
5
4
R6
router with no attached
group member
R5
6
R7
i
link used for forwarding,
i indicates order link
added by algorithm
DVMRP (2)
• Soft state: DVMRP router periodically (1 min.) “forgets”
that branches are pruned:
– mcast data again flows down unpruned branches
– downstream routers: reprune or else continue to
receive data
• Routers can quickly regraft to tree
– following IGMP join at leaf
• Odds and ends
– commonly implemented in commercial routers
– Mbone routing done using DVMRP
• Works well in small autonomous domains
DVMRP: Summary
• Distance Vector Multicast Routing Protocol
• Leaf router sends a prune message to neighbouring
routers when there is no group member on the subnet.
• Intermediate routers perform pruning whenever possible.
• Flooding and pruning are repeated periodically, when the
current state times out.
• Between flooding rounds, a host can re-join a group by
sending a graft message.
• Intermediate routers propagates the graft message
upstream until the path is re-connected.
24
MOSPF
• Extends OSPF for multicasting.
• Every router has the complete topology of its
autonomous system.
• A receiver joins a multicast group by exchanging IGMP
messages with its end-router.
• The end-router broadcasts the presence of this
destination (group membership) to the whole network.
• Each router maintains a group membership table [S,G,
<d1, d2, …>]
• A sender simply sends data packets as they are
available.
• Each router uses the network topology, the group
membership table, and the multicast group ID in the data
packets to compute the route(s) to the destination(s).
25
Core-Based Trees
• For many-to-many multicast
• CBT, PIM-SM, PIM-DM
• Purpose: to reduce the amount of routing info stored at
routers when a multicast group has a large number of
members and multiple senders.
• A multicast group requires a core (rendez-vous point).
• Receivers “join” the (shortest-path) tree rooted at the
core  only one tree per multicast group (used for
multiple senders).
• Sources send multicast data to the core, which then
multicasts the data to the tree.
26
MBone
• Multicast backbone of the Internet
• Was a long-running experimental approach to enabling
multicast between sites through the use of tunnels
• No longer operational
• Not all routers support multicast routing protocols and
IGMP.
• Connecting multicast-capable routers using (virtual) IP
tunnels
27
References
• Multicasting on the Internet and Its Applications, Sanjoy
Paul, Kluwer Academic Publishers, 1998.
28