CS6998-03: Advanced Internet Services

Prof. Henning Schulzrinne
Spring 1998


Implementing the Protocol Independent Multicast (Sparse Mode) on the Opnet Simulation Platform

Constantin M. Adam

e-mail: ctin@comet.columbia.edu
phone : (212) 939-7157

Chien-Ming Yu

e-mail: chien@comet.columbia.edu
phone : (212) 939-7160


Abstract

During this project, we have implemented the Protocol Independent Multicast - Sparse Mode (PIM-SM) on the OPNET simulation platform.

There are three main problems addressed by this implementation work. PIM SM is a protocol that relies on an underlying unicast routing protocol (like OSPF) to compute routes, create adjacency lists, find out the Reverse Path Forwarding neighbors, etc. It also needs to interact with other lower layer network protocols, like the IP routing and the IP encapsulation protocols. The first problem consists in understanding the interaction of PIM SM with these lower layer protocols. The second problem is how to interpret the protocol specification, which is not always exact. The specification needs to be interpreted and the implementation is taylored to the configuration of the real network that is being studied by the simulation. Finally, the third problem is how to implement the algorithms on top of OPNET; in order to do this, it is necessary to understand the capabilities and the limitations of this simulation tool.

Introduction

In this report, we describe the implementation of the Protocol Independent Multicast - Sparse Mode (PIM-SM) on the OPNET simulation platform.

The remainder of this report is organized as follows:

Related Work

There are several implementations of PIM SM that were available to us during our project. One of them is the PIM SM implementation that is being used by the gated UNIX routing daemon. It is from the University of South California.

The other implementation we had access to is from the Harris Corporation and it is running on top of OPNET. But this implementation does not use dynamic routing algorithms.

Finally, there is a PIM DM implementation developped at Columbia by Xin Wang. This implementation provides support for dynamic routing. Currently, our code represents a modification of this implementation that takes into account the conceptual differences between the two protocols (PIM SM and PIM DM).

Background

PIM SM [1] is being developed to provide a multicast routing protocol in wide-area internetworks. The basic idea behind it is that several hosts wishing to participate in a multicast conference do not justify flooding the entire internetwork with periodic multicast traffic. PIM-SM is designed to limit multicast traffic so that only those routers interested in receiving traffic for a particular group "see" it, as opposed to PIM-DM[2], which is mainly a Local Area Network routing protocol.

PIM-SM is designed to scale to large regions of the internet, and to support sparse-groups; this is groups with a receivership that is small compared to the number of potential receivers. Using PIM SM solves the following three problems:

Protocol Independent Multicast routing protocols are not dependent on the mechanisms provided by any particular unicast routing protocol. However, any implementation supporting PIM requires the presence of a unicast routing protocol to provide routing table information and to adapt to topology changes. The unicast routing algorithm used in our case is OSPF [5] . Also, PIM SM does not specify how will the sources or the data receivers inform their designated routers about their interest to join a particular multicast group. This can be done using the IGMP protocol.

The way in which PIM DM and PIM SM perform multicast routing is different. While PIM DM will flood the traffic to all potential receivers, and let those that don't want the traffic prune themselves of the distribution tree, PIM SM will flood the location of a particular location for each group to all routers, and use this location as a rendezvous point for explicit construction of multicast trees from receivers and senders.

The PIM-SM protocol is implemented on top of the OPNET network simulation tool [3] . OPNET is a comprehensive software environment for modeling, simulating, and analyzing the performance of communications networks, computer systems and applications, and distributed systems. In our case, we can model the network, the nodes in the network and the PIM SM process using the OPNET tools. We have also used other processes from OPNET (the IP routing process, the IP enacapsulation process, the OSPF unicast routing algorithm). The OPNET models and the inter-process communication are described in detail in the next section.

Architecture

Our multicast routing algorithm is running on top of the OPNET simulation platform. In order to run the simulation, we have defined several models (network, nodes, processes), as well as several structured collections of data that are being passed between these processes (the interface control information controls the communication between protocols at different network layers, while the packet formats model the messages exchanged between routers). Here is a brief description of these models:

Implementation Details

During the process of implenmetation, we had several questions and problems on how to explain and understand the PIM SM protocol specification. These questions and problems were due to our insufficient knowledge of PIM-SM protocol itself and other directly related protocols such as OSPF at the time when we encountered them.

As time continued, those questions were solved in many ways. Some of them were solved by help from people including Xin Wang, Columbia University, Paul A. Stirpe, from Reuters and PIM implementor mailing list from University of Southern California. Some of them were solved by experience we gained from codding on the OPNET. We also got answers by reading related documentations and the following web sites.

http://netweb.usr.edu/pim

http://www.isi.edu/~eddy/pim

Through this implementation, we have clarified several parts which are not easy to understand from the PIM SM specification. In this section, we have collected those questions and problems we had and we describe the solutions we have found for them. We believe this information is very valuable for other people who try to understand PIM-SM or want to verify our understanding about the PIM-SM.

Here is a list of questions and answers that we have had. They are listed in chronological order, according to the process of the implementation of PIM-SM on top of OPNET.

Program Documentation

Measurements

There are no measurements in this project, but we can visualize the messages exchanged between routers while they are running our protocol implementation.

The visualization of the bootstrap messages exchanged in the system allows us to present the messages exchanged during the bootstrap router election protocol; they also show us how is the information about the Candidate RPs propagated later to every router in the network by the elected Bootstrap router.

We also visualize the way in which an RP multicast tree is built, as well as how do different routers send prune messages in order to cancel their group membership. Our scenario allows to see what happens in the network when a router joins a multicast group, when it has more than one output forwarding interface for a group, what happens when several routers on the same broadcast network join the group in the same time. We also visualize the prune messages, the delayed prunes, how a delayed prune is cancelled, or how it is sent out; finally, the scenario allows to see what happens when the RP receives a Register message for a group without receivers.

Task List

We have implemented together the PIM SM protocol on top of OPNET. We have used implementation ideas from Xin Wang's PIM DM protocol implementation.

References

  1. Deborah Estrin, Dino Farinacci, Ahmed Helmy, David Thaler, Steven Deering, Mark Handley, Van Jacobson, Ching-gung Liu, Puneet Sharma, Liming Wei, "Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification" [text] [postscript]
  2. Steven Deering, Deborah Estrin, Dino Farinacci, Van Jacobson, Ahmed Helmy, Liming Wei, "Protocol Independent Multicast Version 2, Dense Mode Specification" [text]
  3. Mil 3 Inc., OPNET documentation
  4. The PIM SM mailing lists: pim-interest@catarina.usc.edu, pim-implementors@catarina.usc.edu
  5. Moy, J., "OSPF Version 2", Internet Draft, , Ascend, November 1997.

Last updated: May 5, 1998 by
Constantin Adam and Chien-ming Yu