Mobile Ad Hoc Networking Working Group George Aggelou
INTERNET DRAFT University of Surrey, UK
13 September 1999 Rahim Tafazolli
University of Surrey, UK
Relative Distance Micro-discovery Ad Hoc Routing (RDMAR) Protocol
draft-ietf-manet-rdmar-00.txt
Status of This Memo
This document is a submission by the Mobile Ad Hoc Networking Working
Group of the Internet Engineering Task Force (IETF). Comments should
be submitted to the manet@itd.nrl.navy.mil mailing list.
Distribution of this memo is unlimited.
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at
any time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at:
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at:
http://www.ietf.org/shadow.html.
Abstract
This document describes the Relative Distance Micro-discovery Ad
Hoc Routing (RDMAR) protocol for use in mobile ad hoc networks
(MANETs). The protocol is highly adaptive, bandwidth-efficient
and scaleable. A key concept in its design is that protocol
reaction to link failures is typically localised to a very small
region of the network near the change. This desirable behaviour is
achieved through the use of a novel mechanism for route discovery,
called Relative Distance Micro-discovery (RDM). The concept behind
RDM is that a query flood can be localised by knowing the relative
distance (RD) between two terminals. To accomplish this, every
time a route search between the two terminals is triggered, an
iterative algorithm calculates an estimate of their RD, given an
average nodal mobility and information about the elapsed time since
they last communicated and their previous RD. Based on the newly
calculated RD, the query flood is then localised to a limited
region of the network centred at the source node of the route
discovery and with maximum propagation radius that equals to the
estimated relative distance. This ability to localise query flooding
into a limited area of the network serves to increase scalability
and minimise routing overhead and overall network congestion.
Aggelou, Tafazolli Expires 13 March 2000 [Page i]
Internet Draft RDMAR 13 September 1999
Contents
Status of This Memo i
Abstract . . . . . . . . . . . . . . . i
1. Introduction . . . . . . . . . . . . . 1
2. RDMAR Terminology . . . . . . . . . . . . 2
2.1 Specification Language . . . . . . . . 3
3. Protocol Overview . . . . . . . . . . . . 3
3.1 Packet Formats . . . . . . . . . . 4
3.1.1 Route Request (RREQ) Message Format . . 5
3.1.2 Route Reply (RREP) Message Format . . 6
3.1.3 Failure Notification (FN) Message . . 7
3.2 Route Discovery . . . . . . . . . . 7
3.2.1 Generating and Forwarding Route Requests . 7
3.2.2 Generating Route Replies . . . . . 9
3.3 Packet Forwarding And Route Maintenance . . 10
4. Quality Of Service . . . . . . . . . . . . 11
5. Optimizations . . . . . . . . . . . . 12
6. Multicasting . . . . . . . . . . . . 14
7. Configuration Parameters 14
8. Security Considerations 14
References 14
Chair's Address 15
Author's Address 15
1. Introduction
The Relative Distance Micro-discovery Ad hoc Routing (RDMAR)
protocol is designed for operation in mobile ad hoc networks [MANET].
In mobile ad hoc networks (MANETs), nodes are free to move around
randomly and organise themselves arbitrarily; thus, the network's
wireless topology may change rapidly and unpredictably. In many
packet-radio networks the packet radios do not have direct radio
links to all other packet radios in the network and thus
store-and- forward routing of the packets is required.
Therefore, nodes are acting also as routers (also called Mobile
Routers) and dynamically establishing routing patterns among
themselves to form an infrastructure-less network.
Aggelou, Tafazolli Expires 13 March 2000 [Page 1]
Internet Draft RDMAR 13 September 1999
RDMAR is a source-initiated on-demand routing protocol and allows
nodes to maintain routes to destinations that are in active
communication. One distinguishing feature of RDMAR is its use of an
optimised route discovery mechanism, called Relative Distance
Micro-discovery (RDM). According to this mechanism, the routing
protocol limits the range of route searching in order to save the
cost of flooding a route request message into the entire wireless
area. Thus, in contrast to pure flooding mechanism where a route
query would reach every node that is reachable in the wireless
network, in RDMAR a query is propagated only to a limited region of
the network for the successful discovery of the destination terminal.
This is achieved by estimating the relative distance between the
source and destination of the route search, thus restricting the
range of route discovery within an area centred at the source node
of the route discovery and with maximum radius that equals to the
estimated relative distance. Another feature of RDMAR is that the
maintenance of active paths (i.e., paths that carry active calls)
is a distributed operation that exploits the spatial relationship
of nodes when a failure along an active route occurs. Depending on
the relative distance of the node that reports the failure from the
calling and called nodes, two heuristics are considered:
a) if its relative distance from the called node is smaller or equal
to this from the calling node, then RDM is to be applied to localise
the repair of the failed route on the region of the network where
the failure occurs; otherwise,
b) the node proceeds and informs the calling node about the failure
to deliver the call through this path.
RDMAR offers a number of potential advantages over other routing
protocols for mobile ad hoc networks. First, RDMAR uses no periodic
beaconing to keep routing tables updated thus significantly reducing
network bandwidth overhead, conserving battery power and reducing
the probability of packet collision. In addition, in RDMAR nodes
do not make use of their routing caches to reply to route queries.
Using other nodes' cashes results to a storm of route replies and
repetitive updates in hosts' caches, yet early query quenching can
not stop the propagation of all query messages which are flooded all
over the network. Furthermore, RDMAR does not rely on any specific
location aided technology in order to compute routing patterns and
to limit the query flood to a restriction region.
Finally, in the presence of asymmetrical links traditional link-state
or distance vector protocols may compute routes that do not work.
Several factors such as interference, shadowing, differing radio or
antenna capabilities, may turn a link to function asymmetrically.
RDMAR, however, has been designed to compute correct routes even in
the presence of asymmetric links.
2. RDMAR Terminology
Node
A device in the ad hoc network willing to participate in the
routing protocol.
Aggelou, Tafazolli Expires 13 March 2000 [Page 2]
Internet Draft RDMAR 13 September 1999
link
A communication facility or medium over which nodes can
communicate at the link layer, such as an Ethernet (simple
or bridged). A link is the layer immediately below IP.
packet
An IP header plus payload.
active route
A routing table entry with an unexpired Lifetime and a finite
metric. A routing table may contain entries that are not
active. Only active entries can be used to forward data
packets.
Route Discovery
The mechanism in RDMAR where a node S discovers a
route to some node D when one is needed.
Route Maintenance
The mechanism in RDMAR whereby a node is able to detect,
while using a route, if the network topology has changed
such that it can no longer use this route.
2.1 Specification Language
This protocol specification uses conventional capitalised keywords
such as "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and
"OPTIONAL" which are to be interpreted as described in RFC 2119 [RFC].
3. Protocol Overview
In RDMAR, calls are routed between the stations of the network
by using routing tables which are stored at each station of
the network; each node is treated as a host as well as a
store-and-forward node. Each routing table lists all available
destinations, and the number of hops to each. Therefore, the
routing table of each node is a column vector of maximum (N - 1)
row entries, where N is the set of participating nodes in the
network. Apart from the available destination addresses, additional
information is maintained for each destination address D. This
includes: the "Default Router" field that indicates the next hop
node through which the current node can reach D, the
Aggelou, Tafazolli Expires 13 March 2000 [Page 3]
Internet Draft RDMAR 13 September 1999
"RD" field which shows an estimate of the relative distance (RD)
(in hops) between the node and D, the "Time_Last_Update" (TLU)
field that indicates the time elapsed since the node last received
routing information for D, a "RT_Timeout" field which records
the remaining amount of time before the route is considered
invalid, and a "Route Flag" field which declares whether the
route to D is active.
Each mobile node maintains two data structures, in addition to
the routing table, wherein all routing and management information,
learned during protocol operation, is kept; namely these are: the
Data Re-transmission Table and the Route Request Table.
When a source node S wishes to send a data packet to some
destination D, it first examines if it has a route to this
destination. If so, it keeps a copy of the packet in its Data
Re-transmission table and then proceeds and transmits the
packet over its network interface to the next hop identified in
its routing table. The Data Re-transmission Buffer, therefore,
is a queue of data packets that are awaiting the receipt of an
explicit acknowledgement from their destination. Each
intermediate node (IN) upon reception of a data packet, first
acknowledges (link-level acknowledgement) its correct reception
to the previous hop, and forwards it to the next hop, if a path
to destination is available. If an IN is unable to forward the
packet, it starts the Route Maintenance Phase, as described in
section 3.3
On the other hand, if the source, S, of the data packet does not
have a route to destination (either because S did not have
previous information for the destination node, D, or because S
had a valid route for D but the lifetime associated with this route
expired and hence erased from its Routing Table), the node buffers
the packet and attempts to discover one using the Route Discovery
procedure, as described in section 3.2. All information
related to the most recent Route Discovery, is stored in the Route
Request Table. Finally, the node transmits the original packet
once the route is learned from route discovery.
3.1 Packet Formats
Route Requests (RREQs), Route Replies (RREPs), and FN (Failure
Notification) are the three message types defined by RDMAR. These
messages carry all the control information needed for the correct
operation of RDMAR.
Aggelou, Tafazolli Expires 13 March 2000 [Page 4]
Internet Draft RDMAR 13 September 1999
3.1.1 Route Request (RREQ) Message Format
This packet is used during the route discovery phase. It is a
fixed length packet. The various fields contained in this
packet are:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type |E| Reserved | RD |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RREQ_ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source IP address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The format of the Route Request message is illustrated above, and
contains the following fields:
Type Indicates which control packet is sent.
E Emergency flag; set to '1' when a microdiscovery
procedure (RDM) is triggered as a result of a
failure of an intermediate node to forward a call,
according to the rules described in Section 3.3.
Otherwise, the flag is set to '0'.
Reserved Sent as 0; ignored on reception.
Relative Distance (RD)
The number of hops from the Source IP Address to
the node handling the request.
RREQ_ID
A sequence number uniquely identifying the
particular RREQ when taken in conjunction with the
source and destination node's IP address.
Destination Address
The address of the destination for which a route is
desired.
Source IP Address
The IP address of the node which originated the
Route Request.
Source Sequence Number
The current sequence number to be used for route
entries pointing to (and generated by) the source
of the route request.
Aggelou, Tafazolli Expires 13 March 2000 [Page 5]
Internet Draft RDMAR 13 September 1999
3.1.2 Route Reply (RREP) Message Format
This packet is used during the route discovery phase and is sent
by the destination node of a RREQ in response to the RREQ control
packet. It is a fixed length packet. The various fields contained
in this packet are:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type |E| Reserved | RD |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RREP_ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source IP address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Lifetime |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The format of the Route Reply message is illustrated above, and
contains the following fields:
Type Indicates which control packet is sent.
E Emergency flag; set when the RREP is a response of
a RREQ that had the 'E' bit set.
Reserved Sent as 0; ignored on reception.
Relative Distance (RD)
The number of hops from the receiver of the packet
to the Source IP Address.
RREP_ID
A sequence number uniquely identifying the
particular RREP when taken in conjunction with the
source and destination node's IP address.
Destination IP Address
The IP address of the node that requested the a
route.
Source IP Address
The IP address of the node for which a route is
desired.
Lifetime
The time for which nodes receiving the RREP
consider the route to be valid.
Aggelou, Tafazolli Expires 13 March 2000 [Page 6]
Internet Draft RDMAR 13 September 1999
3.1.3 Failure Notification (FN) Message
This Failure Notification (FN) packet is invoked during the Route
Maintenance phase and is sent by an immediate neighboring node
that has detected a link or nodal failure along an active path. Its
packet length is fixed and it has the following format:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Dependent_List.Node |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The format of the Failure Notification message is illustrated above,
and contains the following fields:
Type Indicates which control packet is sent.
Reserved Sent as 0; ignored on reception.
Source Address
The IP address of the destination of the data packet.
Destination Address
The IP address of the source of the data packet.
Dependent_List.Node
The IP address of the node (neighbor) listed in the
Dependent_List (see section 3.3).
3.2 Route Discovery
3.2.1 Generating and Forwarding Route Requests
When an incoming call arrives at node S for destination node D
and there is no route available to route the packet to D, S initiates
a route discovery phase. Here, S has two options; either to flood
the network with a route query in which case the route query packets
are broadcast into the whole network, or instead, to limit the
discovery in a smaller region of the network, if some kind of
location prediction model for D can be established.
Aggelou, Tafazolli Expires 13 March 2000 [Page 7]
Internet Draft RDMAR 13 September 1999
The former case is straightforward. In the latter case, the
source of the route discovery, S, refers to its routing table
in order to retrieve information on its previous relative distance
with D and the time elapsed since S last received routing
information for D. Let us designate this time as Tm. Based on this
information and assuming a moderate velocity, Micro_Velocity, node S
is then able to estimate its new relative distance to destination
node D in terms of actual number of hops.
To accomplish this, a stochastic model, called relative distance
estimation (RDE) algorithm, has been developed [RDMAR_MODEL] to
estimate the minimum relative distance for the successful location
of the destination terminal based on the previous relative distance
of the terminals and the elapsed time since they last communicated
(i.e., Tm). In this model, the total cost is defined as the total
network resources spent during the route discovery procedure and
RDE is then used to determine the optimal relative
distance (in terms of hops) that results in the minimum cost.
Thereafter, node S limits the distribution for route queries by
inserting the normalized hop-wise value of their RD in the
Time-to-Live (TTL) [IP] field in the header of the route request
(RREQ) packet. As TTL decreases at every node that forwards the
packet, the range of broadcast is eventually restricted in a small
area of the network with maximum radius from the source of the
broadcast equal to RD hops. In the worst case, the newly calculated
RD is equal to the radii of the network; that is, pure flooding.
This procedure is called Relative-Distance Microdiscovery (RDM).
After broadcasting a RREQ, a node waits for a RREP. If the RREP
is not received within RREP_WAIT_TIME milliseconds, the node MAY
rebroadcast the RREQ, up to a maximum of RREQ_RETRIES times. Each
rebroadcast MUST increment the RREQ_ID field.
Data packets waiting for a route (i.e., waiting for a RREP after
RREQ has been sent) SHOULD be buffered at the source node. The
buffering SHOULD be FIFO. If a RREQ has been rebroadcast
RREQ_RETRIES times without receiving any RREP, all data packets
destined for the corresponding destination SHOULD be dropped from
the buffer.
When a node (source of RREQ or any intermediate node) receives a
RREP and the node has a valid (in the sense not expired) pending
RREQ, the node keeps a record in its routing table of the correct
value of its RD to the source of the RREP control packet (i.e.,
destination of RREQ).
A Route Discovery for a destination SHOULD NOT be initiated unless
the initiating node has a packet in the Data Re-transmission
Buffer requiring delivery to that destination. A Route Discovery
for a given target node MUST NOT be initiated unless permitted by
the rate-limiting information contained in the Route Request Table.
Aggelou, Tafazolli Expires 13 March 2000 [Page 8]
Internet Draft RDMAR 13 September 1999
A node that receives a RREQ packet which is not destined for it, the
node SHOULD NOT retransmit the packet, SHOULD NOT request explicit
RDMAR acknowledgement from the next hop, SHOULD NOT expect a passive
acknowledgement, and SHOULD NOT place the packet in the RREQ table
for retransmission.
3.2.2 Generating Route Replies
As the RREQ is propagated hop-by-hop outward, each intermediate
node that receives the RREQ packet creates a reverse route to the
source of the RREQ in its routing table with next hop set to the
address of the previous hop included in the RREQ packet.
When a node receives a RREQ or RREP packet it checks the source IP
address, the RREQ_ID/RREP_ ID value and the destination IP address
of the packet. The node first checks whether it is the intended
destination of the packet. If so, the node proceeds and sends a
Route Reply back to the source of the RREQ, according to the rules
described in section 3.2.2.
If, however, the node is not the destination of the RREQ, it checks
to see whether the broadcast packet has already been received in
the past, and thus whether it has already transmitted the broadcast
packet. If there is no existing list entry in its RREQ Table
containing the same IP source address, RREQ_ID/RREP_ID value and
the destination IP address of the packet the node retransmits the
broadcast packet. If there is such a list entry with matching
source IP address , RREQ_ID/RREP_ID value and the
destination IP address of the packet the node MUST not propagate
any copies of it after the first, avoiding the overhead of
forwarding additional copies that reach this node along different
paths.
A Route Reply (RREP) packet MUST be generated in response to a RREQ
only by the destination node for which the RREQ is sent for. The
route is made available by unicasting a RREP back to the source of
the RREQ packet.
If a new route for some destination D is offered to a mobile
station, then if the mobile station has already a route to D it
compares the hop count (i.e., the "RD" field in the RREP message)
of the new route to the RD for the route that already exists in its
table. If the new route carries a smaller RD than the RD of the
pending route, then the new route will be selected. If, however,
the node does not have a route for the destination, it "blindly"
adds the newly coming route. This is because in RDMAR a RREP is
always generated from the destination node of a RREQ. Hence, it
is highly impossible for nodes to receive stale routing
information.
Finally, an intermediate node that receives a new RREP to forward,
it SHOULD send replies not only to the destination node listed in
this RREP, but also to all nodes that have previously sent RREQ to
the source of the RREP and no reply has been forwarded to them yet.
Aggelou, Tafazolli Expires 13 March 2000 [Page 9]
Internet Draft RDMAR 13 September 1999
In conclusion, in RDMAR route decision MUST be performed at the
destination node and only the best selected route will be
valid while all other possible routes remain passive; therefore
avoid stale routes and packet duplicates.
3.3 Packet Forwarding and Route Maintenance
An intermediate node K, upon reception of a data packet, first
processes the routing header and then forwards the packet to
the next hop. In addition to that, node K SHOULD send an explicit
message to the previous node on an attempt to examine whether
bi-directional link can be established with the node where the
packet is received from.
RDMAR, therefore, does not assume bi-directional links but in
contrast nodes SHOULD exercise the possibility of having
bi-directional links. In this way, nodes that forward a data packet
will always have routing information to send the future
acknowledgement back to the source.
If node K is unable to forward the packet because there is no route
available or a forwarding error occurs along the data path as a
result of a link or node failure, K MAY attempt a number of
additional re-transmissions of the same data packet, up to a
maximum number of retries MAX_DATA_RETRIES. The reason for
multiple attempts is that this failure could have been caused by
temporary factors such as noise bursts, moving node was in a radio
shadow area etc. If, however, the failure persists, node K
initiates the Route Maintenance Phase.
During the Route Maintenance procedure, node K exploits the
spatial relation between itself and the source and destination nodes
of the data packet. Depending on its relative position from the
source and destination nodes of the packet, K may optionally
initiate an RDM procedure or notify instead the source of the
active call. This results from the relative distance of K from
the source and destination nodes of a data packet. If K is close
to the destination of the packet at the time of the failure
(referring to its routing table), it SHOULD proceed and initiate an
RDM procedure (to distinguish this RDM phase from the one that is
triggered from a data source node, let us designate this as RM_RDM);
otherwise, if K is close to the source of the data
packet it SHOULD proceed and notify the source about the failure
to deliver the packet through this path.
The latter case is called Failure Notification (FN) phase.
The RREQ traffic generated during the RM_RDM phase MUST have the 'E'
flag set to '1', so as the recipients of this traffic to prioritize
the traffic. This can be achieved by assigning queue priorities (
e.g., by emulation of Priority Queue Discipline [QoS]) so that this
traffic is always transmitted ahead of other types of traffic.
The reasons for prioritizing this control traffic are twofold. On
one hand, an intermediate node that triggers the RM_RDM should
receive a RREP fast so that a fast re-routing is performed in a
manner seamless to data source; seamless in terms of the
application's performance perspective and the graceful degradation
of real-time traffic. On the other hand, data packets destined to
the node for which a route discovery is in progress, keep
accummulating on the input buffer of the node while the discovery
is in progress (i.e., a RREP has not been received yet). Therefore,
unless a route is received fast, the resources (buffers) of the
source node of the RM_RDM will saturate and local congestion
problems may arise at this node. Congestion in turn leads to the
dropping of packets which causes big delays and intermittent
application disruptions.
After broadcasting a RREQ, a node waits for a RREP. If the RREP
is not received within RREP_WAIT_TIME_MICRO milliseconds, the node
MAY rebroadcast the RREQ, up to a maximum of RREQ_RETRIES times.
Each rebroadcast MUST increment the RREQ_ID field.
During the FN phase, each node K, that receives a packet for
forwarding (i.e., the node is not the intended destination of
the packet), keeps a list of all the neighbours that use this
node as their default router to reach a destination D.
We call this list of nodes as "Dependent List" (similar to
the concept of Dependent Downstream Routers, described
in [DVMRP]). The importance of
Aggelou, Tafazolli Expires 13 March 2000 [Page 10]
Internet Draft RDMAR 13 September 1999
this list is that the need of broadcasting is eliminated
by sending FN messages only to the nodes that actually use
the failed path. In this way, nodes that currently need a
route to the destination are notified to search for a
new path, if one still needed. The FN message propagates
upwards towards the source of the data packet.
Each node, upon receipt of a FN message, MUST remove from
its routing table the route associated with the destination
of the data packet, if the next hop to reach this destination
is the one through which the FN message is
received. Additionally, to secure the propagation of error
messages, nodes that receive a FN message but have an empty
"Dependent List" (thus being unable to forward the error
message), MUST use their routing caches to forward the message
to its destination. In this way, we ensure that
the affected data sources from the path failure are always
notified.
Nodes MUST NOT ptrigger the Route Maintenance phase for control
packets (i.e., RREQ, RREP and FN) or for Acknowledgement packets.
A node that receives a FN packet SHOULD NOT retransmit the
packet, SHOULD NOT request explicit RDMAR acknowledgement from the
next hop and SHOULD NOT expect a passive acknowledgement.
4. Quality of Service
RDMAR currently provides some minimal controls to
enable mobile nodes in an ad hoc network to specify, as part
of a Route Discovery, certain Quality of Service parameters that
a route to a destination must satisfy. In particular, a RREQ MAY
include a diverse of QoS Metrics such as Delay or Bandwidth bounds.
If, after establishment of such a route, any node along the
path detects that the requested Quality of Service parameters
can no longer be maintained, that node MUST trigger Route
Maintenance phase and re-discover a QoS route.
Although the RDMAR protocol is not designed to support QoS
guaranteed, the 'QoS Metrics' in RDMAR route discovery and
selection procedure can be customized in accordance to application
QoS requirements. The RDMAR route selection algorithm presented
earlier considers routes with the highest degree of stability and
overall network resource consumption as the more important QoS
metrics, followed by minimum-hop routes and minimum aggregate delay.
In RDMAR, there exists flexibility in terms of route selection
based on which QoS parameter is viewed to be more important
than others. Path stability is chosen to be the most
important factor to be considered first since it determines
how long the other QoS paramters can be maintained before
the route is invalidated by mobile hosts' movements.
Aggelou, Tafazolli Expires 13 March 2000 [Page 11]
Internet Draft RDMAR 13 September 1999
5. Optimizations
A number of optimizations can be added to the basic
operation of Route discovery and Route Maintenance as
described in Sections 3.2 and 3.3, respectively, that can
improve load balancing, efficient bandwidth utilisation and
enhance the quality of the routes used.
Optimisations on the basic RREP mechanism are also proposed:
* Coping with transient network connectivity - Urgent_RREP (U_RREP)
A crucial effect on the performance of a
dynamic routing protocol is the motion pattern of
mobile stations. For example no one of the existing routing
protocols works within a network where all participating
nodes are moving always outside of the hearing range
of each other. However, we are interested in the case
where occasionally a node becomes partitioned (in the sense,
the node is completely disconnected) from the rest of the
networking topology.
Let us study the case where a query flood is in transit
while the destination of this request is effectively partitioned.
In this situation, all RREQ packets that are "in-flight" are
completely unproductive. In this case, upon timeout of the
recently sent RREQ packet, the source of the RREQ will continue
to generate RREQ packets until it receives a RREP or the number
of retransmission exceeds the maximum allowed retransmission
threshold. For the latter case we employ an exponential
backoff delay to limit the rate at which the new
route request targeted to the same host may be initiated,
after the maximum retransmission threshold has been reached.
However, as the partitioned node (say DST) is approaching the
ad hoc vicinity and a MANET terminal realises
that its new neighbour is the one that a request is in
progress (i.e., DST), this terminal immediately proceeds and
sends a RREP to all nodes that need a route to DST. This technique,
called Urgent Route Reply (U_RREP), therefore serves to increase
protocol adaptivity in the phase of transient
connectivity such as the one described here.
* Extensions for Load Balancing Support
In RDMAR, load balancing could be effectively
realised during the route discovery phase where the source
of the route discovery receives a number of paths from
destination and picks one according to the traffic
conditions at the time where the reply arrives. That is,
for a certain path, if the IP layer is responsible for
the monitor of the traffic load for each port interface
of the nodes along this path, the objective of the route
discovery is to search for the least-congested routes
(instead of the shortest-path routes), and to
Aggelou, Tafazolli Expires 13 March 2000 [Page 12]
Internet Draft RDMAR 13 September 1999
report to the source of the RREQ an aggregate of the
traffic conditions along the newly discovered paths.
Furthermore, it is evident for all the MANET routing
schemes proposed so far, that an active path usually
remains unchanged during the call lifetime if no
failure occurs along the path.
Hence, if a session runs for sufficiently long period,
the batteries of the intermediate hosts may be drained
out, since the battery power consumed is essentially
proportional to the size of the data packets sent.
To deal with the situation, we propose that the source,
the destination and the intermediate nodes of a route
should keep track how long the route has been used
for the same call without route reconstruction. When
this time exceeds some predefined limit the route must
be rediscovered. This approach leads to the conclusion
that one important parameter that impacts the relative
behaviour of every MANET routing protocol, is the number
of connection requests an intermediate node is allowed
to accept for call forwarding. Due to resource constraints,
a node can accept a reasonable amount of connection requests
for forwarding other nodes' packets. None of the currently
proposed protocols, however, examines this concern.
* Optimised Handling of Route Errors - Failure Crankback
In our attempt to optimise the handling of error messages,
we use a technique similar to one proposed in PNNI
specification [PNNI], called crankback. We refer to
the modified version of crankback used in RDMAR, as Failure
Crankback technique. According to this, a node K that
receives a data packet to forward, it first keeps a
temporary copy of this packet before forwarding. If
K receives an error message for this packet from some
subsequent node as the packet traverses the path towards
its destination, K may proceed and retransmit the packet
through an alternate path, if one exists, instead of
forwarding the error message to its destination (i.e.,
source of data packet).
The impact of this technique on the overall performance,
is that when a node receives a FN message and meanwhile
the node has received a new route to send the packet
(i.e., next hop of the route is not the hop from where
the FN came from), it proceeds and sends a new copy of
the data packet through the new route. In this way,
protocol makes full use of data caching and distributed
routing, yet there is no need to let unnecessary error
messages propagate up to the source of packet, especially
in case where the distance from the failure to the
senders is relatively high.
* Increasing Protocol Robustness
We are making experiments on the case where a node K that
receives a data packet for destination S and the next hop J
to reach D is unreachable, to send FN messages to all data
source nodes that currently have active calls routed
through J for every destination node that turns to be also
unreachable due to the failure of link K-J, and not
necessarily the source nodes of the active calls for D.
Aggelou, Tafazolli Expires 13 March 2000 [Page 13]
Internet Draft RDMAR 13 September 1999
6. Multicasting
RDMAR has so far addressed only unicast ad hoc routing with a
strong emphasis on network resource consumption and discovery
of stable shortest-path routing patterns. However, a lot of
multimedia collaborative applications today involve multiparty
sessions and thus it is important for a routing protocol to
support multicasting. We recently began experimentation with
ways to customise the reactive route query process in order to
support route querying for multiple destinations and multicast
groups.
7. Configuration Parameters
This section gives default values for some important values
associated with RDMAR protocol operations.
Parameter Name Value
---------------------- -----
ACTIVE_ROUTE_TIMEOUT 3 sec
RREP_WAIT_TIME 2*ESTIMATED_TTL+DELAY_OFFSET
RREP_WAIT_TIME_MICRO 2*ESTIMATED_TTL+DELAY_OFFSET_MICRO
RREQ_RETRIES 3
ESTIMATED_TTL is the hop-wise distance estimated from
the RDE algorithm. DELAY_OFFSET and DELAY_OFFSET_MICRO
is an estimate of the average additional latency that
should be added onto the ESTIMATED_TTL to allow for
queuing delays, interrupt processing times and transfer times,
during the RDM and RM_RDM phase, respectively.
8. Security Considerations
Currently, RDMAR does not address any security concerns.
It is assumed, however, that security issues are adequately
address by IPSec authentication headers with the necessary
key management to distribute keys to the members of the
ad hoc network using RDMAR.
References
[DVMRP] S. Deering. Multicast Routing in Internetworks and
Extended LANs, Stanford University, Department of
Computer Science Technical Report: STAN-CS-88-1214,
July 1988
[IP] J.Postel. Internet Protocol, RFC 791, Septembet 1981
[MANET] Scott Corson and Joseph Macker. Mobile Ad Hoc
Networking (MANET): Routing Protocol Performance
Issues and Evaluation Considerations. RFC 2501,
January 1999.
[PNNI] The ATM Forum Technical committee. Private Network-to
-Network Interface Specification ver. 1.0, March 1996
[QoS] P. Ferguson, G. Huston. Delifering QoS on the Internet
and in Corporate Networks, Wiley Computer Publishing, 1998
[RDMAR_MODEL] G.Aggelou, R. Tafazolli. A Model for the
Route Discovery Mechanism of the RDMAR protocol,
Submitted for Publication
[RFC] S. Bradner. Key Words for Use in RFCs to Indicate
Requirement Levels, RFC 2119, March 1997
Aggelou, Tafazolli Expires 13 March 2000 [Page 14]
Internet Draft RDMAR 13 September 1999
Chair's Address
The Working Group can be contacted via its current chairs:
M. Scott Corson
Institute for Systems Research
University of Maryland
College Park, MD 20742
USA
Phone: +1 301 405-6630
Email: corson@isr.umd.edu
Joseph Macker
Information Technology Division
Naval Research Laboratory
Washington, DC 20375
USA
Phone: +1 202 767-2001
Email: macker@itd.nrl.navy.mil
Author's Address
Questions about this memo can be directed to:
George Aggelou
University of Surrey
Centre for Communications Systems Research
Surrey, GU2 5XH
UK
+44 (0) 1483 300800 ext. 3468/2292
+44 (0) 1483 259504 (fax)
G.Aggelou@ee.surrey.ac.uk
Rahim Tafazolli
University of Surrey
Centre for Communications Systems Research
Surrey, GU2 5XH
UK
+44 (0) 1483 259834
+44 (0) 1483 259504 (fax)
R.Tafazolli@ee.surrey.ac.uk
Aggelou, Tafazolli Expires 13 March 2000 [Page 15]
Internet Draft RDMAR 13 September 1999
