Network Routing Protocol

Published:

The selection of an appropriate routing protocol is a key issue when designing a scalable and efficient wireless networks. In this paper, we investigate different routing protocols and evaluate their performances on 802.16 WiMAX networks.

Introduction

Wireless networks play an important role in modern era for transmitting data with minimal overhead and maximum possible speed. These networks have become more efficient with the introduction of mobility concept of nodes. Two variations of such networks exist. The first one called structured wireless networks, have fixed main nodes concerned with routing or switching of data (sometimes called gateways or base stations). These gateways are usually fixed in nature and are connected to each other using wired or wireless links. These networks are mainly used in office wireless local area networks (WLAN). The other type of networks called infrastructreless or ad hoc networks embeds the concept of mobility within the routing nodes. The nodes communicate with each other using multi-hop wireless links. These networks have no fixed routing nodes. All nodes are capable of movement and can be connected in any random manner. These networks are mainly used in disaster or emergency areas where no prior fixed infrastructure exits.

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

One of the challenging aspects in these ad hoc networks is to find and develop routing protocols that can efficiently find routes between any two nodes. The routing protocol should take into account the mobility factor in these networks and the topology being used. For this reason, performance evaluation of various protocols has been carried out by different authors. In [1], performance of Dynamic Source Routing (DSR) and Ad Hoc On-Demand Distance Vector Routing (AODV) has been considered. The performance is analyzed using various network load, mobility and network size. Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) is another protocol which is a table-driven protocol used in wireless networks [2]. Various performance parameters for these protocols have been explored including packet fractional delay (PDF), average delay, throughput, goodput, normalized routing load (NRL) and routing overhead (RO). Considering the challenging and demanding aspects by the modern wireless systems, the broadband wireless access industry, which provides high-rate network connections to stationary locations and end stations, has advanced to a point at which it now has a robust standard for second generation wireless metropolitan area networks. IEEE 802.16 standard which is well known as worldwide interoperability for microwave access (WiMAX) is the solution for such wireless networks [3]. When this technology is considered for mobile networks, it is expected to provide around 15 Mbps of channel capacity within a particular cell.

In this paper, we have evaluated the performance of DSR, AODV and DSDV in WiMAX networks and studied various performance parameters for such networks. The remainder of this paper is organized as follows: section 2 gives a brief introduction to WiMAX networks and the standards being used at the medium access control (MAC) layer. In section 3, details of DSR, AODV and DSR routing protocols are presented. The performance analysis of the three routing protocols in WiMAX networks has been carried out in section 4. Finally, the conclusion of our work is summarized in section 5.

IEEE 802.16 Networks

The IEEE Standard 802.16-2001 [3] defines the WirelessMAN air interface specification for wireless metropolitan area networks (MANs). The completion of this standard signs the entry of broadband wireless access as a major new tool in the effort to link end stations to core telecommunications networks worldwide. It was developed to include a set of air interfaces based on a common MAC protocol but with physical layer specifications dependent on the available frequency range. The spectrum range is from 10 to 66 GHz, as approved in 2001, which is currently available worldwide but at the expense of some physical deployment issues.

The standard defines the specifications related to the service-specific convergence sublayer (CS), the MAC common part sublayer (CPS), the security sublayer, and the physical layer. The MAC management messages are implemented to operate the WiMAX networks. All operations between the base station (BS) and subscriber station (SS) over a super frame interval follow the procedures of the 802.16 standard.

Basically, the IEEE 802.16 MAC protocol [4]-[5] was designed for point-to-multipoint broadband wireless applications. High data rates at both uplink and downlink is considered to be the main objective of this standard. Resource allocation algorithms are used for channel sharing among users. The 802.16 MAC layer supports continuous and burst nature traffics. The first sublayer in the MAC layer is the convergence sublayer which is used to map different traffics to a form compatible with WiMAX MAC traffic type. The second layer is the common part sublayer which provides the core MAC functionality of system access, bandwidth allocation, scheduling, contention mechanism, connection establishment, and maintenance. It receives data from various sources through the MAC service access points (SAPs), which is classified to particular MAC connections.

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

The quality of service (QoS) types supported by WiMAX are unsolicited grant service (UGS) for the constant bit rate (CBR) service, real-time polling service (rtPS) for the variable bit rate (VBR) service, non-real-time polling service (nrtPS) for non-real-time VBR, and best effort service (BE) for service with no rate or delay requirements. Traffic classes are associated with certain QoS parameters and according to these parameters, MAC scheduler makes appropriate handling. The upper-layer data are queued with an assigned connection ID.

