Internet Engineering Task Force                        Curtis Villamizar
INTERNET-DRAFT                                                       ANS
draft-ietf-isis-omp-01                                          Tony Li
                                                                Juniper
                                                      February 22, 1999


                   IS-IS Optimized Multipath (ISIS-OMP)





Status of this Memo


  This document is an Internet-Draft and is in full conformance with all
  provisions of Section 10 of RFC2026.

  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 mate-
  rial 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.

  Copyright (C) The Internet Society (February 22, 1999).  All Rights
  Reserved.


Abstract


  IS--IS may form multiple equal cost paths between points.  This is
  true of any link state protocol.  In the absence of any explicit sup-
  port to take advantage of this, a path may be chosen arbitrarily.
  Techniques have been utilized to divide traffic somewhat evenly among
  the available paths.  These techniques have been referred to as Equal
  Cost Multipath (ECMP). An unequal division of traffic among the avail-
  able paths is generally preferable.  Routers generally have no knowl-
  edge of traffic loading on distant links and therefore have no basis

INTERNET-DRAFT    IS-IS Optimized Multipath (ISIS-OMP)    February 22, 1999

  to optimize the allocation of traffic.

  Optimized Mulitpath is a extension to IS--IS, utilizing additional
  Type/Length/Value (TLV) tuples to distribute loading information.  An
  algorithm to adjust forwarding, gradually enough to insure stability
  yet provide reasonably fast adjustment when needed, is provided in the
  related document OSPF--OMP [6].  The IS--IS encapsulation and minor
  differences in the dynamics of ISIS--OMP relative to OSPF--OMP are
  described here.



1  Overview


  IS--IS is OSI link state routing protocol [2].  OSPF is a link state
  routing protocol defined within the IETF process [4].  IS--IS can also
  be used as an IP interior gateway protocol (IGP) much as OSPF is used
  [1].

  Networks are often heavily loaded.  Topologies often evolve to include
  multiple paths.  Multiple paths may be initially designed to provide
  redundancy but also result from incremental addition of circuits to
  accommodate traffic growth.  The redundant paths provide a potential
  to distribute traffic loading and reduce congestion.  Optimized Mulit-
  path (OMP) provides a means for a link state protocol such as IS--IS
  or OSPF to make better use of this potential to distribute loading.
  Please refer to [6] for a more complete introduction to OMP.


2  Differences Between ISIS--OMP and OSPF--OMP


  Both IS--IS and OSPF are link state protocols.  The technique of equal
  cost multipath (ECMP) routing is formally defined in OSPF [4] but has
  also been applied to IS--IS implementations.  Because these routing
  protocols are quite similar, application of OMP techniques is very
  similar.

  Differences between OSPF and IS--IS that impact OMP are:



 1.  The encapsulation of IS--IS link state information is different so
     the encapsulation of link loading information will be different.

 2.  IS--IS link state information is flooded in no more than 256 LSPDU
     fragments which must be reflooded in their entirety when any TLV in
     the LSPDU fragment changes.
 3.  IS--IS Level 2 routing differs from OSPF inter--area routing.



Villamizar, Li              Expires  August 22, 1999              [Page 2]


INTERNET-DRAFT    IS-IS Optimized Multipath (ISIS-OMP)    February 22, 1999

 4.  IS--IS handling of external routes in Level 2 differs from OSPF
     handling of external routes.



