CS6998-03: Advanced Internet Services
Prof. Henning Schulzrinne
Spring 1998
Implementing the Protocol Independent Multicast (Sparse Mode) on the
Opnet Simulation Platform
e-mail:
ctin@comet.columbia.edu
phone : (212) 939-7157
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:
-
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.
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).
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.
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.
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.
- 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.
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.
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.
- 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]
- Steven Deering, Deborah Estrin, Dino Farinacci, Van Jacobson,
Ahmed Helmy, Liming Wei,
"Protocol Independent Multicast Version 2, Dense Mode
Specification" [text]
- Mil 3 Inc., OPNET documentation
- The PIM SM mailing lists: pim-interest@catarina.usc.edu,
pim-implementors@catarina.usc.edu
- Moy, J., "OSPF Version 2", Internet Draft,
, Ascend, November 1997.
Last updated: May 5, 1998 by Constantin Adam and
Chien-ming Yu