Printer Friendly

Analysis of routing protocols PIM-DM and PIM-SM for multicast transmission of data using NS-2.

INTRODUCTION

In 1997 the adoption of the concept of the Internet as a linked set of autonomous systems (ASs) began; since then the routing protocols developed guaranteed communication into AS itself. But then came the need to start designing and building standards to ensure routing between ASs (Gacitua, V., 2006). From this perspective is obvious the great advantage that multicast networks have over unicast, where the fact that multicast sending reduces the necessary bandwidth requirement, since this type of communication uses distribution trees for transporting data packets to the destinations of a particular receptor "group". It is important at this point to also note that another advantage of multicast over unicast systems is that many multicast applications involve dynamic groups where members can join or leave the group very often without affecting network performance.

Within the whole aforementioned concept one aspect that is important to define, is related to "multicast routing", which is defined in (Visoottiviseth, V., et al.; 2001), as: given a group M, a set of functions objective of optimization O and a set of restrictions R, multipoint routing is the process of building, based on the topology and status of the network, a multipoint tree T that optimizes the objective functions in O and respects the restrictions set R. According to RFC 3171 (DVMRP., 2014) addresses from 224.0.0.0 to 239.255.255.255 are intended to be multicast addresses. This range is formally called "Class D" in which the sender sends a single datagram from the unicast address of the sender to the multicast address and the router through the knowledge acquired by standard routing would be responsible to make copies and send them to all recipients who have reported their interest in the data of that sender.

Being clear about this concept, this paper aims to present to the community the results found when evaluating the performance of the PIM-SM (Protocol Independent Multicast--Sparse Mode) and PIM-DM (Protocol Independent Multicast--Dense Mode) protocols, as support standards in multicast communication within a networking infrastructure that sends between different AS. For this it divides the paper content into multiple units, beginning with the "Theoretical basis" item where the operation of PIM-SM and PIM-DM is described; followed by the "Materials and Methods" unit, where are specified the characteristics of the topology to be used to evaluate the performance of the protocols, then the "Results and analysis" item qualitatively assesses (using the Network Animator) the data produced by the NS-2 simulator from the simulated internetworking structure for each case. Finally the "Conclusions" and "References" supporting the paper are generated.

Theoretical foundations:

Below are specified in detail the routing protocols proposed to be analyzed in the article, considering that they are those most often used in environments and multicast networks because of their strengths in quality and performance parameters. It is important to stress that this item initially exposes the way the DVMRP standard works since its operation is an essential part of the PIM-DM behavior.

DVMRP (Gacitua, V., 2006):

Distance Vector Multicast Routing Protocol (DVMRP) is a distance vector protocol, used in the MBone (Multicast Backbone), and originally was derived from the RIP (Routing Information Protocol) unicast routing protocol. RIP calculates each next step towards a destination using the Bellman Ford algorithm; Instead DVMRP computes each step from the destinations to the source (backward), based on unicast tables provided by RIP. DVMRP builds trees from a specific source, based on a metric of jumps. The trees are built on demand, and their creation is initiated when a source sends its first packet using the Reverse Path Forwarding (RPF) algorithm. RPF uses the Flood and Prune technique (see Figure 1). This technique involves the sending of packets from the source to all routers in the network (flood) under a minimum-spanning tree formed by such routers. Such a tree is constructed as a Reverse Shortest Path Tree (RSPT) outline. The RPF algorithm takes advantage of existing unicast tables and of the information of existing state of these tables in order to calculate the optimal path to the destination. To understand the DVMRP operation each of the following steps should be considered:

* When a multicast packet is received, the address of the source and

the connection identifier of arrival (p1) is recorded in the source.

* If pi is a connection used to send a unicast packet back to the source (RPF check message), then the packet is sent to all connections except for where it arrived. When a router detects that a packet is not addressed to any of the hosts on its subnet, then it sends a "prune" message to the father router within the RSPT. The pruning message has an associated age, and is updated each time a time threshold is exceeded, again flooding the network. This is done with the hope that new members can join the group, and also allows the protocol to adapt to network topology changes. The Internet Group Management Protocol (IGMP) (Cain, B., et al, 2002) is used in these cases to detect when a member leaves the group. This information is passed "up" to parent routers to prune the tree branches that have no members.

Normally this standard is used over IP-IP tunnels, where the DVMRP router encapsulates the multicast datagram into a unicast datagram before sending it to the remote DVMRP router. The tunnels allow the connection of multicast 'islands' through unicast routers. This will avoid mixing both traffics (unicast and multicast) and their routing protocols so that potential multicast routing problems will not affect unicast traffic.