2.1  Encapsulation


  IS--IS packs link state information in Type/Length/Value tuples.  The
  type and length are one byte each.  The length is a unsigned byte pro-
  viding the length in bytes of the Value portion of the tuple.  The
  ``extended IS reachability TLV'' is defined by Li as type 22 [3].
  Subtypes of this TLV include the following, however if there are any
  differences in a descendant to [3], consider that list to be authori-
  tative.



    IPv4 interface address            subtype 6, length 4
    IPv4 neighbor address             subtype 8, length 4
    Maximum (out) link bandwidth      subtype 9, length 4
    Current (out) bandwidth usage     subtype 12, length 4
    Maximum inbound bandwidth usage   subtype 15, length 4
    Outbound fractional packet loss   subtype 17, length 4
    Inbound fractional packet loss    subtype 18, length 4
    Maximum inbound link bandwidth    subtype 19, length 4



  The value part these TLV tuples are described below:


  IPv4 interface address, subtype 6, length 4  This is the IPv4 address
     of the near end of the interface.

  IPv4 neighbor address, subtype 8, length 4  This is the IPv4 address
     of the far end of a point to point interface.
  Maximum (out) link bandwidth, subtype 9, length 4  This is an IEEE 754
     format 32 bit floating point number representing the bandwidth of
     the interface in bytes per second.  See subtype 19.

  Current (out) bandwidth usage, subtype 12, length 4  This is an IEEE
     754 format 32 bit floating point number representing the outbound
     link utilization of the interface in bytes per second.
  Maximum inbound bandwidth usage, subtype 15, length 4  This is an IEEE
     754 format 32 bit floating point number representing the inbound
     link utilization of the interface in bytes per second.

  Outbound fractional packet loss, subtype 17, length 4  This is an IEEE
     754 format 32 bit floating point number representing the ratio of
     lost outbound packets (generally lost due to queueing drop) to to-
     tal outbound packets.

Villamizar, Li              Expires  August 22, 1999              [Page 3]


INTERNET-DRAFT    IS-IS Optimized Multipath (ISIS-OMP)    February 22, 1999

  Inbound fractional packet loss, subtype 18, length 4  This is an IEEE
     754 format 32 bit floating point number representing the ratio of
     lost inbound packets to total inbound packets.

  Maximum inbound link bandwidth, subtype 19, length 4  This is an IEEE
     754 format 32 bit floating point number representing the inbound
     bandwidth of the interface in bytes per second.  If this subtype is
     not present the link is assumed to be symmetric and the value given
     in a type 9 subtype TLV is used as both the inbound and outbound
     bandwidth of the interface.



2.2  Flooding

  OSPF link state information is flooded in individual Link State At-
  tributes that may be independently flooded or packed for efficiency.
  IS--IS considers the entire link state database to be somewhat of an
  atomic entity expressed as the Link State Protocol Data Unit (LSPDU).
  The LSPDU can be flooded in up to 256 LSPDU fragments.  When a frag-
  ment is reflooded with a change, all link information in that fragment
  must be reflooded.  Link loading information which otherwise might not
  be flooded for some time will be updated.  This is expected to have
  minimal impact on the dynamics of the OMP algorithm.

  An algorithm for filtering raw counter values and determining when
  to flood is provided in [6] stated quite concisely in the appendices.
  The IS--IS algorithm differs only in that link loading may be flooded
  at times simply because the link resides in an LSPDU fragment that
  must be reflooded due to a loading change in another link.



2.3  Relaxing Best Path Criteria

  The IS--IS best path metric criteria can be relaxed just as the best
  path criteria is relaxed in OSPF--OMP. The same restrictions apply.
  In no circumstance should traffic toward an exit point with equal
  external cost or toward an internal destination be sent to an neigh-
  boring router where the path from that router has the same internal
  cost or greater internal cost.  This restriction is sufficient to
  avoid the possibility of routing loops.

  This restriction can be stated more precisely.  Consider the following
  example.  The best path from Router A to destination D has IS--IS path
  metric M_ad.  The best path from Router B to destination D has IS--IS
  path metric M_bd.  The link metric from Router A to Router B is M_ab.
  The path A to B to D is not an equal cost path if:





Villamizar, Li              Expires  August 22, 1999              [Page 4]


INTERNET-DRAFT    IS-IS Optimized Multipath (ISIS-OMP)    February 22, 1999

        M_ab + M_bd > M_ad



  Router A can relax the best path metric criteria is the following
  holds true:




        M_ad > M_bd


