Annex C
Dijkstra Calculation and Forwarding

   Annex C.2 of ISO DP 10589 [1] specifies the SPF (Dikskstra) algorithm
   for calculating routes with the IS-IS routing protocol. This annex
   specifies modifications to the SPF algorithm for supporting IP and
   dual routing, and specifies a compatible method for forwarding IP
   packets. This will result in an order of preference of routes which
   is compatible with that specified in section 3.10.

   This annex is included for informational purposes.

C.1 SPF Algorithm for IP and Dual Use

   This section specifies an SPF Algorithm for calculating routes with
   the IS-IS routing protocol, for support of both TCP/IP and OSI. This
   is based on an extention to the algorithm specified in annex C.2 of
   ISO DP 10589 [1].

   An algorithm invented by Dijkstra known as shortest path first (SPF)
   is used as the basis for the route calculation. It has a
   computational complexity of the square of the number of nodes, which
   can be decreased to the number of links in the domain times the log
   of the number of nodes for sparse networks (networks which are not
   highly connected).

   A number of additional optimizations are possible:

   1) If the routing metric is defined over a small finite field (as in
      this standard), the factor of log n may be removed by using data
      structures which maintain a separate list of systems for each value
      of the metric rather than sorting the systems by logical distance.

   2) Updates can be performed incrementally without requiring a complete
      recalculation. However, a full update must be done periodically to
      ensure recovery from data corruption, and studies suggest that with
      a very small number of link changes (perhaps 2) the expected
      computation complexity of the incremental update exceeds the
      complete recalculation. Thus, this annex specifies the algorithm
      only for the full update.

   3) If only End System LSP information has changed, it is not necessary
      to re-compute the entire Dijkstra tree. If the proper data
      structures are used, End Systems (including IP reachability
      entries) may be attached and detached as leaves of the tree and
      their forwarding information base entries altered as appropriate.

   The original SPF algorithm does not support load splitting over

   multiple paths. The algorithm in this annex does permit load
   splitting by identifying a set of equal cost paths to each
   destination rather than a single least cost path.

C.1.1 Databases

  PATHS -- This represents an acyclic directed graph of shortest paths
  from the system S performing the calculation. It is stored as a set
  of triples of the form <N,d(N),{Adj(N)}>, where:

      N is a system identifier. In the level 1 algorithm, N is a
      6 octet ID for OSI end systems, a 7 octet ID for routers, or
      an 8 octet IP Internal Reachability Information entry. For a
      router which is not a pseudonode, it is the 6 octet system ID,
      with a 0 appended octet. For a pseudonode it is a true 7 octet
      quantity, comprised of the 6 octet Designated Intermediate
      System ID and the extra octet assigned by the Destinated Router.
      The IP Internal Reachability Information entries consist of a
      4 octet IP address plus a 4 octet subnet mask, and will always
      be a leaf, i.e., "End System" in PATHS.

      In the level 2 algorithm, N is either a 7 octet router or
      pseudonode ID (as in the level 1 algorithm); a variable
      length OSI address prefix; an 8 octet IP Internal Reachability
      Information Entry, or an 8 octet IP External Reachability
      Information entry. The variable length OSI address prefixes,
      and 8 octet IP Reachability Information entries will always
      be a leaf, i.e., "End System" in PATHS. As above, the IP
      Reachability Information entries consist of an [IP address,
      subnet mask] combination.

      d(N) is N's distance from S (i.e., the total metric value
      from N to S).

      {Adj(N)} is a set of valid adjacencies that S may use for
      forwarding to N.

   When a system is placed on PATHS, the path(s) designated by its
   position in the graph is guaranteed to be a shortest path.

  TENT -- This is a list of triples of the form <N,d(N),{Adj(N)}>,
  where N, d(N), and {Adj(N)} are as defined above for PATHS.

  TENT can intuitively be thought of as a tentative placement
  of a system in PATHS. In other words, the triple <N,x,{A}>
  in TENT means that if N were placed in PATHS, d(N) would be x,
  but N cannot be placed on PATHS until is is guaranteed that
  no path shorter than x exists.

  Similarly, the triple <N,x,{A,B}> in TENT means that if N
  were placed in PATHS, then d(N) would be x via either
  adjacency A or B.

   Note: It is suggested that the implementation maintain the database
   TENT as a set of list of triples of the form <*,Dist,*>, sorted by
   distance Dist. In addition, it is necessary to be able to process
   those systems which are pseudonodes before any non-pseudonodes at the
   same distance Dist.

   The 8 octet system identifiers which specify IP reachability entries
   must always be distinguishable from other system identifiers. As
   specified in section 3.10, two IP reachability entries which differ
   only in the subnet mask are still considered to be separate, and will
   therefore have distinct system identifiers N. The SPF algorithm will
   therefore calculate routes to each such entry, and the correct entry
   will be selected in the forwarding process.

