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

Chien-Ming Yu

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:

• The Background section gives information about OPNET, about IP routing multicast protocols, and in particular, about the Protocol Independent Multicast protocols (PIM DM and PIM SM). It also highlights the differences between PIM DM and PIM SM.
• The Architecture section describes the models that have been defined in order to run our implementation on top of the OPNET simulation platform. It also explains the interaction of PIM SM with the other simulation processes and the way in which the models are being used during the simulation.
• The Implementation Details section describes the problems and solutions we have encoutered and found during the process of the implementation. It points out several parts of PIM SM protocl which are not easily understood or clearly expressed. The content of this section can be regarded as FAQ from the view of implementors.
• The Program Documentation section contains a pointer to the user manual for our implementation.
• The Measurements section describes the scenarios and the probes we use in order to visualize our work.
• The Task List section lists the tasks accomplished by each member of our team, and the external resources used in this project.
• The References section contains pointers to the reading materials we have used in this project.

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:

• Hosts should not need to know which routing scheme is in use in their locality. This allows the routing protocols to evolve separately from host applications.
• Routers should not need to know about groups for which they are not on the distribution tree. This is necessary for multicast routing to scale.
• Multicast routing should depend only on unicast routing. It should not depend on any higher-level services such as host directories or DNS as we would like to be able to build such services using multicast.

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:

• The Network Model - defines the topology of the network on top of which we are running our simulation. The topology of the network is the same as the one presented in the OSPF RFC.

  

• The Node Models - define the internal structure of the routers and the end-stations in the network. They define a set of processes that are running inside each network component, as well as the interaction between these processes.

  

• Process models - our efforts have concentrated on developping the PIM SM process. Other processes we have interacted with are the IP Routing, IP Encapsulation and OSPF processes (these processes are represented in our figures by the pim_sm, A1_ip3m_rte and A1_ip3m_encap boxes). However, in order to ensure portability and simplicity, we did not make any changes to these processes; we have used their original OPNET implementation.
• When a packet is sent through the network, it will get a new header added to it as it goes through every network layer. The communication between these network layers is modeled by the interface control information structures. In our case, we are using the 'ip3_encap_ind' and 'ip3_rte_ind' ICI formats for incoming packets and 'ip3_encap_req' and 'ip3_rte_req' ICI formats for outgoing packets.
• Each PIM SM packet is described using a packet format. This provides an abstraction that helps sources and receivers to code and decode the packets consistently. Different fields in each message can be retrieved by name or by index.
• Inter-Process communication: PIM SM is created as a process model. In order to communicate with the other OPNET processes, it needs to be initialized in the following steps:
  • Each process has two ids (one inside the global simulation, the other one inside PIM SM simulation), a name and a handle. These are the four parameters that are passed in order to register the process with the model-wide registry.
  • For each PIM SM process, we need to create routing information. There are two routing tables - the OSPF routing table that is accessed using a pointer to it and a pointer to the lookup function, and the multicast routing table that is used to forward the multicast packets, dynamic routing information, that describes the interaction with OSPF. The process name and dynamic routing information attributes of the process are set in the model-wide registry.
  • Right now, we are scheduling some join and prune messages in order to simulate hosts joining and leaving the groups. However, in the future, this should be done using the IGMP protocol. Another handle that allows PIM SM to communicate with IGMP should be added in the future.
  • PIM SM cannot run by itself. It needs an underlying unicast routing protocol (in this case OSPF). It needs to find this process inside its own node, and get a handle to it. It also needs a pointer to the OSPF lookup function and to the OSPF routing table.
  • For each interface of the router, a data structure describes its PIM SM behavior. (More details about the interface structure).
  • Each PIM SM multicast routing table entry is defined by a structure that contains the destination multicast group address, the source address, the list of output interfaces, and the input interface. Each routing table entry can contain a certain set of timers, for scheduling in the future the sending of particular messages.
• Animation Probes - we are visualizing the messages exchanged during our simulation on an animation display. OPNET allows to visualize a simulation while running it. The simulation will open a socket connection to a visualization tool. The animation can also be run after the simulation is over, from a history file. We are tracing different types of packets in the network. The animation can be played using the m3_vuanim utility. This generally provides the visualization of packets flows so that we can check the correctness of our implementation, debug our code, and present it in a very intuitive way.
• Simulation model - PIM SM simulation - this is the simulation object. In order to study the behavior of our program, we need to run this simulation. If we want to visualize the algorithm, we also need to bind an animation probe to the simulation object.

Implementation Details

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.