2.4  Level 2 Routing


  An implied assumption of the IS--IS protocol specification is that
  the Level 2 area has greater capacity and is less congested than the
  Level 1 only areas.  For this reason, Level 2 routers consider the ex-
  ternal metric before the internal metric and Level 1 routers consider
  the shortest path to any Level 2 router.  In practice the Level 2 area
  may not be less congested than Level 1 areas and these restrictions
  are relaxed.

  If consistency with the IS--IS model were maintain, path loading
  information can be passed from Level 1 into Level 2, but not from
  Level 2 into Level 1.  This information would supplement the ``IP In-
  ternal Reachability Information'' (type 128) TLV tuple.  Because the
  type 128 tuple contains fixed sized entries, a new tuple would have
  to be defined whose key is the IP address and subnet mask.  The tuple
  defined in Section 2.1 would be used for this purpose.

  The Level 2 routers may balance load across destinations with equal
  Level 1 metric but may not route toward a higher Level 1 metric.  To
  do so would cause a routing loop if any router in the path decided to
  prefer the lower Level 1 metric as is now specified by IS--IS.


2.5  Handling External Routes


  In IS--IS, as specified only Level 2 routers may carry external rout-
  ing information.  Level 1 routers are expected to route only to des-
  tinations in their own area or to the nearest Level 2 router.  The
  Level 2 routers have complete information and can route the packet
  toward the correct area or to a router advertising the external route.
  In practice this is rarely an issue and implementations allow this
  aspect of the specification to be violated.

  Generally ISIS is not used to carry exterior routing information.
  Instead, a separate exterior gateway protocol is used, specifically
  BGP--4 [5].  When BGP--4 is used to carry external routes within an AS

Villamizar, Li              Expires  August 22, 1999              [Page 5]


INTERNET-DRAFT    IS-IS Optimized Multipath (ISIS-OMP)    February 22, 1999

  (this is referred to as Internal BGP or IBGP), IS--IS is used strictly
  as an Interior Gateway Protocol (IGP). IBGP learned routes contain a
  NEXT_HOP attribute which contains an address that is reachable via the
  IGP but often not directly connected.  This is commonly referred to as
  a recursive route lookup.  When the IS--IS learned IGP route is used,
  the load balancing used to reach the IGP destination specified by the
  BGP NEXT_HOP is applied to the traffic routed toward that intermediate
  destination.

  Some relaxation of routing criteria is possible to improve load bal-
  ancing without creating route loops.  For IS--IS external routes the
  external metric is considered before the internal metrics.  This rule
  cannot be relaxed.  With BGP--4, the BGP LOCAL_PREF and other BGP at-
  tributes are considered first.  This rule cannot be relaxed.  Given
  otherwise equal external routes, the IGP cost to reach one or more
  equally preferred exit point is considered.  In this case the IGP
  cost is the IS--IS path metric.  The best IS--IS path criteria can be
  relaxed as described in Section 2.3.

  The path loading tuple defined in Section 2.4 could be used to pro-
  vide exterior loading information if exterior routes are injected into
  IS--IS, a strongly discouraged practice.  Carrying path loading infor-
  mation in an exterior routing protocol such as BGP--4 is outside the
  scope of this document.



Acknowledgments


  Numerous individual have provided valuable comments regarding this
  work.  Dave Ward made a very substantial contribution by pointing out
  that the best path criteria could be relaxed.  Dave Ward, John Scud-
  der, and Daniel Awduche have provided particularly valuable review and
  comments.


References


  [1]  R.W. Callon.  Use of osi is-is for routing in tcp/ip and dual en-
       vironments.  Technical Report RFC 1195, Internet Engineering Task
       Force, 1990. ftp://ftp.isi.edu/in-notes/rfc1195.txt.
  [2]  ISO/IEC.         Iso/iec 10589 - information processing systems -
       telecommunications and information exchange between systems -
       intermediate system to intermediate system intra-domain routing
       information exchange protocol for use in conjunction with the
       protocol for providing the connectionless-mode network service
       (iso 8473).      Technical report, International Organization for
       Standardization, 1992. ftp://merit.edu/pub/iso/iso10589.ps.gz.



