Performance Improvement of Efficient Routing Protocol Based on Small End-to-End Sequence Numbers

작은 종단연결 순차번호를 이용한 효율적인 라우팅 프로토콜의 성능향상

  • cc icon

    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.

    네트워크 통신에서 베이스노드가 목적지 노드에 데이터를 전송하는데 데이터가 목적지 노드에 전송하는 경로방향을 설정하는 것은 효율적인 데이터 전송을 위해 매우 중요하다고 할 수 있다. 표준 프로토콜의 하나인 애드혹 프로토콜은 패킷 혹은 데이터가 어떻게 목적지에 도달하는지 경로를 결정한다. 그중 대표적인 것이 애드혹 주문형 거리프로토콜 (AODV)이나 동적 소스 라우팅 프로토콜 (DSR) 이다. 본 논문에서 제안하는 작은 종단연결 순차번호를 이용한 라우팅 프로토콜은 라우트 방향이 가이드 노드의 도움을 받아 적절히 업데이트 되어 효율적이고 프로토콜의 성능분석에 초점을 맞추어 다른 두 프로토콜과 비교한다. 실험은 네트워크 시뮬레이터 (NS-2)를 사용하고 시뮬레이션 시간, 노드개수, 패킷 크기 같은 파라미터에 근거하고 패킷전송비율, 라우팅 부하, 데이터 전송률 같은 본 논문에서 제시한 성능지표에 따라 비교 분석한다. 그 결과 작은 종단연결 순차번호를 이용한 라우팅 프로토콜이 애드혹 주문형 거리 프로토콜 (AODV) 이나 동적 소스 라우팅 프로토콜 (DSR) 에 비해 우수한 성능을 가진 것으로 나타난다.


    AODV Protocol , DSR Protocol , Small End-to-End Sequence Numbers Protocol


    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.

       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.

    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.

    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.

       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.4Fig.8).

    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.

  • 1. “List of ad-hoc Routing Protocols”, Wikipedia google
  • 2. “Destination Sequenced Distance Vector (DSDV)”, Wikipedia google
  • 3. Kashalkar Kiran A. 2009 “Implementation of an Efficient Wireless Routing Protocol Based on Small End-to-End Sequence Numbers”, (Master’s Thesis) google
  • 4. Perkins C. 2003 “Ad hoc On-Demand Distance Vector (AODV) Routing” google
  • 5. Johnson D. 2007 “The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4” google
  • 6. TORA (Temporally Ordered Routing Algorithm) - Wikipedia google
  • 7. Metzner J. 2008 “New acknowledgement protocols for dynamic wireless routing and multiple path transmission”, Draft google
  • 8. The Network Simulator (NS-2) google
  • [그림 1.] 프로토콜 토폴로지
    프로토콜 토폴로지
  • [그림 2.] 메시지 다이어그램 [3]
    메시지 다이어그램 [3]
  • [표 1.] 시뮬레이션 파라미터
    시뮬레이션 파라미터
  • [그림 3.] 성능기준 지표
    성능기준 지표
  • [그림 4.] 패킷 전송 비율 (20 커넥션)
    패킷 전송 비율 (20 커넥션)
  • [그림 5.] 라우팅 부하 (20 커넥션)
    라우팅 부하 (20 커넥션)
  • [그림 6.] 데이터 전송률 (20 커넥션)
    데이터 전송률 (20 커넥션)
  • [그림 7.] 데이터 전송률 (10 커넥션)
    데이터 전송률 (10 커넥션)
  • [그림 8.] 데이터 전송률 (5 커넥션)
    데이터 전송률 (5 커넥션)