Transcript Multicast Routing

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
- Currently: The Multicast Backbone
(MBONE) carries audio and video
multicasts of IETF meetings, NASA space
shuttle missions,.. etc.
Ahmed Helmy - UF
8
- How do hosts know about new groups?
- The Session Directory (SD) tool lists active
multicast sessions on MBONE and allows
to join a conference using MBONE tools:
- vat (visual audio tool), rat (robust audio tool)
- vic (video tool)
- wb (shared white board)
- nte (network text editor), .. etc.
Ahmed Helmy - UF
9
Ahmed Helmy - UF
10
Ahmed Helmy - UF
11
Ahmed Helmy - UF
12
Ahmed Helmy - UF
13
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
14
Multicast Scope Control:
TTL Expanding-Ring Search
to reach or find a nearby subset of a group
s
1
2
3
Ahmed Helmy - UF
15
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
16
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
17
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
18
• 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
19
Addressing
• Types of IP addresses:
– Unicast: used to transmit packets to one destination.
– Broadcast: used to send datagrams to entire subnet.
– Multicast: used to deliver datagrams to a set of
hosts (members of a multicast group) in various
scattered subnets.
Ahmed Helmy - UF
20
• IP-Multicast is a “best-effort” service.
– Reliable/ordered delivery are not guaranteed.
– Reliability may be provided by upper-layer
protocols (e.g., reliable multicast protocols).
• IP-Multicast packets include a "group address"
(Class D) in the Destination field of the IP
header.
Ahmed Helmy - UF
21
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
22
• 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
23
Mapping Class D to Ethernet
Address
• All multicast addresses in IANA's reserved
block begin with 01-00-5E (hex)
• Mapping between a Class D and an
Ethernet multicast address is obtained by:
– placing the low-order 23 bits of the Class D
address into the low-order 23 bits of IANA's
reserved address block.
Ahmed Helmy - UF
24
– How multicast group address 224.10.8.5 (E0-0A-08-05) is
mapped into an Ethernet (IEEE-802) multicast address.
• The mapping may place up to 32 different IP groups
into the same Ethernet address because the upper
five bits of the IP multicast group ID are ignored.
Ahmed Helmy - UF
25
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
26
Ahmed Helmy - UF
27
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
28
• This receiver-initiated join process scales
well:
– as the group size increases, it becomes more
likely for a new member to locate a nearby
branch of the multicast distribution tree.
Ahmed Helmy - UF
29
• 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
30
Internet Group Management
Protocol (IGMP)
• IGMP runs between hosts and their
immediately neighboring multicast routers.
• The protocol allows a host to inform its
‘first-hop’ router that it wishes to receive
packets destined to a specific group.
Ahmed Helmy - UF
31
Router Operation in IGMP
• Routers periodically query the LAN to
determine if group members are still active.
• One router per LAN is elected as "querier"
to query for group members.
• Through IGMP a router determines which
multicast traffic needs to be forwarded to
each of its "leaf" subnets.
Ahmed Helmy - UF
32
IGMP Version 1
• RFC-1112
• To determine local group membership:
– Multicast routers periodically transmit ‘Host
Membership Query’ messages
– Queries are ddressed to the all-hosts group
(224.0.0.1) with TTL = 1 (i.e., not forwarded
by any other multicast router).
Ahmed Helmy - UF
33
Hosts Joining Groups
• Upon receiving a Query, a host responds with a
‘Host Membership Report’ for each group that it
wishes to Join
• Observation: The router only needs to know of at
least one group member on the leaf subnet
Ahmed Helmy - UF
34
Report Suppression Mechanism
• To avoid Report implosion:
– Each host starts a random delay timer for its Reports.
– If during the delay period another Report is heard for
the same group, the host resets its timer
– Otherwise, the host transmits a Report causing other
group members to reset their timers
• Thus, Reports are spread out over time and Report
traffic is minimized
Ahmed Helmy - UF
35
– IGMP-Query Message
Ahmed Helmy - UF
36
Updating Local Membership
• The querier periodically transmits Queries
to update local membership
• If no Report is received for a group after a
number of Queries, the router assumes that
members are no longer present on that LAN
– the group is removed from the membership list
of that interface/subnet
Ahmed Helmy - UF
37
Reducing Join Latency
• When a host first joins a group, it
immediately transmits a Report for the
group rather than waiting for a router
Query.
Ahmed Helmy - UF
38
IGMP Version 2 (IGMP V2)
• IGMP V2 was part of IP-mcast (V3.3-3.8)
– spec <draft-ietf-idmr-igmp-v2-01.txt>
• IGMP V2 enhances IGMP V1
– IGMP V2 elects one querier for each LAN, the
router with the lowest IP address.
– In V1, the querier election was done by the
multicast routing protocol (different multicast
routing protocol used different methods).
Ahmed Helmy - UF
39
• IGMP V2 defines a new Query message,
the ‘Group-Specific Query’, to Query a
specific group rather than all groups
Ahmed Helmy - UF
40
Reducing Leave Latency
• To reduce ‘leave latency’ V2 defines a ‘Leave
Group’ message
– When a host leaves a group, it sends a ‘Leave Group’
to the all-routers group (224.0.0.2) with the group field
set to the group to be left.
– Upon receiving a Leave from a LAN, the querier
sends Group-Specific Query on that LAN.
– If there are no Reports in response to the GroupSpecific Query, the group is removed from the
membership list of that subnet.
Ahmed Helmy - UF
41
• Observation: With IGMP V1 and V2, if a
host wants to receive any sources from a
group, the traffic from all sources for the
group has to be forwarded onto the subnet.
Ahmed Helmy - UF
42
IGMP Version 3 (IGMP v3)
• Spec: <draft-ietf-idmr-igmp-v3-03.txt>
• IGMP V3 supports Group-Source Reports:
– A host can elect to receive traffic from specific
sources of a multicast group.
– An inclusion Group-Source Report specifies the
sources a host wants to receive.
– An exclusion Group-Source Report identifies
the sources a host does not want to receive.
Ahmed Helmy - UF
43
• IGMP v3 enhances support for Leave
Group messages to support ‘Group-Source’
Leave messages:
– A host can leave an entire group or specific
(source, group) pair(s).
Ahmed Helmy - UF
44
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
45
• 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
46
• These algorithms are implemented in the
most prevalent multicast routing protocols
in the Internet today.
 Distance Vector Multicast Routing Protocol