Operation:

As is known, because it is a distance vector protocol, DVMRP works with source trees (SPT). For its construction it performs a flood and pruning type process. In Figure 1 this process is shown, where it is shown that First the network is flooded forwarding packets from the source through all the interfaces to all the equipment. Then, using pruning messages, those branches that have no interested receivers are eliminated (Waitzman, C., et al., 1988). Once built the tree, packets received by a router are forwarded if the RPF test is met and provided "down" links have not been pruned. If these two conditions are not met, the package is removed (as shown in Figure 2), which shows that the destination that does not belong to the multicast group will not receive the package.

Limitations:

One of the limitations of this protocol is that it is only efficient under the assumption that in many of the branches are clients of the group. Otherwise it would saturate the network with useless messages. Other limitations are derived from its status as distance vector protocol, as the fact of being affected by ties of transition, and its origin in RIP; and the limitations of scalability. Furthermore, it is limited to a small number of emitters, like all protocols using SRTP.

PIM (Bartczak, T., 2009):

PIM is a very efficient routing protocol for IPv4 and IPv6, which is completely independent of any unicast routing table used primarily for checking the performance of Reverse Path Forwarding (RPF). In other words, regardless of the unicast routing protocols used in these networks, PIM takes advantage of the existence of these unicast tables and their contents in order to build and maintain its own multicast routing table like other protocols.

PIM takes its name from the fact that its way of performing multicast routing is independent of the protocol with which has been built the routing table. PIM relies on unicast routing tables constructed by any routing protocol to design its multicast forwarding function both to perform the RPF check and to forwarding itself. Although in principle it is a solution for sparse networks, the result of expanding the use of multicast technology, PIM provides a way to dense routing (PIM-DM) and to a sparse (PIMSM) one, which are explained below.

PIM-DM (Deering, S., 1994):

The Protocol Independent Multicast--Dense Mode (PIM-DM) is a standard that was designed to be used in groups with many members, hence the name PIM "dense mode". As in DVRMP, PIM-DM uses the RPF algorithm with the technique of "flooding and pruning". However, PIM-DM is independent of the unicast protocol present in the network; it simply assumes that the unicast routing tables exist and are symmetrical. In PIM-DM initially multicast datagrams are flooded to all areas of the network (Adams, A., 2003). The RPF algorithm is used to prevent loops as flooding is produced. If any of the areas of the network does not have group members, PIM-DM will prune the branches of this area. When a new member appears in a pruned area, a router can "graft" a new branch on the tree. PIM-DM has a simpler design compared with multicast routing protocols that have mechanisms embedded for discovery of the existing network topology such as DVRMP. PIM-DM does not require network topology information. However, this simplification makes PIM-DM to incur in more overhead because of the "flooding and pruning" that happen to some links that would not need it if more information was available about the network topology (e.g. If a connection is useful or not to reach group members).

Basically, the difference between DVMRP and PIM-DM is that DVMRP, before sending packets through a certain connection, makes sure the connection leads to a node that recognizes the local node as a node that is on the shortest path between it and the source (this ensures that with DVRMP sending packets takes place across the shortest road from source to destination). Unlike DVMRP, PIMDM sacrifices an additional overhead on the network in order to simplify the algorithm for packet forwarding. Apart from the above, the protocol is very similar in many respects to DVMRP.

PIM-SM(Fenner, B., et al, 2003):

The Protocol Independent Multicast--Sparse Mode (PIM-SM) as the name suggests is designed for scattered groups. PIM-SM can use the underlying unicast routing information or build its own base of information for routing. PIM-SM builds for each group a unidirectional shared tree based on a meeting (Rendezvous Point (RP)). Also, it optionally builds a shortest path tree for each source. The main function of the routing tables in PIM-SM is to provide the next step to be followed by a message of unity or pruning to a neighboring router. Data flows through the way reverse to the binding messages. Binding messages flow from destination to source, usually through the RP. Similarly to all routing protocols that implement the service model of RFC 1112 PIM-SM should be able to route packets from source to destination without any sources or destinations knowing a priori the existence of the others. This is essentially done in three phases even when sources and destinations may leave at any time, the three phases occurring simultaneously.

Operation (Gacitua, V., 2006):

First phase: RP Tree: Destinations express interest in receiving traffic for a certain multicast group. One of the local destination routers is chosen as the "designated router" (DR Designated Router) for the subnet as shown in Figure 3.

