Transcript Multicast Routing Algorithms & Protocols (Intro)

IP-Multicast (outline)
- Motivation and Background
- Multicast vs. unicast
- Multicast Applications
- Delivery of Multicast
- Local delivery and multicast addressing
- WAN delivery and its model
- Group Membership Protocol (IGMP)
- Multicast Algorithms and Concepts
- Flooding, Spanning Tree, Reverse Path
Broadcasting (RPB), Truncated RPB, Reverse
Path Multicasting, Center-Based Trees
Ahmed Helmy - UF
1
Outline (Contd.)
- Multicast Routing Protocols
-
Dense vs. Sparse Multicast
DVMRP
MOSPF
PIM (PIM-DM, PIM-SM)
- Multicast and the Internet
- The MBONE
- Recent deployment
Ahmed Helmy - UF
2
Unicast vs. Multicast
• Multicast provides multipoint-to-multipoint
communication
• Today majority of Internet applications rely on
point-to-point transmission (e.g., TCP).
• IP-Multicast conserves bandwidth by replicating
packets in the network only when necessary
Ahmed Helmy - UF
3
Unicast vs. Multicast
S
S
R1
R1
R2
R2
R3
R3
R4
Multiple unicasts
R4
Multicast
Ahmed Helmy - UF
4
Example Multicast Applications
• One-to-Many
– Scheduled audio/video distribution: lectures,
presentations
– Push media: news headlines, weather updates
– Caching: web site content & other file-based updates
sent to distributed replication/caching sites
– Announcements: network time, configuration updates
– Monitoring: stock prices, sensor equipment
Ahmed Helmy - UF
5
IP Multicast Applications (contd.)
• Many-to-One
–
–
–
–
Resource discovery
Data collection and sensing
Auctions
Polling
Ahmed Helmy - UF
6
IP Multicast Applications (contd.)
– Many-to-Many
• Multimedia Teleconferencing (audio, video, shared
whiteboard, text editor)
• Collaboration
• Multi-Player Games
• Concurrent Processing
• Chat Groups
• Distributed Interactive Simulation
Ahmed Helmy - UF
7
Ahmed Helmy - UF
8
Ahmed Helmy - UF
9
Ahmed Helmy - UF
10
More Applications ...
• Resource Discovery
– Multicast may be used (instead of broadcast) to
transmit to group members on the same LAN.
– Multicast may be used for resource discovery
within a specific scope using the TTL field in
the IP header.
Ahmed Helmy - UF
11
Multicast Scope Control:
TTL Expanding-Ring Search
to reach or find a nearby subset of a group
s
1
2
3
Ahmed Helmy - UF
12
Multicast Scope Control:
Administrative TTL Boundaries
to keep multicast traffic within an
administrative domain, e.g., for privacy
reasons
the rest of the Internet
an administrative domain
Ahmed Helmy - UF
TTL threshold set on
interfaces to these links,
greater than the diameter
of the admin. domain
13
Multicast Scope Control:
Administratively-Scoped Addresses
– RFC 1112
– uses address range 239.0.0.0 — 239.255.255.255
the rest of the Internet
address boundary set on
interfaces to these links
an administrative domain
Ahmed Helmy - UF
14
Transmission and Delivery of
Multicast Datagrams
• Over the same (LAN):
– The source addresses the IP packet to the
multicast group
– The network interface card maps the Class D
address to the corresponding IEEE-802
multicast address
– Receivers notify their IP layer to receive
datagrams addressed to the group.
– Key issue is ‘addressing’ & filtration
Ahmed Helmy - UF
15
• Over different subnets:
– Routers implement a multicast routing protocol
that constructs the multicast delivery trees and
supports multicast data packet forwarding.
– Routers implement a group membership
protocol to learn about the existence of group
members on directly attached subnets.
– Hosts implement the group membership
protocol that provides the ‘IP-multicast host
model’
Ahmed Helmy - UF
16
Ahmed Helmy - UF
17
Multicast Addressing
• An IP multicast group is identified by a
Class D address.
• Multicast group addresses range from
(224.0.0.0) to (239.255.255.255).
Ahmed Helmy - UF
18
• The Internet Assigned Numbers Authority
(IANA) registers IP multicast groups.
• The block of multicast addresses ranging
from (224.0.0.1) to (224.0.0.255) is
reserved for local LAN multicast:
– used by routing protocols and other low-level
topology discovery or maintenance protocols
– E.g., "all-hosts" group (224.0.0.1), "all-routers”
group (224.0.0.2), "all DVMRP routers", etc.
• The range (239.0.0.0) to (239.255.255.255)
are used for site-local "administratively
scoped" applications.
Ahmed Helmy - UF
19
The Multicast Host Model
• Hosts can join or leave a group at any time
• A host may be a member of multiple groups
• Senders need not be members of the group
• Participants do not know about each other
• The two components of IP-multicast:
– the group membership protocol
– the multicast routing protocol
Ahmed Helmy - UF
20
Group Membership Protocol
• Routers need to learn about the presence of
group members on directly attached subnets
• When a host joins a group:
– it transmits a group membership message for
the group(s) that it wishes to receive
– sets its IP process and network interface card to
receive packets sent to those groups.
Ahmed Helmy - UF
21
• Multicast Routing Protocols
– Run on routers and establish the multicast
distribution tree to forward packets from sender(s)
to group members.
• Based on unicast routing concepts:
– DVMRP is a distance-vector routing protocol,
– MOSPF is an extension to the OSPF link-state
unicast routing protocol.
• Center-based trees (e.g., CBT & PIM-SM)
introduce the notion of the tree ‘core’.
Ahmed Helmy - UF
22
Multicast Forwarding
Algorithms
• A multicast routing protocol is responsible
for the establishment of the multicast
distribution tree and for performing packet
forwarding.
Ahmed Helmy - UF
23
• Several algorithms may be employed by
multicast routing protocols:
 Flooding
 Spanning Trees
 Reverse Path Broadcasting (RPB)
 Truncated Reverse Path Broadcasting (TRPB)
 Reverse Path Multicasting (RPM)
 Core-Based Trees