(DVMRP)
 Multicast OSPF (MOSPF)
 Protocol-Independent Multicast (PIM) [PIMDM and PIM-SM]
Ahmed Helmy - UF
47
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
48
• 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
49
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
50
• 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
51
• 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
52
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
53
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
54
• 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
55
• Reverse Path Broadcasting (RPB)
Forwarding
Ahmed Helmy - UF
56
• 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
57
• 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
58
• Example of Reverse Path Broadcasting
Ahmed Helmy - UF
59
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
60
Limitations
• Does not take into account group membership
when building the distribution tree.
• As a result, packets may be unnecessarily
forwarded to subnets with no group members.
Ahmed Helmy - UF
61
Truncated Reverse Path
Broadcasting (TRPB)
• Using IGMP, routers discover group
members and avoid forwarding packets onto
leaf subnets with no members.
• The spanning delivery tree is "truncated" if
a leaf subnet has no group members.
Ahmed Helmy - UF
62
• Truncated Reverse Path Broadcasting
(TRPB)
Ahmed Helmy - UF
63
• TRPB eliminates unnecessary traffic on leaf
subnets
• But it does not consider group membership
when building the branches of the
distribution tree.
Ahmed Helmy - UF
64
Reverse Path Multicasting
(RPM)
• RPM enhances TRPB.
• RPM creates a delivery tree that spans only:
-Subnets with group members
-Routers and subnets along the shortest path
to group members
• In RPM, non-member branches are pruned
• Packets are forwarded only along branches
leading to group members.
Ahmed Helmy - UF
65
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
66
• 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
67
• Reverse Path Multicasting (RPM)
Ahmed Helmy - UF
68
• To adapt to membership/network dynamics,
the prune state is timed out periodically, and
packets are broadcast throughout the network.
• This may result in a burst of prune messages.
Ahmed Helmy - UF
69
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
70
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
71
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.
Ahmed Helmy - UF
72
• Intermediate routers process the join request:
– The interface on which the join was received is
added to the delivery tree.
• Intermediate routers forward join requests
toward the core until the join reaches a core or
a router on the distribution tree.
• Senders unicast their packets toward the core.
• When the unicast packet reaches a member of
the delivery tree, the packet is multicast to all
outgoing interfaces that are part of the tree.
Ahmed Helmy - UF
73
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
74
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
75
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
76
Dense vs. Sparse Mode Multicast
S
R1
R2
R3
R4
Dense-Mode Multicast
Ahmed Helmy - UF
77
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
78
Distance Vector Multicast
Routing Protocol (DVMRP)
• DVMRP constructs source-rooted trees
using variants of RPM.
• Many MBONE routers run DVMRP
• DVMRP was first defined in RFC-1075.
– The original spec was derived from the Routing
Information Protocol (RIP) and used TRPB.
– Mrouted version 3.8 uses RPM.
Ahmed Helmy - UF
79
DVMRP Basic Operation
• DVMRP implements RPM.
• The first packet for any (source, group) pair
is broadcast to the entire network, providing
the packet's TTL permits.
• Leaf routers with no local members send
prune messages back toward the source.
Ahmed Helmy - UF
80
• Prune messages cause the removal of
branches that do not lead to group members
• The result is source-specific shortest path
tree with all leaves having group members.
• After a period of time, the pruned branches
grow back and the packets are broadcast
throughout the network.
• A “graft” mechanism helps to quickly reestablish previously pruned branches.
Ahmed Helmy - UF
81
• A new member joining the group causes
the first-hop router to send a graft message
to the group's previous-hop router.
• When an upstream router receives a graft
message, it removes the prune state.
• Graft messages may cascade back toward
the source allowing previously pruned
branches to be restored.
Ahmed Helmy - UF
82
Example DVMRP Scenario
g
g
s
Ahmed Helmy - UF
g
83
Initial Broadcast using Truncated
Broadcast
g
g
s
Ahmed Helmy - UF
g
84
Prune non-member branches
g
g
prune (s,g)
s
prune (s,g)
Ahmed Helmy - UF
g
85
Graft new members
g
g
g
report (g)
graft (s,g)
s
graft (s,g)
g
Ahmed Helmy - UF
86
DVMRP Distribution Tree
g
g
g
s
g
Ahmed Helmy - UF
87
Avoiding duplicates on LANs
• To avoid duplicates, one router per LAN is
elected the Dominant Router
Ahmed Helmy - UF
88
• The router with lowest metric to the source
subnet (with the lowest IP address as tie
breaker) becomes the Dominant router
• A dominant router is ‘the’ forwarder for the
LAN for traffic from the source subnet
Ahmed Helmy - UF
89
DVMRP Forwarding Table
• Entries in a typical DVMRP forwarding table:
– Source Subnet
– Multicast Group
– InPort - The parent port for the (S, G) pair. A "Pr"
indicates that a prune was sent to upstream.
– OutPorts - The child ports over which packets for
the (S, G) pair are forwarded. A ‘p’ indicates prune
message received on that interface.
Ahmed Helmy - UF
90
DVMRP Forwarding Table
Ahmed Helmy - UF
91
Multicast Extensions to
OSPF (MOSPF)
• OSPF V2 is defined in RFC-1583.
• OSPF is a unicast routing protocol that
distributes topology information and
calculates routes for a single domain.
• MOSPF is defined in RFC-1584.
• MOSPF routers maintain a current image of
the network topology through the unicast
OSPF link-state routing protocol.
Ahmed Helmy - UF
92
• MOSPF does not support tunnels
• Basic MOSPF runs in a single OSPF domain
• MOSPF uses IGMP to discover members on
directly attached subnets.
• The Designated Router (DR) is responsible for
sending membership information to all routers in
the OSPF domain.
• The DR floods Group-Membership Link State
Advertisements (LSAs) throughout the OSPF
domain.
Ahmed Helmy - UF
93
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
94
• Source-rooted shortest-path tree is
constructed using Dijkstra's algorithm.
• To forward packets to downstream
members, each router determines its
position in the shortest path tree
• After the tree is built, Group-Membership
LSAs are used to prune those branches that
do not lead to group members.
Ahmed Helmy - UF
95
• All routers within an OSPF domain
calculate the same shortest path trees.
 MOSPF LS-DB allow a router to perform
