Mobile Ad hoc Networking (MANET) J. Dean Internet-Draft Naval Research Lab, United States Expires: January 25, 2008 July 24, 2007 Representing metric values in MANETs draft-dean-manet-metriclv-00 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 January 25, 2008. Copyright Notice Copyright (C) The IETF Trust (2007). Dean Expires January 25, 2008 [Page 1] Internet-Draft Metric TLV July 2007 Abstract This document defines two TLVs (type-length-value structures) for representing cost values using the generalized MANET packet/message format [1]. A message block TLV is defined for representing a cost value associated with the local node. An address block TLV is defined for representing a cost value associated with links or a cost value associated with other nodes. Both TLVs defined are for use within MANET protocols. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 5 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 6 5. Metric Representation of Cost Value . . . . . . . . . . . . . 7 5.1. Linear Metric Representation . . . . . . . . . . . . . . . 7 5.2. Exponential Metric Representation . . . . . . . . . . . . 7 6. Metric TLVs . . . . . . . . . . . . . . . . . . . . . . . . . 9 6.1. Message TLV . . . . . . . . . . . . . . . . . . . . . . . 9 6.2. Address Block TLV . . . . . . . . . . . . . . . . . . . . 9 6.2.1. Other Node Metric TLV . . . . . . . . . . . . . . . . 9 6.2.2. Outbound Link Metric TLV . . . . . . . . . . . . . . . 9 6.2.3. Inbound Link Metric TLV . . . . . . . . . . . . . . . 9 6.2.4. Symmetric Link Metric TLV . . . . . . . . . . . . . . 9 7. Metric Subtype . . . . . . . . . . . . . . . . . . . . . . . . 10 7.1. Metric Representation Semantics . . . . . . . . . . . . . 10 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 9. Security Considerations . . . . . . . . . . . . . . . . . . . 12 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 10.1. Normative References . . . . . . . . . . . . . . . . . . . 13 10.2. Informative References . . . . . . . . . . . . . . . . . . 13 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 14 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 15 Intellectual Property and Copyright Statements . . . . . . . . . . 16 Dean Expires January 25, 2008 [Page 2] Internet-Draft Metric TLV July 2007 1. Introduction The generalized packet/message format [1] specifies a signaling format which MANET protocols can employ for exchanging protocol information. This format presents the ability to express and associate attributes to packets, messages or addresses, by way of a general TLV (type-length-value) mechanism. This document specifies a general Metric TLV structure, which can be used by any MANET protocol which needs to express/exchange values associated with a cost of using a node or a link. This document does not specify how cost values are generated or used. Differing physical and mac layers may have differing cost value generating capabilities and differing MANET protocols may have differing concepts and uses for sharing cost values. This document specifies how to convey cost value information within a MANET using metric TLVs within the [1]b framework. Dean Expires January 25, 2008 [Page 3] Internet-Draft Metric TLV July 2007 2. Terminology 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 RFC2119 [2]. Additionally, this document uses terminology from [1], and introduces the following terminology: Node - A MANET router. Link - A pair of nodes, where at least one node is able to received traffic from the other. Symetric Link - A link in which both nodes are able to received traffic from the other. Cost Value - the value to be transmitted using metric representation. Metric - an 8 bit number associated with the cost value. Node Metric - a metric associated with the cost of using a node. Link Metric - a metric associated with the cost of using a link. Dean Expires January 25, 2008 [Page 4] Internet-Draft Metric TLV July 2007 3. Applicability Statement The TLV described in this document is applicable whenever a metric associated with either a node or a link is required in a protocol using the generalized MANET packet/message format [1]. The metric value SHOULD represent a concept which is related to cost of routing. Examples of costs concepts to be represented by metrics that MAY be included in a protocol message are: o The amount of power, normalized to some standard, a node has remaining represented as a node metric. o The amount of bandwidth provided by a link represented by a symmetric link metric. o The estimated quality of a link represented by a inbound or outbound link metric. The generation of values for transmission within a metric TLV is not defined in this document. The usage of transmitted values by metric TLVs is also not defined in this document. Protocols using this metric TLV must define the concept of the value to be transmitted, generation of the value, and protocol behavior when receiving metric TLVs. Dean Expires January 25, 2008 [Page 5] Internet-Draft Metric TLV July 2007 4. Protocol Overview and Functioning This document outlines mechanisms for encoding cost values using the TLV mechanism of [1]. Protocols using the mechanisms and TLVs specified in this document must ensure that they do so in a coherent way. This document does not specify a protocol nor does it mandate specific node or protocol behavior. Node metrics SHOULD represent cost values associated with routing though that node. Node metric TLVs can be either message TLVs, when representing a local node cost value, or address block TLVs, when representing a cost value associated with a node other than the originator. Multiple node metric values MAY be associated with any one address. Link metrics SHOULD represent cost values associated with routing though links. Link metric TLVs are contained only in address block TLVs. More than one link metric TLV MAY be associated with each address. Link metric TLVs can be either directional or directionless. Dean Expires January 25, 2008 [Page 6] Internet-Draft Metric TLV July 2007 5. Metric Representation of Cost Value This document specifies a TLV structure in which a cost values can be represented as metrics. One or more metrics, of a specific type may be included in a single TLV value field. Each TLV only represents one type of cost. However, multiple metric TLV's may be applied to an address or a group of addresses. Allowing for multiple values and representation of those values to be associated with a single address. Independent of cost type, two different metric representations are defined in this document: a linear representation and an exponential representation. 5.1. Linear Metric Representation Each linear metric consists of 8 bits which directly map to the cost value being transmitted. The linear metric consisting of all zeros MUST not be used. The minimum cost value that can be represented in this manner is 1. The maximum cost value that can be represented in this manner is 255. 5.2. Exponential Metric Representation Each exponential metric consists of 8 bits, the least significant four bits represent the mantissa (a), and the most significant four bits represent the exponent (b), so that: o cost value = (1 + a/16) * 2^b o exponential metric = 16 * b + a Note that ascending values of the exponential metric represent ascending cost values, cost values may thus be compared by comparison of exponential metrics. An algorithm for computing the exponential metric representing the smallest representable cost value not less than the cost value v is: 1. find the largest integer b such that v >= 2^b; 2. set a = 16 * (t / (2^b) - 1), rounded up to the nearest integer; 3. if a == 16 then set b = b + 1 and set a = 0; 4. if a and b are in the range 0 and 15 then the required time value can be represented by the exponential metric 16 * b + a, otherwise it can not. Dean Expires January 25, 2008 [Page 7] Internet-Draft Metric TLV July 2007 The minimum cost value that can be represented in this manner is 1. The maximum cost value that can be represented in this manner is 63488. Not all integers between 1-63488 can be expressed using this representation. Dean Expires January 25, 2008 [Page 8] Internet-Draft Metric TLV July 2007 6. Metric TLVs This document defines one message block TLV and one address block metric TLV. Address block TLVs are broken down further into four different generalized types; node, outbound, inbound, and symmetric. 6.1. Message TLV The message block TLV is used for signaling values associated with the local node. If a metric message TLV is to be included in a message, the 0 bit of the msg-semantics field MUST be cleared and the originator-address MUST be included in the msg-header-info as defined in [1] . 6.2. Address Block TLV The address block TVL is used for signaling values associated with addresses contained within the address block. 6.2.1. Other Node Metric TLV The cost value carried by the metric is associated with the appropriate address contained in the address block. 6.2.2. Outbound Link Metric TLV The cost value carried by the metric is associated with the directional link originating from the originator address and ending at the associated address contained in the address block. 6.2.3. Inbound Link Metric TLV The cost value carried by the metric is associated with the directional link originating from the originator address and ending at the associated address contained in the address block. 6.2.4. Symmetric Link Metric TLV The cost value carried by the metric is associated with the bi- directional link formed from the originator address and the associated address contained in the address block. Dean Expires January 25, 2008 [Page 9] Internet-Draft Metric TLV July 2007 7. Metric Subtype TLVs defined in this document MUST have the hassubtype bit set to 1 in the tlv-semantics field as defined in [1] . The subtype field of a metric TLV as defined in this document is comprised of two parts, the metric representation and the value type. The three upper bits define which metric representation the values represent. Usage of these bits is defined below. The five lower bits allow for differing value types (delay and power being examples of differing value types) Usage and definitions for values included in this field is not defined in this document. 7.1. Metric Representation Semantics bit 0 (exprep) : If bit is set the cost value is stored using an exponential metric representation as defined in Section 5.2 . If bit is unset the cost value is stored using a linear metric representation as defined in Section 5.1 . bit 1 (outbound) and bit 2 (inbound) : Bits 1 and 2 are defined in Table 1 . +--------------+---------+--------------------------------------+ | Outbound | Inbound | Value representation | +--------------+---------+--------------------------------------+ | 0 | 0 | Node Metric | | | | | | 0 | 1 | Inbound Link Metric | | | | | | 1 | 0 | Outbound Link Metric | | | | | | 1 | 1 | Symmetric Link Metric | +--------------+---------+--------------------------------------+ Table 1 An outbound link metric is associated with a link which originates from the originator address and ends at the appropriate address. An inbound link originates for the appropriate address and ends at the originator address. Dean Expires January 25, 2008 [Page 10] Internet-Draft Metric TLV July 2007 8. IANA Considerations This specification defines one message TLV type, and one address TLV type which must be allocated from the "Assigned Message TLV Types" repository of [1]. +-------------+------+---------+------------------------------------+ | Mnemonic | Type | Subtype | Description | +-------------+------+---------+------------------------------------+ | METRIC | TBD | 0 | RESERVED | | | | | | | | TBD | 1-255 | Bits 0-2 as defined in this | | | | | document. Bits 3-7 as defined in | | | | | documents using this | | | | | specification. | +-------------+------+---------+------------------------------------+ Table 2 Lower bit subtype definitions may be based per protocol as differing information MAY be useful to differing protocols. Protocol goals and usages as well as radio technology suggests protocol dependant type assignment. Dean Expires January 25, 2008 [Page 11] Internet-Draft Metric TLV July 2007 9. Security Considerations This document does not specify any security considerations. Dean Expires January 25, 2008 [Page 12] Internet-Draft Metric TLV July 2007 10. References 10.1. Normative References [1] Clausen, T., Dean, J., Dearlove, C., and C. Adjih, "Generalized MANET Packet/Message Format", Work In Progress draft-ietf-manet-packetbb-03.txt, June 2006. [2] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, BCP 14, March 1997. 10.2. Informative References Dean Expires January 25, 2008 [Page 13] Internet-Draft Metric TLV July 2007 Appendix A. Acknowledgements The author would like to thank Brian Adamson, Ian Chakares, Thomas Clausen, Chris Dearlove, and Joe Macker for their input which helped shape this document. Dean Expires January 25, 2008 [Page 14] Internet-Draft Metric TLV July 2007 Author's Address Justin Wendell Dean Naval Research Lab, United States Phone: +1 202 767 3397 Email: jdean@itd.nrl.navy.mil URI: http://pf.itd.nrl.navy.mil/ Dean Expires January 25, 2008 [Page 15] Internet-Draft Metric TLV July 2007 Full Copyright Statement Copyright (C) The IETF Trust (2007). 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. 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, THE IETF TRUST 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. Intellectual Property 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. Acknowledgment Funding for the RFC Editor function is provided by the IETF Administrative Support Activity (IASA). Dean Expires January 25, 2008 [Page 16]