C.1.2 Use of Metrics in the SPF Algorithm

   Internal metrics are not comparable to external metrics. For external
   routes (routes to destinations outside of the routing domain), the
   cost d(N) of the path from N to S may include both internal and
   external metrics. d(N) may therefore be maintained as a two-
   dimensioned vector quantity (specifying internal and external metric
   values).

   d(N) is initialized to [internal metric = 0, external metric = 0].

   In incrementing d(N) by 1, if the internal metric value is less than
   the maximum value MaxPathMetric, then the internal metric value is
   incremented by one and the external metric value left unchanged; if
   the internal metric value is equal to the maximum value
   MaxPathMetric, then the internal metric value is set to 0 and the
   external metric value is incremented by 1. Note that this can be
   implemented in a straightforward manner by maintaining the external
   metric as the high order bits of the distance.

   In the code of the algorithm below, the current path length is held
   in the variable "tentlength". This variable is a two-dimensional
   quantity tentlength=[internal metric, external metric], and is used
   for comparing the current path length with d(N) as described above.
   Tentlength is incremented in the same manner as d(N).

C.1.3 Overview of the Algorithm

   The basic algorithm, which builds PATHS from scratch, starts out by
   putting the system doing the computation on PATHS (no shorter path to

   SELF can possibly exist). TENT is then pre-loaded from the local
   adjacency database.

   Note that a system is not placed on PATHS unless no shorter path to
   that system exists. When a system N is placed on PATHS, the path to
   each neighbor M of N, through N, is examined, as the path to N plus
   the link from N to M. If <M,*,*> is in PATHS, this new path will be
   longer, and thus ignored.

   If <M,*,*> is in TENT, and the new path is shorter, the old entry is
   removed from TENT and the new path is placed in TENT. If the new path
   is the same length as the one in TENT, then the set of potential
   adjacencies {Adj(M)} is set to the union of the old set (in TENT) and
   the new set {Adj(N)}. If M is not in TENT, then the path is added to
   TENT.

   Next the algorithm finds the triple <N,x,{Adj(N)}> in TENT, with
   minimal x. Note: This is done efficiently because of the optimization
   described above. When the list of triples for distance Dist is
   exhausted, the algorithm then increments Dist until it finds a list
   with a triple of the form <*,Dist,*>.

   N is placed in PATHS. We know that no path to N can be shorter than x
   at this point because all paths through systems already in PATHS have
   already been considered, and paths through systems in TENT still have
   to be greater than x because x is minimal in TENT.

   When TENT is empty, PATHS is complete.

   Note that external metrics can only occur in "IP External
   Reachability Information" entries, which correspond to a leaf (i.e.,
   End System in PATHS). Any route utilizing an entry with an external
   metric will always be considered to be less desireable than any entry
   which uses an internal metric. This implies that in the addition of
   systems to PATHS, all systems reachable via internal routes are
   always added before any system reachable via external routes.