• Bootstrap messages: A Bootstrap message carries the RP-set information collected from all the Candidate RP routers. The list is sent by the elected Bootstrap router to all the PIM-SM routers, that can be reached using the IP address 224.0.0.13.
  • Question: Why certain routers cannot be configured as candidate or elected Bootstrap and Candidate RP routers?
  • Answer: The current OSPF model as implemented in OPNET (as well as the OSPF RFC specification) implies that OSPF does not provide routing information to non-stub routers which do not connect to any networks or hosts. The column of destination address of the OSPF routing table only contains entries toward networks or hosts. Packets can not be routed to these non-stub routers by routing table lookup. In the beginning, we have set non-stub routers as Candidate Bootstrap routers, and our program did not work. This information was provided to us by the MIL 3 technical support.
• Candidate RP advertisement: This message carries multicast groups supported by the sending router which is configured as Candidate router.
  • Question: What is the impact if the RP-set information on each router is not consistent with one on the other routers?
  • Answer: This circumstance will cause the join and prune messages as well as register messages from DR of source not be able to reach the same RP. Only those downstream routers which have the same RP as DR of source does can receive packets. A router that receives a message destinated to a group, but that does not have the same group RP as its own group RP will discard the message. Failure to do so will result in loops, where two or more routers will increase each other's multicast routing tables with cyclical information.
• Join shared RP tree: Every last-hop router which receives IGMP membership reports will send Join and Prune message to DR if on the multiaccess network or reverse path forwarding neighbor router toward RP.
  • Question:What is the content of a single join/prune message.
  • Answer: A hash funciton is used to map a group to one of C-RPs from RP-Set. Information about groups that have the same RP is not necessarily sent in a single join/prune message. Instead, the join/prune messages will be merged if they are sent via the same RPF neighbor toward different RPs.
  • Question:Join/prune messages are sent out periodically from last-hop router. When an upstream router receives this join/prune message, will it forward it to the next hop toward to RP until they reach the RP?
  • Answer: The intermediate routers only forward the incoming join/prune message when there is no corresponding entry in the Multicast route table. If the entry is already there, the router will check the group address and will not forward this join/prune message. But every Join Period the router will periodically check its Multicast routing table, and will send join/prune messages. If it does not do this, then the upstream routers will timeout that entry and remove it. Triggered messages are only sent out when the entry is created or destroyed.
• Sending data on the shared RP tree.
  • Question: How can the DR send the Register message to RP?
  • Answer: DR does not simply encapsulate the packet destinated to the group G to the RP which is the mapping of G from hash function. It creates a (S,G) entry first but the register-supprssion-timer is turned off for this entry. As long as this timer is off, all the data destinated to group G and received from the directly connected hosts will be encapsulated and sent to RP through encapsulated unicast packets.
• Switching from shared RP tree to shortest path tree.
  • Question:What happens if the source specific shortest path join/prune messages cannot reach the DR of this specific source, S?
  • Answer:RP will send join/prune messages toward DR of this specific source, S for switching to SP-Tree. If this message can not reach the DR, then DR will never be able to turn off the register-suppression-timer of (S, G) entry and send data natively to RP. Therefore the switch to the shortest path tree between DR and RP will never take place.
• Prune message on multiaccess network:
  • Question: When will prune messages trigger join messages.
  • Answer:Prune messages are sent upstream toward RP. In the following network, the prune message is going downstream to the router RT 2. In this case RT 2 which receives this prune message with (S, G) and (*, G) on the iif of its active (S, G) and (*, G) entries will send join message in order to prevent DR to cut the interface to the network on which RT 2 is.

    

• Assert messages.
  • Question: When will assert messages be sent?
  • Answer: Data packets are sent downstream toward last-hop routers. When a router receivers data packets from its oif of its corresponding (*, G) entry, it will send Assert messages so that other router will decide not to forward data packet to the interface on which it receive assert messages. In the following network, we can see a normal situation in which assert messeages will be needed. RT 2 sends join message for group G to DR, on the same time RT 1 sends join message for the same group G to its RP alone the path of reverse path forwarding. Now both DR and RPF are forwarding data for group G. In this case, packets are duplicated since both DR and RPF will forward packets received from RP.
• Multicast route table
  • Question:(S,G) entry is kept alive by data packets arriving from that source; what will happen to a (*,G) entry when it will expire?
  • Answer:(*,G) will not expire as long as there are directly connected hosts sending IGMP membership reports to the DR. This (*, G) is teared down only if there are no hosts that members of the group and the output interface is null.

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.