Performance Improvement of Efficient Routing Protocol Based on Small End-to-End Sequence Numbers
Performance Improvement of Efficient Routing Protocol Based on Small End-to-End Sequence Numbers
Journal of the Korea Institute of Information and Communication Engineering. 2014. Jul, 18(7): 1565-1570
Copyright © 2014, The Korea Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License( which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : May 24, 2014
  • Accepted : June 23, 2014
  • Published : July 31, 2014
Export by style
Cited by
About the Authors
장영 김

In networking communication, nodes and base station send data to each nodes and destination nodes. In this perspective, it is very important to determine the direction in which data sent to each nodes or destination nodes. Ad-hoc routing protocol is a standard routing protocol that determines how the packets sent to destination. Ad-hoc routing protocol includes protocols such as Ad-hoc On-demand Distance Vector (AODV) and Dynamic Source Routing (DSR). In our efficient proposed protocol based on small end-to-end sequence numbers, route direction can be changed properly with the assistance of helper nodes. In this paper, we focus on the simulation analysis of proposed protocol and comparison with other routing protocol models such as AODV and DSR. We simulated using Network Simulator (NS-2) by parameters such as simulation time, number of nodes and packet size based on our metrics (packet delivery fraction, routing load, data throughput). Our proposed protocol based on small end-to-end sequence numbers shows better performance and superior to other two protocols.
Mobile Ad-hoc Networks (MANET) [1] include several lists of ad-hoc routing protocols. In addition, there are two representative categories: pro-active and reactive (on-demand) protocols. One example of pro-active protocols is DSDV (Destination Sequenced Distance Vector), which is based on Bellman Ford algorithm; this computes shortest paths in weighted graphs [2] . The DSDV (Destination Sequenced Distance Vector) protocol is suitable for a small number of nodes but not proper for dynamic networks. The disadvantages of this pro-active protocol are a large amount of data and slow response for maintenance. On the other hand, reactive (on-demand) protocol sends packets based on the packet requests. Thus, the reactive protocol minimizes the extra consumptions and is more efficient than pro-active protocol, especially with large numbers of nodes and traffic network communication. The proposed protocol (small end-to-end sequence numbers) [3] is motivated by the disadvantages of the reactive and pro-active protocols. The two representative protocol AODV (Ad-hoc On-demand Distance Vector) [4] and DSR (Dynamic Source Routing) [5] are based on route discovery and maintenance.
The above two protocols attempt to transmit data and packets with reliability. However, when the routes failed or other problems occurred on route maintenance, it will be inefficient to use those routing protocols. Furthermore, in MANET, the route maintenance mechanism works dynamically and routes needed to be changed often when a link failed. So we can consider a more dynamic and efficient protocol based on small end-to-end sequence numbers. Sequence numbers are ordered numbers arranged in segmented packets or data that transferred. For example, we need to send 100 Bytes of data through 10 Byte Internet connections. We need to partition into 10 segments by sequence numbers to send data. Hence, it will be more efficient when it is based on small sequence numbers.
DSR is the first representative routing protocol of a reactive protocol. It is similar to AODV in that it is based on packet requests. However, DSR uses source routing instead of routing table. DSR mechanism accumulates the address of each device between source and destination during route discovery. The path information is cached by node processing. The paths are used to route packets. To do source routing, the packets contain the address of each device that the packet will traverse. This may result in large overhead or large addresses. To avoid this issue, DSR forwards packets on a hop basis optionally. In DSR, a route is established only when it is required so the need to find routes to all other nodes in the network as required.
The next reactive protocol is AODV. Generally, AODV is motivated by disadvantages of DSR but DSR has better performance of packet transmission in some cases. AODV is a routing protocol proper for MANET and other wireless ad-hoc networks. It establishes a route to a destination only on demand. AODV avoids the counting-to-infinity problem of other distance vector protocols by using sequence numbers on route updates. For our proposed protocol based on small sequence numbers [3] , [7] , we have conceptualized the use of end-to-end sequence numbers utilizing performance metric based on the resource availability of participating nodes. In this protocol, routes change dynamically with feedback responses. This protocol deals with the problem of communication to a base station or a network of multiple base stations, with the assistance of helper nodes. These helper nodes can be implemented to relay data to the base stations or other nodes. The route can change based on window information and sender desires. Route establishment and end-to-end acknowledgement re-send are not needed. If helper nodes or nodes are used, there is additional hop-by-hop acknowledgement. The return acknowledgement can be relayed back on the same route. Whenever a node joins as a helper node, it can distribute resources dynamically.
- 3.1. Protocol Topology
This section will introduce and describe the wireless efficient protocol based on the small end-to-end sequence numbers. As Fig.1 shows, the sender node is “X” and the base node is the “Y”. Two intermediate nodes are helper nodes (H1 and H2). The helper nodes relay and guide the packets and data to their destination. The sender node sends data and packets and the base node receives data. In this topology, helper nodes have an important role for route discovery and packet transmission performance.
PPT Slide
Lager Image
프로토콜 토폴로지 Fig. 1 Protocol Topology
- 3.2. Protocol Assumptions
In previous Fig.1 , station X is willing to communicate with station Y. Station X has an address IDX and station Y has an address IDY. Let H# denote a helper node, where # means a number of hops. Routes can be changed dynamically and no pre-establishments needed. Ranges are short and collisions between nodes can be minimized. In some cases, limited collision avoidance can be employed. We can also assume that the network is of the wideband, low utilization type. This is a common situation with low energy, short range transmissions.
In Fig.2 , sender X wishes to send a “seek” packet to Y with the address of X which is IDX to Y (IDY). Sender X and Base station Y can communicate directly. If Sender X and Base station Y cannot communicate directly, Sender X needs to send a “seek” packet to helper nodes. After Helper node H receives a “seek” packet, it sends an “offer” packet to Sender X. After the T time expires, the data can be forwarded from Sender X to Y.
PPT Slide
Lager Image
메시지 다이어그램 [3] Fig. 2 Message Diagram [3]
Helper nodes (H) information in the “offer” packet will be a “window length” that indicates the number of packets that the helper nodes can control in time T. T is a system constant. The window length is a variable that can change dynamically with the helper nodes and varies with number of hops to the destination nodes. Apart from data itself, data packets include the sender ID, destination ID, relay ID (helper node) and a sequence number.
- 3.3. Protocol Description
The protocol description contains three main parts. First, small number based on window size of W packets in T seconds. Second, the intermediate station can not send any packets more than T seconds after received, which means that if packets are older than T seconds, then they will be discarded. Third is the limitation on the number of hops. The source has maximum window size of W packers and transmitted time T. One objective is to reduce the number of bits in the sequence number that prevents ambiguity. If the sequence number is large, there will be a high probability of making ambiguity. This is also one of the main goal to propose an efficient routing protocol based on small sequence numbers. Sometimes, the source or sender stations change routes or send the same copies to different nodes or destinations. In this case, the ambiguity problems also may occur which is the reason why we need to design based on small end-to-end (station-to-station) sequence numbers protocol. In addition, to maintain our previous assumptions, we exclude the situation related to out-of-order transmissions. Our protocol is implemented for a small number of hops and short range which is proper for wireless communication networks.
In this section, we set the simulation parameters using Network Simulator (NS-2) [8] and define the performance metrics (packet delivery fraction, routing load, data throughput) with three protocol models such as AODV [4] , DSR [5] and E2ESeqNumAgent [3] . In Table.1 , we set the eight parameters, which can be adjusted. This simulation is based on 500m by 500m map size and CBR (Constant Bit Rate) traffic type. CBR is also useful for streaming multi-media content and packets or data transmission in the wireless communication networks.
시뮬레이션 파라미터Table. 1Simulation Parameters
PPT Slide
Lager Image
시뮬레이션 파라미터 Table. 1 Simulation Parameters
Other parameters are number of nodes and packet size. The packet size is fixed to 512 bytes which is same as 512*8 bits. Number of nodes are 25 nodes and 50 nodes. The connection rate is also fixed to 8 packets per second. The total simulation time is 100 seconds and pause time is 0, 10, 20, 40, 100 seconds. We simulated based on 5, 10, 15 and 20 connections with 10 trials to get the average results.
- 5.1. Performance Metrics
The three performance metrics are packet delivery fractions (PDF), routing load and data throughput. First, PDF is the portion rate of how many packets are sent and received. Second, routing load is related to the number of routing packets and the number of packets received. Third, data throughput is the data that is received per second and is notated as bits per second. The formula is shown below Fig 3 .
PPT Slide
Lager Image
성능기준 지표 Fig. 3 Performance Metrics
- 5.2. Simulation Results and Comparison Analysis
We present results based on Packet delivery fraction, routing load and data throughput which demonstrates the superior performance of E2ESeqNumAgent. The results are generated by the average number of simulations and each number of connections as shown below ( Fig.4 Fig.8 ).
PPT Slide
Lager Image
패킷 전송 비율 (20 커넥션) Fig. 4 Packet Delivery Fraction (20 connections)
PPT Slide
Lager Image
라우팅 부하 (20 커넥션) Fig. 5 Routing Load (20 connections)
PPT Slide
Lager Image
데이터 전송률 (20 커넥션) Fig. 6 Data Throughput (20 connections)
PPT Slide
Lager Image
데이터 전송률 (10 커넥션) Fig. 7 Data Throughput (10 connections)
PPT Slide
Lager Image
데이터 전송률 (5 커넥션) Fig. 8 Data Throughput (5 connections)
We present five figures of each performance metric based on 25 nodes and 50 nodes. Each graphic has three bars (representing AODV, DSR, E2ESeqNumAgent) of each performance metric based on two different numbers of nodes. E2ESeqNumAgent model shows high packet delivery fraction and low routing load, which is efficient. Although, Fig. 6 and 7 show low data throughput on 20 and 10 connections, it shows high data throughput on 5 connections as shown in Fig. 8 . That is, E2ESeqNum Agent model will be useful in small number of connections. Overall, our E2ESeqNumAgent model demonstrates high performance.
Another protocol, DSDV (Destination Sequenced Distance Vector) [2] , uses TCP (Transmission Control Protocol). Although the DSDV was not used as a protocol for comparison analysis, this protocol has the second highest performance on the packet delivery fraction ratio and the third best performance on the data throughput and routing load. DSDV uses TCP, which is very proper for data or packet transmission.
TORA (Temporally Ordered Routing Algorithm) [6] is another routing protocol. TORA is a situation-aware routing protocol and we can predict it will have good performance on our performance metric even though it is not selected for our simulation experiments. Thus in our performance comparison analysis, we compared the performance of the reactive (on-demand) protocols.
Overall, the small end-to-end sequence numbers protocol performed better than AODV [4] and DSR [5] protocols based on the performance metrics (packet delivery fraction, data throughput, routing load). Considering the packet transmission speed and energyefficiency of end-to-end small sequence number protocol, will be a future work. For other possible future work, we can consider security and energy efficiency. This protocol and experimental setup is designed by NS-2 (Network Simulator second version) [8] with Tcl scripts file. Tcl scripts file can generate other possible scenario or traffic scripts. With this view, we can consider generating an energy efficient routing scenario through the Tcl scripts.
Special thanks to Prof. John Metzner and Mr. Kiran Kashalkar to extend his work. Additionally, special thanks to numerous authors of netowrking references and other participants in this paper. This work was supported by the GRRC program of Gyeonggi province. [(GRRCSUWON2014-B1), Cooperative Recognition and Response System based on Tension Sensing]. The paper was supported by The University of Suwon in 2014.
김장영(Jang-Young Kim)
2005년 2월: 연세대학교 컴퓨터과학 공학사
2010년 5월: Pennsylvania State Univ. 공학석사
2013년 7월: State University of New York 공학박사
2013년 8월: University of South Carolina 조교수
2014년 3월: 수원대학교 컴퓨터학과 조교수
※관심분야 : Big data, Cloud computing, Networks
“List of ad-hoc Routing Protocols”, Wikipedia
“Destination Sequenced Distance Vector (DSDV)”, Wikipedia Sequenced_Distance_Vector_routing
Kashalkar Kiran A. 2009 “Implementation of an Efficient Wireless Routing Protocol Based on Small End-to-End Sequence Numbers”, (Master’s Thesis) Pennsylvania State University at University Park
Perkins C. 2003 “Ad hoc On-Demand Distance Vector (AODV) Routing”
Johnson D. 2007 “The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4”
TORA (Temporally Ordered Routing Algorithm) - Wikipedia _routing_algorithm
Metzner J. 2008 “New acknowledgement protocols for dynamic wireless routing and multiple path transmission”, Draft
The Network Simulator (NS-2)