Transcript Set 11 in powerpoint - UCSC Computer Communication Research

CMPE 252A:
Computer Networks
Set 11:
Algorithms and
Protocols for
IP Multicasting
1
Multicasting

Uses:








Multimedia “broadcast”: IP radio, webcasts
Teleconferencing: multiparty videoconferencing with
(Mbone, CUSeeMe)
Database replication
Distributed computing: immediate updates to all
members
Real-time workgroups: multimedia collaboration
System management: concerted file updates to group of
hosts
Stock ticker: low-bandwidth quotes to millions of hosts
(cf. Pointcast)
Single LAN segment:

straightforward (IEEE 802 includes provision for MAClayer multicast addresses)
2
Multicasting




Purpose: Support one-to-many and many-to-many
communication needed for many applications across LANs
and WANs.
Problem: To minimize the communication and processing
overhead entailed in disseminating the same data packets
to a group of receivers.
Goal: Identify the receiver set in a convenient way and
distribute packets to the set efficiently.
Approach:
 Disseminate packets over a tree spanning all the
intended receivers.
 Identify the receivers with a group identifier or the set
of receiver identifiers.
3
Multipoint Dissemination

Broadcasting packet to each network


Multiple Unicasts



Takes 13 copies of packet; 13 interfaces
Send packet only to networks that have
hosts in group
11 packets
Multicasting





Determine least cost path to each
network that has host in group
Gives spanning tree configuration
containing networks with group
members
Transmit single packet along spanning
tree
Routers replicate packets at branch
points of spanning tree
8 packets required
4
IP Multicast Architecture





Based on Steve Deering’s original proposal
(SIGCOMM 88 Proceedings; his PhD thesis)
The architecture expands LAN multicasting to the Internet.
It consists of three basic components:
 Group addressing based on globally unique
identifiers (IP multicast addresses)
 Separation of senders and receivers with anonymous
receiver affiliation
 A tree-based routing and group structure
Advantages: Efficiency of packet forwarding and
simplicity
Disadvantages: Scalability, difficult to adapt to group
dynamics, limited services
5
IP Multicast


Addresses used:
224.0.0.0 through
239.255.255.255 (the former
Class D addresses in IPv4)
Abstraction:
multicast address associated with
multicast group
 host joins / leaves group and
receives address dynamically
 sender host sends packets to
multicast group (one or more
destinations) not individuals!
 routers deliver to all hosts that
joined group address
To avoid unnecessary duplication of
packets, routers must route packets
using source and destination addresses,
and an efficient routing structure must
be built!


6
IP Internet Multicasting
R
R
R
R
R
R
R
G
R
R
R
R
G
R
G
7
Internet Group Management
Protocol (IGMP)




RFC 1112 - used by hosts and routers to exchange multicast group
membership information over LAN
Multicast routers use IGMP in conjunction with a multicast routing protocol,
to support IP multicasting across the Internet.
Takes advantage of broadcast nature of LAN to updates - IGMP v1 - 3
Two kinds of packets: query / response
8
Constructing The
Multicast Routing Structure



If routers know the topology of the network, they
can compute a multicast routing tree locally.
If routers maintain only distance or path
information to destinations, multicast routing tree
must be computed in a distributed manner.
Internet multicast routing protocols are based on
reverse path forwarding.
9
Link-State Multicast



Goal: route packets to all hosts that joined multicast group
address
Each host on a LAN periodically announces the groups to which it
belongs (IGMP).
Each router uses link-state flooding to distribute



Each router computes





cost of links to neighbors
multicast addresses it wants to receive (hosts joined group)
regular unicast routing (Dijkstra's algorithm to compute shortest-path
spanning tree for each source/group pair)
spanning tree for M nodes joining to each active multicast address
Augment link-state update messages to include set of groups that have
members on a particular LAN.
Each router caches tree for currently active source/group pairs.
Possible algorithm:


