INTERNET-DRAFT Michael Welzl draft-welzl-opt-lookup-00.txt University of Linz Expiration Date: 22. September 2001 Telecooperation Department Experimental March 2001 IP Fast Option Lookup Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC 2026. 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 This memo describes a new IP Option type that allows routers to more efficiently check whether the IP header contains options that need further processing. 1. Definitions The key words "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. Unless otherwise noted, "other options" are all IP options except for options 0, 1 and TO BE ASSIGNED (the Fast Option Lookup option itself). Michael Welzl Expires: 22. September 2001 [Page 1] Internet Draft draft-welzl-opt-lookup-00.txt March 2001 2. Introduction Processing of IP options is well known to be an expensive operation for transit routers. Typically, only a few options will be supported in a router as some may need to be explicitely turned on by the administrator [RFC1812]. If a packet contains options but none of them are relevant to the router, it will still be necessary to examine all of them. This process, which is caused by variable option sizes (it is not clear where an option starts without looking at the preceding one) and lack of a predefined order for options in the IP header (e.g., a router cannot stop searching for option number 2 upon reaching option number 7), may unnecessarily cause a packet to be put into the slow path of the router. To facilitate scanning for supported options, a new option type is defined. 3. The Fast Option Lookup IP Option 3.1. Overview Fast Option Lookup is a variable-size IP option containing a list of Option Entries in predefined order. These entries, which represent other options in the packet, enable routers to detect options by searching a consecutive memory block instead of skipping memory blocks based on option lengths. Searching for an option that is not contained in the IP header may sometimes be interrupted earlier because Option Entries are sorted. Options may also be found earlier because it is possible to start searching from any direction; if, for instance, the Option Entries are sorted according to their option number, it will be more efficient to start searching for a recently defined option from the end of the field containing them. As the number of IP options grows, even more sophisticated approaches such as doing a binary search may become feasible. To restrict the number of options to be looked at to those relevant within a domain, an edge router may insert a Fast Option Lookup option where the enclosed Option Entries only represent a supported subset of all options in the header. Michael Welzl Expires: 22. September 2001 [Page 2] Internet Draft draft-welzl-opt-lookup-00.txt March 2001 3.2. Format The Fast Option Lookup option has the following format: 0 1 2 3 4 5 6 7 +--------+--------+-+-+-+-+-+-+-+-+---------//-----------+ |000XXXXX| Length |I| Order | Option Entries | +--------+--------+-+-+-+-+-+-+-+-+---------//-----------+ Type: Copied flag: 1 (all fragments must carry this option) Option class: 0 (control) Option number: XXXXX- TO BE ASSIGNED (decimal) Length: The option-length octet counts the option-type octet and the option-length octet as well as the Option Entries [RFC791]. Depending on the Incomplete flag, the number of either all or the possibly relevant other options in the IP header is given by Length-3. I - The Incomplete flag: If the Incomplete flag is 0, the Option Entries represent all other options in the header. If the Incomplete flag is 1, the Option Entries only represent a subset of these options. Order: A 7 bit field in network byte order with the following values: 0 The Option Entries are sorted by their option-type number. 1 The Option Entries are sorted by the value of their option-type octets (which means that they are sorted by their copied flag followed by option class and number). 2-127 Reserved to IANA for future use. Option Entries: Depending on the Incomplete flag, the Option Entries either identify all other options in the IP header or a subset of the other options, sorted according to the value of the Order field. An Option Entry has the following format: Michael Welzl Expires: 22. September 2001 [Page 3] Internet Draft draft-welzl-opt-lookup-00.txt March 2001 +--------+--------+ |opt-type| offset | +--------+--------+ Each Option Entry uniquely identifies an option that can be found in the IP header via two octets: opt-type: a copy of the option-type octet of the identified option offset: the distance (in octets) between the beginning of the Fast Option Lookup option and the beginning of the identified option 3.3. Usage Fast Option Lookup is a compromise between processing efficiency and additional space in the IP header. The relative amount of bandwidth used by this option depends on the packet size and the number of options in the header. In special cases, it may be feasible to copy this option upon fragmentation, but since the goal is processing efficiency, this operation should generally be avoided. Therefore, hosts including this option SHOULD perform Path MTU Discovery [RFC1191], thereby setting the "Don't Fragment" flag in the IP header. If there are less than two other options (not counting options 0 and 1), Fast Option Lookup MUST NOT be used. Hosts SHOULD use Fast Option Lookup if there are at least two other options in the header (not counting options 0 and 1). A host including the Fast Option Lookup option in IP header SHOULD set the Order field to 0 and SHOULD include Option Entries for all other options, thereby setting the Incomplete flag to 0. A router MAY insert a Fast Option Lookup option with an arbitrary Order field value (and accordingly sorted Option Entries) to use specific sorting rules within a domain. This process MUST NOT lead to an increase in the packet size if the "Don't Fragment" flag is set as this may indicate that Path MTU Discovery is being used [RFC1191]. As a packet enters a domain, an edge router MAY insert a Fast Option Lookup option with Option Entries representing only a supported subset of all options in the IP header and set the Incomplete flag to 1. As a packet leaves a domain, an edge router MUST replace a Fast Option Lookup option where the Incomplete flag is 1 with a Fast Option Lookup option where the Incomplete flag is Michael Welzl Expires: 22. September 2001 [Page 4] Internet Draft draft-welzl-opt-lookup-00.txt March 2001 0 and update the Option Entries accordingly or remove the Fast Option Lookup option. There MUST NOT be more than one Fast Option Lookup options in an IP header. A Fast Option Lookup option with a set Incomplete flag MUST NOT be replaced by another Fast Option Lookup option. The Fast Option Lookup option MUST NOT be preceded by any other option except for the IP Router Alert Option [RFC2113]. If the size of the entire Fast Option Lookup option (including its option-type and Length octets) is no multiple of 4 bytes, Option 1 (No Operation) option octets SHOULD be inserted before the beginning of the subsequent option. 4. Discussion Apart from the additional space needed in the IP header, this new option may cost processing power in routers which do not support Fast Option Lookup. Since it may only be used in conjunction with other options, including Fast Option Lookup will only result in one more option to be looked at in such routers; this makes it unlikely that a packet will be processed in the slow path because of Fast Option Lookup. Still, end-to-end flows may see a performance degradation. 5. Security Considerations If supported options are not included in the Fast Option Lookup Option Entries, these options may not be processed. If the Fast Option Lookup option contains Option Entries which do not represent existing options, the flow may experience a performance degradation because packet processing may unnecessarily continue in the slow path. 6. IANA Considerations The Order field described in Section 3.2 is registered and maintained by IANA. New values are to be assigned via IETF Consensus as defined in [RFC2434]. References [RFC791] Postel, J., "Internet Protocol", STD 5, RFC 791, September 1981. Michael Welzl Expires: 22. September 2001 [Page 5] Internet Draft draft-welzl-opt-lookup-00.txt March 2001 [RFC1191] Mogul, J.C., and Deering, S.E., "Path MTU discovery", RFC 1191, November 1990. [RFC1812] Baker, F., Editor, "Requirements for IP Version 4 Routers", RFC 1812, June 1995. [RFC2113] Katz, D., "IP Router Alert Option", RFC 2113, February 1997. [RFC2434] Alvestrand, H. and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 2434, October 1998. Michael Welzl Expires: 22. September 2001 [Page 6] Internet Draft draft-welzl-opt-lookup-00.txt March 2001 Author's Address Michael Welzl University of Linz Institute for Technical Computer Science and Telematics Telecooperation Department Altenberger Str. 69 4040 Linz, Austria Phone: +43 (732) 2468-9264 Fax: +43 (732) 2468-9829 Email: michael@tk.uni-linz.ac.at Comments should be sent to michael@tk.uni-linz.ac.at Michael Welzl Expires: 22. September 2001 [Page 7] Internet Draft draft-welzl-opt-lookup-00.txt March 2001 Full Copyright Statement Copyright (C) The Internet Society (1997). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implmentation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS 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." Michael Welzl Expires: 22. September 2001 [Page 8]