C.1.4 The Algorithm

   The Decision Process Algorithm must be run once for each supported
   routing metric (i.e., for each supported Type of Service). A level 1
   router runs the algorithm using the level 1 LSP database to compute
   level 1 paths (for those level 1 routers which are not level 2
   routers, this includes the path to the nearest attached level 2
   router). Level 2 routers also separately run the algorithm using the
   level 2 LSP database to compute level 2 paths. IP-capable level 2
   routers must keep level 2 internal IP routes separate from level 2
   external IP routes.

   Note that this implies that routers which are both level 1 and level
   2 routers, and which support all four routing metrics, must run the
   SPF algorithm 8 times (assuming partition repair is not implemented).

   If this system is a Level 2 Router which supports the partition
   repair optional function the Decision Process algorithm for computing
   Level 1 paths must be run twice for the default metric. This first
   execution is done to determine which of the area's
   manualAreaAddresses are reachable in this partition, and to elect a
   Partition Designated Level 2 Router for the partition. The partition
   Designated Level 2 Router will determine if the area is partitioned
   and will create virtual Level 1 links to the other Partition
   Designated Level 2 Routers in the area in order to repair the Level 1
   partition. This is further described in section 7.2.10 of [1].

   The SPF algorithm specified here will calculate routes for both OSI
   and IP. In particular, routes are calculated to all system
   identifiers N, where N may specify an OSI End System, the OSI address
   of a router, or an IP reachability entry. In computing the forwarding
   database, it is an implementation specific issue whether the IP
   forwarding database is kept separately from the OSI forwarding
   database. Where appropriate, this annex will refer separately to
   entries in these two forwarding data bases. This is not meant to
   preclude any specific implementation method.

   OSI and IP use separate mechanisms to determine whether a packet is
   in the area (in particular, OSI makes use of area addresses, and IP
   determines that a destination is not in an area by looking in the
   level 1 forwarding database and determining that no entry exists for
   that destination within the area). The route to the nearest level 2
   router will result in separate entries in the forwarding database for
   OSI and IP. For IP, the route to the nearest attached level 2 router
   may be entered in the forwarding database as a default route (i.e., a
   route with a subnet mask of all 0).

   One approach would be to put the results of each Dijkstra algorithm
   in a separate forwarding database. For a router which supports both
   level 1 and level 2 routing (including level 2 internal and level 2
   external routes), and which supports all four types of service, this
   would result in twelve separate forwarding databases for IP.
   Implementations may choose to minimize the number of forwarding
   databases by combining the information from the multiple Dijkstra
   calculations into a single database per supported TOS. This is
   discussed in section C.2 below.

   The SPF algorithm specified in section C.2.3 of [1] is amended to
   appear as follows:

   Step 0: Initialize TENT and PATHS to empty. Initialize tentlength to
   [internalmetric=0, externalmetric=0].

   (tentlength is the pathlength of elements in TENT that we are
   examining.)

   1) Add <SELF,0,W> to PATHS, where W is a special value indicating
      traffic to SELF is passed up to internal processes (rather than
      forwarded).

   2) Now pre-load TENT with the local adjacency database (Each
      entry made to TENT must be marked as being either an End System
      or a router to enable the check at the end of Step 2 to be made
      correctly - Note that each local IP reachability entry is
      included as an adjacency, and is marked as being an End System).
      For each adjacency Adj(N) (including level 1 OSI Manual
      Adjacencies, or level 2 OSI enabled reachable addresses, and
      IP reachability entries) on enabled circuits, to system N of
      SELF in state "Up" compute:

         d(N) = cost of the parent circuit of the adjacency (N),
         obtained from metric.k , where k = one of {default metric,
         delay metric, monetary metric, error metric}

         Adj(N) = the adjacency number of the adjacency to N

   3) If a triple <N,x,{Adj(M)}> is in TENT, then:

         If x = d(N), then {Adj(M)} <--- {Adj(M)} U {Adj(N)}.

   4) If N is a router or an OSI End System entry, and there are now
      more adjacencies in {Adj(M)} than maximumPathSplits, then remove
      excess adjacencies as described in Clause 7.2.7 of [1]. If N
      is an IP Reachability Entry, then excess adjacencies may be
      removed as desired. This will not effect the correctness of
      routing, but may eliminate the determinism for IP routes (i.e.,
      IP packets still follow optimal routes within an area, but
      where multiple equally good routes exist, will not necessarily
      follow precisely the route that any one particular router
      would have anticipated).

   5) If x < d(N), do nothing.

   6) If x > d(N), remove <N,x,{Adj(M)}> from TENT and add the triple
      <N,d(N),{Adj(N)}>.

   7) If no triple <N,x,{Adj(M)}> is in TENT, then add <N,d(N),{Adj(N)}>
      to TENT.

   8) Now add systems to which the local router does not have adjacencies,
      but which are mentioned in neighboring pseudonode LSPs. The
      adjacency for such systems is set to that of the designated router.
      Note that this does not include IP reachability entries from
      neighboring pseudonode LSPs. In particular, the pseudonode LSPs
      do not include IP reachability entries.

   9) For all broadcast circuits in state "On", find the pseudonode
      LSP for that circuit (specifically, the LSP with number zero and
      with the first 7 octets of LSPID equal to LnCircuitID for that
      circuit, where n is 1 (for level 1 routing) or 2 (level 2
      routing)). If it is present, for all the neighbors N reported in
      all the LSPs of this pseudonode which do not exist in TENT add
      an entry <N,d(N),{Adj(N)}> to TENT, where:

         d(N) = metric.k  of the circuit.
         Adj(N) = the adjacency number of the adjacency to the DR.

   10) Go to Step 2.

   Step 1: Examine the zeroeth link state PDU of P, the system just
   placed on PATHS (i.e., the LSP with the same first 7 octets of LSPID
   as P, and LSP number zero).

   1) If this LSP is present, and the "Infinite Hippity Cost" bit is
      clear, then for each LSP of P (i.e., all LSPs with the same
      first 7 octets of LSPID and P, irrespective of the value of
      LSP number) compute:

         dist(P,N) = d(P) + metric.k(P,N)

   for each neighbor N (both End System and router) of the system P. If
   the "Infinite Hippity Cost" bit is set, only consider the End System
   neighbors of the system P. Note that the End Systems neighbors of the
   system P includes IP reachable address entries included in the LSPs
   from system P. Here, d(P) is the second element of the triple

         <P,d(P),{Adj(P)}>

   and metric.k(P,N) is the cost of the link from P to N as reported in
   P's link state PDU.

   2) If dist(P,N) > MaxPathMetric, then do nothing.

   3) If <N,d(N),{Adj(N)}> is in PATHS, then do nothing.

         Note: d(N) must be less than dist(P,N), or else N would not
         have been put into PATHS. An additional sanity check may be

         done here to ensure that d(N) is in fact less than dist(P,N)

   4) If a triple <N,x,{Adj(N)}> is in TENT, then:

     a) If x = dist(P,N), then {Adj(N)} <-- {Adj(N)} U {Adj(P)}.

     b) If N is a router or an OSI end system, and there are now more
        adjacencies in {Adj(N)} than maximumPath Splits, then remove
        excess adjacencies, as described in clause 7.2.7 of [1]. For
        IP Reachability Entries, excess adjacencies may be removed as
        desired. This will not effect the correctness of routing, but
        may eliminate the determinism for IP routes (i.e., IP packets
        will still follow optimal routes within an area, but where
        multiple equally good routes exist, will not necessarily follow
        precisely the route that any one particular router would have
        anticipated).

     c) if x < dist(P,N), do nothing.

     d) if x > dist(P,N), remove <N,x,{Adj(N)}> from TENT, and add
        <N,dist(P,N),{Adj(P)}>

   5) if no triple <N,x,{Adj(N)}> is in TENT, then add
      <N,dist(P,N),{Adj(P)}> to TENT.

   Step 2: If TENT is empty, stop. Else:

   1) Find the element <P,x,{Adj(P)}>, with minimal x as follows:

     a) If an element <*,tentlength,*> remains in TENT in the list for
        tentlength, choose that element. If there are more than one
        elements in the list for tentlength, choose one of the elements
        (if any) for a system which is a pseudonode in preference to one
        for a non-pseudonode. If there are no more elements in the list
        for tentlength, increment tentlength and repeat Step 2.

     b) Remove <P,tentlength,{Adj(P)}> from TENT.

     c) Add <P,d(P),{Adj(P)}> to PATHS.

     d) If this is the Level 2 Decision Process running, and the system
        just added to PATHS listed itself as Partition Designated Level 2
        Intermediate system, then additionally add <AREA.P,d(P),{Adj(P)}>
        to PATHS, where AREA.P is the Network Entity Title of the other
        end of the Virtual Link, obtained by taking the first AREA
        listed in P's LSP and appending P's ID.

     e) If the system just added to PATHS was an end system, go to

        step 2. Else go to Step 1.

   NOTE - In the level 2 context, the "End Systems" are the set of
   Reachable Address Prefixes (for OSI), the set of Area Addresses with
   zero cost (again, for OSI), plus the set of IP reachability entries
   (including both internal and external).

