Internet DRAFT - draft-welzl-opt-lookup

draft-welzl-opt-lookup









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]