RPM computation "in memory".
 No need for broadcast and prune.
Ahmed Helmy - UF
96
Forwarding Cache
• Forwarding cache entry contains the
(source, group) pair, the upstream node, and
the downstream interfaces.
• MOSPF Forwarding Cache
Ahmed Helmy - UF
97
• The forwarding cache contains:
– Destination: The group address
– Source: The packet’s source subnet.
– Upstream: The interface from which (S,G)
packets are received.
– Downstream: The interfaces to which (S,G)
packets are forwarded
– TTL: min. number of hops a packet needs to
reach the group members. [This allows the
router to discard packets with no chance of
reaching the members.]
Ahmed Helmy - UF
98
• The forwarding cache is not aged. The
forwarding cache will change when:
 The topology of the OSPF network changes,
forcing all of the datagram shortest-path trees to
be recalculated.
 There is a change in the Group-Membership
LSAs indicating that the distribution of
individual group members has changed.
Ahmed Helmy - UF
99
Limitations
 Limited to OSPF domains
 Flooding membership information does not
scale well for Internet-wide multicsat
Ahmed Helmy - UF
100
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
101
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
102
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
103
How PIM-DM works
• Packets initially flow on broadcast tree
• Forwarded away from source using the RPF
algorithm
– A router forwards a multicast datagram if received on
the interface used to send unicast datagrams to the
source
• Then, Prunes are sent up the tree to remove
branches with no members
Ahmed Helmy - UF
104
How PIM-DM works
Source
A
B
G
C
D
F
H
Receiver 1
E
I
Receiver 2
Ahmed Helmy - UF
105
How PIM-DM works
Source
A
B
G
C
Prune
D
F
H
E
I
Receiver 1
Receiver 2
Ahmed Helmy - UF
106
How PIM-DM works
Source
A
B
G
C
D
F
Asserts
H
E
I
Receiver 2
Receiver 1
Ahmed Helmy - UF
107
How PIM-DM works
Source
A
B
G
C
D
F
H
E
I
Receiver 2
Receiver 1
Ahmed Helmy - UF
108
How PIM-DM works
Source
A
Prune
B
G
C
D
F
Join Override
Prune
E
H
I
Receiver 1
Receiver 2
Ahmed Helmy - UF
109
How PIM-DM works
Source
A
B
G
C
D
F
H
E
I
Receiver 1
Receiver 2
Ahmed Helmy - UF
110
How PIM-DM works
Source
A
B
G
C
D
F
Graft
E
H
I
Receiver 2
Receiver 1
Receiver 3
Ahmed Helmy - UF
111
How PIM-DM works
Source
A
B
G
C
D
F
H
E
I
Receiver 1
Receiver 2
Receiver 3
Ahmed Helmy - UF
112
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
113
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
114
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
115
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
116
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
117
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
118
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
119
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
120
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
121
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
122
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
123
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
124