C.2 Forwarding of IP packets

   The SPF algorithm specified in section C.1 may be used to calculate
   (logically) separate IP forwarding tables for each type of service,
   and for level 1, level 2 internal, and level 2 external routes.
   Section C.2.1 describes how to forward IP packets, based on these
   multiple forwarding databases. Section C.2.2 describes how the
   multiple forwarding databases can be combined into a single
   forwarding database per supported TOS.

C.2.1 Basic Method for Forwarding IP packets

   For level 1-only routers:

   - Determine if the IP destination address matches any entry in the
     level 1 forwarding table for the specified TOS.

   - Determine if the IP destination address matches any entry in the
     level 1 forwarding table for the default TOS.

   - If default TOS resulted in more specific entry, forward according
     to default TOS.

   - If equally specific entries found, or specified TOS resulted in
     more specific entry, forward according to specified TOS

   - If no entry was found (which includes no default route entry), then
     destination is unreachable.

   Note: For level 1 only routers, the route to the nearest attached
   level 2 router will be entered into the forwarding database as a
   default route (i.e., a route with a subnet mask which is all 0). Thus
   this last event (no entry found) can occur only if there is no
   attached level 2 router reachable in the area.

   For routers which are both level 1 and level 2 routers:

   - Determine if the IP destination address matches any entry in the
     level 1 forwarding table for the specified TOS.

   - Determine if the IP destination address matches any entry in the

     level 1 forwarding table for the default TOS.

   - If default TOS resulted in more specific entry (i.e., more bits in
     the subnet mask take the value 1), forward according to default TOS.

   - If equally specific entries found, or specified TOS resulted in
     more specific entry, forward according to specified TOS

   - If no entry found:

   - Determine if the IP destination address matches any entry in the
     level 2 internal forwarding table for the specified TOS.

   - Determine if the IP destination address matches any entry in the
     level 2 internal forwarding table for the default TOS.

   - If default TOS resulted in more specific entry, forward according
     to default TOS.

   - If equally specific entries found, or specified TOS resulted in
     more specific entry, forward according to specified TOS

   - If no entry found:

   - Determine if the IP destination address matches any entry in the
     level 2 external forwarding table for the specified TOS.

   - Determine if the IP destination address matches any entry in the
     level 2 external forwarding table for the default TOS.

   - If default TOS resulted in more specific entry, forward according
     to default TOS.

   - If equally specific entries found, or specified TOS resulted in
     more specific entry, forward according to specified TOS

   - If no entry is found, then destination is unreachable

   For level 2-only routers, the above algorithm can be used, except
   since there is no level 1 forwarding database, the corresponding
   steps can be skipped.

   As discussed in section 3.10.2, for level 2 routers which are
   announcing manually configured summary addresses in their level 2
   LSPs, in some cases there will exist IP addresses which match the
   manually configured addresses, but which do not match any addresses
   which are reachable via level 1 routing in the area. Packets to such
   addresses are handled according to the rules specified in section

   3.10.2. This may be accomplished by adding the manually configured
   [IP address, subnet mask] entry to the level 2 forwarding database
   (for the appropriate TOS), with a special "next hop" address which
   specifies that packets for which this entry is selected are to be
   discarded. This will work correctly because more desireable entries
   (such as delivering the packet via level 1 routing to the correct
   destination, or a more specific level 2 route) will automatically
   take precedence according to the forwarding rules specified above.
   Less desireable routes (such as using a level 2 external route to the
   "default route" entry) are not possible because other level 2 routers
   will believe the summary addresses advertised by this router.

