Internet DRAFT - draft-perkins-aodvqos

draft-perkins-aodvqos




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

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

   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 and destinations.  To






Perkins, Belding-Royer           Expires 14 May 2002            [Page i]

Internet Draft               QoS for AODV               14 November 2001


   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 using these extensions.








































Perkins, Belding-Royer           Expires 14 May 2002           [Page ii]

Internet Draft               QoS for AODV               14 November 2001


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 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 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 document specifies extensions which can be used to ensure
   maximum delay and minimum bandwidth along a route between a source
   and destination.

   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

   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 RREQ MAY include a QoS Object extension (see
   Section 3.2) which includes bandwidth and delay parameters.  In order
   to enable accumulated measurement for end-to-end delay, AODV also
   provides an Maximum Permissible Delay extension (see Section 3.4).

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






Perkins, Belding-Royer           Expires 14 May 2002            [Page 1]

Internet Draft               QoS for AODV               14 November 2001


3. Extensions

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


3.1. Routing Table Extensions

   The following fields are added to each route table entry
   corresponding to each destination requesting QoS.

    -  Maximum Delay

    -  Minimum Available Bandwidth

    -  List of Sources Requesting Delay Guarantees

    -  List of Sources Requesting Bandwidth Guarantees


3.2. QoS Object Format

   The QoS information about a microflow is expected to be encoded into
   a standard format [3], 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 well-known requirements for 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.




Perkins, Belding-Royer           Expires 14 May 2002            [Page 2]

Internet Draft               QoS for AODV               14 November 2001


    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|    QoS Profile Type   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :N:              Non-Default Values Bit Vector                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :N|    Additional Non-Default Values Bit Vector (if present)    :
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :         QoS fields with non-default values (if present)       :
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+



                      Figure 1: QoS Object Format



      NNNNN        If QoS Profile Type is zero, this bit is not defined
                   to be part of the QoS Object format.  Otherwise, if
                   the QoS Profile Type is nonzero, when the `N' bit is
                   set, the next 31 bits are part of the "Non-Default
                   Values" bit vector

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

      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

      Capacity Requirement

         32-bit number, measured in bits/second






Perkins, Belding-Royer           Expires 14 May 2002            [Page 3]

Internet Draft               QoS for AODV               14 November 2001


      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. QoS Object Extension Format

   A node MAY append a QoS Object extension to a RREQ in order to find 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 length; as defined in section 3.2.

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




Perkins, Belding-Royer           Expires 14 May 2002            [Page 4]

Internet Draft               QoS for AODV               14 November 2001


   or implicitly, it MUST also append a Maximum Jitter Extension after
   the QoS Object extension.


3.4. Maximum Delay Extension Format

   The Maximum Delay Extension Format may only be applied to RREQ
   messages containing the QoS Object extension.  It provides
   information about the cumulative delay 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     |           Delay               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


      Type         TBD

      Length       2

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

   The Maximum Delay Extension can be appended to a RREQ by a node
   requesting a QoS route in order to measure the existing delay from
   the originating node, in order to determine whether the path can
   still meet the required Maximum Delay specification within the QoS
   Object data.

   Before forwarding the RREQ, an intermediate node MUST compare its
   NODE_TRAVERSAL_TIME to the (remaining) Delay indicated in the Maximum
   Delay Extension.  If the Delay is less, the node MUST discard the
   RREQ and not process it any further.  Otherwise, the node subtracts
   NODE_TRAVERSAL_TIME from the Delay value in the extension and
   continues processing the RREQ as specified in [2].





Perkins, Belding-Royer           Expires 14 May 2002            [Page 5]

Internet Draft               QoS for AODV               14 November 2001


   A node forwarding a RREP also records the Source IP address in 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 change in NODE_TRAVERSAL_TIME at this node.


3.5. Maximum Jitter Extension Format

   The Maximum Jitter Extension Format may only be applied to
   RREQ messages containing 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 the RREQ on
                    behalf of the originating node.

   The Maximum Jitter Extension can be appended to a RREQ by a node
   requesting a QoS route in order to measure the existing jitter from
   the originating node, in order to determine whether the path can
   still meet the required Maximum Jitter specification within the QoS
   Object data.

   Before forwarding the RREQ, an intermediate node MUST compare its
   approximate jitter to the (remaining) Jitter indicated in the Maximum
   Jitter Extension.  If the Jitter is less, the node MUST discard the
   RREQ and not process it any further.  Otherwise, the node subtracts




Perkins, Belding-Royer           Expires 14 May 2002            [Page 6]

Internet Draft               QoS for AODV               14 November 2001


   its estimated jitter value from the (remaining) Jitter value in the
   extension and continues processing the RREQ as specified in [2].

   A node forwarding a RREP 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 at this node.


4. 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 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      |           Destination IP address
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                   |
   +-+-+-+-+-+-+-+-+


      Type   8

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

   This message is extended using the QoS Object Extension (see
   section 3.2).  Typically, QoS Profile Type zero is used, with field
   reporting the actual measured parameter which fails 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 indicated in the Capacity Requirement field.  The
   Maximum Permissible Delay parameter is present when there is a
   substantial increase in the forwarding delay at a particular node;
   likewise for the Maximum Permissible Jitter parameter.




Perkins, Belding-Royer           Expires 14 May 2002            [Page 7]

Internet Draft               QoS for AODV               14 November 2001


   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 sources are recorded in a list as a part of the route table
   entry.


5. Security Considerations

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

































Perkins, Belding-Royer           Expires 14 May 2002            [Page 8]

Internet Draft               QoS for AODV               14 November 2001


References

   [1] S. Bradner.  Key words for use in RFCs to Indicate Requirement
       Levels.  RFC 2119, March 1997.

   [2] C. E. Perkins, E. M. Belding-Royer, and S. R. Das.  Ad hoc
       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 in IP Networks.  IETF Internet Draft,
       draft-westphal-seamoby-qos-relocate-00.txt, November 2001.  (Work
       in Progress).


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


      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, Belding-Royer           Expires 14 May 2002            [Page 9]