find node with smallest host address among M
use Dijkstra to build tree, rooted at that host reaching all M nodes
10
Limitations of Link-State Multicasting



Routers need to maintain too much state for
each multicast group.
Routers need to send many more link-state
updates.
Routers need to compute a multicast routing
tree for each source of a group in the worst
case, in order to decide when to forward
packets.
11
Multicast Extensions to Open
Shortest Path First (MOSPF)


RFC-1583: OSPFv2 - Interior Gateway Protocol (IGP) specifically
designed to distribute unicast topology information among routers
belonging to a single Autonomous System
RFC-1584: MOSPF routers maintain a current image of the network
topology through the unicast OSPF link-state routing protocol


Extends OSPF by providing the ability to route multicast IP
traffic
Extension is backward compatible so that routers running
MOSPF will interoperate with non-multicast OSPF routers when
forwarding unicast IP data traffic.
12
Distributed Approaches for
Building Multicast Trees
Approaches:
 Source-based tree: One tree per source
shortest path trees
 reverse path forwarding


Group-shared tree: Entire group uses one
tree
Minimal spanning (Steiner)
 Center-based trees

13
Shortest Path Tree

Multicast 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
14
Reverse Path Forwarding
 Rely on router’s knowledge of unicast
shortest path from it to sender
 Each router has simple forwarding behavior:
if (mcast datagram received on incoming
link on shortest path back to “center”)
then flood datagram onto all outgoing
links
else ignore datagram
15
Reverse Path Forwarding:
Example
S: source
LEGEND
R1
R4
router with attached
group member
R2
R5
R3
R6
R7
router with no attached
group member
datagram will be forwarded
datagram will not be
forwarded
• result is a source-specific reverse shortest path tree
– may be a bad choice with asymmetric links
16
Reverse Path Forwarding: Pruning

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
S: source
R1
router with attached
group member
R4
R2
router with no attached
group member
P
R5
R3
R6
P
R7
P
prune message
links with multicast
forwarding
17
Distance-Vector Multicast
Routing Protocol (DVMRP)




Implemented by the mrouted program.
Specified in RFC-1075.
Implemented version differs in packet format,
different tunnel format, additional packet types.
Maintains routing knowledge via a distancevector routing protocol:


Much like RIP, described in RFC-1058
Routers maintain hop count to all possible multicast
sources.
18
DVMRP


DVMRP: distance vector multicast routing
protocol, RFC1075
flood and prune: reverse path forwarding,
source-based tree
RPF tree based on DVMRP’s 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

19
DVMRP: continued…

soft state: DVMRP router periodically (1 min.)
“forgets” branches are pruned:



routers can quickly regraft to tree


mcast data again flows down un-pruned branch
downstream router: re-prune or else continue to receive
data
following IGMP join at leaf
odds and ends


Mbone routing was done using DVMRP
Replaced by PIM
20
Tunneling
How do we connect “islands” of multicast
routers in a “sea” of unicast routers?
physical topology
logical topology
 mcast datagram encapsulated inside “normal” (non-multicast-addressed)
datagram
 normal IP datagram sent thru “tunnel” via regular IP unicast to receiving
mcast router
 receiving mcast router unencapsulates to get mcast datagram
21
Problems with Basic Approach





Flooding the Internet to establish a multicast
routing tree is not an option!
This is the key reason why multicasting (based on
DVMRP) cannot be deployed on a large scale.
The problem stems from the lack of addressing
information in an IP multicast address!
Where is a multicast group on the Internet?
The solution to this problem is to use
special nodes as the “address” of a group
22
Shared-Tree: Steiner Tree




Steiner Tree: minimum cost tree connecting all
routers with attached group members
Problem is NP-complete
Good heuristics exist
Not used in practice:



Computational complexity
Information about entire network needed
Monolithic: rerun whenever a router needs to
join/leave
23
Core-Based Trees



Single delivery tree shared by all
One router identified as “core” of tree
To join:




