Mobile Ad Hoc Networking Working Group Namhi Kang INTERNET DRAFT DASAN Networks Inc. 17 October 2005 Younghan Kim University of Soongsil, Korea Quality of Service Extension to Dynamic MANET OnDemand Routing Protocol draft-kang-dymoqos-00.txt Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. 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. This Internet-Draft will expire on April 2006. Copyright Notice Copyright (C) The Internet Society (2005). Abstract This document describes extensions to the Dynamic MANET On-demand (DYMO) routing protocol in order to enable mobile nodes to discover and maintain QoS routes. DYMO is a reactive (on-demand) routing protocol designed for use by mobile nodes in multi-hop wireless ad hoc networks. Extensions of this document include the necessary addition to the routing table and the DYMO message element. Kang, Kim [Page 1] Internet Draft QoS Extension to DYMO 17 October 2005 1. Introduction The DYMO routing protocol specifies a reactive means to discover a route to the destination for MANET nodes. A source node disseminates RREQ message toward the destination node to discover a route to the node. Once the RREQ message arrives at the destination node, it responds RREP message back to the source node over the discovered path by unicasting. During such a route discovery process, intermediate nodes (i.e. nodes that relay the RREQ and RREP message) update its routing table based on the routing information that is present in those two messages for each direction. DYMO also offers adaptation to changing network topology, which can be occurred by the mobility of nodes as the main cause, by means of the route maintenance mechanisms [1]. In order to provide MANET nodes with QoS routes, extensions to DYMO message elements are required. These extensions specify the service requirements (say maximum tolerable delay, maximum tolerable jitter, and/or minimum bandwidth limitation) that must be guaranteed by nodes along a route from a source to the destination. This document presents which extensions are required for support QoS in routing, how service guarantees are achieved by using the defined extensions without high impacts on the existing DYMO operations and how QoS routes are discovered and maintained are also briefly described. The extensions of this document conform to the DYMO routing protocol (i.e. the the extentions to DYMO data structure specified in [1]). In this document, the extension to routing table is first described and then two message element extensions, QoS Route Element (QRE) and QoS Route Error (QRERR), are presented for supporting QoS routing. The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [2]. Kang, Kim [Page 2] Internet Draft QoS Extension to DYMO 17 October 2005 2. Routing Table Entries for QoS Routing In QoS routing, routing table entries can be defined differently according to the type of QoS model; per-flow based model such as IntServ model [3] or per-class based model such as DiffServ model [4]. In case of the per-flow based mechanism, the following entries may be added to the routing table of each DYMO router on the path. A routing table entry is defined for a flow to specify QoS requirements requested by the source (requestor) of the particular flow, where a flow can be identified by the pair of IP address and port number. - Maximum Tolerable Delay - Maximum Tolerable Jitter - Minimum Available Bandwidth - List of Sources Identifier Requesting Delay Guarantees - List of Sources Identifier Requesting Jitter Guarantees - List of Sources Identifier Requesting Bandwidth Guarantees, where the Source Identifier consists of IPSourceAddress and Port number. In case of the class-based model , on the other hand, the following fields may be added to the routing table of a DYMO router. Each routing table entry is defined for each pre-specified class, where a packet belonging to each class can be distinguished by DSCP (DiffServ Code Point) as specified in [5]. - Maximum Tolerable Delay - Maximum Tolerable Jitter - Minimum Available Bandwidth - List of Classes - List of Sources Identifier Belonging to Each Class Kang, Kim [Page 3] Internet Draft QoS Extension to DYMO 17 October 2005 3. Extensions to DYMO Message Elements In this section, we present two extensions to DYMO message element for support QoS route. The work especially considers the compact representation for use by mobile nodes in using of limited capacity, the future extensions for covering various QoS parameters and the support of the per-flow based mechanism and the per-class based mechanism as well. 3.1 QoS Routing Element (QRE) 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 | Len | TTL |I|A| Res | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : NotifyAddress (QoS Requestor) : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : TargetAddress : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | TargetSeqNum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : : QoS Information Block (QIB) : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : : QoS State Information Block (QSIB) : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | THopCnt |Res| : +-+-+-+-+-+-+-+-+ : : : : Routing Blocks (RBlocks) : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1. QoS Routing Element (QRE) QoS Routing Element (QRE) is an extension to the DYMO Routing Element Kang, Kim [Page 4] Internet Draft QoS Extension to DYMO 17 October 2005 (RE) in order to enable a source to discover a path that is able to guarantee the QoS requirements. The QoS requirements of the source are specified in the QIB (QoS Information Block) field. Element Type (Type) The Type field identifies that this element is QRE and the han- dling by nodes that do not implement or understand QoS exten- sions. The data structure of the Type is as follows. 0 0 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 +-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+ | Type | = |M| H | | +-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+ Figure 2. Type In QRE, M bit MUST be set to one (1) in order to indicate that QRE requires notification via an UERR when QRE is not under- stood or handled by a node on the path. Therefore QRE MUST convey NotifyAddress field to which UERR is sent. As well as the H bits in the Type field MUST set to (11) in order to force a node which does not support QRE to drop the QRE packet with- out processing any other QoS DYMO elements. NotifyAddress (QoS Requestor) IP address of the source that have originally generated this QRE to request a particular service. Most of fields conform to the DYMO message element specified in [2] except the newly defined two information block fields (i.e. QoS Information Block (QIB) and QoS State Information Block (QSIB)). Those two blocks are defined as follows. QoS Information Block (QIB) This field can be used differently according to the type of element message (i.e. in a route request and a route reply ele- ment with QoS extensions). In QRREQ message, on one hand, the QIB field indicates the service requirements that must be met at nodes along a route to the destination. On the other hand, in QRREP message, the destination uses this field to inform the Kang, Kim [Page 5] Internet Draft QoS Extension to DYMO 17 October 2005 route's resources available for the QoS requestor. The route's resources are gathered or updated by intermediate nodes and contained within the QSIB field during the route discovery process. The data structure of QIB field is described in Fig- ure 3. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |QPCnt| QoS PM |Res|Traffic Cls| QoS Param Value 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |QoS Param Value N(if presented)| Padding Bits (if needed) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 3. QoS Information Block (QIB) QoS Parameter Count (QPCnt) The most significant 3 bits, QPCnt bits, indicate the number of QoS parameters being presented within the QIB field. QoS Parameter Mark (QoS PM) The 5 bits marker of QoS PM field specifies which parameter is present in QIB to specify the service requirements. This field consists of the following bit marker. 0 0 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 +-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+ | QoS PM | = |B|D|J| Res | +-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+ Figure 4. QoS Parameter Marker (QoS PM) B-bit (B) 1-bit marker to indicate whether the minimum bandwidth is spec- ified as one of the service requirements within QIB. D-bit (D) 1-bit marker to indicate whether the maximum delay (end to end delay) is specified as one of the service requirements within Kang, Kim [Page 6] Internet Draft QoS Extension to DYMO 17 October 2005 QIB. J-bit (J) 1-bit marker to indicate whether the maximum jitter (end to end jitter) is specified as one of the service requirements within QIB. Reserved (Res) Reserved 2 bits for the future extensions (i.e. for other QoS parameters such as power of a node). Typically, these bits are set to zero (0) and ignored in any processing. In addition to these 2 bits, there exist two more bits at the next field (between QoS PM and Traffic Class fields). These Res bits also can be used for the future extensions. (At the time of writing this document, these two Res fields are conceptually distin- guished in order to support easy to implement, i.e. byte based variable allocation in conventional programming language such as C.) Traffic Class (Traffic Cls) The Traffic Cls field allows mobile nodes to employ the per- class based mechanism (say DiffServ). This field is specified by using 6-bits code, called DSCP (Differentiated Services Code Points) that indicate a particular class. QoS parameter value (QoS Param Value) The number and the type of QoS parameters depend on the first 16 bytes of QIB as above addressed. If B and D bit are set to one (1), for example, there MUST exist two parameter value fields so that the padding field does not needed. QoS Param Value fields are defined as follows. - Minimum Bandwidth Requirement 16-bit number, measured in kbits/second (kbps). The maximum value is about 131 Mbps (2^17 - 1 kbps). If the required band- width is less than 1kbps, the value is set to one (1) That is, the least bandwidth requirement the source requires is 1 Kbps. - Maximum End to End Delay Requirement 16-bit number, measured in milliseconds (ms) - Maximum End to End Jitter Requirement Kang, Kim [Page 7] Internet Draft QoS Extension to DYMO 17 October 2005 16-bit number, measured in milliseconds (ms) Padding Bits The Padding field of QIB is used to confirm to DYMO message element. If QoS PCnt is even number then these bits are set to zero (0). QoS State Information Block (QSIB) In QoS routing, intermediate nodes along a path to the destina- tion should inform the destination about its current state of resources in order that the destination is able to decide the optimal route among route candidates. The number and the kinds of QoS State Value depend on the QIB field. As an example, if a source specifies a delay parameter as a QoS requirement (i.e. D bit in QoS PM field is set), there MUST exist a QoS state value in SIB for presenting a delay value on candidate paths. In this case, all intermediate nodes MUST accumulate its mea- sured delay. The data structure of the QSIB is illustrated in figure 5. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS State Value 1 |QoS State Value N(if presented)| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |QoS State Value N(if presented)| Padding Bits (if needed) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 5. QoS State Information Block (QoS SIB) 3.2 QoS Route Error (QRERR) QoS Route Error (QRERR) is an extension to the DYMO RERR message ele- ment. QRERR message element is generated when an intermediate node realizes a lack of ability to maintain the QoS guarantees for a spe- cific route. The data structure of this element is as follows. Kang, Kim [Page 8] Internet Draft QoS Extension to DYMO 17 October 2005 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 | Len | TTL |I|Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : QUNodeAddress1 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QUNodeSeqNum1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | UQParam1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : Additional QUNodeAddressN (if needed) : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Additional QUNodeSeqNumN (if needed) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 6. QoS Route Error (QRERR) QoS Unsupported Node Address (QUNodeAddress) The IP address of the node that cannot guarantee QoS any more. QoS Unsupported Node Sequence Number (QUNodeSeqNum) The sequence number of the node that cannot guarantee QoS, if known; otherwise this field set to zero (0). Unsupported QoS Parameter (UQParam) The main difference between RERR and QRERR is the UQParam (Unsupported QoS Parameter) field which is used to inform the QoS requestor about which QoS parameter is no longer available for the originally specified QoS requirements. Once the QoS requestor receives the QRERR, it re-builds a QoS route process based on the unavailable QoS parameters if it still has packets to deliver. This field is illustrated in figure 7. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |QPCnt| QoS PM |Res|Traffic Cls| QoS Param Value 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |QoS Param Value N(if presented)| Padding Bits (if needed) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 7. UQParam field Kang, Kim [Page 9] Internet Draft QoS Extension to DYMO 17 October 2005 All fields are equivalent to the fields of QIB in the QRE message element but differently used. QoS PCnt indicates the number of scarce resource and each of their kinds are marked in QoS PM filed to iden- tify the next fields (i.e. which parameter(s) is (are) present in UQParam field). QoS Parameter Value The QoS Parameter Value field reports the measured QoS parame- ter(s) that fails to meet the originally requested QoS. If a particular node is aware of higher delay than the maximum per- missible delay, the measured delay is reported to the QoS requestor. The QRERR message MUST be delivered to all QoS requestor potentially affected by the change in the QoS parameter. 4. QoS DYMO Operations 4.1 QoS Route Discovery Like DYMO routing procedures, a QoS route is also discovered by means of two way handshaking consisting of a route request and route reply cycle. Instead of DYMO RREQ, the source (QoS requestor) disseminates QRREQ (RREQ with a QoS extension) to the destination. QRREQ message elements therefore should contain required QoS parameters as well as the QoS reporting information on the path that the message has been experienced. Thereafter, the destination node decides a correct route that can meet the QoS requirements and then sends QRREP (RREP with a QoS extension) to the source. Ahead of re-broadcasting a QRREQ message by an intermediate node, the node must check its resources whether it is available for the QoS requirements contained within the QRREQ message during the route dis- covery process. Thereafter, if resources are enough to meet service requirements, the intermediate node updates QoS information that is present in the QRREQ message to inform the destination about the cur- rent QoS states related to the path. Kang, Kim [Page 10] Internet Draft QoS Extension to DYMO 17 October 2005 That is, QRREQ should contain two different fields. One is used to specify the QoS requirements of the source (i.e. QoS requestor) that must be met at nodes through the path. The other field is used to inform both the QoS requestor and the destination that selects a proper QoS route the current network conditions such as delay, jit- ter, and/or bandwidth. In case of delay and jitter, intermediate nodes accumulate each of their measured delay and jitter value to the corresponding value of the received QRREQ message. For this reason, the destination can be aware of the end to end delay and jitter along the path. In case of bandwidth (i.e. capacity to transmit), the node compares its measured value with the value of QSIB field in the received QRREQ message. If the measured value is smaller than the value of the mes- sage, the field is updated to the measured one. This field allows the destination to be aware of the actual minimum bandwidth over a route from the source to the destination since the value of QSIB is always bigger than the minimum value that the QoS requestor requires. If it is not the case, a node MUST drop the QRREQ message since there is not enough bandwidth to guarantee the required one. Such a way allows the QoS requestor to be able to increase the minimum bandwidth requirement according to the network condition dynamically. In QoS enabled DYMO, M-bit MUST be set to one (1) and H-bits MUST be set to (11). Therefore, if the QoS extended element is not supported or handled by the processing node, the node MUST send a UERR to the NotifyAddress (QoS requestor) and drop the message to prevent that unsupported message is not propagated further. In DYMO, I bit of RE message indicates whether the element has been ignored by some intermediate nodes. Therefore, in QoS DYMO, if the I bit is (1), the QRE message MUST be dropped. 4.2 QoS Route Maintenance In order to react to changes in the network resources, nodes monitor their links under the aspect of QoS. When a node is aware of the fact that resources of its link is no longer available for the QoS Kang, Kim [Page 11] Internet Draft QoS Extension to DYMO 17 October 2005 requestor, a QoS-Route Error (QRERR) is sent to the QoS requestor to inform the current unavailable QoS parameters of the route. Once the requestor receives the QRERR, it re-builds a QoS route process based on the unavailable QoS parameters if it still has packets to deliver. 5. Security Considerations This document does not discuss any special security concerns in detail. The protocol of this document is built on the assumption that all participating nodes are trusted each other as well as there is no adversary who modifies/injects false route elements to corrupt the QoS routes. However, support of secure routing protocol is prerequisite for launching a secure communication in the presence of adversaries. In such an environment, most of all MANET routing protocols including DYMO are vulnerable to many kinds of attacks. It is fairly easy to inject fake routing messages or modify legitimate ones so that net- work operation would be heavily disturbed (e.g., by creating loops or disconnecting the network). Therefore, it is necessary to find a means to authenticate/verify control messages to discover and main- tain a proper route. Especially, QRE message MUST be authenticated to enable nodes participating in QoS DYMO routing protocol to assure the origin of the QRE message. References [1] I. Chakeres, E. M. Belding-Royer and C. E. Perkins. Dynamic MANET On-demand (DYMO) Routing. IETF Internet Draft draft-ietf-manet- dymo-02 June 2005. Work in Progress. [2] S. Bradner. Key words for use in RFCs to Indicate Requirement Levels. Internet RFC 2119, March 1997. [3] R. Braden, D. Clark, and S. Shenker, Integrated Services in the Internet Architecture: an Overview, Internet RFC 1633, June 1994. [4] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss, An Architecture for Differentiated Services Internet RFC 2475, Decem- ber 1998. Kang, Kim [Page 12] Internet Draft QoS Extension to DYMO 17 October 2005 [5] Nichols, K., Blake, S., Baker, F. and D. Black. Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Head- ers, Internet RFC 2474, December 1998. Author's Addresses Questions about this memo can be directed to: Namhi Kang Ubiquitous Network Research Center DASAN Networks Inc. 3F FineVenture Bldg. 345-1, YaTap-Dong, BunDang-Gu, SeongNam-Si, KyongGi-Do, 463-070 Korea +82 2 814 0151 nalnal@dcn.ssu.ac.kr Younghan Kim University of Soongsil in Seoul 11F Hyungnam Engineering Bldg. 317, Sangdo-Dong, Dongjak-Gu, Seoul 156-743 Korea +82 2 820 0904 yhkim@dcn.ssu.ac.kr Kang, Kim [Page 13] Internet Draft QoS Extension to DYMO 17 October 2005 Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Copyright Statement Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Kang, Kim [Page 14] Internet Draft QoS Extension to DYMO 17 October 2005