Multicast Applications
Multicasting
News/sports/stock/weather updates Distance learning Configuration, routing updates, service location Pointcast-type push apps Teleconferencing (audio, video, shared whiteboard, text editor) Distributed interactive gaming or simulations Email distribution lists Content distribution; Software distribution Web-cache updates Database replication
2
Multicast: one sender to many receivers
Multicast: one sender to many receivers
Multicast: act of sending datagram to multiple receivers with single transmit operation analogy: one teacher to many students Question: how to achieve multicast
Multicast: act of sending datagram to multiple receivers with single transmit operation analogy: one teacher to many students Question: how to achieve multicast
Multicast via unicast
source sends N unicast datagrams, one addressed to each of N receivers
3
Network multicast
Router actively participate in multicast, making copies of packets as needed and forwarding towards multicast receivers
4
routers forward unicast datagrams
multicast receiver (red) not a multicast receiver (red)
Multicast routers (red) duplicate and forward multicast datagrams
Multicast: one sender to many receivers
Multicast Apps Characteristics
Multicast: act of sending datagram to multiple receivers with single transmit operation analogy: one teacher to many students Question: how to achieve multicast
Application-layer
Number of (simultaneous) senders to the group The size of the groups
Number of members (receivers) Geographic extent or scope Diameter of the group measured in router hops
multicast
end systems involved in multicast copy and forward unicast datagrams among 5 themselves
The longevity of the group Number of aggregate packets/second The peak/average used by source Level of human interactivity
Lecture mode vs interactive Data-only (eg database replication) vs multimedia
6
Internet Multicast Service Model
128.59.16.12 128.119.40.186
Multicast groups
class D Internet addresses reserved for multicast:
multicast group 226.17.30.197
128.34.108.63
128.34.108.60
multicast group concept: use of indirection hosts addresses IP datagram to multicast group routers forward multicast datagrams to hosts that have joined that multicast group
7
host group semantics: o anyone can join (receive) multicast group o anyone can send to multicast group o no network-layer identification to hosts of members needed: infrastructure to deliver mcastaddressed datagrams to all hosts that have joined that multicast group
Joining a mcast group: two-step process
IP Multicast Architecture
Service model
Host-to-router protocol (IGMP)
Routers Hosts
local: host informs local mcast router of desire to join group: IGMP (Internet Group Management Protocol) wide area: local router interacts with other routers to receive mcast datagram flow many protocols (e.g., DVMRP, MOSPF, PIM)
IGMP wide-area multicast routing IGMP IGMP
Multicast routing protocols (various)
10
IP Multicast Concepts
IP Multicast Concepts
Message sent to multicast group (of receivers)
Senders need not be group members A group identified by a single group address
Use group address instead of destination address in IP packet sent to group
Packets are not duplicated or delivered to destinations outside the group
Distribution tree constructed for delivery of packets Packets forwarded away from the source No more than one copy of packet appears on any subnet Packets delivered only to interested receivers => multicast delivery tree changes dynamically Network has to actively discover paths between senders and receivers
Groups can have any size; Group members can be located anywhere on the Internet Group membership is not explicitly known Receivers can join/leave at will
11
12
IGMP: Internet Group Management Protocol
IGMP
host: sends IGMP report when application joins mcast group IP_ADD_MEMBERSHIP socket option host need not explicitly unjoin group when leaving router: sends IGMP query at regular intervals host belonging to a mcast group must reply to query
query report
13
IGMP version 1 router: Host Membership Query msg broadcast on LAN to all hosts host: Host Membership Report msg to indicate group membership
randomized delay before responding implicit leave via no reply to Query
IGMP v2: additions include group-specific Query Leave Group msg
last host replying to Query can send explicit Leave Group msg router performs groupspecific query to see if any hosts left in group RFC 2236
14
RFC 1112
Goal:
find a tree (or trees) connecting routers having local mcast group members
tree: not all paths between routers used source-based: different tree from each sender to rcvrs shared-tree: same tree used by all group members
Multicast Routing: Problem Statement
Approaches for building mcast trees
Approaches: source-based
tree: one tree per source
shortest path trees reverse path forwarding
group-shared
tree: group uses one tree
minimal spanning (Steiner) center-based trees
we first look at basic approaches, then specific protocols adopting these approaches
Shared tree
Source-based trees
Shortest Path Tree
mcast
Reverse Path Forwarding
rely on routers knowledge of unicast shortest path from it to sender each router has simple forwarding behavior:
forwarding tree: tree of shortest path routes from source to all receivers
Dijkstras algorithm
S: source R1 1 R2 3 R3 4 R6 6 R7 2 R4 5 R5 i LEGEND router with attached group member router with no attached group member link used for forwarding, i indicates order link added by algorithm
if (mcast datagram received on incoming link on shortest path back to center) then flood datagram onto all outgoing links else ignore datagram
Reverse Path Forwarding: example
S: source R1 R2 R5 R3 R6 R7 R4 LEGEND router with attached group member router with no attached group member datagram will be forwarded datagram will not be forwarded
forwarding tree contains subtrees with no mcast group members no need to forward datagrams down subtree prune msgs sent upstream by router with no downstream group members
LEGEND R1 R2 P R5 P P R7 R4 router with attached group member router with no attached group member prune message links with multicast forwarding
Reverse Path Forwarding: pruning
S: source
result is a source-specific reverse SPT may be a bad choice with asymmetric links
R3
R6
Shared-Tree: Steiner Tree
Steiner
Center-based trees
single
Tree: minimum cost tree connecting all routers with attached group members problem is NP-complete excellent heuristics exists not used in practice:
computational complexity information about entire network needed monolithic: rerun whenever a router needs to join/leave
delivery tree shared by all one router identified as center of tree to join:
edge router sends unicast join-msg addressed to center router join-msg processed by intermediate routers and forwarded towards center join-msg either hits existing tree branch for this center, or arrives at center path taken by join-msg becomes new branch of tree for this router
Center-based trees: an example
Suppose R6 chosen as center:
LEGEND R1 3 R2 2 R5 R3 1 R6 R7 R4 router with attached group member router with no attached group member path order in which join messages generated
Internet Multicasting Routing: DVMRP
DVMRP: distance vector multicast routing protocol, RFC1075 flood and prune: reverse path forwarding, source-based tree
RPF tree based on DVMRPs own routing tables constructed by communicating DVMRP routers no assumptions about underlying unicast initial datagram to mcast group flooded everywhere via RPF routers not wanting group: send upstream prune msgs
DVMRP: continued
Tunneling
Q:
soft state: DVMRP router periodically (1 min.) forgets branches are pruned:
mcast data again flows down unpruned branch downstream router: reprune or else continue to receive data
How to connect islands of multicast routers in a sea of unicast routers?
routers can quickly regraft to tree
following IGMP join at leaf
odds and ends
commonly implemented in commercial routers Mbone routing done using DVMRP
mcast datagram encapsulated inside normal (non-multicastaddressed) datagram normal IP datagram sent thru tunnel via regular IP unicast to receiving mcast router receiving mcast router unencapsulates to get mcast datagram
physical topology
logical topology
PIM: Protocol Independent Multicast
Consequences of Sparse-Dense Dichotomy:
Dense
not dependent on any specific underlying unicast routing algorithm (works with all)
Sparse:
two different multicast distribution scenarios : Dense: Sparse:
group members densely packed, in close proximity. bandwidth more plentiful # networks with group members small wrt # interconnected networks group members widely dispersed bandwidth not plentiful
group membership by routers assumed until routers explicitly prune data-driven construction on mcast tree (e.g., RPF) bandwidth and nongroup-router processing profligate
no membership until routers explicitly join receiver- driven construction of mcast tree (e.g., centerbased) bandwidth and nongroup-router processing conservative
PIM- Dense Mode
flood-and-prune RPF, similar to DVMRP but
underlying unicast protocol provides RPF info for incoming datagram less complicated (less efficient) downstream flood than DVMRP reduces reliance on underlying routing algorithm has protocol mechanism for router to detect it is a leaf-node router
PIM - Sparse Mode
center-based approach router sends join msg to rendezvous point (RP)
intermediate routers update state and forward join
R1 join R2 join R6 join
R4
after joining via RP, router can switch to source-specific tree
increased performance: less concentration, shorter paths
R5 R7 rendezvous point
R3
all data multicast from rendezvous point
PIM - Sparse Mode
Multicast OSPF (MOSPF)
Extend
sender(s): unicast data to RP, which distributes down RP-rooted tree RP can extend mcast tree upstream to source RP can send stop msg if no attached receivers
no one is listening!
R1 join R2 join R6 join
R4
R5 R7 rendezvous point
R3
all data multicast from rendezvous point
OSPF to support multicast Multicast-capable routers flag link state routing advertisements Link-state packets include multicast group addresses to which local members have joined Routing algorithm augmented to compute shortest-path distribution tree from a source to any set of destinations
32
Example of MOSPF
Source 1 Z W Q T Receiver 1 Receiver 2
33
Link Failure/Topology Change
Source 1 Z W Q T Receiver 1 Receiver 2
34
Group Membership Change
Source 1 Z W Q T Receiver 1 Receiver 2
35
MOSPF: Impact on Route Computation
Cant
Receiver 3
pre-compute all source multicast trees Compute tree on-demand when first packet from a source S to a group G arrives New link-state advertisement
May lead to addition or deletion of outgoing interfaces if it contains different group addresses May lead to re-computation of entire tree if links are changed
36