When the DR receives a message that expresses the interest of the destination to join a group G; then it sends a join message, which is known, as (*, G) Join. The * indicates that the group has not only one specific source. The message (*, G) Join travels hop by hop towards the RP group, and every time this message passes through a router, the state of the multicast tree for group G is updated. Usually the message (*, G) Join will reach the RP or a router that has already received a message (*, G) Join. When multiple destinations have asked to join group G, and their binding posts have converged to RP, they will form a distribution tree for group G, originating from the RP. This tree is known as RP Tree (RPT), which is shared by all sources that send data to the same group. The binding messages are regularly forwarded to the destinations that remain in the group. When all destinations on the network leave the group, the DR sends a prune message (PIM (*, G) Prune) toward the RP of the multicast group. However, if for some reason the prune message is not sent, the state of the tree expires, since it has an associated expiration time. When a multicast source starts sending packets destined to a group, the local router takes this data, encapsulates it as unicast, and sends them directly to the RP. RP destination then receives encapsulated data packets, decapsulates them and sends it over the shared tree. The packets then follow routes established by the multicast tree of the group (*, G), being replicated in all branches of this tree. Thus packages normally will reach all destinations in the multicast group. The process of encapsulating data packets is called "Registering" and the encapsulated packets are called "PIM register packets". At the end of phase one, multicast traffic is flowing encapsulated to RP, and from it towards the multicast destinations.

Second phase: Register Stop: Usually the encapsulation register is inefficient for two reasons:

* Encapsulation and decapsulation may be a relatively expensive operation to run for a router, depending on whether or not the router has an appropriate hardware for the task.

* Travel through all the way to the RP, and only then return to the shared tree could cause packets to travel a relatively long distance to reach destinations that are close to a source.

From this perspective, for some applications increasing latency (time to successfully receive a packet) is undesirable. Since the registration process could continue indefinitely, the RP will elect to support a native sending. This means that when the RP receives a data packet with encapsulation record from a source S in a group G, then an (S, G) Source-Specific Join message will be initiated towards S. This message travels hop by hop towards S, instantiating the multicast tree (S, G) in the routers along the way. The information of the multicast tree routes (S, G) is used only to send packets to group G if those packets come from source S. Union messages that reach subnet S or a router that already has the information of the multicast tree (S, G), starts flowing along the routes provided by the (S, G) tree to the RP. However, these data packets could reach routers with status (*, G) along the path to RP; if this happens, they can take a shortcut over the RP tree at this point. While the RP is in the process of joining the source- specific tree S, data packets will continue to be encapsulated and sent to the RP. When the S packets also start to arrive natively" to the RP, the RP will be receiving two copies of each packet. At this time, the RP starts to discard the encapsulated copies and sends a Register-Stop (back) message to the DR of S to prevent unnecessary encapsulation, of packets. At the end of stage two, the traffic will be flowing natively from S through a specific source tree to destinations. In the place where the two trees intersect, traffic could be transferred from the specific source tree to the RP tree, and thus it avoids taking the fork through the RP. It must be kept in mind that a source could start sending data before or after a destination joins the group, and thus phase two may happen before the shared to destinations tree is built.

Third phase: Shortest-Path Tree: Even when you have removed the encapsulation overhead, this does not mean that the routes chosen are optimal. For many destinations, the route through the RP could mean a significant deviation compared to the shortest path from the source to that destination. For low latency, a router on a LAN of a destination (typically the DR) may optionally initiate the transfer of the shared tree to a specific shortest path (SPT) source tree. In doing so, it sends a (S, G) Join towards S. This message instances the situation in the routers along the way to S. When the join message reaches S's subnet or a router that already has the information on the status of (S, G), the S data packets start flowing along the routes of the (S, G) tree until they reach the destinations. At this time the destinations (or router in its way to the destinations) will be receiving two copies of data, one from the SPT and one from the RPT. When the first traffic starts to arrive from the SPT, the DR or router on the way (upstream) begins to discard packets for G from S that arrive via the RP tree. In addition, it sends a Prune message (S, G) toward the RP. This is known as (S, G, rpt) Prune (Fenner, B., 2003). The prune message travels hop by hop, instancing the status along the path towards the RP indicating that traffic from S to G should not be sent this way. In this regard, the prune message is propagated until it reaches the RP or a router requiring traffic from S to other destinations. At that time, the destinations will be receiving traffic from S through the shorter path tree between destinations and S. Moreover, the RP will be receiving traffic from S, but such traffic will no longer be reaching destinations through the RP tree, implying that for destinations, the shortest path tree is the tree of final distribution.

MATERIALS AND METHODS