Ahmed Helmy - UF
24
Flooding
• The simplest technique for multicast delivery.
• When a router receives a multicast packet it
determines whether or not this is the first time
it has seen this packet.
– On first reception, a packet is forwarded on all
interfaces except the one on which it arrived.
– If the router has seen the packet before, it is
discarded.
Ahmed Helmy - UF
25
• A router does not maintain a routing table, but
needs to keep track of recently seen packets.
• Flooding does not scale for Internet-wide
application:
- Generates a large number of duplicate packets and
uses all available paths across the internetwork.
- Routers maintain a distinct table entry for each
recently seen packet (consumes memory).
Ahmed Helmy - UF
26
Spanning Tree
• More effective than flooding
• Defines a tree structure where one active path
connects any two routers on the Internet.
• Spanning Tree rooted at R
Ahmed Helmy - UF
27
• A router forwards each multicast packet to
interfaces that are part of the spanning tree
except the receiving interface.
• A spanning tree avoids looping of multicast
packets and reaches all routers in the
network.
Ahmed Helmy - UF
28
• A spanning tree algorithm is easy to
implement
• However, a spanning tree solution:
– may centralize traffic on small number of links
– may not provide the most efficient path
between the source and the group members.
Ahmed Helmy - UF
29
Reverse Path Broadcasting
(RPB)
• More efficient than building a single
spanning tree for the entire Internet.
• Establishes source-rooted distribution trees
for every source subnet.
• A different spanning tree is constructed for
each active (source, group) pair.
Ahmed Helmy - UF
30
RPB Algorithm
• For each (source, group) pair
– if a packet arrives on a link that the router
considers to be the shortest path back to the source
of the packet
• then the router forwards the packet on all interfaces
except the incoming interface.
– Otherwise, the packet is discarded.
Ahmed Helmy - UF
31
• The interface over which a router accepts
multicast packets from a particular source is
called the "parent" link.
• The outbound links over which a router
forwards the multicast packets are called the
"child" links.
Ahmed Helmy - UF
32
• Reverse Path Broadcasting (RPB)
Forwarding
Ahmed Helmy - UF
33
• Enhancement to reduce packet duplication:
– A router determines if a neighboring router
considers it to be on the shortest path back to
the source.
– If Yes, the packet is forwarded to the neighbor.
– Otherwise, the packet is not forwarded on that
potential child link.
Ahmed Helmy - UF
34
• To derive the parent-child information:
– link-state routing protocol already has it (since
each router maintains a topological database for
the entire routing domain).
– distance-vector routing protocol uses ‘poison
reverse’:
• a neighbor can either advertise its previous hop for
the source subnet as part of its routing update
messages or "poison reverse" the route.
Ahmed Helmy - UF
35
• Example of Reverse Path Broadcasting
Ahmed Helmy - UF
36
Benefits
• Reasonably efficient and easy to implement.
• Does not require keeping track of previous
packets, as flooding does.
• Multicast packets follow the "shortest" path
from the source to the group members.
• Avoids concentration over single spanning tree
Ahmed Helmy - UF
37
Reverse Path Multicasting
(RPM)
• RPM enhances TRPB.
• In RPM, non-member branches are pruned
• Packets are forwarded only along branches
leading to group members.
Ahmed Helmy - UF
38
RPM Operation
• The first multicast packet is forwarded
(using TRPB) to all routers in the network.
• Routers at edges of the network with no
downstream routers are called ‘leaf’routers.
• A leaf router with no downstream members
sends a "prune" message on its parent link
to stop packet flow down that branch.
Ahmed Helmy - UF
39
• Prune messages are sent hop-by-hop back
toward the source.
• A router receiving a prune message stores
the prune state in memory.
• A router with no local members that
receives prunes on all child interfaces sends
a prune one hop back toward the source.
• This succession of prune messages creates a
multicast forwarding tree that contains only
branches that lead to group members.
Ahmed Helmy - UF
40
• Reverse Path Multicasting (RPM)
Ahmed Helmy - UF
41
Limitations
• Despite improvements over RPM, there are
scaling issues and limitations:
– Multicast packets are periodically forwarded to
every router in the network.
– Routers maintain prune state off-tree for all
(source,group) pairs.
• These limitations are amplified with increase
in number of sources and groups.
Ahmed Helmy - UF
42
Center/Core-Based Trees
(CBT)
• Earlier algorithms build source-based trees
• CBT builds a single delivery tree (rooted at the
core) that is shared by all group members.
• Multicast traffic for each group is sent and
received over the shared tree, regardless of the
source.
Ahmed Helmy - UF
43
CBT Operation
• A core-based tree involves one or more
cores in the CBT domain.
• Each leaf-router of a group sends a hop-byhop "join" message toward the "core tree"
of that group.
• Routers need to know the group core to
send the join request.
• Senders unicast packets toward the core.
Ahmed Helmy - UF
44
Benefits
• Advantages over RPM, in terms of scalability:
– A router maintains state information for each
group, not for each (source, group) pair.
– Multicast packets only flow down branches
leading to members (not periodically broadcast).
– Only join state is kept on-tree
Ahmed Helmy - UF
45
Limitations
• CBT may result in traffic concentration near the
core since traffic from all sources traverses the
same set of links as it approaches the core.
• A single shared delivery tree may create suboptimal routes resulting in increased delay.
• Core management issues
– dynamic core selection
– core placement strategies
Ahmed Helmy - UF
46
Multicast Routing Protocols
• In general, there are two classes of multicast
routing protocols:
– Dense-mode protocols (broadcast-and-prune)
• DVMRP, PIM-DM, (MOSPF!)
– Sparse-mode protocols (explicit-join)
• PIM-SM, CBT, BGMP
Ahmed Helmy - UF
47
Dense vs. Sparse Mode Multicast
S
R1
R2
R3
R4
Dense-Mode Multicast
Ahmed Helmy - UF
48
Dense vs. Sparse Mode Multicast
S
S
R1
R1
R2
R2
R3
Root
R3
R4
Dense-Mode Multicast
R4
Sparse-Mode Multicast
Ahmed Helmy - UF
49
Distance Vector Multicast
Routing Protocol (DVMRP)
• DVMRP constructs source-rooted trees
using variants of RPM (broadcast-andprune).
• The first packet for any (source, group) pair
is broadcast to the entire network.
• Leaf routers with no local members send
prune messages back toward the source.
Ahmed Helmy - UF
50
Example DVMRP Scenario
g
g
s
Ahmed Helmy - UF
g
51
Initial Broadcast using Truncated
Broadcast
g
g
s
Ahmed Helmy - UF
g
52
Prune non-member branches
g
g
prune (s,g)
s
prune (s,g)
Ahmed Helmy - UF
g
53
Graft new members
g
g
g
report (g)
graft (s,g)
s
graft (s,g)
g
Ahmed Helmy - UF
54
DVMRP Distribution Tree
g
g
g
s
g
Ahmed Helmy - UF
55
DVMRP Forwarding Table
Ahmed Helmy - UF
56
Multicast Extensions to
OSPF (MOSPF)
• MOSPF routers maintain current image of
the network topology via OSPF.
• Basic MOSPF runs in OSPF domain
• MOSPF uses IGMP to discover members
on directly attached subnets.
• The subnet router floods GroupMembership Link State Advertisements
(LSAs) throughout the OSPF domain.
Ahmed Helmy - UF
57
Building the Shortest Path Tree
• The shortest path tree for (S, G) pair is built "on
demand" when a router receives the first packet
for (S,G).
• When the initial packet arrives, the source
subnet is located in MOSPF link state database.
– MOSPF LS-DB = OSPF LS-DB + Group-Membership LSAs
Ahmed Helmy - UF
58
Forwarding Cache
• Forwarding cache entry contains the
(source, group) pair, the upstream node, and
the downstream interfaces.
• MOSPF Forwarding Cache
Ahmed Helmy - UF
59
Limitations
 Limited to OSPF domains
 Flooding membership information does not
