Transcript Reverse path multicast - comp

Group Communications:
Reverse Path Multicast
Dr. Rocky K. C. Chang
19 March, 2002
1
Multicast routing protocols
• All multicast routing protocols build distribution trees.
• So far, distribution trees are mainly either sourcespecific trees or shared trees.
– The former is rooted at an active source for a particular
group, e.g., DVMRP, MOSPF, PIM/DM.
– The latter is rooted at a “core router” for a particular group,
e.g., PIM/SM, CBT.
• In terms of the methods of joining a tree:
– Implicit joins: They use the data itself to control the
building of the tree (data-driven or broadcast-and-prune),
e.g., DVMRP and PIM/DM.
– Explicit joins: A host needs to explicitly join a group before
receiving data, e.g., OSPF, PIM/SM, and CBT.
2
Several approaches
• Reverse path broadcasting (RPB)
– Mainly for broadcasting
– Trade network efficiency for simplicity
• Truncated reverse path broadcasting
– Improve on RPB in terms of network efficiency but need
additional protocols: a distance-vector unicast routing
protocol and IGMP.
• Reverse path multicasting
– Improve on Truncated RPB in terms of network efficiency
by providing pruning and grafting mechanisms.
3
Reverse path forwarding (or broadcast)
• RPB algorithm performs broadcast delivery using
only the local unicast routing table:
– If a broadcast datagram is received over the link that is on
the shortest path to the source,
• the router then forwards a copy of the datagram to each link except
the link from which the datagram is received (the corresponding
router port is referred to as RPB port).
– Else, drop the datagram.
• Each router receives a copy of the datagram over the
reverse of the path used to send unicast packets to the
source.
• When used in multicasting, the group membership is
not considered by RPB.
4
An example
source
member
r1
r2
member
member
5
Reverse path forwarding (or broadcast)
• One problem with this approach is generation of
excess datagrams between r1 and r2 .
– Problem: Excess datagrams between two routers that are
directly connected using their nonRPB ports.
– Solution: Have each router periodically send a message to
each of its neighboring routers, saying “I use this link to
reach these destinations.”
• A router sends copies on only those links that either lead to a host or
lead to a router that claims to use the link to reach the source.
• Now r1 and r2 do not send copies to each other, because they do not
use the corresponding links to reach the source.
• The approach is referred to as extended RPB in Deering’s thesis.
6
Reverse path forwarding (or broadcast)
• However, this approach does not work when routers
are connected by multi-access links.
– If r1 and r2 treat the multi-access link as a host link, they
both forward a copy of datagram from the source to the link,
resulting in duplicate copies.
– If they treat it as a router link, neither sends a copy, because
no router uses the link to reach the source.
7
An example
source
member
r1
r2
8
Truncated RPB
• The truncated RPB uses a distance-vector routing
protocol and IGMP to solve the multi-access problem
and to truncate tree branches.
• On each network k, the attached router that has the
shortest distance back to a multicast source s assumes
sole responsibility for forwarding multicast datagrams
from s to the network (compare IP addresses if tie).
– In the example, k1 (k2) is said to be the child of r1 (r3).
– Each router is able to determine from a distance-vector
routing protocol which of its attached networks are its
children for each possible source.
• A network is a child for s if the network is not the the router’s nexthop network towards s, and if there is no other router on the network
9
with a shorter distance to s.
Truncated RPB
source
:
:
:
:
5 hops
r1
6 hops
r2
k1
r3
k2
10
Truncated RPB
• A leaf network is one that no router uses to reach the
source, e.g., k2 in the example.
• When split horizon with poisoned reverse is employed,
the absence of receiving a “distance of infinity to s”
routing message indicates that a network is a leaf for s.
– In the example, r3 sends a “distance of infinity to s” message
onto k1, but r3 does not receive such a message from k2.
• If an attached network n is a leaf network of router r, n is
also r’s child network.
• Additional states: A list of flags for child networks, and a
list of flags for leaf networks.
11
Truncated RPB
• Truncated RPB Algorithm:
– If a multicast datagram is received from the RPB for the
source,
• a copy of the datagram is forwarded to all child networks for that
source (1) that are not leaf networks or (2) that have members of the
destination multicast group.
• If no interfaces satisfy the two conditions above, the datagram will
be discarded.
– Otherwise, the datagram will be discarded.
• In the example, if there are no members of the
destination group on k2, r3 will discard the datagram.
– Because the only attached network is a leaf network, and
there are no members on that network.
12
Reverse path multicasting (RPM)
• Add an on-demand pruning of multicast trees.
– Routing costs associated with a particular multicast tree are
incurred only while that tree is active.
• When a first multicast datagram is sent from a source
to a group,
– routers do not have information about (source, group).
– The datagram is therefore delivered according to the
Truncated RPB.
• When a router does not need to forward the datagram
to any of its interfaces (because of not meeting the
two conditions in the Truncated RPB),
– it generates a prune message for the (source, group) pair to
13
the next-hop router towards the source.
RPM: Pruning
– If the next-hop router receives prune messages from all of
its subordinate routers, and there are no members on the
attached networks, it also generates a prune message.
– Each prune message is associated with a lifetime.
– Any branch that is pruned from the tree “grows back” after
the lifetime expires.
• Compared with the truncated RPB, now each router is
required to know
– the address of the next-hop router towards the source (for
sending prune messages),
– the subordinate routers--routers attached to its child
networks that use those networks to reach the source (the
truncated RPB only needs to know the presence of
14
subordinate routers).
RPM: Grafting
• In order to be considered for forwarding, a multicast
datagram must meet two conditions:
– (1) It must arrive via the network used to reach the source of
the datagram (the normal RPB requirement).
– (2) There must be no record of a prune message having been
sent for the datagram’s source and group.
• To quickly adapt to the group membership change and
topology change, add a grafting mechanism which
grafts a pruned branch back onto a multicast tree.
– A router may cancel a previously sent prune message by
sending a graft message to the same router.
– The graft message is propagated as far as necessary to rejoin
the originating router into the multicast tree.
15
RPM: Grafting
• Events that trigger a router to generate a graft message
for (s, g), within the lifetime of a previously sent
prune message:
–
–
–
–
Group g membership appears on a child network for s.
A network on which g is present becomes a new child for s.
A new subordinate router for s appears on a child network.
A graft message for (s, g) is received from a subordinate
router for s.
• Unlike prune messages, it is important that the graft
messages are reliably delivered.
• Both Distance Vector Multicast Routing Protocol
(DVMRP) and Protocol Independent Multicast-16
Dense Mode implement the RPM.
An example
B
A
R1
R2
R3
R4
C
R6
R5
R7
17
Distance vector multicast routing protocol
• DVMRP implements the RPM to build per-sourcegroup multicast distribution trees.
• The interfaces of a DVMRP router may be either
– a physical interface to a directly connected network or
– a tunnel interface to another multicast-capable island.
• All interfaces are configured with a TTL to scope a
multicast transmission.
• Each tunnel interface must be explicitly configured
with two additional parameters:
– IP address of the local router’s tunnel interface, and
– IP address of the remote router’s tunnel interface.
18
DVMRP routing and forwarding tables
• DVMRP keeps a DVMRP routing table and a forwarding
table (in a cache)
– Each entry in the routing table mainly consists of a source
network’s address and the interface which is closest to the
source network (for RPB check)
– Each entry in the forwarding table keeps (source network,
multicast group, incoming interface, a set of outgoing interfaces).
• Each incoming and outgoing interface may be in a “prune” state.
• The outgoing interfaces include only those which a copy of multicast
datagram should be forwarded to according to the RPM.
• Upon receiving a multicast datagram,
– use the routing table to check for the correct incoming interface.
– If passed, use the forwarding table for copying the datagram.
19
DVMRP messages
• DVMRP supports five messages types:
– DVMRP Probe: Discover neighbor DVMRP routers by
multicasting the message to the All-DVMRP-Routers group.
– DVMRP Report: Exchange multicast routing information
• Each message contains a list of source networks and a metric.
• First purpose: Ensure that all DVMRP routers have a consistent
view of the path back to a source.
• Second purpose: Determine the leaf routers using poisoned reverse.
• Outcome: The multicast routing table and forwarding table.
– DVMRP Prune: Prune away tree branches.
– DVMRP Graft: Graft back a previously pruned branch.
– DVMRP Graft Ack: Provide reliable branch grafting.
20
DVMRP performance
• Weaknesses of DVMRP:
– Multicast traffic is periodically broadcast across the entire
network; therefore not scalable to a wide-area multicasting.
– A router, which is not on a multicast tree, is still required to
keep state of the tree.
– DVMRP’s state overhead is in the order of SG, where S is
the number of sources and G is the number of groups.
– Similar to its counterpart in unicast routing, DVMRP is
slow to adapt to topology change.
• Advantages:
– “Relatively” easy to implement.
– Suitable for a dense population of members.
– Suitable for “short-term” multicast sessions.
21
Acknowledgements
• The notes are based on
– S. Deering, Multicast Routing in a Datagram Internetwork,
PhD Thesis, December, 1991.
– T. Pusateri, Distance Vector Multicast Routing Protocol,
Internet draft draft-ietf-idmr-dvmrp-v3-09.txt, Sept., 1999.
22