Paper Menu >>
Journal Menu >>
I. J. Communications, Network and System Sciences. 2008; 1: 1-103 Published Online February 2008 in SciRes (http://www.SRPublishing.org/journal/ijcns/). Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103 QoS in Node-Disjoint Routing for Ad Hoc Networks Luo LIU1, Laurie CUTHBERT2 Department of Electronic Engineering, Queen Mary, University of London, Mile End Road, E1 4NS, UK E-mail: 1 luo.liu@elec.qmul.ac.uk Abstract Ad hoc network (MANET) is a collection of mobile nodes that can communicate with each other without using any fixed infrastructure. To support multimedia applications such as video and voice MANETs require an efficient routing protocol and quality of service (QoS) mechanism. Node-Disjoint Multipath Routing Protocol (NDMR) is a practical protocol in MANETs: it reduces routing overhead dramatically and achieves multiple node-disjoint routing paths. QoS support in MANETs is an important issue as best-effort routing is not efficient for supporting multimedia applications. This paper presents a novel adaptation of NDMR, QoS enabled NDMR, which introduces agent-based SLA management. This enhancement allows for the intelligent selection of node-disjoint routes based on network conditions, thus fulfilling the QoS requirements of Service Level Agreements (SLAs). Keywords: MANET, Node-Disjoint, Multipath, Agent-based SLA Management 1. Introduction Mobile ad hoc networks are infrastructureless networks that can be rapidly deployed. They are characterized by multihop wireless connectivity, frequently changing network topology and the need for efficient dynamic routing protocols [1]. There are no static nodes such as base stations in the network. Each mobile node operates not only as a host but also as a router, forwarding packets to other mobile nodes in the network that may not be within direct wireless transmission range of each other. The design of efficient and reliable routing protocols in such a network is a challenging issue. On-demand routing protocols are widely used because they use much lower routing load than proactive protocols [2]. Ad Hoc on-demand Distance Vector (AODV) [3] and Dynamic Source Routing (DSR) [4] are the two most widely studied on-demand ad hoc routing protocols. The limitation of both of them is they build and rely on a unipath route for each data transmission. Whenever there is a link break on the route, both of the two protocols need to initiate a new route discovery process. This results in a high routing load. On-demand multipath routing protocols can alleviate these problems by establishing multiple routes between the source node and destination node during one route discovery process. A new route discovery is initiated only when all the paths fail or only one path is available. This paper presents an approach built on the Node-Disjoint Multipath Routing Protocol (NDMR) [5]. NDMR has two novel aspects compared to the other on-demand multipath protocols: it reduces routing overhead dramatically and achieves multiple node-disjoint routing paths [5]. Because of the rising popularity of multimedia applications in the commercial environment and the ever- growing requirements of mission-critical applications in the military arena, a best-effort service cannot meet all requirements in most situations. QoS support in mobile ad hoc networks has become an important area of research. Compared to the demands of traditional data- only applications, these new requirements generally include high bandwidth availability, high packet delivery ratio and low delay rate. Software agents have been demonstrated to provide effective QoS support in networks [6, 7]. The main rationale for using intelligent agents in ad hoc networks is to give greater autonomy to the mobile nodes (since they act as router as well as host). That autonomy, plus the flexibility associate with agents [8] allows the system to meet different QoS requirements as network conditions, eg traffic load [9], change. 2. Node-disjoint multipath routing protocol (NDMR) Node-disjoint multipath routing protocol (NDMR) is a new protocol developed by Xuefei Li [5], modifying and extending AODV to enable the path accumulation feature of DSR in route request packets. It can efficiently QOS IN NODE-DISJOINT ROUTING FOR AD HOC NETWORKS 75 Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103 discovery multiple paths between source and destination nodes with low broadcast redundancy and minimal routing latency. In the route discovery process, the source creates a route request packet (RREQ) containing message type, source address, current sequence number of source, destination address, the broadcast ID and route path. Then the source node broadcasts the packet to its neighbouring nodes. The broadcast ID is incremented every time that the source node initiates a RREQ, forming a unique identifier with the source node address for the RREQ. Finding node-disjoint multiple paths with low overhead is not straightforward when the network topology changes dynamically. NDMR routing computation has three key features that help it to achieve low broadcast redundancy and avoid introducing a broadcast flood in MANETs: Path accumulation, Decreasing multipath broadcast routing packets (using shortest routing hops), Selecting node-disjoint paths. In NDMR, AODV is modified to include path accumulation in RREQ packets. When the packets are broadcast in the network, each intermediate node appends its own address to the RREQ packet. When a RREQ packet finally arrives at its destination, the destination is responsible for judging whether or not the route path is a node-disjoint path. If it is a node-disjoint path, the destination will create a route reply packet (RREP) which contains the node list of whole route path and unicasts it back to the source that generated the RREQ packet along the reverse route path. When an intermediate node receives a RREP packet, it updates the routing table and reverse routing table using the node list of the whole route path contained in the RREP packet. When receiving a duplicate RREQ, the possibility of finding node-disjoint multiple paths is zero if it is dropped, for it may come from another path. But if all of the duplicate RREQ packets are broadcast, this will generate a broadcast storm and dramatically decrease the performance. In order to avoid this problem, a novel approach is introduced in NDMR recording the shortest routing hops to keep loop-free paths and decrease routing broadcast overhead. When a node receives a RREQ packet for the first time, it checks the node list of the route path calculates the number of hops from the source node to itself and records the number as the shortest number of hops in its reverse routing table. If the node receives a duplicate RREQ packet again, it computes the number of hops and compares it with the shortest number of hops in its reverse routing table. If the number of hops is larger than the shortest number of hops in the reverse routing table, the RREQ packet is dropped. Only when it is less than or equal to the shortest number of hops, the node appends its own address to the node list of the route path in a RREQ packet and broadcasts it to neighbouring nodes again. The destination node is responsible for selecting and recording multiple node-disjoint paths. When receiving the first RREQ packet, the destination records the list of node IDs of the entire route path in its reverse route table and sends a RREP packet along the reverse route path. When the destination receives a duplicate RREQ, it compares the whole node IDs of the entire route path in the RREQ to all of the existing node-disjoint paths in its reverse routing table. If there is no common node (excepting the source and destination node) between the node IDs from the RREQ and node IDs of any node- disjoint path in the destination’s reverse table, the route path in current RREQ is a node-disjoint path and is recorded in the reverse routing table of the destination. Otherwise, the current RREQ is discarded. 3. Quality of service (QoS) in NDMR Differentiated Services (DiffServ) is a standard approach to achieve QoS in any IP network and could potentially be used to provide QoS in MANETs. DiffServ provides QoS by dividing traffic into a small number of classes and allocating network resources on a per-class basis. The class is marked directly on the packet, in the 6 bit DiffServ Code Point (DSCP) field. The DSCP field is part of the original type of service (ToS) field in the IP header. The IETF redefine the meaning of the little-used ToS field, splitting it into the 6-bit DSCP field and a 2- bit unused field. The unused field is being allocated to the Explicit Congestion Notification (ECN) mechanisms, as shown in Figure 1. Figure 1. DSCP and ECN The basic goal of the Differentiated Services architecture is to meet the performance requirements of the users. It classifies traffic into different priority levels and applies priority scheduling and queuing management mechanisms to obtain QoS support. DiffServ is a fully distributed and stateless model. No state information is required to be maintained at any node. The model aims at pushing the complexity to the edge nodes of the network so that the process in intermediate nodes can be as simple and fast as possible. Instead of providing QoS at per flow granularity, DiffServ differentiates the traffic into a fixed number of classes. The notion of QoS is a guarantee by the network to satisfy some predetermined service performance constraints for the users in terms of the end-to-end delay, 76 L. LIU ET AL. Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103 available bandwidth, probability of packet loss, and so on [10]. Future ad hoc mobile networks will carry increasing levels of diverse multimedia applications such as voice, video and data. This has resulted in an increasing focus on guaranteeing the QoS for such eg delay sensitive applications such as voice, as specified to the customer in a Service Level Agreement (SLA). This section introduces a novel approach to QoS in MANETS: QoS enhanced NDMR, which combines the advantages of NDMR and DiffServ and makes it suitable for the environment of MANETs to support end-to-end QoS solutions In NDMR, after deciding a path is a node-disjoint path, the destination will create a route reply packet (RREP) which contains the node list of whole route path and unicasts it back to the source. However, since an RREP only currently contains the route path, it cannot provide effective QoS support for MANETs. It is proposed that RREP packets should carry more information such as delay time (queue length) in order to meet certain SLA requirements. When each intermediate node receives a RREP packet, it adds the queue length of this node to the “queue_length” field in RREP packet. Thus, when the source node receives the RREP from the destination node it knows the exact queue length along the path. Each source keeps three node-disjoint paths for a particular destination. With the “queue_length” field in RREP packet, it chooses the path with the minimum queue length. This allows it to minimise the delay time thus providing higher QoS. Figure 2 shows queue length along the multiple paths. Assume source node S first receives the RREP from route 2 (R2) (s-a-b-d). In standard NDMR, S will always transmit data on that route so long as no link break happens, even though route 3 (R3) (s-g-h-i-d ) has a smaller queue length and hence a lower rate of delay. With the introduction of the “queue_length” field in RREP, S will initially choose route 2 (R2) (s-a-b-d) to transmit data as it receives an RREP from that route fqairst. But after receiving the RREP from route 3 (R3) (s-g-h-i-d), it will compare the queue length of the existing routes, then change to route 3 (R3) (s-g-h-i-d) to continue transmitting data. Using this approach, it can reduce the transmission delay rate and meet the SLA requirements. As an RREP is generated only in the route discovery process, the protocol currently cannot frequently refresh the queue length of each path. As part of the enhancement to NDMR, the need for a similar packet, RUP, route update packet, containing the “queue_length” field used in an RREP packet that performs more frequent updates has been identified. The destination node will periodically unicast RUP packet containing up-to-date queue length to the source node. The source will be able to choose the best path according to the change of queue length in real time. R3 s ce f d a b g h i R1 R2 Q ueue length is 5 9 3 2 1 3 5 10 Figure 2. Queue length in multiple node-disjoint paths Figure 3 shows that the simulation results by OPNET of packet average delay for QoS enabled NDMR give better performance than that of NDMR. The delay time for all mobile velocities tends to be equal. The reason is that with RREP packets carrying real-time delay time back and RUP, the data packets will always be transmitted along the lowest congestion path. Figure 3. Average delay – CBR Figure 4. Average delay - exponential source QOS IN NODE-DISJOINT ROUTING FOR AD HOC NETWORKS 77 Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103 It can be seen from Figure 4 that QoS enabled NDMR gives better performance when the source generates packets exponentially as well as in constant bit rate (CBR). Figure 5. Average delay -different source, CBR Figure 5 shows the average delay of different number of sources that generate packets. QoS enabled NDMR keep the packet delay time lower as well. Figure 6. Average delay - different priority It is necessary to let the Expedited forwarding (EF) traffic which often requires low packet delay time transmit on lower delay time path and Best effort (BE) traffic transmit on other node-disjoint paths. With QoS enabled NDMR, source is able to choose the best path for EF traffic. Figure 6 shows the average delay time of different priority traffic. EF traffic gets the lower delay than BE traffic. 4. Agent-based SLA management An agent is a computational entity, such as a software program or a robot [11]. It acts upon its environment and is autonomous in that the behavior depends on its own experience. There are four main properties according to [12]: autonomy, reactiveness, proactiveness and social ability. Autonomous means an agent must be able to work without direct command from a programmer or user. Reactiveness means agents are capable of controlling the environment and can efficiently move from current situation to the goals. Proactiveness means agents can instigate actions to move towards the goals. Social ability means agents can communicate with other agents directly and act on information from other agents to make their own decision. The main reason to use intelligent agents is to give greater autonomy to the mobile nodes. The autonomy increases the flexibility to deal with new situations to acquire QoS to meet different SLAs. A major feature of the QoS enabled NDMR proposed in this paper is the application of intelligent software agents for SLA management. Employing intelligent agents provides greater autonomy to the mobile nodes, allowing for the essential flexibility to respond to the dynamic nature MANETs. This flexibility will allow the system to meet the QoS requirements agreed in SLAs. The delay time for each path is calculated from queue length or buffer length. These two parameters are very important in queue management and should be taken into consideration to meet the requirements of any SLAs. A technique to keep the queue length short in a long buffer is necessary. It is proposed that this technique be under the control of an intelligent agent. Figure 7. General agent structure [6] The general agent structure is shown in Figure 7. It uses three layers – reactive, local planning and co- operative – allowing it to take action and make decisions in different timescales. The reactive layer is designed for quick response in real-time. More complex and slower acting functions are implemented in the two planning layers. Generally the local planning layer is concerned with long-term actions within its own node and the co- operative planning layer is concerned with long-term 78 L. LIU ET AL. Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103 actions with other agents. Future work will develop the communication and cooperation with agents in other nodes. In QoS enhanced NDMR, the co-operative planning layer is used for deciding whether to change path or not (according to the queue length of this node and other nodes); the local planning layer is for choosing which path to transmit data (according to the queue length of this node). As illustrated in Figure 8, the packet is transmitted on the reactive layer and the parameters critical to decision making (such as queue length) are passed up to the planning layers. After calculating delay and choosing the appropriate path, the packet will be routed out along this path. Packet in Routing Local Planning layer Co-operative Planning layer Parameter reporting Path choosing Figure 8. NDMR agent structure 5. Conclusion This paper has presented architecture for guaranteeing QoS based on Node-Disjoint Multipath Routing Protocol (NDMR) in mobile ad hoc networks. The issue of QoS provision is highly challenging for MANETs and necessarily different from traditional fixed networks. Due to the growth in demand for diverse multimedia applications, fulfilling the QoS guarantees in SLAs requires solutions that are responsive to network state. The use of multiple node-disjoint paths gives the opportunity for allocating packets to paths in an optimum way to meet instantaneous constraints. This paper has compared performance in different situation of NDMR and found a means of developing NDMR – through the queue length field and additional route update packets – to allow for QoS measurement along such node-disjoint paths. By using intelligent agents it will be possible to distribute this optimisation at the planning layer, thus allowing very fast processing to occur at the reactive layer while still taking into account the needs of all nodes. 6.References [1] Charles E. Perkings, Elizabeth M.Royer and Samir R.Das, Performance Comparison of Two On- Demand Routing Protocols for Ad Hoc Networks, IEEE Personal Communications, Feb 2001. [2] Z.J. Haas and S. Tabrizi, “On Some Challenges, and Design Choices in Ad hoc Communcations”, Proceedings of the IEEE Military Communications Conference (MILCOM), Bedford, MA, October 1998, pp.187-192. [3] Charles E. Perkings, Elizabeth M. Belding-Royer, Samir R.Das, Ad Hoc On-Demand Distance Vector (AODV)Routing, http://www.ietf.org/internetdrafts/draft-ietf-man et- aodv-13.txt, IETF Internet draft, Feb 2003 [4] J.Broch, D.Johnson, and D. Maltz, The Dynamic Source Protocol for MobileAd hoc Networks, http://www.ietf.org/internet-drafts/d raft-ietf-manet- dsr-10.txt, IETF Internet draft, 19 July 2004. [5] Xuefei Li and Laurie Cuthbert, On-demand Node- Disjoint Multipath Routing in Wireless Ad hoc Networks, In Proceedings of the 29th Annual IEEE Conference on Local Computer Networks, LCN 2004, Tampa, Florida, U.S.A., November 16-18, 2004 [6] L.G. Cuthbert, D. Ryan, L. Tokarchuk, J. Bigam and E. Bodanese, Using intelligent agents to manage resource in 3G Networks, Journal of IBTE, 2(4), 2001 [7] Alex Hayzelden & John Bigham Heterogeneous Multi-Agent Architecture for ATM Virtual Path Network Resource Configuration, in Intelligent Agents for Telecommunications Applications (IATA ’98), LANAI 1437, S.Albayrak & F.J.Garijo (eds), Springer-Verlag, 1998, ISBN 3-540-64720-1 [8] M.Wooldridge & N.R. Jennings, Agent Theories, Architectures and Languages: a Survey in Wooldridge & Jennings eds. Intelligent Agents, Springer-Verlag, Berlin, 1995 [9] Soamsiri Chantaraskul, An Intelligent-Agent Approach for Managing Congestion in W-CDMA Networks, PhD thesis, University of London, August 2005 [10] S. Chakrabarti, A. Mishra, QoS Issues in Ad hoc Wireless Networks, IEEE Communications Magazine, February 2001. [11] G. Weiss, Multiagent System: A Modern Approach to Distributed Artificial Intelligence, the MIT Press, Cambridge, Massachusetts, London, England, 1999. [12] M. Luck, R. Ashri and M. d’Inverno,Agent-Based Software Development, Artech House, Inc., 2004. |