wdiff draft-perkins-manet-aodvqos-00.txt draft-perkins-manet-aodvqos-01.txt

Mobile Ad Hoc Networking Working Group Charles E. Perkins
INTERNET DRAFT Nokia Research Center
14 November 2001 October 2003 Elizabeth M. Belding-Royer
University of California, Santa Barbara

Quality of Service for Ad hoc On-Demand Distance Vector Routing
draft-perkins-manet-aodvqos-00.txt
draft-perkins-manet-aodvqos-01.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

The Ad hoc On-Demand Distance Vector (AODV) routing protocol is
intended for use by mobile nodes in an ad hoc network. It offers
quick adaptation to dynamic link conditions, low processing and
memory overhead, low network utilization, and determines both
unicast and multicast routes
between sources source and destinations. destination addresses. To provide quality of
service, extensions can be added to the messages used during route
discovery. These extensions specify the service requirements which
must be met by nodes rebroadcasting a Route Request or returning a
Route Reply for a destination. This draft describes how service guarantees are met
partners discover routes that can satisfy QoS service conditions by
using these extensions.

1. Introduction

Route discovery in AODV is on-demand and follows a route
request/route reply query cycle. When a source is in need of needs a route
to a destination, it broadcasts a Route Request (RREQ) control in
search of a route. Nodes having a current route to the indicated
destination respond by unicasting a Route Reply (RREP) to the source
node. To provide quality of service, extensions can be added to
these messages during the route discovery process. A node which
receives a RREQ with a quality of service extension must be able agree to
meet that service requirement in order to either rebroadcast the RREQ
(if it does not have a route to the destination) or unicast a RREP to
the source. For more details on the route discovery process, please
see the AODV Internet Draft [2].

This base specification [3].

In particular, this document specifies extensions which can be used
to ensure
maximum that delay and minimum bandwidth does not exceed a maximum value, or to ensure
that a certain amount of network capacity (i.e., bandwidth) is made
available along a route between a source
and destination. communication partners.

This protocol specification uses conventional meanings [1] for
capitalized words such as MUST, SHOULD, etc., to indicate requirement
levels for various protocol features.

2. Quality of Service Overview

Using the extensions in this document, AODV enables mobile nodes
in an ad hoc network to specify, as part of a RREQ, Quality of
Service requirements that a route to a destination must satisfy.
In particular, a the RREQ MAY include a QoS Object extension (see
Section 3.2) 3) which includes specifies bandwidth and and/or delay parameters. In
order to enable measurements to be accumulated measurement for end-to-end delay,
AODV also provides an Maximum Permissible Delay Accumulated Value extension (see Section 3.4). 4.3).
Any QoS parameters that have to be measured and accumulated at each
hop along the way can be stored along with the associated RREQ
message.

Every RREQ QoS extension also carries with it a "session-ID" value
which is used to identify the particular QoS flow that will be
established according to the parameters of the RREQ. The session-ID
has to be stored along with the route table information associated
with the particular flow that might be created because of the
extended RREQ. Every flow is uniquely identified by the triplet
including the source IP address, the destination IP address, and the
session-ID. This places a limitation of 65,535 unique flows between
any two nodes in an ad hoc network.

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 originate transmit a ICMP QOS_LOST
message back to the node which had originally requested the now
unavailable parameters.

3. Extensions

Several extensions are needed
unmaintainable level of service. This typically requires additional
information to be stored in the routing each per-destination route table structure and entry
(see section 4.1). The ICMP QOS_LOST message identifies the
RREQ and RREP messages for supporting broken
flow by including the session-ID value associated with the flow.

For QoS routing. The extensions parameters that are affected by cumulative measures at each
intermediate node of a routing path, an extension is defined in this section conform to the format defined
enable a running total to be maintained for extensions that measure as the RREQ
is propagated. Each intermediate node that elects to forward a
RREQ and RREP messages as specified MUST adjust the accumulated value in [2]. We first describe the
extensions needed for extension so that an
accurate determination must be made. This approach is better than
modifying the routing table.

3.1. Routing Table Extensions

The following fields are added values in the QoS object directly, because it enables
the original request to each be authenticated whenever that is required.

An intermediate node that can satisfy a RREQ with QoS parameters
specified typically SHOULD always rebroadcast the RREQ, even if it
has a route table entry
corresponding to each the destination. This contrasts with the situation
with unconstrained RREQ messages, because without any need for QoS
an intermediate is allowed to answer with an RREP message if it has
a route to the destination. Unfortunately, the intermediate node
is not likely to have current enough information about whether the
remaining nodes along the path to the destination requesting can also satisfy
the requested QoS.

- Maximum Delay

- Minimum Available Bandwidth

- List of Sources Requesting Delay Guarantees

- List Effectively, according to this specification,
every QoS path to the destination will be ultimately approved by the
destination itself along with every intermedate node along the path
from the source to the destination.

When the destination issues the RREP message, it MUST also copy
over the QoS extension into the RREP message. Each intermediate
node forwarding the RREP message back to the originator of Sources Requesting Bandwidth Guarantees

3.2. the RREQ
message also MUST copy over the QoS extension.

In the future, if a specification is made enabling an intermediate
node to have reliable information about the remaining nodes along
the path, then the node could issue an RREP, along with a gratuitous
RREP unicast towards the destination. The gratuitous RREP would
then enable the remaining nodes to make the appropriate resource
reservations that would be needed to satisfy the QoS route discovery
request.

3. QoS Object Format

The

QoS information about a microflow is expected to be encoded into a standard format [3], format,
illustrated in figure 1. The standard format allows both complete
flexibility for specification of arbitrary values for various QoS
requirements, and also allows very compact representation, especially
for the well-known requirements for of common applications such as voice
over IP (VoIP). In this section, we present the standard object
format. This object format is used as the main part of the QoS
Object Extension (see section 3.3).

Reservd Sent as 0, value unused and undefined on reception

QoS Profile Type
If nonzero, an index for a list of QoS parameter
field definitions and default values for those
fields. If zero, the fields are as listed below in
this section, and there are no default values. 4.2).

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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Reservd|
|A|N|rsv| QoS Profile Type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
:N: Non-Default Values Bit Vector
| Session ID |Non-Dflt Bit Vect. (if present)|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
:N| Additional Non-Default Values Bit Vector (if present) :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Data (32 bits) (if present) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: QoS fields with non-default values (if present) :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: More QoS fields with non-default values (if present) :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 1: QoS Object Format

NNNNN If

rsv Sent as 0, value unused and undefined on reception

QoS Profile Type is
If nonzero, an index for a list of QoS parameter
field definitions and default values for those
fields. If zero, the fields are as listed below in
this section, and there are no default values.

A If this bit is not defined
to be part of set, the Authentication Data field
is present following the bit vectors indicating the
non-default values.

N If QoS Object format. Profile Type is zero, this bit MUST be zero.
Otherwise, if if the QoS Profile Type is nonzero,
when the `N' bit is set, the next 31 16 bits following the
"session-ID" field are present and part of the
"Non-Default Values" bit vector

Session-ID 16-bit value identifying the flow which could be
set up as a result of the extended route discovery
operation controlled by this RREQ message.

Non-Default Values
A Bit Vector
a bit vector with one bit for each field parameter
field defined for the particular QoS Profile Type
number.

Authentication Data
When present, supplies authentication data so that
nodes receiving the RREQ can check whether or not the
data in the QoS object is the same as specified by
the source node.

QoS Parameter Fields
Defined
defined in accordance with the QoS Profile Type. If
the profile type is 0, then the fields are as defined
below in this section.

For QoS Profile Type zero, the following parameter fields are defined
defined, and MUST appear in this order as indicated by the
corresponding bit in the "Non-Default Values Bit Vector":

Capacity Requirement
32-bit number, measured in bits/second

Maximum Permissible Delay
16-bit number, measured in milliseconds

Maximum Permissible Jitter
16-bit number, measured in milliseconds

Traffic Class
According to Differentiated Services Code Points

3.3.

Some fields that might occur for profile type not equal 0
Peak data rate, Maximum permissible BER, ...

4. Extensions

Several extensions are needed in the routing table structure and
the RREQ and RREP messages for supporting QoS routing. We first
describe the extensions needed for the routing table. The extensions
defined in the section after that conform to the format defined for
extensions to RREQ and RREP messages as specified in [3].

4.1. Routing Table Extensions

Certain fields are conceptually added to each route table entry
corresponding to each network node requesting QoS. The fields are
needed to notify endpoint nodes in cases where QoS parameter value
are agreed upon, but the associated service qualities can no longer
be supplied or maintained. The specific additional fields depend on
the QoS object field entries (see section 3), but the following list
illustrates the general idea.

- Session-ID

- Maximum Delay

- Minimum Available Bandwidth

- List of Sources Requesting Delay Guarantees

- List of Sources Requesting Bandwidth Guarantees

4.2. QoS Object Extension Format

A node MAY append appends a QoS Object extension to a RREQ in order to find disover a
path that satisfies the QoS parameters which are present in the QoS
Object, which is situated within the QoS Object extension data.

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 | Length | QoS Object (variable) ... :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Type TBD

Length variable

QoS Object variable varliable length; as defined in section 3.2. 3.

A node originating a RREQ message MAY append a QoS Object Extension
after the RREQ data. If a delay parameter is specified, either
explicitly or implicitly data, optionally followed by a default value for some QoS Profile
type, the originating node MUST also append a Maximum Delay Extension
for use of the intermediate nodes that need one or more Accumulated
Value extensions according to accumulate the
expected value for delay across various candidate paths.

Likewise, if an originating node specifies a maximum value for
allowable Jitter as part of the QoS parameter data, either explicitly
or implicitly, it MUST also append a Maximum Jitter Extension after specific data in the QoS Object
extension.

3.4. Maximum Delay

4.3. Accumulated Value Extension Format

The Maximum Delay Accumulated Value Extension Format may only be applied to RREQ
messages containing the QoS Object extension. It provides
information about the cumulative delay value that has been experienced by
nodes along the path from the originating node to the node currently
processing the RREQ.

Type TBD

Length 2

Delay

Value Type 8 bits specifying the type of the value stored in the
Accumulated Value field.

Reserved Sent as zero, ignored on reception

Accumulated Value
This field indicates the current estimate of
cumulative delay parameter value from the originating node
up to the intermediate node retransmitting the RREQ
on behalf of the originating node.

The Maximum Delay Accumulated Value Extension can MUST be appended to a RREQ by a node
requesting
rebroadcasting a request for a QoS route in order whenever it is needed to
measure the existing delay accumulated value of the parameter of the type given in
the Value Type field; the accumulation occurs at each node starting
from the originating node. This allows each next intermediate node, in order
or the destination, to determine whether the path can still meet the
required Maximum Delay parameter specification within the QoS Object data.

The following table gives the currently specified subtype values
for the Accumulated Value extension. The last column gives the
conventional name of the Accumulated Value extension when used with
the particular subtype.

Delay == 1 Accumulated Delay Extension

Jitter == 2 Accumulated Jitter Extension

4.4. QoS Object Authentication Extension

The QoS Object Authentication Extension may be used so that nodes
receiving QoS route discovery message may verify that the QoS request
was in fact originated by the source node. This extension does
not verify the contents of any extension other than the QoS Object
extension, because other extensions may have mutable fields that are
modified in transit.

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 | Length |S| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SPI (32 bits) (if present) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: Authentication Data :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 2: QoS Object Authentication Extension Format

S If this bit is set, the SPI field is present.

Authentication Data
When present, supplies authentication data so that
nodes receiving the RREQ can check whether or not the
data in the QoS object is the same as specified by
the source node.

5. Link Capacity

A capacity (bandwidth) specification in a QoS object does not require
the inclusion of any Accumulated Value extension in the RREQ. Any
node that has sufficient unreserved link capacity to forward data,
or in the case of the destination to supply data, does not modify
any contents of the RREQ for the purpose of fulfilling a bandwidth
specification in the QoS object.

Note, however, that in order to properly fulfill such a
specification, a node has to take into account neighborhood
traffic conditions. If recent history indicates that neighboring
transmissions will likely interfere with the node's ability to carry
out the indicated bandwidth specification, then the node SHOULD NOT
rebroadcast the RREQ. Exact mechanisms for estimating neighborhood
traffic levels are beyond the scope of this document. Additional
signaling and protocols may be defined in the future in order to
obtain a higher probability of collecting the necessary neighborhood
bandwidth utilization information.

6. Delay

If the QoS object in the RREQ specifies a delay parameter, then any
node forwarding the request MUST ensure that an Accumulated Delay
extension is present in the RREQ before forwarding the message. A
node that agrees to satisfy delay constraints has to measure the
average time it is currently requiring to forward a data packet,
including processing time, average queuing delays and propagation
delays. Call this average time the FORWARDING_DELAY. Before
forwarding the RREQ, an intermediate node MUST compare the current
value of its
NODE_TRAVERSAL_TIME FORWARDING_DELAY to the (remaining) current value of the difference
between the Maximum Delay indicated value in the Maximum QoS object extension, and
the value in the Accumulated Delay Extension. If the Delay remaining
delay is less, the node MUST discard the RREQ and not process it any further. retransmit it.
Otherwise, the node subtracts
NODE_TRAVERSAL_TIME FORWARDING_DELAY from the Delay value in the
Accumulated Value extension and continues processing the RREQ as
specified in [2]. [3].

A node forwarding a RREP also records the Source IP address in the
RREP message in the list of source nodes requesting delay guarantees
in the corresponding destination's route table entry. These source
nodes are to be notified with an ICMP QOS_LOST message in case there
is a signficant change in NODE_TRAVERSAL_TIME FORWARDING_DELAY at this node.

3.5. Maximum

7. Jitter Extension Format

The Maximum Jitter Extension Format may only be applied to
RREQ messages containing

If the QoS Object extension. It provides
information about the cumulative jitter that has been experienced by
nodes along the path from the originating node to the node currently
processing the RREQ.

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 | Length | Jitter |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Type TBD

Length 2

Jitter This field indicates the current estimate of
cumulative jitter from the originating node up to
the intermediate node retransmitting object in the RREQ on
behalf of the originating node.

The Maximum Jitter Extension can be appended to a RREQ by a node
requesting specifies a QoS route in order to measure the existing jitter from parameter, then any
node forwarding the originating node, request MUST ensure that an Accumulated Jitter
extension is present in order to determine whether the path can
still meet the required Maximum Jitter specification within RREQ before forwarding the QoS
Object data. message.
Before forwarding the RREQ, an intermediate node MUST compare its
approximate
recently computed typical jitter value (call it NODE_JITTER) to the (remaining)
current value of the difference between the Maximum Jitter indicated value in
the Maximum QoS object extension, and the value in the Accumulated Jitter
Extension. If the Jitter remaining allowable jitter is less, the node MUST
discard the RREQ and not process it any further. Otherwise, the
node subtracts
its estimated jitter value NODE_JITTER from the (remaining) Jitter value in the Accumulated Jitter
extension and continues processing the RREQ as specified in [2]. [3].

A node forwarding a RREP with the QoS extension also records the
Source IP address in RREP message in the list of source nodes
requesting jitter guarantees in the corresponding destination's route
table entry. These source nodes are to be notified with an ICMP
QOS_LOST message in case there is a substantial change in the jitter experienced NODE_JITTER at this
node.

8. ICMP QOS LOST Message

An ICMP QOS_LOST message is generated when an intermediate node
experiences a significant change in its ability to live up to th the QoS
guarantees it has made as part of generating a RREP during the QoS
Route Discovery process. The format of this message is as follows.

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 | Value Type | Session-ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination IP address
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
+-+-+-+-+-+-+-+-+
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Type 8 TBD

Value Type
The type of the parameter which can no longer be guaranteed
to conform to the value indicated in the original QoS
Object data of the RREQ. The subtype values are as
specified in section 4.3.

Destination IP address
IP address of the destination node using the link for
which there has been a change in a the QoS parameter.

This parameter of the
indicated subtype.

The QOS_LOST message is extended using forwarded to all sources potentially affected
by the change in the QoS Object Extension parameter. These are those sources to which
a RREP with a QoS extension has been forwarded in the past (see
section 3.2). Typically, 4.1 for a method of determining these sources).

9. ICMPv6 QOS LOST Message

The ICMPv6 QOS_LOST message is generated when an intermediate node
experiences a significant change in its ability to live up to th QoS Profile Type zero
guarantees it has made as part of generating a RREP during the QoS
Route Discovery process. The format of this message is used, with field
reporting as follows.

Type TBD

Value Type
The type of the actual measured parameter which fails can no longer be guaranteed
to conform to meet some
previously requested QoS. For instance, the Minimum Bandwidth field
is used when there is a drop in link capacity and the change in
bandwidth is value indicated in the Capacity Requirement field. original QoS
Object data of the RREQ. The
Maximum Permissible Delay parameter is present when subtype values are as
specified in section 4.3.

Destination IP address
IP address of the destination node using the link for
which there is has been a
substantial increase change in the forwarding delay at a particular node;
likewise for QoS parameter of the Maximum Permissible Jitter parameter.
indicated subtype.

The QOS_LOST message is forwarded to all sources potentially affected
by the change in the QoS parameter. These are those sources to which
a RREP with a QoS extension has been forwarded before. Recall that
these These sources
are recorded able to be conveniently stored in a list as a part of the route
table entry.

10. IANA Considerations

The type number for the ICMP QoS_LOST message is to be taken from
the space of available type numbers for the Internet Control Message
Protocol, ICMP [4]. The type number for the ICMPv6 QoS_LOST message
is to be taken from the space of available type numbers for the
Internet Control Message Protocol for IPv6 [2].

The type numbers for the extensions in section 4 are to be taken from
the space of extensions to AODV [3].

11. Security Considerations

This draft specifies mechanisms for handling quality of service. It
does not introduce any special security considerations vulnerabilities which were
not already present in the AODV routing protocol [2]. [3].

References

[1] S. Bradner. Key words for use in RFCs to Indicate Requirement
Levels. RFC Request for Comments (Best Current Practice) 2119, March
Internet Engineering Task Force, Mar. 1997.

[2] A. Conta and S. Deering. Internet Control Message Protocol
(ICMPv6) for the Internet Protocol version 6 (IPv6)
specification. Request for Comments (Draft Standard) 2463,
Internet Engineering Task Force, Dec. 1998.

[3] C. E. Perkins, E. M. Belding-Royer, Royer, and S. R. Das. Ad hoc
On-Demand Distance Vector on demand distance
vector (AODV) Routing. IETF Internet Draft,
draft-ietf-manet-aodv-09.txt, November 2001. (Work in Progress).

[3] C. Westphal, R. Koodli, and C. E. Perkins. Context Relocation
of QoS Parameters routing (work in IP Networks. IETF progress). Internet Draft,
draft-westphal-seamoby-qos-relocate-00.txt, November 2001. (Work
in Progress).
Internet Engineering Task Force, Feb. 2003.

[4] J. Postel. Internet Control Message Protocol. Request for
Comments (Standard) 792, Internet Engineering Task Force, Sept.
1981.

Author's Addresses

Questions about this memo can be directed to:

Charles E. Perkins
Communications Systems Laboratory
Nokia Research Center
313 Fairchild Drive
Mountain View, CA 94303
USA
+1 650 625 2986
+1 650 625 2502 (fax)
charliep@iprg.nokia.com
charles.perkins@nokia.com

Elizabeth M. Belding-Royer
Dept. of Computer Science
University of California, Santa Barbara
Santa Barbara, CA 93106
+1 805 893 3411
+1 805 893 8553 (fax)
ebelding@cs.ucsb.edu