Mobile Ad Hoc Networking Working Group Charles E. Perkins INTERNET DRAFT Nokia Research Center 14 July 2000 Elizabeth M. Royer University of California, Santa Barbara Samir R. Das University of Cincinnati Quality of Service for Ad hoc On-Demand Distance Vector Routing draft-ietf-manet-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 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, Royer Expires 14 January 2001 [Page i] Internet Draft QoS for AODV 14 July 2000 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. This section defines other terminology used with AODV that is not already defined in [3]. 2. Quality of Service AODV currently provides some minimal controls to enable mobile nodes in an ad hoc network to specify, as part of a RREQ, certain Quality of Service parameters that a route to a destination must satisfy. In particular, a RREQ MAY include a Maximum Delay extension (see Section 3.2) or a Minimum Bandwidth extension (see Section 3.3). 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. 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. Perkins, Royer Expires 14 January 2001 [Page 1] Internet Draft QoS for AODV 14 July 2000 3.1. Routing Table Extensions The following fields are added to each route table entry corresponding to each destination. - Maximum Delay. - Minimum Available Bandwidth - List of Sources Requesting Delay Guarantees - List of Sources Requesting Bandwidth Guarantees 3.2. Maximum Delay Extension Format 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 6 Length 2 Delay This field has different meanings for RREQ and RREP messages. In a RREQ message it indicates the maximum number of seconds allowed for a transmission from the source (or from an intermediate node forwarding the RREQ) to the destination. In a RREP message, it indicates the current estimate of cumulative delay from the intermediate node forwarding the RREP to the destination. The Maximum Delay Extension can be appended to a RREQ by a node requesting a QoS route in order to place a maximum bound on the acceptable time delay experienced on any acceptable path from the source to the destination. 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]. When the destination originates a RREP in response to a RREQ the Maximum Delay Extension, the Delay field in the RREP is initially Perkins, Royer Expires 14 January 2001 [Page 2] Internet Draft QoS for AODV 14 July 2000 zero. Each intermediate node forwarding the RREP adds its own NODE_TRAVERSAL_TIME to the Delay field and then records this Delay value in the route table entry for that destination before propagating the RREP. This enables the intermediate nodes to reply to a later RREQ with a Maximum Delay Extension by just comparing the Maximum Delay field in the route table entry and the requested maximum Delay in the RREQ. 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.3. Minimum Bandwidth Extension Format 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 | Bandwidth ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... Bandwidth | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 7 Length 4 Bandwidth In a RREQ message this field indicates the minimum bandwidth (in Kbits/sec) that must be available along an acceptable path from source to destination. In a RREP message this indicates the minimum bandwidth available in the route from the node forwarding the RREP to the destination. The Minimum Bandwidth Extension can be appended to a RREQ by a requesting node in order to specify the minimum amount of bandwidth that must be made available along an acceptable path from the source to the destination. Before forwarding the RREQ, an intermediate node MUST compare its available link capacity to the Bandwidth field in the extension. If the requested amount of bandwidth is not available, the node MUST discard the RREQ and not process it any further. Otherwise, the node continues processing the RREQ as specified in [2]. Perkins, Royer Expires 14 January 2001 [Page 3] Internet Draft QoS for AODV 14 July 2000 When the destination generates a RREP in response to a RREQ with a Minimum Bandwidth Extension, the Bandwidth field in the RREP is initially infinity (a very large number). Each node forwarding the RREP compares the Bandwidth field in the RREP and its own link capacity and maintains the minimum of the two in the Bandwidth field of the RREP before forwarding the RREP. This value also goes in the route table entry for the corresponding destination (as per the Destination IP address in the RREP) and indicates the available minimum bandwidth to the destination. It enables the intermediate node to respond to a later RREQ with a Minimum Bandwidth Extension by comparing the requested minimum bandwidth and the available bandwidth recorded in the route table entry. A node forwarding a RREP also records the Source IP address in RREP message in the list of source nodes requesting bandwidth 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 link capacity at this node. 4. ICMP QOS LOST Message An ICMP QOS_LOST message is generated when an intermediate node experiences an increase in NODE_TRAVERSAL_TIME or a decrease in link capacity. This may affect the QoS guarantees previously provided to some sources. 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 either the Minimum Bandwidth or the Maximum Delay Extensions as described before. The Minimum Bandwidth Extension is used when there is a drop in link capacity and the change in bandwidth is indicated in the Bandwidth field. The Maximum Delay Extension is used when there is an increase in NODE_TRAVERSAL_TIME and change in delay in indicated in the Delay field. Perkins, Royer Expires 14 January 2001 [Page 4] Internet Draft QoS for AODV 14 July 2000 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, Royer Expires 14 January 2001 [Page 5] Internet Draft QoS for AODV 14 July 2000 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] C. Perkins, E. Royer, and S. Das. Ad hoc on demand distance vector (AODV) routing (work in progress). Internet Draft, Internet Engineering Task Force, Mar. 2000. [3] C. E. Perkins. Terminology for Ad-Hoc Networking (work in progress). draft-ietf-manet-terms-00.txt, Nov. 1997. 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 691 2170 (fax) charliep@iprg.nokia.com Elizabeth M. Royer Dept. of Electrical and Computer Engineering University of California, Santa Barbara Santa Barbara, CA 93106 +1 805 893 7788 +1 805 893 3262 (fax) eroyer@alpha.ece.ucsb.edu Samir R. Das Dept of ECECS University of Cincinnati Cincinnati, OH 45221-0030 USA +1 513 556 2594 +1 513 556 7326 (fax) sdas@ececs.uc.edu Perkins, Royer Expires 14 January 2001 [Page 6]