The design of multipoint routing protocols must have as main guidelines the following elements, which were taken into account in the construction of the algorithms and simulation of network topology:

* The burden imposed by the algorithm on the network should be the smallest possible.

* Reliable transmission must be ensured, since a reliable transmission guarantees that all data will reach the destination.

* The algorithm must be able to select routes tending to optimal, taking into account different cost functions and constraints imposed by applications and/or users. The routes should remain tending to optimum, although changes occur in the group or network.

* The algorithm should minimize the amount of information that it stores in the routers, so that more groups may be supported without incurring in scalability problems.

* The transmission of data should only reach group members.

For the proposed simulations the Network Simulator 2 (NS_2) (. NS-2, 2014) tool will be used, which consists of its own graphic interface; one to display the packet traffic simulation directly on the network topology (NAM) and the other that displays using a Cartesian plane the operation and variations in time that are to be simulated (XGRAPH) For this case will be simulated in each algorithm bandwidth variations that the topology shows through its nodes and interfaces, under the following criteria.

Simulation criteria:

The network structure on which the PIM-DM and PIM-SM protocol will be implemented is shown in Figure 4, in order to evaluate the behavior of bandwidth for each link in the topology and its variation over time in the simulation.

Topology has the following:

* It consists of one source (n0) that is configured as follows: emitter belonging to group1 sending UDP packets with size of 300 bits and a constant bit rate of 1000kbps.

* 5 nodes are configured (n1, n2, n3, n4, n5) which process packets every 10 ms and that take care of requests with a FIFO (First In First Out_ DropTail) type tail.

* All links are full-duplex type with bandwidth support up to 10 Mb.

For the proper functioning and correct simulation in NS_2, it is required that events be scheduled to determine variations in the sending of messages that ultimately determine likewise variations in bandwidth; this requires to determine in the structure of the network the nodes that will act as receptors interested in the multicast network. For the simulation the nodes n6, n7, n8 and n9 are configured in blue (see Figure 4) that are the destinations that will join as interested in the multicast messages to the network group or otherwise will leave the group indicating that they are not interested in receiving information from the source. For this, the following events were scheduled:

Sec 0.4 simulation starts Sec 0.8 N6 Receiver joins group1 Sec 1.6-n7 receiver joins group1 Sec 2.1-n8 receiver joins group1 Sec 2.7-n9 receiver joins group1 Sec 3.7-n6 receiver leaves group1 Sec 4.1-n7 receiver leaves group1 Sec 5.0 Receiver n8 leaves group1 Sec 5.4 receiver n9 leaves group1 Sec 7.1 N6 Receiver joins group1 Sec 7.7-n7 receiver joins group1 Sec 6.2-n8 receiver joins group1 Sec 6.7-n9 receiver joins group1 Sec 8.9-n6 receiver leaves group1 Sec 9.1-n7 receiver leaves group1 Sec 7.7 Receiver n8 leaves group1 Sec 7.3 n9 Receiver leaves group1 Sec 7.7 simulation ends

RESULTS AND ANALYSIS

The results of the simulations in NS2 in terms of bandwidth and performance of network traffic are validated below.

PIM-DM Simulation:

For the operation of this standard, code was implemented in the TCL script that simulates the characteristics of PIM-DM, where the main feature that makes the call to this routine is known as "PIM-DM" (developed by the authors of the paper): set PMproto PM-DM set mrthandle [$ns prtproto $PMproto {}]

Events arising during the simulation time are described below:

At time t = 0.5 the source sends a flood (red frame) message in order to make the recognition of receivers interested in receiving information flow from said source; these in turn respond with response frames (frames in purple) indicating their interest (Figure 5).

By default in NS2 this process is done every 0.5 seconds, time standardized in the standard (Adams, A., 2003). The simulation indicates that the recipients initially join the group at certain periods of time, which were described in the lines of code shown in item "Materials and Methods". In Figure 6 is basically observed the recognition process for the receivers interested for nodes 6 and 7; being in this way validated that the PIM-DM protocol performs regularly authorizations by flooding and pruning messages from the network status.

At the moment all receiving nodes join the group it is observed that data takes the shortest way to reach the source as seen in figure 7.

The results in terms of bandwidth are shown in Figure 8, their behavior being similar to other receiving nodes since they are carrying the same information (data only). As a particular element should be noted that in the graph shown by the NAM, peaks are observed that appear as the starting product of decongestion of the means of transportation.

PIM-SM Simulation:

To activate this protocol two lines in the NS_2 must be configured (Bhaskar, N., 2008):