Edge router sends unicast join-msg addressed to
center router
join-msg “processed” by intermediate routers and
forwarded towards core
join-msg either hits existing tree branch for this core,
or arrives at core
path taken by join-msg becomes new branch of tree
for this router
24
Example of Core-Based
Trees
Suppose R6 chosen as center (core):
LEGEND
R1
3
R2
router with attached
group member
R4
router with no attached
group member
2
R5
R3
1
R6
1
path order in which join
messages generated
R7
25
Core-Based Tree (CBT)




Ballardi, Crowcroft, and Francis proposed CBT to solve the
problems found with Deering’s original scheme (DVMRP)
based on RPF [Proc. ACM SIGCOMM 93]
The basic idea consists of using a router, called the core,
as the de facto address for a multicast group.
In addition, a single shared multicast routing tree is used
for the entire group, rather than one tree per source per
group.
The links in the tree are bidirectional, meaning that
multicast packets can flow between two neighbor
members of the tree in either direction.
26
Core-Based Trees (CBT)




CBT is receiver-initiated, in that a router needs to send a
JOIN request towards the core of the group to become a
group member.
JOIN request is forwarded along the shortest path to the
core.
Any router in the multicast tree receiving the JOIN replies
with an ACK that makes the router join the group.
The ACK propagates back along the same path followed by
the JOIN.
27
Limitations of CBT



Using a single core is a vulnerability, CBT does not work
correctly with multiple cores, and CBT can have temporary
loops.
Location of core is critical to performance
Paths over multicast tree can be much longer than the
shortest paths.
A
B
28
PIM: Protocol Independent Multicast


Not dependent on any specific underlying unicast routing
algorithm (works with all)
Multiple multicast modes:
Sparse, dense, bidirectional, source-specific.
Dense:
Sparse:
 group members densely
 # networks with group members
packed, in “close”
proximity.
 bandwidth more plentiful
small wrt # interconnected
networks
 group members “widely
dispersed”
 bandwidth not plentiful
29
Consequences of Sparse-Dense
Dichotomy:
Dense



group membership by
routers assumed until
routers explicitly prune
data-driven
construction on mcast
tree (e.g., RPF)
bandwidth and nongroup-router
processing profligate
Sparse:



no membership until
routers explicitly join
receiver- driven
construction of mcast
tree (e.g., centerbased)
bandwidth and nongroup-router
processing
conservative
30
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
31
PIM - Sparse Mode


Center (core)-based
approach
router sends join msg to
rendezvous point (RP)

R1
intermediate routers
update state and forward
R2
join

after joining via RP,
router can switch to
source-specific tree

increased performance:
less concentration, shorter
paths
R4
join
join
R5
join
R3
R7
R6
all data multicast
from rendezvous
point
rendezvous
point
32
PIM - Sparse Mode
sender(s):
 unicast data to RP, which
distributes down RProoted tree
 RP can extend mcast tree
upstream to source
 RP can send stop msg if
no attached receivers

“no one is listening!”
R1
R4
join
R2
join
R5
join
R3
R7
R6
all data multicast
from rendezvous
point
rendezvous
point
33
IP Multicast Addressing Issues




There are plenty of IPv4 and IPv6 addresses for globally
unique multicast addresses, if done carefully
The problem is how to assign these addresses
permanently or temporarily to multicast groups.
Using globally unique multicast addresses requires
Internet-wide coordination/rules in the assignment of
identifiers to groups.
Evolving solution:





GLOP addressing
Unicast-prefix-based IPv4 mcast addresses
Administratively scoped IPv4 mcast addresses
How do we map IP to MAC multicast addresses?
Check: http://en.wikipedia.org/wiki/Multicast_address
34
IP Multicast Addresses


28 bits for identifying groups ~ 250 million
groups can exist at the same time
Two kinds of supported addresses:

Permanent, e.g.,
224.0.0.1 all systems on LAN
 224.0.0.2 all routers on LAN


Temporary - must be created before
they can be addressed (join and leave)
35