C.2.2 Reduction of IP Forwarding Databases

   The multiple forwarding databases used in the basic forwarding method
   in section C.2.1 can be reduced, by combining the multiple databases
   into one database for each supported TOS.

   For reduction of IP forwarding databases, it is assumed that for any
   two overlapping address entries, either the entries are identical, or
   one range contains the other. In other words, for any two [IP
   address, subnet mask] entries A and B, if there is at least one IP
   address which matches both entries, then either: (i) the two entries
   are identical; or (ii) entry A contains entry B (i.e., any IP address
   which matches entry B also matches entry A); or (iii) entry B
   contains entry A (any IP address which matches entry A also matches
   entry B).

   Non-contiguous subnet masks can be configured to violate this
   assumption. For example, consider the two entries:

   - A=[address="01010101 00000101 00000000 00000000",
     mask="11111111 00001111 00000000 00000000"]

   - B=[address="01010101 01010000 00000000 00000000",
     mask="11111111 11110000 00000000 00000000"]

   In this case neither entry contains the other. Specifically;

   - there are IP addresses which match both A and B (e.g.,
     "01010101 01010101 xxxxxxxx xxxxxxxx"),

   - there are IP addresses which match A but not B (e.g.,
     "01010101 11110101 xxxxxxxx xxxxxxxx")

   - there are IP addresses which match B but not A (e.g.,
     "01010101 01011111 xxxxxxxx xxxxxxxx").

   The reduction of the multiple forwarding databases for each TOS to a
   single database for each TOS is based on the use of "best match"
   routing, combined with reduction of the entries placed in the
   forwarding database in order to eliminate entries which are not to be
   selected (based on the order of preference of routes specified in
   section 3.10). The specific algorithm for creation of the IP
   forwarding database can be described as follows:

   1) Make use of the the Dijkstra algorithm described in section C.1 to
      create separate forwarding databases for each supported TOS for
      level 1 routes, level 2 internal routes, and level 2 external
      routes. (Note that each entry in the forwarding database will
      specify an [IP address, subnet mask] combination, as well as the
      next hop router for IP packets which match that entry).

   2) For each level 1 route entry which has been placed in the level 1
      IP forwarding database for a specific TOS, copy that entry into
      the overall IP forwarding database for that TOS.

   3) For each route entry X which has been placed in the level 2 internal
      IP forwarding database for a specific TOS, search for overlapping
      entries in the level 1 IP forwarding database for the specific TOS,
      and also for the default TOS:

      a) If there is any overlapping entry Y in the level 1 forwarding
         database (for the specfic TOS, or for the default TOS) such
         that either (i) Y contains X; or (ii) Y is identically specific
         to X; then ignore entry X.

      b) Otherwise, copy entry X into the overall IP forwarding database
         for the specific TOS.

   4) For each route entry X which has been placed in the level 2
      external IP forwarding database for a specific TOS, search for
      overlapping entries in the level 1 IP forwarding database for
      the specific TOS, and for the default TOS, and the level 2
      internal IP forwarding database for the specific TOS, and for
      the default TOS.

      a) If there is an overlapping entry Y such that either (i) Y
         contains X; or (ii) Y is identically specific to X; then
         ignore entry X.

      b) Otherwise, copy entry X into the overall IP forwarding database
         for the specific TOS.

   This method will result in one forwarding database for each supported
   TOS. The forwarding of packets can then be simplified to be as follows:

   1) For IP packets which map to the default TOS metric (or to an
      unsupported TOS metric), search the default TOS forwarding
      database and select the entry which has the most specific match.
      Forward the packet accordingly.

   2) For packets which map to a specific (non-default) TOS metric,
      search the specific TOS forwarding database and select the entry
      j which has the most specific match. Also search the default TOS
      forwarding database and select the entry k which has the most
      specific match. Forward the packet as follows:

      a) If k is more specific than j, forward according to entry k

      b) If j and k are equally specific, forward according to entry j

      c) If j is more specific than k, forward according to entry j