For the uplink traffic, each SS should range to the BS before entering the domain. In the first ranging duration, a burst record is established between SS and BS which includes interval usage code (DIUC) to the BS. Similarly, after that, uplink interval usage code (UIUC) is going to be agreed upon between BS and SS. The downlink-MAP and uplink-MAP which contain the channel ID and the MAP information elements (IEs) describes the physical layer specification. The burst profile includes the DIUC, UIUC, and the type-length-value (TLV) encoded information. The burst profile also includes type-length-value (TLV) encoded information. The TLV encoded information will notify the physical layer of the modulation type, (Forward error control) FEC code type, and encoding parameters (e.g. coding rates). The final MAC data payload is packed by these encoding types. The IEEE 802.16 uses the frame-based transmission architecture where the frame length is variable. These frames called superframes are divided into two subframes: downlink subframe and the uplink subframe.

In [5], authors developed a WiMAX module called Mac802._16 which is in accordance with the specifications of the IEEE 802.16-2004 standard and based on the ns-2 version 2.29. We have used the same module for our simulations.

Routing Protocols

Since our simulation results are based on three routing protocols, specifically, DSDV, DSR and AODV, a brief detail of these protocols is given below along with their performances in IEEE 802.11 ad hoc networks.

DSDV

This is one of the table-driven routing protocols based on the Bellman-Ford routing mechanism. In table-driven routing protocols [6], the main objective is to maintain consistent and up-to-date routing information from each source node to other destination nodes in the network. Each node maintains one or more tables to store the required routing information. These tables are updated according to changes in network topology by propagating update information throughout the network. Two key elements are important in such protocols, the number of routing tables and the update method being used.

In DSDV, the entries in the table are indicated by numbers assigned by the destination node. These numbers act as status indicators of the nodes which therefore minimizes routing loops. Routing update packets are transmitted throughout the network to maintain table consistency. These packets indicate which nodes are accessible from each node and the number of hops required reaching the destination nodes using distance-vector algorithms. These update packets can result in large amount of traffic. Two types of update packets are present in DSDV based networks. The first one which is infrequently transmitted is called the full dump. This type of packet carries all available routing information. The second type called incremental packet is used to forward only that information which has changed since the last full dump. Both update packets have fixed size network protocol data unit (NPDU).

AODV

This protocol is based on source-initiated on-demand routing. This type of routing creates routes only when desired by the source node. Route discovery process starts on demand by the source. This process is completed once a route is found or all possible routes have been explored. It provides unicast, broadcast, and multicast communication in ad hoc mobile networks [7]. Routes are maintained as long as they are needed by the source node. AODV nodes maintain a route table in which next hop routing information for destination nodes is stored.

When a source node desires to send a data to a destination node and no route information is available, a path exploration process to find the destination node takes place. It broadcasts a route request (RREQ) packet to adjacent nodes, which in turn, forward the request to their adjacent nodes, and so on, until the destination node is found. Each node maintains a sequence number and a broadcast ID. The broadcast ID is incremented for each generated RREQ. The RREQ packet consists of the node sequence number, broadcast ID and the most recent sequence number it has for the destination node. Only those nodes reply to the RREQ which have their sequence numbers greater than or equal to that contained in the RREQ.

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

DSR

DSR protocol [8] is another on-demand routing protocol that is based on the concept of source routing. It allows nodes to dynamically discover a source route across multiple network hops to any destination in the ad hoc network. The protocol is a combination of two steps: route discovery and route maintenance. When a node wants to transmit data to a destination node, it checks it own cache for an existing route. If a route is available, the source node uses that route otherwise a route discovery takes place. A route request packet is generated containing the source and destination address, along with a unique identification number. Each intermediate node intercepts this packet and checks whether it is familiar with a route to the destination node or not. If it does not know about the route, it adds its own address to packet and forwards the packet to the next node. A reply is generated by the final node when the route request packet reaches the destination or when an intermediate node finds an unexpired route to the destination.

Performance Evaluation of 802.16 Networks using Routing Protocols

In this section, we have investigated the performance of the three protocols in WiMAX networks. The results shown in Fig.1 are obtained using the following parameters: CBR traffic type with 50 nodes having 20 maximum connections. The nodes maximum speed is 20 m/s and generating packets at the rate of 4 packets/s. The simulation is carried out for 900 simulation time and using a topology size of 1200 by 300. In Fig.1 (a), the PDF for DSDV outperforms that of both DSR and AODV. For highest mobility, almost 75% of the packets are delivered in case of DSDV. Further, almost 100% PDF is achieved at 500 pause time. The PDF performance for both on-demand routing protocols is very poor. But as shown in Fig.1 (b), the average delay is high in DSDV compared to both DSR and AODV for the first 30 seconds of pause time after which the delay is almost the same for all protocols. Similarly, Fig. 1 (c) shows the goodput for all the protocols. Goodput is the number of data packets successfully sent and received by the entire network within a certain period of time which is proportional to PDF. As expected, DSDV has the best goodput and outperforms the other two protocols.