Villamizar, Li              Expires  August 22, 1999              [Page 6]


INTERNET-DRAFT    IS-IS Optimized Multipath (ISIS-OMP)    February 22, 1999

  [3]  Tony Li and Henk Smit.           Is-is extensions for traffic en-
       gineering.          Internet Draft (Work in Progress) draft-ietf-
       isis-traffic-00, Internet Engineering Task Force, 2 1999.
       ftp://ftp.isi.edu/internet-drafts/draft-ietf-isis-traffic-00.txt.

  [4]  J. Moy. Ospf version 2. Technical Report RFC 2328, Internet Engi-
       neering Task Force, 1998. ftp://ftp.isi.edu/in-notes/rfc2328.txt.
  [5]  Y. Rekhter and T. Li. A border gateway protocol 4 (bgp-4).  Tech-
       nical Report RFC 1771, Internet Engineering Task Force, 1995.
       ftp://ftp.isi.edu/in-notes/rfc1771.txt.

  [6]  Curtis Villamizar.  Ospf optimized multipath (ospf-omp).   Inter-
       net Draft (Work in Progress) draft-ietf-ospf-omp-01, Internet
       Engineering Task Force, 10 1998.      ftp://ftp.isi.edu/internet-
       drafts/draft-ietf-ospf-omp-01.txt.


Security Considerations


  In deployments which use a strong IS--IS authentication method, and
  require signatures on LSP fragments from the originating router, no
  leveraging of a partial compromise beyond a localized disruption of
  service is possible.  In deployments which use a strong IS--IS authen-
  tication method, but do not require signatures on LSP fragments from
  the originating router, compromise of a single router can be lever-
  aged to cause significant disruption of service with or without the
  use of these TLV tuples, but disruption of service cannot be achieved
  without such a compromise.  In deployments which use a weak IS--IS
  authentication method, significant disruption of service can be caused
  through forged protocol interactions with or without the use of these
  TLV tuples.



Author's Addresses


  Curtis Villamizar            Tony Li
  ANS                          Juniper Networks
  <curtis@ans.net>             <tli@juniper.net>



A  Configuration Options


  Many of the capabilities must be configurable.  The ability to enable
  and disable capability subsets is needed.  Many parameters used by the
  algorithm should also be configurable.  Please refer to [6] for pa-
  rameter settings.  ISIS--OMP differs from OSPF--OMP in the capability
  subsets.

Villamizar, Li              Expires  August 22, 1999              [Page 7]


INTERNET-DRAFT    IS-IS Optimized Multipath (ISIS-OMP)    February 22, 1999

A.1  Capability Subsets


  There should at least be the ability to enabled and disabled the fol-
  lowing.



      default description of capability
        ON   Flooding any loading information
        ON   Flooding loading information for specific links
        -    Relaxing best path criteria
        -    Adjusting traffic shares (default to even split)
        OFF  Flooding loading information into IS-IS Level 2
        OFF  Flooding loading information for specific IS-
  IS Level 1 routes
        OFF  Flooding loading information for external routes
        OFF  Flooding loading information for specific external routes
        OFF  Considering loading information for IS-IS Level 2
        OFF  Considering loading information for specific IS-
  IS Level 1 routes
        OFF  Considering loading information for external routes
        OFF  Considering loading information for specific exter-
  nal routes



  Flooding and considering Level 1 routes loading information into
  Level 2 and flooding external route loading information should be
  disabled by default.  Flooding loading information should be enabled
  by default.  Relaxing best path criteria and adjusting traffic shares
  could be enabled or disabled by default, depending on vendor prefer-
  ence.




















Villamizar, Li              Expires  August 22, 1999              [Page 8]