CS716
Advanced Computer Networks
By Dr. Amir Qayyum
1

1


Lecture No. 27 

2


Multicast

3


Internetworking
• Basics of internetworking (heterogeneity)
– IP protocol, address resolution, control messages …

• Routing
• Global internets (scale)
– Virtual geography and addresses
– Hierarchical routing

• Future internetworking: IPv6
• Multicast traffic
• MPLS
4

Internet Multicast Outline
•
•
•
•
•

Motivation and challenges
Support strategy
IP multicast service model
Multicast in the Internet
Routing
– Review of ELAN techniques
– Multicast routing
• Limitations
5


Multicast
•
•
•
•

Unicast: one destination
Broadcast: all destinations
Multicast: subset of destinations
When is multicast useful ?

– Send data to multiple receivers at once
• Videoconferencing, video­on­demand, 
telecollaboration
• Software update to group of customers
– Limited broadcast/self­defined multicast
• Send question to unknown receiver
• Resource discovery; Distributed database
6


Multicast
• Why not just use broadcast/unicast ?
– Broadcast not supported outside of LAN
– Unicast sends multiple copies across common links

• Multicast support
– Often supported by hardware in LAN’s (as 
broadcast, if not multicast)
– But difficult to extend in scalable manner

• Multicast challenges
– Efficient distribution on an internetwork
– Specification of recipient group (abstraction must 
support self­definition)
7


Multicast Support Strategy
• IPv4 used as basis for experimental solutions
– Use class D addresses (1110 <28 bits>)

– Demonstrated with MBone
– Uses tunneling

• Multicast integrated into IPv6
• Internet Group Management Protocol (IGMP)

• Several routing/forwarding schemes:
– Distance­vector
– Link­state
– Protocol­independent
8


IP Multicast Service Model
• Each group uses a single address
– Class D addresses (1110 <28 bits>)
– Some are well­known, some are dynamically assigned
• Group membership
– Members located anywhere in the Internet
– Number of receivers is arbitrary
– Members can join/leave dynamically
– Hosts can belong to more than one group
9


IP Multicast Service Model
• Senders simply use group address as destination
– Sender need not be in group
– LAN loopback needed for sender in group


• Multicast scope
– LAN (local scope)
– Administrative scope (e.g. campus), may overlap, can 
assign group addresses dynamically
– TTL scope (no more than N hops)

• Scope is exposed to protocols and applications 
(by exposing IP TTL)
10


IP Multicast Service Model

• Multicast reception requires membership in 
group
– Internet Group Management Protocol 
(IGMP), RFC 1112
– New operations to join and leave group
– LAN routers track local membership
– Forwarding depends on routing scheme
– Last hop typically uses LAN broadcast
• Packet reception same as IP unicast
11


Internet Multicast Backbone ­ MBone
•
•
•
•


Existing infrastructure for multicast in the Internet
Multicast route propagation using DVMRP
Problem: most IP routers do not support multicast
Solution: tunneling by multicast­capable routers
– Encapsulate multicast traffic in IP packets
– Send to other multicast­capable routers
– Recipients unpack & forward original multicast packet

• Passes through multicast­incapable areas of 
Internet
12


ELAN Multicast Techniques
• Direct support (Ethernet)
– Application subscribes to group
– IP layer notifies Ethernet card to listen to 
packets with group address
• Support through broadcast (LANE)
• Flooding in ELANs
– Each packet sent on all but incoming link
– Switches must remember each packet!
• Spanning tree: every host gets one copy
13


ELAN Multicast Techniques
• Spanning tree selection
– Elect a leader; spanning tree is shortest path to leader 

(Perlman)
– Distribute topology everywhere, compute in parallel 
(link­state)

• Problems with spanning trees
– Bandwidth wasted for groups with few receivers; 
Solution: prune LAN’s with no receivers from tree
– For very large ELAN’s, no single tree is efficient; 
Solution: define tree per group or tree per source

• The same solutions are used in the Internet!
14


Spanning Tree Tradeoffs
• Tree per group or tree per source ?
• Per group advantage
– One routing entry per group

• Per source advantages
– More efficient distribution
– Spreads load better across links
– Leverage unicast routing tables
15


Multicast Routing in the Internet
• Multicast Open Shortest Path First 
(MOSPF)
• Distance­Vector Multicast Routing Protocol 

(DVMRP, used in MBONE)
• Protocol­Independent Multicast (PIM)
– Deals with scalability issues of above protocols
– Dense Mode (PIM­DM)
– Sparse Mode (PIM­SM)
16


Multicast Routing in the Internet
• How do senders find receivers?
– Receivers inform all senders of interest (MOSPF)
– Send to all receivers; uninterested receivers prune 
(DVMRP, PIM­DM)
– Agree on set of rendezvous points (PIM­SM)

• Types of distribution trees
– Separate tree from each sender (DVMRP, 
MOSPF, PIM­DM, PIM­SM)
– Tree rooted at rendezvous point (PIM­SM)
17


Link State Multicast (MOSPF)
• Each host on a LAN
– Periodically announces its group memberships, via 
Internet Group Management Protocol (IGMP)

• Extend LSP to include set of groups with 
members on a given LAN
• MOSPF routing extends OSPF

– Uses Dijkstra’s algorithm
– Computes shortest­path spanning tree for source­
group pairs
– Forward packet on local portion of tree
18


Link State Multicast (MOSPF)
• Tree computation
– Can’t precompute for all source­group pairs
– Compute on demand when first packet from a 
source S to a group G arrives
– Cache trees for active source­group pairs
– Recompute when link­state changes

• Scalability limitations
– Reasonable intra­AS scalability
– But meaningless for inter­AS
– Source­group pairs scale with sources (needs to 
be hierarchical)
19


Distance Vector Multicast (DVMRP)
• Idea
– Graph of directed next­hop edges to a destination S 
form a tree
– Use reverse edges to broadcast from S
• Implementation (Reverse Path Broadcast, or RPB)
– Forward multicast packet on all links

– If and only if packet came from next hop for packet 
source
• Avoid repetition on LAN’s
– Assign parent router for each LAN
– Has shortest path to source, ties broken by ID
– Track parenthood via vector exchanges
20


RPB and RPM
M
M

M
M

G
M
M

M
M

Member of 
multicast 
group G

RPM from S to G
RPB from S


SS

Unicast route to S
Pruned

21


RPB to RPM (reverse path multicast)
• Identify leaf networks
– Only one router on network
– Thus no distance packets received on interface

• Prune leaf networks

– Without hosts in a group
– Hosts must self­identify using IGMP

• Forward pruning information

– Extend distance vector with group information
– Forward packets only to interested parties
– Only when multicast source active
22


Distance Vector Multicast
RPM Implementation
• Assume that everyone is interested
• Respond to unwanted packets with 

prune requests
• Prune requests
– Canceled by graft request
– Time out periodically

• Need ARQ for prune or graft ?
23


Distance Vector Multicast ­ Scalability
• Packets are periodically broadcast (thus 
guaranteed to reach all interested members)
• High overhead for sparse groups, consider:
– Multicast group of 10 members
– Scattered around the world
– Packets periodically reach all routers in Internet

• High overhead for routers
– All off­tree routers maintain pruning state
– And periodically retransmit
24


Protocol Independent Multicast (PIM)
• Approach
– Define rendezvous points (RP) for each group
– Need multiple RP’s to handle failures

• Two versions
– Dense mode


• Explicit prune messages
• Shared tree

– Sparse mode

• Explicit join messages
• Shared or source­specific tree

25