The performance of the protocols in terms of normalized routing load, which is the number of routing packets transmitted per data packet delivered at the destination, and the routing overhead, which is the total number of routing packets transmitted during the simulation are shown in Fig.1 (d) and (e) respectively. Both these parameters measure the scalability of a protocol, the degree to which it will function in congested or low bandwidth environments, and its efficiency in terms of consuming node battery power. These two parameters are related to PDF in the sense that lower PDF means that the delay metric is evaluated with lesser number of samples. Longer the path lengths, the higher the probability of a packet drop. Hence, sending large numbers of routing packets can also increase the probability of packet collisions and may delay data packets in network interface transmission queues. Thus, with a lower PDF, samples are usually biased in favor of smaller path lengths and thus have less delay [1].As indicated in the figure, DSDV has highest routing overhead whereas both on-demand protocols have very low routing overhead. For this reason, in DSDV, packets exhibit more delay because of the increase in probability of packet collisions. For this reason, the key motivation behind the design of on-demand protocols is the reduction of the routing load.

Figure 2 shows the performance for all the protocols using different nodes. For this simulation, the pause time is fixed to zero, the data rate is 2 packets/s and the maximum number of connections is 10. PDF for all the protocols have the same pattern. For a fixed number of nodes, the PDF DSDV is better than those for the other two on-demand protocols. For average delay, it is interesting to see that the number of nodes in DSR has no impact on the delay. Further, for higher number of nodes, the delay converges to the same value. For NRL, the performance is almost the same for all nodes with DSR and AODV. But this performance shoots up for DSDV. Although at 50 nodes, the average delay for all the protocols are same, but the routing overhead difference between DSDV and DSR or AODV is considerable.

Based on the previous results, Fig. 3 shows the performance of the best protocol DSDV (i.e. PDF performance wise) for different number of connections and varying data rates. The PDF for DSDV as the number of connections and data rate vary has no large impact. But for the average delay, variation of delay is produced when the data rate is 2 packets/s. But as the data rate increases, the system becomes more stable in terms of end to end delay. On the other hand, as the number of connections increases, the NRL decreases for a fixed data rate. This is because the total number of data packets increases as the number of connections increases (i.e. larger number of nodes sending packets) and becomes much larger than the routing packets. Also, from the RO figure (fig. 3 (d) ), the number of routing packets is almost the same for all the connections.

Conclusions

Different routing protocols behave differently in 802.16 networks according to their internal working mechanism. It has been seen that the table-driven DSDV protocol has the best performance in terms of the packet delivery fraction parameter which outperforms both DSR and AODV but the delay experienced by DSDV packets are greater than the delay experienced by the on-demand routing protocols.

References

[1] Samir R. Das, Charles E. Perkins, and Elizabeth M. Royer. "Performance Comparison of Two On-demand Routing Protocols for Ad Hoc Networks." Proceedings of the IEEE Conference on Computer Communications (INFOCOM), Tel Aviv, Israel, March 2000, p. 3-12

[2] Charles Perkins and Pravin Bhagwat, Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers, in Proc. ACM SIGCOMM, London, United Kingdom, October 1994, pp. 234 - 24

[3] IEEE 802.16-2001, IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed Broadband Wireless Access Systems, Apr. 2002

[4] Carl Eklund, Roger B. Marks, Kenneth L. Stanwood, Stanley Wang, "IEEE standard 802.16: A technical overview of the wirelessMANTM air interface for broadband wireless access", IEEE Communications Magazine, vol.40, no.6, Jun 2002, pp.98-107

[5] Chiang-Wei Chang, Jenhui Chen, Jhenjhong Guo, Chih-Hsin Hung, Wei-Jen Lien, Syao-Syuan Liu, Jui-Hsiang Sum, Frank Chee-Da Tsai and Chih-Chieh Wang, The design and implementation of WiMAX module for ns-2 simulator, in Proc. Workshop on ns2: The IP network simulator, Pisa, Italy, October 2006

[6] E.M. Royer and C-K Toh., A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks,. IEEE Personal Communications, vol. 6, no. 2, pp. 46-55, Apr. 1999

[7] Elizabeth M. Royer and Charles E. Perkins, An Implementation Study of the AODV Routing Protocol, in Proc. IEEE Wireless Communications and Networking Conference (WCNC 2000), Chicago, IL, September 2000

[8] David B. Johnson, David A. Maltz, and Josh Broch. DSR: The Dynamic Source Routing Protocol for Multihop Wireless Ad Hoc Networks, in Ad Hoc Networking, edited by Charles E. Perkins, chapter 5, pp. 139--172. Addison-Wesley, 2001