Mobile Ad hoc Networking (MANET) J. Dean Internet-Draft Naval Research Lab, United States Expires: September 12, 2008 March 11, 2008 Representing metric values in MANETs draft-dean-manet-metriclv-01 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 September 12, 2008. Copyright Notice Copyright (C) The IETF Trust (2008). Dean Expires September 12, 2008 [Page 1] Internet-Draft Metric TLV March 2008 Abstract This document defines TLVs (type-length-value) structures for representing cost values using the generalized MANET packet/message format. A message block TLV structure is defined for representing a cost value associated with the local node. An address block TLV structure is defined for representing a cost value associated with links or a cost value associated with other nodes. Both TLV structures are defined for use within MANET protocols. Registry space is created for TLVs which follow this format. 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 5.2.1. 8-bit Exponential Metric Representation . . . . . . . 7 5.2.2. 16-bit Exponential Metric Representation . . . . . . . 8 5.2.3. 32-bit Exponential Metric Representation . . . . . . . 8 5.2.4. 64-bit Exponential Metric Representation . . . . . . . 9 6. Metric TLVs . . . . . . . . . . . . . . . . . . . . . . . . . 10 6.1. Message TLV . . . . . . . . . . . . . . . . . . . . . . . 10 6.1.1. Message Metric Representation Semantics . . . . . . . 10 6.2. Address Block TLV . . . . . . . . . . . . . . . . . . . . 10 6.2.1. Other Node Metric TLV . . . . . . . . . . . . . . . . 11 6.2.2. Inbound Link Metric TLV . . . . . . . . . . . . . . . 11 6.2.3. Outbound Link Metric TLV . . . . . . . . . . . . . . . 11 6.2.4. Symmetric LInk Metric TLV . . . . . . . . . . . . . . 11 6.2.5. Address Metric Representation Semantics . . . . . . . 11 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 7.1. Message TLV Types . . . . . . . . . . . . . . . . . . . . 13 7.2. Address TLV Types . . . . . . . . . . . . . . . . . . . . 13 8. Security Considerations . . . . . . . . . . . . . . . . . . . 15 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 16 9.1. Normative References . . . . . . . . . . . . . . . . . . . 16 9.2. Informative References . . . . . . . . . . . . . . . . . . 16 Appendix A. Contributors . . . . . . . . . . . . . . . . . . . . 17 Appendix B. Acknowledgements . . . . . . . . . . . . . . . . . . 18 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 19 Intellectual Property and Copyright Statements . . . . . . . . . . 20 Dean Expires September 12, 2008 [Page 2] Internet-Draft Metric TLV March 2008 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 protocols which need to express values associated with a cost of using a node or 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 consepts and uses for sharing cost values. This document specifies a metric TLV structure which can be used to convey cost value information within the packetbb framework. Dean Expires September 12, 2008 [Page 3] Internet-Draft Metric TLV March 2008 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 [3]. Additionally, this document uses terminology from [1], and introduces the following terminology: Cost Value - The unit to be conveyed by a metric TLV. Node - A MANET router. Link - A pair of nodes, where at least one node is able to received traffic from the other. Symmetric Link - A link in which both nodes are able to received traffic from the other with the same link properties. Metric - an number associated with routing cost value as defined in Section 5. 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 September 12, 2008 [Page 4] Internet-Draft Metric TLV March 2008 3. Applicability Statement The TLV structures described in this document are 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 cost value conveyed by the metric SHOULD represent a concept which is related to cost of routing. Examples of cost value concepts 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 symetric 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 a metric TLV as defined by this document MUST: define the concept of the value to be transmitted, specify generation of the value, define protocol behavior when receiving the specified metric TLV, and request an extended type assignment from the appropriate registry defined in Section 7. Dean Expires September 12, 2008 [Page 5] Internet-Draft Metric TLV March 2008 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 type of link metric TLV MAY be associated with each address. Link metric TLVs can be either directional or directionless. Dean Expires September 12, 2008 [Page 6] Internet-Draft Metric TLV March 2008 5. Metric Representation of Cost Value This document specifies a TLV structure in which a cost values of a certain type are each represented as metric, one or more of which may be used in a TLV's value field. Each TLV extended type can only represent one type of cost, although multiple TLV's of differing extended type may be applied to an address or a group of addresses. Two different metric representations are defined in this document: a linear representation and an exponetial representation. 5.1. Linear Metric Representation Each linear metric MUST consisit of a multiple of 8 bits. These bits are the binary representation, in network byte order, of the cost value being transmitted. The length of the single metric is determined by [1], using the TLV semantics bits and the optional TLV length field of when present. For multivalue TLVs the single metric value is equal to the single-length value as determined by [1]. The linear metric consisting of all zeros SHOULD not be used. Documents which define metrics in which all zero representation is allowed MUST state the reasoning and meaning of the all zeros metric. The minimum cost value that can be represented in this manner is 1. The maximum cost value that can be represented, with N bytes per metric, in this manner is 2^(N*8)-1. 5.2. Exponential Metric Representation There are three exponential metric representations permitted by this document; an 8 bit representation, a 16 bit representation, a 32 bit representation and an 64 bit representation. Each exponential metric MUST consists of either 8, 16, 32 or 64 bits. The length of the single metric is determined by [1], using the TLV semantics bits and the optional TLV length field of when present. For multivalue TLVs the single metric value is equal to the single-length value as determined by [1]. 5.2.1. 8-bit Exponential Metric Representation In exponential metrics consistsing 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 Dean Expires September 12, 2008 [Page 7] Internet-Draft Metric TLV March 2008 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. 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 minimum-maximum can be expressed using this representation. 5.2.2. 16-bit Exponential Metric Representation Exponential metric representation using 16-bits uses the half precision representation as defined in [5] in network byte order. Some restrictions on encoding apply. o The sign bit SHOULD NOT be used. o The reserved exponents 0x00 and 0x1f SHOULD NOT be used. o The zero representation (0x0000) SHOULD not be used. o The infinity representation (0x7c00) SHOULD NOT be used. Documents which define metrics in which one or more of the above representations is allowed MUST state the reasoning and meaning of those representations. This minimum cost value that can be represented in this mannor is is ~ 6.10 *10^-5 The maximum cost value that can be represented in this mannor is 65504. Not all integers between minimum-maximum can be expressed using this representation. 5.2.3. 32-bit Exponential Metric Representation Exponential metric representation using 32-bits uses the single precision representation as defined in [4] in network byte order. Dean Expires September 12, 2008 [Page 8] Internet-Draft Metric TLV March 2008 Some restrictions on encoding apply. o The sign bit SHOULD NOT be used. o The reserved exponents 0x00 and 0xff SHOULD NOT be used. o The zero representation (0x0000 0000) SHOULD not be used. o The infinity representation (0x7f80 0000) SHOULD NOT be used. Documents which define metrics in which one or more of the above representations is allowed MUST state the reasoning and meaning of those representations. This minimum cost value that can be represented in this mannor is ~ 1.175 x 10^-38. The maximum cost value that can be represented in this mannor is ~ 3.403 x 10^38. Not all integers between minimum- maximum can be expressed using this representation. 5.2.4. 64-bit Exponential Metric Representation Exponential metric representation using 64-bits uses the double precision representation as defined in [4] in network byte order. Some restrictions on encoding apply. o The sign bit SHOULD NOT be used. o The reserved exponents 0x000 and 0x7ff SHOULD NOT be used. o The zero representation (0x0000 0000 0000 0000) SHOULD not be used. o The infinity representation (0x7ff0 0000 0000 0000) SHOULD NOT be used. Documents which define metrics in which one or more of the above representations is allowed MUST state the reasoning and meaning of those representations. This minimum cost value that can be represented in this mannor is ~ 1.113 x 10^-308. The maximum cost value that can be represented in this mannor is ~ 1.798 x 10^308. Not all integers between minimum- maximum can be expressed using this representation. Dean Expires September 12, 2008 [Page 9] Internet-Draft Metric TLV March 2008 6. Metric TLVs This document defines one message block TLV structure and one address block TLV structure. Both TLV structures defined by this document MUST have the thastypeext bit set to 1 in the tlv-semantics field as defined in [1] . 6.1. Message TLV A metric message block TLV SHOULD be used for signaling values associated with the local node. If a metric message TLV is to be included in a message, the originator-address MUST be included in the msg-header-info as defined in [1]. The field of a metric message TLV is further defined in this document by: = where: a 1 bit field (exprep) whos bit is described in Section 6.1.1 a 7 bit field containing the value type of the metric being conveyed. 6.1.1. Message Metric Representation Semantics The upper bit (exprep) of the field in a metric message block TLV represents the . Bit 0 (exprep) : If the bit is set the cost value is stored using an exponential metric representation as defined in Section 5.2. If the bit is unset the cost value is stored using a linear metric representation as defined in Section 5.1. 6.2. Address Block TLV A metric address block TLV SHOULD be used for signaling values associated with the addresses contained within the address block. The field of a metric address block TLV is further defined in this document by: = where: Dean Expires September 12, 2008 [Page 10] Internet-Draft Metric TLV March 2008 a 3 bit field whos bit is described in Section 6.2.5 a 5 bit field containing the value type of the metric being conveyed. 6.2.1. Other Node Metric TLV The cost value carried by the metric SHOULD associated with the appropriate address conatined in the address block. This association SHOULD NOT convey any information in association with the originator address. 6.2.2. Inbound Link Metric TLV The cost value carried by the metric SHOULD be associated with the directional link originating from the associated address contained in the address block and ending at the originator address. If an inbound link metric is to be used the originator-address MUST be included in the msg-header-info as defined in [1]. 6.2.3. Outbound Link Metric TLV The cost value carried by the metric SHOULD be associated with the directional link originating from the originator address and ending at the associated address contained in the address block. If an outbount link metric is to be used the originator-address MUST be included in the msg-header-info as defined in [1]. 6.2.4. Symmetric LInk Metric TLV The cost value carried by the metric SHOULD be associated with the bi-directional link from the associated address contained in the address block and the originator address. If an symmetric link metric is to be used the originator-address MUST be included in the msg-header-info as defined in [1]. 6.2.5. Address Metric Representation Semantics The upper three bits of the field in a metric address block TLV represent the . Bit 0 (exprep) : If the bit is set the cost value is stored using an exponential metric representation as defined in Section 5.2. If the bit is unset the cost value is stored using a linear metric representation as defined in Section 5.1. Dean Expires September 12, 2008 [Page 11] Internet-Draft Metric TLV March 2008 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 Dean Expires September 12, 2008 [Page 12] Internet-Draft Metric TLV March 2008 7. IANA Considerations This specification defines a structure for a message TLV type and structure for an address TLV type, which must be allocated from the "Assigned Message TLV Types" and "Assigned Address Block TLV Types" repository of [1]. 7.1. Message TLV Types This document requests IANA assignment of the "METRIC" message TLV type from the "Assigned Messsage TLV Types" of [1] This document defines two associated name-spaces for the tlv-type-ext field, defined in [1], of the message TLV type "METRIC": ietf:manet:metric:msgLin ietf:manet:metric:msgExp Assignment from these namespaces is as follows: Assigned Message TLV Type Namespaces +---------+------+---------+-------------+--------------------------+ | Mnemoni | TLV | TLV | Value | Name-Space | | c | Type | Type | Layout | | | | | Ext | | | +---------+------+---------+-------------+--------------------------+ | METRIC | TBD | 0 | N/A | UNASSIGNED | | | | | | | | | TBD | 1-127 | Section 5.1 | ietf:manet:metric:msgLin | | | | | | | | | TBD | 128-255 | Section 5.2 | ietf:manet:metric:msgExp | +---------+------+---------+-------------+--------------------------+ Table 2 A designated expert MUST review any requests for for registry values from ietf:manet:metric:msgLin or ietf:manet:metric:msgExp before assignment is given. The definition, generation and use of the cost value to be conveyed by a new metric MUST be explicitly documented before assignment is given. 7.2. Address TLV Types This document requests IANA assignment of the "METRIC" address block TLV type from the "Assigned Address Block TLV Types" of [1] This document defines eight associated name-spaces for the tlv-type-ext field, defined in [1], of the address block TLV type "METRIC": ietf:manet:metric:addrBlkLin:Node ietf:manet:metric:addrBlkLin:Inbound Dean Expires September 12, 2008 [Page 13] Internet-Draft Metric TLV March 2008 ietf:manet:metric:addrBlkLin:Outbound ietf:manet:metric:addrBlkLin:Symmetric ietf:manet:metric:addrBlkExp:Node ietf:manet:metric:addrBlkExp:Inbound ietf:manet:metric:addrBlkExp:Outbound ietf:manet:metric:addrBlkExp:Symmetric Assignment from these namespaces is as follows: Assigned Address TLV of Type Metric and their Namespaces +----------+-------------+------------+-----------------------------+ | TLV Type | Value | Value | Name-Space | | Ext | Layout | Concept | | +----------+-------------+------------+-----------------------------+ | 0 | N/A | N/A | UNASSIGNED | | | | | | | 1-31 | Section 5.1 | Node | metric:addrBlkLin:Node | | | | | | | 32-63 | Section 5.1 | Inbound | metric:addrBlkLin:Inbound | | | | | | | 64-95 | Section 5.1 | Outbound | metric:addrBlkLin:Outbound | | | | | | | 96-127 | Section 5.1 | Symmetric | metric:addrBlkLin:Symmetric | | | | | | | 128-159 | Section 5.2 | Node | metric:addrBlkExp:Node | | | | | | | 160-191 | Section 5.2 | Inbound | metric:addrBlkExp:Inbound | | | | | | | 192-223 | Section 5.2 | Outbound | metric:addrBlkExp:Outbound | | | | | | | 224-255 | Section 5.2 | Symmetric | metric:addrBlkExp:Symmetric | +----------+-------------+------------+-----------------------------+ Table 3 A designated expert MUST review and approve any requests for for registry values from ietf:manet:metric:addrLin or ietf:manet:metric: addrExp name-spaces before assignment is given as defined in [2]. The definition and use of the cost value to be conveyed by a metric MUST be explicitly documented before assignment is given. The generation of the cost values SHOULD also be addressed before assignment is given. Additionally, the associated concept of a value which is to be conveyed using an address block metric SHOULD corrospond to the correct name-space, ie the address block TLV extended type value conforms to the rules layed out in Section 6.2, specifically Section 6.2.5. Dean Expires September 12, 2008 [Page 14] Internet-Draft Metric TLV March 2008 8. Security Considerations This document does not specify any security considerations. Dean Expires September 12, 2008 [Page 15] Internet-Draft Metric TLV March 2008 9. References 9.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] Narten, T. and H. Alvestrand, "Guildlines for Writing an IANA Considerations Section in RFCs", RFC 2423, BCP 26, October 1998. [3] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, BCP 14, March 1997. [4] Institue of Electrical and Electronics Engineers, "IEEE Standard for Binary Floating-Point Arithmetic, (ANSI/IEEE Std 754-1985)", August 1985. [5] Institue of Electrical and Electronics Engineers, "Draft Standard for Floating-Point Arithmetic P754", October 2007. 9.2. Informative References [6] Clausen, T. and P. Jacquet, "The Optimized Link State Routing Protocol", RFC 3626, October 2003. Dean Expires September 12, 2008 [Page 16] Internet-Draft Metric TLV March 2008 Appendix A. Contributors Dean Expires September 12, 2008 [Page 17] Internet-Draft Metric TLV March 2008 Appendix B. Acknowledgements The authors would like to thank Brian Adamson and Justin Dean (both NRL) for their contributions. Dean Expires September 12, 2008 [Page 18] Internet-Draft Metric TLV March 2008 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 September 12, 2008 [Page 19] Internet-Draft Metric TLV March 2008 Full Copyright Statement Copyright (C) The IETF Trust (2008). 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 September 12, 2008 [Page 20]