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]