Annex D
Use of the Authentication Field

   The use of the Authentication field is outside of the scope of this
   specification. However, there is a urgent need for simple error
   detection/authentication mechanisms (such as a simple password) to
   protect against certain types of errors. This annex therefore
   proposes a possible use of this field.

   This annex is included for informational purposes.

D.1 Authentication Field in IS-IS packets

   All IS-IS packets may optionally include the authentication field, as
   described in sections 3.9 and 5 of this specification. As described
   in section 5, the authentication field is encoded as a (Code, Length,
   Value) triplet. This annex proposes that the contents of the Value
   field consist of a one octet "Authentication Type" field, plus a
   variable length "Authentication Information" field. A specific value
   of the "Authentication Type" is assigned to passwords, transmitted in
   the clear without encryption. The authentication field is encoded as
   follows:

  7 Authentication Information -- Information used to authenticate
    the PDU

    x CODE - 133

    x LENGTH - total length of the value field

    x VALUE -
                                              No. of Octets
          +--------------------------------+
          |      Authentication Type       |      1
          +--------------------------------+
          |   Authentication Information   |      VARIABLE
          +--------------------------------+

The Authentication Type is assigned as follows:

      Type  =  0        reserved

      Type  =  1        simple password

      Type  >  1        reserved

D.2 Authentication Type 1 - Simple Password

   Using this authentication type, a variable length password is passed
   in the clear (i.e., not encrypted) in the Authentication Information
   field.

   WARNING: The use of a simple password does not provide useful
   protection against intentional misbehavior. In particular, since the
   password is transmitted in the clear without encryption, it is easy
   for a hostile system to intercept the passwords, and to transmit
   authenticated packets. The use of simple passwords should be
   considered only as a weak protection against accidental errors such
   as accidental misconfiguration.

   The password shall be configured on a per-link, per-area, and per-
   domain basis. Specifically, when this form of authentication is used:

   - IS-IS Hello and 9542 IS Hello packets shall contain the
     per-link password

   - Level 1 Link State Packets shall contain the per-area password

   - Level 2 Link State Packets shall contain the per-domain password

   - Level 1 Sequence Number Packets shall contain the per-area password

   - Level 2 Sequence Number Packets shall contain the per-domain
     password

   Also, each of these three passwords shall be configured with: (i)
   "Transmit Password", whose value is a single password, and (ii)
   "Receive Passwords", whose value is a set of passwords. The transmit
   password value is always transmitted. However, any password contained
   in the receive password set will be accepted on receipt. This method
   allows the graceful changing of passwords without temporary loss of
   connectivity.

   For example, consider the case that an area has the configured area
   password "OLDAREAPASSWORD". In this case, the per-area transmit
   password value is set to OLDAREAPASSWORD, and the per-area receive
   password value is set to {OLDAREAPASSWORD}. Suppose that it is
   desired to change the per-area password to "NEWERPASSWORD".  The
   first step would be to manually configure all of the routers in the
   area to set the per-area receive password value to {OLDAREAPASSWORD,
   NEWERPASSWORD}. When this step is complete, then all routers in the
   area will still be using the old password OLDAREAPASSWORD in their
   level 1 LSPs and SNPs. However, they will also accept the alternate
   password NEWERPASSWORD. The second step would be to configure the

   routers in the area to set the per-area transmit password to
   NEWERPASSWORD. When the second step is complete, then all routers
   will be using the new value of the per-area password, but will accept
   the old value as well. Finally, the third step is to change all
   routers in the area to have the per-area receive password set to
   {NEWERPASSWORD}.

   By configuring transmit and receive values for the passwords in this
   manner, it is possible to maintain continuous correct operation. For
   example, in the middle of the second step in the above example, some
   of the routers in the area will be transmitting level 1 LSPs and SNPs
   using the old password OLDAREAPASSWORD, and some will be transmitting
   level 1 LSPs and SNPs using the new password NEWERPASSWORD. However,
   during the second step of the transition all routers in the area will
   accept level 1 LSPs and SNPs using either password.

