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
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.