PIM-SM Multicast Routing Protocol

Operating System

White Paper

Abstract

This paper is an introduction to the PIM-SM multicast routing protocol, concentrating on version 2. It is intended for IT managers who are already familiar with multicasting, and who want an overview before reading the PIM-SM RFC. PIM-SM was designed to operate efficiently across wide area networks, where groups are sparsely distributed. It uses the traditional IP multicast model of receiver-initiated membership, supports both shared and shortest-path trees, is not dependent on a specific unicast routing protocol, and uses soft-state mechanisms to adapt to changing network conditions.

The information contained in this document represents the current view of Microsoft Corporation on the issues discussed as of the date of publication. Because Microsoft must respond to changing market conditions, it should not be interpreted to be a commitment on the part of Microsoft, and Microsoft cannot guarantee the accuracy of any information presented after the date of publication.

This white paper is for informational purposes only. MICROSOFT MAKES NO WARRANTIES, EXPRESS OR IMPLIED, IN THIS DOCUMENT.

Microsoft, MSN, Windows, and WindowsNT are either registered trademarks or trademarks of Microsoft Corporation in the United States and/or other countries.

Other product and company names mentioned herein may be the trademarks of their respective owners.

Microsoft Corporation • One Microsoft Way • Redmond, WA 98052-6399 • USA

12/99

Contents

Introduction 1

The PIM-SM Protocol 3

Flooding and Reverse Path Forwarding 3

Shortest-Path Trees 4

Shared Trees 6

Examining the PIM-SM Protocol 9

Hello Messaging 9

Forwarding Multicast Packets 9

Joining the Shared Tree 10

The Designated Router 12

Registering with the RP 12

Interface Pruning 15

Assert Messaging 16

Winning an Assert 17

SPT Switching 18

Determining the RP 18

Unresolved Issues 20

PIM-SM Control Messages 21

PIM Control-Message Encapsulation 22

PIM-SM Packet Header 22

Encoded Unicast Address 23

Encoded Group Address 24

Encoded Source Address 24

Assert Message 25

Bootstrap Message 27

Candidate RP Message 29

Hello Message 30

Join/Prune Message 31

Summary 34

For More Information 34

Introduction

Protocol Independent Multicast-Sparse Mode (PIM-SM) routes multicast packets to multicast groups, and is designed to efficiently establish distribution trees across wide area networks (WANs). PIM-SM is called “protocol independent” because it can use the route information that any routing protocol enters into the multicast Routing Information Base (RIB), or, as it is known in Windows terminology, the multicast view. Examples of these routing protocols include unicast protocols such as the Routing Information Protocol (RIP) and Open Shortest Path First (OSPF), but multicast protocols that populate the routing tables—such as the Distance Vector Multicast Routing Protocol (DVMRP)—can also be used. Sparse mode means that the protocol is designed for situations where multicast groups are thinly populated across a large region. Sparse-mode protocols can operate in LAN environments, but they are most efficient over WANs.

A sparse group can be defined as “one in which a) the number of networks or domains with group members present is significantly smaller than the number of networks/domains in the Internet, b) group members span an area that is too large/wide to rely on a hop-count limit or some other form of limiting the scope of multicast packet propagation, and c) the internetwork is not sufficiently resource rich to ignore the overhead of current [dense mode] schemes.”[1]

In contrast, dense-mode protocols such as DVMRP and Multicast OSPF (MOSPF) are designed for situations where multicast groups are widely represented and bandwidth is plentiful. With these schemes, data packets and/or membership report information may be sent out unnecessarily on interfaces that don’t lead to multicast sources or interested receivers; additionally, routers store the associated state for these uninterested nodes, which is also unnecessary. This overhead is acceptable when most hosts are interested in the data and there is enough bandwidth to support the flow of control messages, but is otherwise inefficient. PIM-SM assumes that no host wants data unless it is explicitly requested. PIM does, however, have a dense-mode counterpart (PIM-DM) that is interoperable with sparse mode.

PIM-SM was designed to support the following goals:

