Mobile Ad hoc Networking (MANET) T. Clausen Internet-Draft LIX, Ecole Polytechnique, France Intended status: Standards Track C. Dearlove Expires: January 11, 2009 BAE Systems Advanced Technology Centre July 10, 2008 Representing multi-value time in MANETs draft-ietf-manet-timetlv-05 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 11, 2009. Abstract This document describes a general and flexible TLV (type-length-value structure) for representing time using the generalized MANET packet/ message format. It defines two message and two address block TLVs for representing validity and interval times for MANET routing protocols. Clausen & Dearlove Expires January 11, 2009 [Page 1] Internet-Draft Time TLV July 2008 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Motivation and Rationale . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 5 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 5 5. Representing Time . . . . . . . . . . . . . . . . . . . . . . 5 6. General Time TLV Structure . . . . . . . . . . . . . . . . . . 6 6.1. Single-value Time TLVs . . . . . . . . . . . . . . . . . . 7 6.2. Multi-value Time TLVs . . . . . . . . . . . . . . . . . . 8 7. Message TLVs . . . . . . . . . . . . . . . . . . . . . . . . . 9 7.1. INTERVAL_TIME TLV . . . . . . . . . . . . . . . . . . . . 9 7.2. VALIDITY_TIME TLV . . . . . . . . . . . . . . . . . . . . 9 8. Address Block TLVs . . . . . . . . . . . . . . . . . . . . . . 9 8.1. INTERVAL_TIME TLV . . . . . . . . . . . . . . . . . . . . 9 8.2. VALIDITY_TIME TLV . . . . . . . . . . . . . . . . . . . . 10 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 9.1. Expert Review: Evaluation Guidelines . . . . . . . . . . . 10 9.2. Message TLV Types . . . . . . . . . . . . . . . . . . . . 11 9.3. Address Block TLV Types . . . . . . . . . . . . . . . . . 11 10. Security Considerations . . . . . . . . . . . . . . . . . . . 12 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 12 11.1. Normative References . . . . . . . . . . . . . . . . . . . 12 11.2. Informative References . . . . . . . . . . . . . . . . . . 12 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 12 Clausen & Dearlove Expires January 11, 2009 [Page 2] Internet-Draft Time TLV July 2008 1. Introduction The generalized packet/message format [packetbb] specifies a signaling format which MANET routing 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 Time TLV structure, which can be used by any MANET routing protocol that needs to express either single time-values or a set of time-values with each time-value associated with a range of hop counts, as provided by the message header of [packetbb]. This allows a receiving node to determine a single time-value if either it knows its hop count from the originator node, or the Time TLV specifies a single time-value. This document also specifies two message TLV types, which use the TLV structure proposed. These TLV types are INTERVAL_TIME and VALIDITY_TIME, specifying respectively the maximum time before another message of the same type as this message from the same originator should be received, and the duration for which the information in this message is valid after receipt. Note that, if both are present, then the latter will usually be greater than the former in order to allow for possible message loss. This document also specifies two address block TLV types, which use the TLV structure proposed. These TLV types are INTERVAL_TIME and VALIDITY_TIME, defined equivalently to the two message TLVs with the same names. 1.1. Motivation and Rationale The TLV mechanism as specified in [packetbb] allows associating a "value" to either a packet, a message or to addresses. The data structure for doing so - the TLV - is identical in each of the three cases, however the TLV's position in a received packet allows determining if that TLV is a "packet TLV" (it appears in the packet header, before any messages), a "message TLV" (it appears in the TLV block immediately following a message header) or an "address block TLV" (it appears in the TLV block immediately following an address block). While TLVs may be structurally identical, that which they express may be different. This is determined from the kind (packet, message or address block) and type of the TLV. For example one TLV might associate a lifetime to an address, another a content sequence number to a message, and another a cryptographic signature to a packet. For this reason, [packetbb] specifies separate registries for packet, Clausen & Dearlove Expires January 11, 2009 [Page 3] Internet-Draft Time TLV July 2008 message and address block TLV types, and does not specify any structure in the TLV value field. The TLVs defined in this document express, essentially, that "this information will be refreshed within X seconds" and that "this information is valid for X seconds after being received", each allowing the "X seconds" to be specified as a function of the number of hops from the originator of the information. This document specifies a general format allowing expressing and encoding this as the value field of a TLV. This representation uses a compact (8 bit) representation of time, as message size is an issue in many MANETs, and the offered precision and range is appropriate for MANET routing protocols. A TLV of this format may be used for packets, messages or addresses. For example, a proactive MANET routing protocol periodically reporting link state information could include a TLV of this format as a message TLV. This may indicate a different periodicity in different scopes (possibly frequently up to a few hops, less frequently beyond that) because some messages may be sent with limited scope, as specified in [packetbb]. A reactive MANET routing protocol could include a TLV of this format as an address block TLV for reporting the lifetime of routes to individual addresses. In addition to defining the general format as outlined above, this document requests IANA assignments for INTERVAL_TIME and VALIDITY_TIME TLVs. These IANA assignments are requested in this document in order to avoid interdependencies between otherwise unrelated MANET protocols and in order to not exhaust the TLV type spaces by having different protocols request types for essentially identical data structures. Only message and address block TLVs are requested, as these are those for which a need has been demonstrated. 2. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. Additionally, this document uses terminology from [packetbb], and introduces the following terminology: hop count - the number of hops from the message originator to the message recipient. This is defined to equal the field in the element defined in [packetbb], if present, after it is incremented on reception. If the field is not present, or in a packet TLV, then hop count is defined to Clausen & Dearlove Expires January 11, 2009 [Page 4] Internet-Draft Time TLV July 2008 equal 255. time-value - a time, measured in seconds. time-code - an 8 bit field, representing a time-value. 3. Applicability Statement The TLV structure described in this document is applicable whenever a single time-value, or a time-value that varies with the number of hops from the originator of a message, is required in a protocol using the generalized MANET packet/message format [packetbb]. Examples of time-values that may be included in a protocol message are: o The maximum time interval until the next message of the same type is to be generated by the message's originator node. o The validity time of the information with which the time-value is associated. Either of these may vary with the hop count between the originating and receiving nodes, e.g. if messages of the same type are sent with different hop limits as defined in [packetbb]. Parts of this document have been generalized from material in the proactive MANET routing protocol OLSR (The Optimized Link State Routing Protocol) [RFC3626]. 4. Protocol Overview and Functioning This document does not specify a protocol nor does it mandate specific node or protocol behavior. Rather, it outlines mechanisms for encoding time-values using the TLV mechanism of [packetbb]. 5. Representing Time This document specifies a TLV structure in which time-values are each represented in an 8 bit time-code, one or more of which may be used in a TLV's field. Of these 8 bits, the least significant 3 bits represent the mantissa (a), and the most significant 5 bits represent the exponent (b), so that: o time-value = (1 + a/8) * 2^b * C o time-code = 8 * b + a Clausen & Dearlove Expires January 11, 2009 [Page 5] Internet-Draft Time TLV July 2008 All nodes in the MANET MUST use the same value of the constant C, which will be specified in seconds, hence so will be all time-values. C MUST be greater than 0 seconds. Note that ascending values of the time-code represent ascending time-values, time-values may thus be compared by comparison of time-codes. An algorithm for computing the time-code representing the smallest representable time-value not less than the time-value t is: 1. find the largest integer b such that t/C >= 2^b; 2. set a = 8 * (t / (C * 2^b) - 1), rounded up to the nearest integer; 3. if a == 8 then set b = b + 1 and set a = 0; 4. if 0 <= a <= 7, and 0 <= b <= 31, then the required time-value can be represented by the time-code 8 * b + a, otherwise it can not. The minimum time-value that can be represented in this manner is C. The maximum time-value that can be represented in this manner is 15 * 2^28 * C, or about 4.0 * 10^9 * C. If, for example, C = 1/1024 second, then this is about 45 days. A protocol using this time representation MUST define the value of C. A protocol using this specification MAY specify that the all bits zero time-value (0) represents a time-value of zero and/or that the all bits one time-value (255) represents an indefinitely large time- value. 6. General Time TLV Structure The following data structure allows the representation of a single time-value, or of a default time-value plus pairs of (time-values, hop counts) for when hop count dependent time-values are required. The time-values are represented as time-codes as defined in Section 5. This data structure is specified, using the regular expression syntax of [packetbb], by: = ()* where: is an 8 bit unsigned integer field containing a time- code as defined in Section 5. Clausen & Dearlove Expires January 11, 2009 [Page 6] Internet-Draft Time TLV July 2008 is an 8 bit unsigned integer field specifying a hop count from the message originator. A structure thus consists of an odd number of octets; with a repetition factor of n for the (time, hop count) pairs in the regular expression syntax, it contains 2n+1 octets. On reception, n is determined from the length. A field may be thus represented by: ... ... , ... , if present, MUST be a strictly increasing sequence, with < 255. Then, at the receiving node's hop count from the originator node, the time-value indicated is that represented by the time-code: o , if n > 0 and hop count <= ; o , if n > 1 and < hop count <= for some i such that 1 <= i < n; o otherwise, i.e. if n == 0 or hop count > . If included in a message without a field in its message header, or in a packet TLV, then the form of this data structure with a single time-code in (i.e. n == 0) SHOULD be used. 6.1. Single-value Time TLVs The purpose of a single value Time TLV is to allow a single time- value to be determined by a node receiving an entity containing the Time TLV, based on its hop count from the entity's originator. The Time TLV may contain information that allows that time-value to be a function of the hop count, and thus different receiving nodes may determine different time-values. A single-value Time TLV may be a packet TLVs, a message TLV or an address block TLV. A Time TLV which has the tismultivalue flag cleared ('0') in its field, as defined in [packetbb], contains a single , as defined above, in its field. For such a Time TLV: o The field in the TLV MUST contain the value 2n+1, with n being the number of (time-value, hop count) pairs in the Time TLV. Clausen & Dearlove Expires January 11, 2009 [Page 7] Internet-Draft Time TLV July 2008 o The number of (time-value, hop count) pairs MUST be identified by inspecting the field in the TLV. The number of such pairs, n, is: * n = ( - 1) / 2 This MUST be an integer value. 6.2. Multi-value Time TLVs The purpose of a multi-value Time TLV is to associate a set of structures to an identically sized set of addresses, as described in [packetbb]. For each of these structures, a single time-value can be determined by a node receiving an entity containing the Time TLV, based on its hop count from the entity's originator. The Time TLV may contain information that allows that time-value to be a function of the hop count, and thus different receiving nodes may determine different time-values. Multi-value Time TLVs MUST be address block TLVs. A multi-value Time TLV MUST NOT be a packet or message TLV. A Time TLV which has the tismultivalue flag set ('1') in its field, as defined in [packetbb], contains a sequence of structures, as defined above, in its field. For such a Time TLV: o The field in the TLV MUST contain the value m * (2n+1), with n being the number of (time-value, hop count) pairs in the Time TLV, and m being number-values as defined in [packetbb]. o The number of structures included in the field is equal to number-values as defined in [packetbb]. o The number of (time-value, hop count) pairs in each structure MUST be the same, and MUST be identified by inspecting the field in the TLV and using number-values as defined in [packetbb]. The number of such pairs in each structure, n, is: * n = (( / number-values) - 1) / 2 This MUST be an integer value. The lists of hop count values MAY be different. Clausen & Dearlove Expires January 11, 2009 [Page 8] Internet-Draft Time TLV July 2008 7. Message TLVs Two message TLVs are defined, for signaling message interval (INTERVAL_TIME) and message validity time (VALIDITY_TIME). 7.1. INTERVAL_TIME TLV An INTERVAL_TIME TLV is a message TLV that defines the maximum time before another message of the same type as this message from the same originator should be received. This interval time MAY be specified to depend on the hop count from the originator. (This is appropriate if messages are sent with different hop limits, so that receiving nodes at greater hop counts have an increased interval time.) A message MUST NOT include more than one INTERVAL_TIME TLV. An INTERVAL_TIME TLV is an example of a Time TLV specified as in Section 5. 7.2. VALIDITY_TIME TLV A VALIDITY_TIME TLV is a message TLV that defines the validity time of the information carried in the message in which the TLV is contained. After this time the receiving node MUST consider the message content to no longer be valid (unless repeated in a later message). The validity time of a message MAY be specified to depend on the hop count from its originator. (This is appropriate if messages are sent with different hop limits, so that receiving nodes at greater hop counts receive information less frequently and must treat is as valid for longer.) A message MUST NOT include more than one VALIDITY_TIME TLV. A VALIDITY_TIME TLV is an example of a Time TLV specified as in Section 5. 8. Address Block TLVs Two address block TLVs are defined, for signaling address advertisement interval (INTERVAL_TIME) and address validity time (VALIDITY_TIME). 8.1. INTERVAL_TIME TLV An INTERVAL_TIME TLV is an address block TLV that defines the maximum time before this address from the same originator should be received again. This interval time MAY be specified to depend on the hop count from the originator. (This is appropriate if addresses are Clausen & Dearlove Expires January 11, 2009 [Page 9] Internet-Draft Time TLV July 2008 contained in messages sent with different hop limits, so that receiving nodes at greater hop counts have an increased interval time.) A protocol using this TLV and the similarly named message TLV MUST specify how to interpret the case when both are present (typically that the former over-rides the latter for those addresses which are covered by the former). An INTERVAL_TIME TLV is an example of a Time TLV specified as in Section 5. 8.2. VALIDITY_TIME TLV A VALIDITY_TIME TLV is an address block TLV that defines the validity time of the addresses to which the TLV is associated. After this time the receiving node MUST consider the addresses to no longer be valid (unless these are repeated in a later message). The validity time of an address MAY be specified to depend on the hop count from its originator. (This is appropriate if addresses are contained in messages sent with different hop limits, so that receiving nodes at greater hop counts receive information less frequently and must treat is as valid for longer.) A protocol using this TLV and the similarly named message TLV MUST specify how to interpret the case when both are present (typically that the former over-rides the latter for those addresses which are covered by the former). A VALIDITY_TIME TLV is an example of a Time TLV specified as in Section 5. 9. IANA Considerations This specification defines two message TLV types, which must be allocated from the "Assigned Message TLV Types" repository of [packetbb] as specified in Table 1 and two address block TLV types, which must be allocated from the "Assigned Address Block TLV Types" repository of [packetbb] as specified in Table 2. IANA is requested to assign the same numerical value to the message TLV and address block TLV types with the same name. 9.1. Expert Review: Evaluation Guidelines For the registries for TLV type extensions where an Expert Review is required, the designated expert SHOULD take the same general recommendations into consideration as are specified by [packetbb]. Clausen & Dearlove Expires January 11, 2009 [Page 10] Internet-Draft Time TLV July 2008 9.2. Message TLV Types +---------------+------+-----------+--------------------------------+ | Name | Type | Type | Description | | | | Extension | | +---------------+------+-----------+--------------------------------+ | INTERVAL_TIME | TBD1 | 0 | The maximum time before | | | | | another message of the same | | | | | type as this message from the | | | | | same originator should be | | | | | received | | | | 1-223 | Expert Review | | | | 224-255 | Experimental Use | | VALIDITY_TIME | TBD2 | 0 | The time from receipt of the | | | | | message during which the | | | | | information contained in the | | | | | message is to be considered | | | | | valid | | | | 1-223 | Expert Review | | | | 224-255 | Experimental Use | +---------------+------+-----------+--------------------------------+ Table 1 9.3. Address Block TLV Types +---------------+------+-----------+--------------------------------+ | Name | Type | Type | Description | | | | extension | | +---------------+------+-----------+--------------------------------+ | INTERVAL_TIME | TBD1 | 0 | The maximum time before | | | | | another message of the same | | | | | type as this message from the | | | | | same originator and containing | | | | | this address should be | | | | | received | | | | 1-223 | Expert Review | | | | 224-255 | Experimental Use | | VALIDITY_TIME | TBD2 | 0 | The time from receipt of the | | | | | address during which the | | | | | information regarding this | | | | | address is to be considered | | | | | valid | | | | 1-223 | Expert Review | | | | 224-255 | Experimental Use | +---------------+------+-----------+--------------------------------+ Table 2 Clausen & Dearlove Expires January 11, 2009 [Page 11] Internet-Draft Time TLV July 2008 10. Security Considerations This document does not specify any security considerations. 11. References 11.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, BCP 14, March 1997. [packetbb] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, "Generalized MANET Packet/Message Format", draft-ietf-manet-packetbb-13.txt (work in progress), June 2008. 11.2. Informative References [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State Routing Protocol", RFC 3626, October 2003. Appendix A. Acknowledgements The authors would like to thank Brian Adamson and Justin Dean (both NRL) and Ian Chakeres (Motorola) for their contributions, and Alan Cullen (BAE Systems) for his careful review of this specification. Authors' Addresses Thomas Heide Clausen LIX, Ecole Polytechnique, France Phone: +33 6 6058 9349 EMail: T.Clausen@computer.org URI: http://www.ThomasClausen.org/ Christopher Dearlove BAE Systems Advanced Technology Centre Phone: +44 1245 242194 EMail: chris.dearlove@baesystems.com URI: http://www.baesystems.com/ Clausen & Dearlove Expires January 11, 2009 [Page 12] Internet-Draft Time TLV July 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. Clausen & Dearlove Expires January 11, 2009 [Page 13]