scale well for Internet-wide multicsat
Ahmed Helmy - UF
60
Protocol-Independent
Multicast (PIM)
• Design Rationale:
– Broadcast and prune keeps state off-tree and is
suitable when members are densely distributed
– Explicit join/center-based approach keeps state
on-tree and is suitable when members are
sparsely distributed
– PIM attempts to combine the best of both
worlds
Ahmed Helmy - UF
61
Design Choices
• Shared trees or shortest path trees?
– Both: use shared trees to ‘Rendezvous’ then
switch to shortest path to deliver
• DV or LS for routing?
– Use routing tables regardless of which protocol
created them (hence the name ‘Protocol
Independent’)
Ahmed Helmy - UF
62
PIM Operation Modes
• PIM provides both dense-mode (DM) and
sparse-mode (SM) protocols
• PIM-DM: similar to DVMRP but does not
build its own routing table
• PIM-SM: similar to CBT but provides
switching to SPT and bootstrap mechanism
for electing the tree center dynamically
Ahmed Helmy - UF
63
How PIM-SM works
• A Rendezvous Point (RP) is chosen as tree center
per group to enable members and senders to
“meet”
• Members send their explicit joins toward the RP
• Senders send their packets to the RP
• Packets flow only where there is join state
• (*,G) [any-source,group] state is kept in routers
between receivers and the RP
Ahmed Helmy - UF
64
How PIM-SM works
• When should we use shared-trees versus sourcetrees?
– Source-trees tradeoff low-delay from source with
more router state
– Shared-trees tradeoff higher-delay from source with
less router state
• Switch to the source-tree if the data rate is above
a certain threshold
Ahmed Helmy - UF
65
How PIM-SM works
Source
A
B
D
RP
C
E
Link
(*,G) Data
(S,G) Data
Receiver 1
Receiver 2
Ahmed Helmy - UF
Control
66
How PIM-SM works
Source
A
C
B
D
RP
E
(*, G)
Join
Link
(*,G) Data
(S,G) Data
Receiver 1
Receiver 2
Ahmed Helmy - UF
Control
67
How PIM-SM works
Source
A
B
D
RP
C
E
Link
(*,G) Data
(S,G) Data
Receiver 1
Receiver 2
Ahmed Helmy - UF
Control
68
How PIM-SM works
Source
Register
A
B
D
RP
C
E
Link
(*,G) Data
(S,G) Data
Receiver 1
Receiver 2
Ahmed Helmy - UF
Control
69
How PIM-SM works
Source
(S, G)
Join
A
(S, G)
Join
B
D
RP
C
E
Link
(*,G) Data
(S,G) Data
Receiver 1
Receiver 2
Ahmed Helmy - UF
Control
70
How PIM-SM works
Source
Register-Stop
A
B
D
RP
C
E
Link
(*,G) Data
(S,G) Data
Receiver 1
Receiver 2
Ahmed Helmy - UF
Control
71
How PIM-SM works
Source
A
B
D
RP
(S, G) Join
C
E
Link
(*,G) Data
(S,G) Data
Receiver 1
Receiver 2
Ahmed Helmy - UF
Control
72
How PIM-SM works
Source
(S, G) Prune
A
B
D
RP
C
E
(*,G) Data
(S, G) RP Bit
Prune
Receiver 1
Link
(S,G) Data
Receiver 2
Ahmed Helmy - UF
Control
73
How PIM-SM works
Source
A
C
B
D
RP
E
(*, G)
Join
Link
(*,G) Data
(S,G) Data
Receiver 1
Receiver 2
Ahmed Helmy - UF
Control
74
How PIM-SM works
Source
A
B
D
RP
C
E
Link
(*,G) Data
(S,G) Data
Receiver 1
Receiver 2
Ahmed Helmy - UF
Control
75