· Maintain the traditional IP multicast service model of receiver-initiated multicast group membership. In this model, sources simply put packets on the first-hop Ethernet, without any signaling. Receivers signal to routers in order to join the multicast group that will receive the data.

· Leave the host model unchanged. PIM-SM is a router-to-router protocol, which means that the hosts don’t have to be upgraded, but that PIM-SM-enabled routers must be deployed in the network.

· Support both shared and source distribution trees. For shared trees, PIM-SM uses a central router, called the Rendezvous Point (RP), as the root of the shared tree. All source hosts send their multicast traffic to the RP, which in turn forwards the packets through a common tree to all the members of the group. Source trees directly connect sources to receivers. There is a separate tree for every source. Source trees are considered shortest-path trees from the perspective of the unicast routing tables. PIM-SM can use either type of tree or both simultaneously.

· Maintain independence from any specific unicast routing protocol (see above).

· Use soft-state mechanisms to adapt to changing network conditions and multicast group dynamics. Soft-state means that, unless it is refreshed, the router’s state configuration is short-term and expires after a certain amount of time.

The remainder of this paper expands on these points and shows examples of how PIM-SM operates. It concentrates on PIM-SM version 2, specified in RFC 2362, June 1998 (which has an experimental status), and points out the places where version 2 differs from version 1.

The PIM-SM Protocol

The PIM-SM protocol can be broken down into the following parts:

· Hello messaging

· Forwarding multicast packets

· Joining the shared tree

· Registering with the RP

· Shortest-path tree (SPT) switching

· Pruning interfaces

· Assert messaging

· Determining the RP

We will discuss each part in turn, assuming a stable system, meaning one where the RP has already been elected. The last section will show how this happens.

As a preliminary, we will first talk about:

· Flooding and reverse path forwarding (RPF)

· Shortest-path trees

· Shared trees

Understanding these terms will make understanding the PIM-SM protocol easier.

Flooding and Reverse Path Forwarding

Flooding is a simple scheme for routing that doesn’t depend on having any routing information. In flooding, a packet is transmitted on every interface except the one from which it was received. To limit the number of times a packet is replicated, a metric, such as a hop count, is used. When the metric reaches a given threshold, the packet is dropped.

The problem with flooding is that it creates an exponential number of copies of each packet. So, on the one hand, flooding guarantees that a copy of each packet will be delivered to each node, provided that packets aren’t lost; on the other hand, flooding can generate so much congestion that packets very likely will be lost.

Reverse path forwarding (RPF) is a concept that was first introduced by Yogen Dalal.[2] It is an optimized form of flooding, where the router accepts a packet from source S through interface I only if I is the interface the router would use in order to reach S. It determines whether the interface is correct by consulting its unicast routing tables. This technique dramatically decreases the overhead associated with standard flooding. Because a router accepts a packet from only one neighbor, it floods the packet only once, which means (assuming point-to-point links) each packet is transmitted over each link once in each direction. An example of RPF is shown in Figure 1 below.

Figure 1. Example of RPF

In this example, the router discards the packet that came from a source on network 172.16.0.0/20 through interface I0. This is because its routing table does not list this interface as the shortest path to network 172.16.0.0/20. If the router had a packet to forward to that network, it would use I1. The packet that arrives through interface I1 is forwarded because the routing table lists this interface as the shortest path to the network. Notice that the router’s unicast routing table determines the shortest path for the multicast packets.

Shortest-Path Trees

Shortest-path trees (SPTs) are also called source-based trees, meaning that the forwarding paths are based on the shortest unicast path to the source. This is what we mean when we say that source trees are considered shortest-path trees from the perspective of the unicast routing tables. If the unicast routing metric is hop counts, then the branches of the multicast SPT are minimum hop. If the metric is delay, the branches are minimum delay.

For every multicast source, there is a corresponding multicast tree that directly connects the source to all receivers. Once the tree for a source and its associated group is constructed, all traffic to the members of the group passes along this tree. SPTs have an (S, G) entry with a list of outgoing interfaces, where S is the source address and G is the multicast group. Examples of other protocols that use SPTs are DVMRP and MOSPF, which are dense-mode protocols. Figure 2 below shows an example of an SPT.