Annex E
Interaction of the Integrated IS-IS with Brouters

   A "brouter" is a device which operates an both a bridge and a router.
   One possible type of brouter acts as a router for IP traffic, and
   acts as a bridge for all other types of traffic.

   Depending upon the manner in which a brouter is implemented, and
   depending upon the network topology, there is an obscure bug which
   can result from the interaction of the Integrated IS-IS protocol, and
   brouters. This appendix gives an example of the bug, and proposes a
   simple correction to the operation of brouters to correct the
   problem.

   This annex is included for informational purposes.

E.1 The Problem

   Suppose that we have a brouter which treats IP packets as if it were
   a normal IP router, and which treats all other packets as if it is a
   bridge.

   Suppose that two routers "X" and "Y" (which implement the integrated
   IS-IS protocol), two Ethernets, and a brouter B are all connected as
   follows:


                     |                               |
                +----+---+                      +----+---+
                | Router |                      | Router |
                |   X    |                      |   Y    |
                +----+---+                      +----+---+
                     |                               |
                -----+------------+-   -+------------+----
                                  |     |
                                +-+-----+-+
                                | Brouter |
                                |    B    |
                                +---------+


   Here suppose that X and Y are running the Integrated IS-IS protocol,
   and are both level 1 routers in the same area. Thus X and Y send IS-
   IS Hello packets on the LAN. These Hello packets are received and
   forwarded by the brouter (using normal bridge functions). Similarly,
   X and Y receive each other's IS-IS LSP packets. In this way, it
   appears to the Brouter that X and Y are exchanging OSI packets, and
   so they are forwarded using normal bridge functions. It appears to X

   and Y as if they are on the same LAN, and so they learn each others
   48-bit Ethernet addresses and exchange routing information.

   Now, suppose that X receives an IP packet, which it needs to forward
   via Y. Since X thinks that it and Y are on the same Ethernet, it just
   forwards the IP packet directly, using normal Ethernet encapsulation
   and using the 48-bit Ethernet address of Y as the destination address
   in the Ethernet header. Brouter B, when thinking as a bridge says:
   "this is an IP packet, I don't forward this as a bridge". Brouter B,
   when thinking like an IP router says: "this is an IP packet, I know
   how to forward IP packets. However, this is sent to an Ethernet
   address which is not me, thus I will ignore it". The result is that
   the IP packet does not get forwarded.

   This problem relates directly to the fact that X and Y are exchanging
   OSI packets to determine the connectivity of the path between them,
   but then are trying to send IP packets over the path. Also, there is
   a device between X and Y on the path which treats OSI and IP packets
   differently.

   Also note that this problem can also occur in more complex
   topologies, whenever a brouter is treating OSI and IP packets in a
   fundamentally different manner.

E.2 Possible Solutions

E.2.1 More Sophisticated Brouter

   One solution is that brouter B needs to be a little more
   sophisticated. In particular, it needs to use the following rules:

   - For packets which are not IP packets, act as a bridge (this is the
     same as before).

   - For IP packets sent to an Ethernet broadcast or multicast address,
     act as an IP router (this is also the same as before).

   - For IP packets sent to my own Ethernet 48-bit address(es), act as
     an IP router (this is also the same as before).

   - For IP packets sent to a single station 48-bit address which is not
     one of my addresses, act at a bridge (THIS IS NEW).

   With this change, the IP packet transmitted from X to Y is forwarded
   by the brouter, acting as a bridge. This allows the Brouter and the
   multiprotocol routers to interoperate properly.

E.2.2 Dual Router / Brouter

   An alternate solution would be for the Brouter to route both OSI and
   IP equally. If the Brouter used the integrated IS-IS for this
   purpose, then it could be part of the same routing domain and
   interoperate like any other dual router (except for the ability to
   bridge other protocol suites).  If it used other protocols for
   routing OSI and IP, then it would need to be part of another routing
   domain, and could interoperate with integrated IS-IS routers like any
   other external router.