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]