Figure 2. Example of an SPT

In this example, the SPT for Source1 is through interface I0 on Router 1, even though there is an alternative path through the combination of Routers 1 and 3. The SPT for Source2 is through interface I3, even though, once again, there is an alternative but longer path. (In this example, the metric is hop counts).

Shared Trees

Shared trees are, for PIM-SM, called RP trees (RPT) since they rely on a central router called the rendezvous point (RP) that receives all the traffic from the sources and forwards that traffic to the receivers. Members send explicit joins to the central node, so there is no assumption that all hosts are receivers. The result is a single tree for each multicast group, no matter how many sources there are. The only routers that know about the group are the ones that are on the tree, and data is sent only to interested receivers. RPTs have a (*,G) entry (called a wildcard entry), where G is the multicast group. With an RP, receivers have a place to join to even if no sources exist yet.

The shared tree is unidirectional, which means data flows only from the RP to the receivers. For a host other than the RP to send on the tree, the data must first be tunneled to the RP before it can be multicast to the participants. This means that if a receiver is also a source, it can’t use that tree to send packets to the RP. It can only use it to receive packets from the RP. (While this is true in general, there are unusual exceptions, such as when the source is located between the RP and the receivers, and is already on the tree. In this case, the data flows directly from the source to the receivers.)

RPTs have longer delays (packets must first be sent to the RP before they can be distributed), but have less router state to maintain. Some examples of applications where an RPT is appropriate include:

· Networks with many low-rate data sources

· Applications that can tolerate delay

· Applications requiring consistent policy and access control across most participants in a group

· Networks where most of the source trees overlap topologically with the shared tree

Conferencing applications can use both the SPTs and the RPT (recall that PIM-SM supports their simultaneous use). The RPT could be used for keep-alive packets, because these are sent at a low data rate. The sources could use the SPTs because they are sending out a great deal of data.

An example of a PIM-SM RPT is illustrated below in Figure 3.

Figure 3. Example of a shared tree

In this example, although the network configuration is the same as in the shortest-path example, the traffic flow is different. All multicast traffic from Source(1) flows through interface I(1) on Router 1 to Router 3, which is the RP; from Source(2), it flows to the RP through interface I(2) on Router 2. (The paths from the sources to this central point are the shortest-path routes.) The RP then distributes the data to receivers that have explicitly joined the multicast group, using a single tree to all receivers. Multiple RPs can exist in a network, but there should be only one RP for each multicast group.

Although each path from the RP to a receiver is the shortest path, the shortest path from the source to the receivers is not the same as the path from the receiver to the RP. A legitimate question is: Why not use the SPT rather than the RPT? For PIM-SM, there are two answers. First, PIM-SM has a method that allows the last-hop router (the one directly attached to the receivers) to leave the RPT and join the SPT if the volume of traffic warrants it. This is called an SPT switch, and is discussed later in the paper. Second, when the RPT is used, routers don’t need to maintain as much state, which decreases the amount of memory required.

Examining the PIM-SM Protocol

We will now examine each of the parts of the PIM-SM protocol, beginning with neighbor discovery. As we stated earlier, we will assume that the RP has already been chosen. In the last section, we will show how this happens. Recall that, when discussing control messages such as Hello and Join/Prune, we are referring to PIM-SM version 2. Version 2 messages are encapsulated in IP packets with a protocol number set to 103. Version 1 messages were encapsulated in Internet Group Management Protocol (IGMP) packets. To see the format for IP encapsulation, or for any of the control messages, refer to the “Control Messages” section at the end of this paper.

Hello Messaging

PIM routers periodically send Hello messages to discover neighboring PIM routers. Hello messages are multicast using the address 224.0.0.13 (ALL-PIM-ROUTERS group). A Holdtime field specifies how long the information is valid. Routers don’t send any acknowledgement that a Hello message was received. Also, unlike some other protocols, such as DVMRP, when a Hello message is received, its interface is not automatically added to the list of outgoing interfaces for forwarding multicast traffic. PIM-SM uses an explicit join model; a downstream receiver must join a group before traffic is forwarded on the interface.