$ns mrtproto BST BST set RP_($group1) $n3

Unlike the PIM-DM protocol, PIM-SM does not congest the network with flooding messages; for that a Rendezvous Point (RP) is configured, which is the meeting point for recipients interested in information from the source; thus the origin of the data is constantly connected only to the RP so that the receivers do not flood the links close to the source.

Figure 9 shows the connection between the source and the n3 configured as RP for the implementation of the PIM-SM protocol.

Figure 10 shows that unlike the PIM-DM protocol, PIM-SM connects its interested receivers to the RP because as mentioned, this node becomes the meeting point of the network for group 1.

Seen in Figure 11 are the different bandwidths along the simulation for n2, n6, n9 nodes when the type of traffic being sent is for video, audio and data.

Conclusions:

In this paper a comparison between the most widely used for multicast routing protocols was made, to know its performance in terms of the effectiveness and efficiency with which they manage the network resources.

In multicast networks routing protocols determine their speed and allow controlling the key performance parameters for network operation.

The bandwidth is directly affected regarding the implemented protocol for the proposed simulation; the PIM-DM protocol requires a higher percentage of bandwidth than PIM-SM due to the need to be sending messages of flooding and pruning to know the status of the network.

The currently implemented protocols use as an operating engine algorithms that generate less efficient trees, there are no tools or implementations distributed for these computational implementations, allowing a glimpse of the existence of future research in this field of telecommunications.

ARTICLE INFO

Article history:

Received 12 March 2015

Accepted 28 April 2015

Available online 1 June 2015

Corresponding Author: Nancy Yaneth Gelvez, Facultad de Ingenierias, Department of System Engineering, Francisco Jose de Caldas University, Bogota. Colombia--South America.

E-mail: nygelvez@udistrital.edu.co

REFERENCIAS

Adams, A., J. Nicholas, W. Siadak, 2003. Protocol Independent Multicast--Dense Mode (PIM-DM): Protocol

Bartczak, T., 2009. Validation of PIM DM and PIM SM protocols in the NS2 network simulator.

Bhaskar, N.A., J. Gall, Lingard, S. Venaas, 2008. Bootstrap Router (BSR) Mechanism for Protocol Independent Multicast (PIM), RFC 5059 (Standards Track).

Cain, B, S. Deering, I. Kouvelas, B. Fenner, A. Thyagarajan, 2002. Internet Group Management Protocol, Version 3 RFC 3376.

Deering, S., 1994. Protocol Independent Multicast (PIM), Dense Mode Protocol: Specification, IETF Draft, working progress.

DVMRP. [On line], accessed 10 April 2014, available:http://www.juniper.net/techpubs/en_US/junos11.4/topics/topic-map/mcast-pim-dvmrp.html

Fenner, B., M. Handley, H. Holbrook, I. Kouvelas, 2003. Protocol Independent Multicast Sparce Mode (PIM-SM): Protocol Specification (Revised), Draft IETF.

Gacitua, V., 2006. Evaluation de algoritmos de enrutamiento multipunto en redes de computadores, pp: 15-75.

Specification (Revised), Draft IETF.

The Network Simulator--ns-2. [On line], accessed 15 June 2014, available: http://www.isi.edu/nsnam/ns/.

Visoottiviseth, V., T. Mogami, N. Demizu, Y. Kadobayashi, S. Yamaguchi, 2001. M/TCP: The Multicast-extension to Transmission Control protocol, Muju, Korea, ICACT.

Waitzman, D., C. Partridge, S. Deering, 1988. "Distance Vector Multicast Routing Protocol", RFC 1075.

(1) Nancy Yaneth Gelvez, (2) Oscar Eduardo Gualdron, (1) Danilo Alfonso Lopez S

(1) Facultad de Ingenierias, Department of System Engineering, Francisco Jose de Caldas University, Bogota. Colombia--South America

(2) Facultad de Ingenierias, Department of System Engineering, Pamplona University, Pamplona. Colombia--South America
COPYRIGHT 2015 American-Eurasian Network for Scientific Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Protocol Independent Multicast-Sparse Mode and Protocol Independent Multicast-Dense Mode using Network Simulator 2
Author:Gelvez, Nancy Yaneth; Gualdron, Oscar Eduardo; Lopez S., Danilo Alfonso
Publication:Advances in Natural and Applied Sciences
Article Type:Report
Date:Jun 15, 2015
Words:4350
Previous Article:Design of fast adders with optimal placement and routing in FPGAs using muxed AOI logic.
Next Article:Load balanced deadlock free reconfiguration on wire cum wireless network.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters