[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01

Mobile Ad Hoc Networking Working Group                Charles E. Perkins
INTERNET DRAFT                                     Nokia Research Center
14 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-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 routes
   between source and 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
   partners discover routes that can satisfy QoS service conditions by
   using these extensions.








Perkins, Royer              Expires 14 April 2004               [Page i]


Internet Draft               QoS for AODV                14 October 2003


1. Introduction

   Route discovery in AODV is on-demand and follows a route
   request/route reply query cycle.  When a source is 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 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 base specification [3].

   In particular, this document specifies extensions which can be used
   to ensure that delay 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 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, the RREQ MAY include a QoS Object extension (see
   Section 3) which specifies bandwidth and/or delay parameters.  In
   order to enable measurements to be accumulated for end-to-end delay,
   AODV also provides an Accumulated Value extension (see Section 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.





Perkins, Royer              Expires 14 April 2004               [Page 1]


Internet Draft               QoS for AODV                14 October 2003


   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 transmit a ICMP QOS_LOST
   message back to the node which had originally requested the now
   unmaintainable level of service.  This typically requires additional
   information to be stored in each per-destination route table entry
   (see section 4.1).  The ICMP QOS_LOST message identifies the broken
   flow by including the session-ID value associated with the flow.

   For QoS parameters that are affected by cumulative measures at each
   intermediate node of a routing path, an extension is defined to
   enable a running total to be maintained for that measure as the RREQ
   is propagated.  Each intermediate node that elects to forward a
   RREQ MUST adjust the accumulated value in the extension so that an
   accurate determination must be made.  This approach is better than
   modifying the values in the QoS object directly, because it enables
   the original request to 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 to 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 can also satisfy
   the requested QoS. 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 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

   QoS information is expected to be encoded into a standard format,
   illustrated in figure 1.  The standard format allows both complete



Perkins, Royer              Expires 14 April 2004               [Page 2]


Internet Draft               QoS for AODV                14 October 2003


   flexibility for specification of arbitrary values for various QoS
   requirements, and also allows very compact representation, especially
   for the well-known requirements 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 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
                                   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                                   |A|N|rsv|    QoS Profile Type   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |           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


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

      A            If this bit is set, the Authentication Data field
                   is present following the bit vectors indicating the
                   non-default values.

      N            If QoS 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 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.



Perkins, Royer              Expires 14 April 2004               [Page 3]


Internet Draft               QoS for AODV                14 October 2003


      Non-Default Values 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 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, 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

      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



Perkins, Royer              Expires 14 April 2004               [Page 4]


Internet Draft               QoS for AODV                14 October 2003


   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 appends a QoS Object extension to a RREQ in order to 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   varliable length; as defined in section 3.

   A node originating a RREQ message MAY append a QoS Object Extension
   after the RREQ data, optionally followed by one or more Accumulated
   Value extensions according to the specific data in the QoS Object
   extension.


4.3. Accumulated Value Extension Format

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




Perkins, Royer              Expires 14 April 2004               [Page 5]


Internet Draft               QoS for AODV                14 October 2003



    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     |   Value Type  |   Reserved    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Accumulated Value                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      Type         TBD

      Length       2

      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 parameter value from the originating node
                   up to the intermediate node retransmitting the RREQ
                   on behalf of the originating node.

   The Accumulated Value Extension MUST be appended to a RREQ by a node
   rebroadcasting a request for a QoS route whenever it is needed to
   measure the 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,
   or the destination, to determine whether the path can still meet the
   required 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




Perkins, Royer              Expires 14 April 2004               [Page 6]


Internet Draft               QoS for AODV                14 October 2003


   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.






Perkins, Royer              Expires 14 April 2004               [Page 7]


Internet Draft               QoS for AODV                14 October 2003


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 FORWARDING_DELAY to the current value of the difference
   between the Maximum Delay value in the QoS object extension, and
   the value in the Accumulated Delay Extension.  If the remaining
   delay is less, the node MUST discard the RREQ and not retransmit it.
   Otherwise, the node subtracts FORWARDING_DELAY from the value in the
   Accumulated Value extension and continues processing the RREQ as
   specified in [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 FORWARDING_DELAY at this node.


7. Jitter

   If the QoS object in the RREQ specifies a jitter parameter, then any
   node forwarding the request MUST ensure that an Accumulated Jitter
   extension is present in the RREQ before forwarding the message.
   Before forwarding the RREQ, an intermediate node MUST compare its
   recently computed typical jitter value (call it NODE_JITTER) to the
   current value of the difference between the Maximum Jitter value in
   the QoS object extension, and the value in the Accumulated Jitter
   Extension.  If the remaining allowable jitter is less, the node MUST
   discard the RREQ and not process it any further.  Otherwise, the
   node subtracts NODE_JITTER from the value in the Accumulated Jitter
   extension and continues processing the RREQ as specified in [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 change in NODE_JITTER at this
   node.







Perkins, Royer              Expires 14 April 2004               [Page 8]


Internet Draft               QoS for AODV                14 October 2003


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 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   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 the QoS parameter of the
             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 in the past (see
   section 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
   guarantees it has made as part of generating a RREP during the QoS
   Route Discovery process.  The format of this message is as follows.












Perkins, Royer              Expires 14 April 2004               [Page 9]


Internet Draft               QoS for AODV                14 October 2003



    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          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   |                      128-bit Destination                      |
   |                         IPv6 address                          |
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      Type   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 the QoS parameter of the
             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.  These sources
   are 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 vulnerabilities which were
   not already present in the AODV routing protocol [3].



Perkins, Royer              Expires 14 April 2004              [Page 10]


Internet Draft               QoS for AODV                14 October 2003


References

   [1] S. Bradner.  Key words for use in RFCs to Indicate Requirement
       Levels.  Request for Comments (Best Current Practice) 2119,
       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. Perkins, E. Royer, and S. Das.  Ad hoc on demand distance
       vector (AODV) routing (work in progress).  Internet Draft,
       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)
      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










Perkins, Royer              Expires 14 April 2004              [Page 11]


Html markup produced by rfcmarkup 1.129c, available from https://tools.ietf.org/tools/rfcmarkup/