ERROR METRIC is the value of the error metric for the link to the
listed neighbor. If this IS does not support this metric it shall
set the bit "S" to 1 to indicate that the metric is unsupported.
Bit 7 of this field is reserved, and must be set to zero on
transmission and ignored on reception.
IP ADDRESS is a 4-octet Internet address
SUBNET MASK is a 4 octet IP subnet mask.
7 IP External Reachability Information -- IP addresses outside the
routing domain reachable via interfaces on this Intermediate
system.
This is permitted to appear multiple times, and in an LSP with
any LSP number. However, this field must not appear in pseudonode LSPs.
x CODE - 130.
x LENGTH - a multiple of 12.
x VALUE -
No. of Octets
+----------------------------+
| 0 |I/E| DEFAULT METRIC | 1
+----------------------------+
| S | R | DELAY METRIC | 1
+----------------------------+
| S | R | EXPENSE METRIC | 1
+----------------------------+
| S | R | ERROR METRIC | 1
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
| SUBNET MASK | 4
+----------------------------+
: :
: :
+----------------------------+
| 0 |I/E| DEFAULT METRIC | 1
+----------------------------+
| S | R | DELAY METRIC | 1
+----------------------------+
| S | R | EXPENSE METRIC | 1
+----------------------------+
| S | R | ERROR METRIC | 1
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
| SUBNET MASK | 4
+----------------------------+
DEFAULT METRIC is the value of the default metric for the
path to the listed IP addresses. Bit 8 of this field is
reserved, and must be set to zero on transmission and ignored
on reception. Bit 7 of this field indicates the metric type
(internal or external) for all four TOS metrics, and may be
set to zero indicating internal metrics, or may be set to 1
indicating external metrics.
DELAY METRIC is the value of the delay metric for the path
to the listed IP addresses. If this IS does not support this
metric it shall set the bit "S" to 1 to indicate that the metric
is unsupported. Bit 7 of this field is reserved, and must be
set to zero on transmission and ignored on reception.
EXPENSE METRIC is the value of the expense metric for the link
to the listed IP addresses. If this IS does not support this
metric it shall set the bit "S" to 1 to indicate that the metric
is unsupported. Bit 7 of this field is reserved, and must be
set to zero on transmission and ignored on reception.
ERROR METRIC is the value of the error metric for the link to
the listed IP addresses. If this IS does not support this metric
it shall set the bit "S" to 1 to indicate that the metric is
unsupported. Bit 7 of this field is reserved, and must be set to
zero on transmission and ignored on reception.
IP ADDRESS is a 4-octet Internet address
SUBNET MASK is a 4 octet IP subnet mask
7 Inter-Domain Routing Protocol Information -- Inter-domain routing
protocol information carried transparently through level 2 for
the convenience of any Inter-Domain protocol that may be running
in the boundary ISs.
This is permitted to appear multiple times, and in an LSP with
any LSP number.
x CODE - 131.
x LENGTH - total length of the value field
x VALUE -
No. of Octets
+-------------------------------+
| Inter-Domain Information Type | 1
+-------------------------------+
| External Information | VARIABLE
+-------------------------------+
INTER-DOMAIN INFORMATION TYPE indicates the type of the
external information which is encoded in the field.
EXTERNAL INFORMATION contains inter-domain routing protocol
information, and is passed transparently by the IS-IS protocol.
5.3.6 Level 1 Complete Sequence Numbers PDU
- Additional codes for IP support are:
7 Authentication Information -- Information used to authenticate
the PDU
x CODE - 133
x LENGTH - total length of the value field
x VALUE - TBD
5.3.7 Level 2 Complete Sequence Numbers PDU
- Additional codes for IP support are:
7 Authentication Information -- Information used to authenticate
the PDU
x CODE - 133
x LENGTH - total length of the value field
x VALUE - TBD
5.3.8 Level 1 Partial Sequence Numbers PDU
- Additional codes for IP support are:
7 Authentication Information -- Information used to authenticate
the PDU
x CODE - 133
x LENGTH - total length of the value field
x VALUE - TBD
5.3.9 Level 2 Partial Sequence Numbers PDU
- Additional codes for IP support are:
7 Authentication Information -- Information used to authenticate
the PDU
x CODE - 133
x LENGTH - total length of the value field
x VALUE - TBD
5.3.10 ISO 9542 ISH PDU
- Additional codes for IP support are:
7 Protocols Supported -- the set Network Layer Protocol Identifiers
for Network Layer protocols that this Intermediate System is
capable of relaying.
This appears in ISO 9542 ISH PDUs transmitted on point-to-point
links.
x CODE - 129
x LENGTH - total length of the value field (one octet per
protocol supported).
x VALUE - one octet NLPID (as assigned by ISO/TR 9577) for
each supported data protocol.
No. of Octets
+----------------------------+
| NLPID | 1
+----------------------------+
: :
: :
+----------------------------+
| NLPID | 1
+----------------------------+
NLPID - ISO/TR 9577 registered Network Layer Protocol Identifier.
7 Authentication Information -- Information used to authenticate
the PDU
x CODE - 133
x LENGTH - total length of the value field
x VALUE - TBD
6 Security Considerations
The integrated IS-IS has a provision for carrying authentication
information in all IS-IS packets. This is extensible to multiple
authentication mechanisms. However, currently the only defined
mechanism is a simple password, transmitted in the clear without
encryption (see Annex D). The use of a simple password does not
provide useful protection against intentional misbehavior. Rather,
this should be thought of as a weak protection against accidental
errors such as accidental mis-configuration. Definition of other
authentication mechanisms is beyond the scope of this document.
Other aspects of security are not discussed in this document.
7 Author's Address
Ross Callon
Digital Equipment Corporation
550 King Street, LKG 1-2/A19
Littleton, MA 01460-1289
508-486-5009
8 References
[1] "Intermediate System to Intermediate System Intra-Domain
Routeing Exchange Protocol for use in Conjunction with the
Protocol for Providing the Connectionless-mode Network Service
(ISO 8473)", ISO DP 10589, February 1990.
[2] "Protocol for Providing the Connectionless-Mode Network
Service", ISO 8473, March 1987.
[3] "End System to Intermediate System Routeing Exchange Protocol
for Use in Conjunction with the Protocol for Providing the
Connectionless-Mode Network Service (ISO 8473)", ISO 9542,
March 1988.
[4] Braden,R., and Postel,J., "Requirements for Internet Gateways",
RFC1009, June 1987.
[5] Moy,J., "The OSPF Specification", RFC1131, October 1989.
[6] Postel,J., "Internetwork Protocol", RFC791, September 1981.
[7] Postel,J., "Internet Control Message Protocol", RFC792,
September 1981.
[8] "MIB for Use with the Extended OSI IS-IS in TCP/IP and Dual
Environments", forthcoming.
[9] GOSIP Advanced Requirements Group, "Government Open Systems
Interconnection Profile (GOSIP) Version 2.0 [Final Text]",
Federal Information Processing Standard, U.S. Department of
Commerce, National Institute of Standards and Technology,
Gaithersburg, MD, October 1990.
[10] "Standard for Local Area Networks and Metropolitan Area
Networks: Overview and Architecture of Network Standards",
IEEE Standard 802.1a-1990.
Annex A
Inter-Domain Routing Protocol Information
This annex specifies the contents and encoding of the Inter-Domain
Routing Protocol Information (IDRPI) field. This annex is an integral
part of the Integrated IS-IS specification. However, it is expected
that this annex may be augmented or superceded by future efforts
outside of the scope of the IS-IS specification.
A.1 Inter-Domain Information Type
As specified in sections 3.4 and 5.3, the IDRPI field consists of a
one-octet inter-domain information type field, plus a variable
external information field. This section specifies initial values for
the inter-domain information type field. Other values for inter-
domain information type will be assigned and maintained in future
versions of the "Assigned Numbers" RFC.
The following types have been assigned:
Type = 0 reserved
Type = 1 local (uses routing-domain specific format)
Type = 2 AS Number Tag
Type = 1 indicates that the inter-domain routing protocol information
uses a format which is local to the routing domain.
Type = 2 indicates that the inter-domain routing protocol information
includes autonomous system information used to tag IP external
reachability information. In this case the inter-domain routing
protocol information entry must include a single AS number, which is
used to tag all subsequent External IP Reachability entries until the
end of the LSP, or until the next occurence of the Inter-Domain
Routing Protocol Information field.
A.2 Encoding
As specified in section 5.3.5, the IDPRI entry is encoded as a
variable length field, as follows:
x CODE - 131
x LENGTH - total length of the value field
x VALUE -
No. of Octets
+-------------------------------+
| Inter-Domain Information Type | 1
+-------------------------------+
| External Information | VARIABLE
+-------------------------------+
INTER-DOMAIN INFORMATION TYPE indicates the type of the
external information which is encoded in the field.
EXTERNAL INFORMATION contains inter-domain routing protocol
information, and is passed transparently by the IS-IS protocol.
The Inter-domain information type field indicates the type of
information which is contained in the external information field, as
follow:
Type = 0 is reserved (must not be sent, and must be ignored on receipt).
Type = 1 indicates that the external information field contains
information which follows a locally specified format.
Type = 2 indicates that the external information field contains an
autonomous system number tag, to be applied to subsequent IP external
reachability information entries. In this case, this "inter-domain
routing protocol information" entry must contain precisely one 2
octet AS number. The AS tag is associated with subsequent IP External
Reachability entries, until the end of the LSP, or until the next
occurence of the Inter-Domain Routing Protocol Information field.
In this case, the VALUE contains the following:
x VALUE -
No. of Octets
+---------------------------------+
| Inter-Domain Information Type=2 | 1
+---------------------------------+
| Autonomous System Number | 2
+---------------------------------+
Annex B
Encoding of Sequence Number Packets
The Integrated IS-IS protocol defined in this specification makes use
of the ISO Draft Proposed standard for Intra-domain routing (ISO DP
10589 [1]) as the base routing protocol, upon which IP support may be
added.
However, DP 10589 contains a bug regarding encoding of the variable
length fields in Sequence Number Packets. In particular, DP 10589
encodes the variable length fields in SNPs in a manner which is not
flexible (additional variable length fields cannot be defined for
sequence number packets), and which is inconsistent with the encoding
of the variable length fields in all other IS-IS and ES-IS packets.
The encoding of the variable length fields in SNPs is expected to be
fixed in future versions of 10589. Also, this bug represents the only
expected change to 10589 which cannot be made backward compatible
with existing DP 10589 implementations. For these reasons, the
current version of the Integrated IS-IS will use the anticipated
future encoding of the variable length part of the SNPs. This should
allow future versions of this specification to be compatible with
implementations based on this specification.
This annex specifies the encoding of SNPs, as amended to fix the
encoding of variable length fields. This annex is an integral part of
the Integrated IS-IS specification.
The encoding of SNPs for OSI-only use is shown in this section. For
IP-only or Integrated use, the additional variable length fields
specified in sections 5.3.6 through 5.3.9 are also applicable to
SNPs.
B.1 Level 1 Complete Sequence Numbers PDU
No. of Octets
+--------------------------------+
| INTRA-DOMAIN ROUTEING | 1
| PROTOCOL DISCRIMINATOR |
+--------------------------------+
| LENGTH INDICATOR | 1
+--------------------------------+
| VERSION/PROTOCOL ID EXT | 1
+--------------------------------+
| RESERVED | 1
+--------------------------------+
| R | R | R | TYPE | 1
+--------------------------------+
| VERSION | 1
+--------------------------------+
| ECO | 1
+--------------------------------+
| USER ECO | 1
+--------------------------------+
| PDU LENGTH | 2
+--------------------------------+
| SOURCE ID | 7
+--------------------------------+
| START LSP ID | 8
+--------------------------------+
| END LSP ID | 8
+================================+====================
| VARIABLE LENGTH FIELDS | VARIABLE
+--------------------------------+
- INTRADOMAIN ROUTEING PROTOCOL DISCRIMINATOR - architectural constant
- LENGTH INDICATOR - Header Length in octets (33.)
- VERSION/PROTOCOL ID EXTENSION - 1
- RESERVED - transmitted as 0, ignored on receipt
- TYPE (bits 1 through 5) - 24. Note bits 6, 7 and 8 are Reserved,
which means they are transmitted as 0 and ignored on receipt.
- VERSION - 1
- ECO - transmitted as zero, ignored on receipt
- USER ECO - transmitted as zero, ignored on receipt
- PDU LENGTH - Entire Length of this PDU, in octets, including header
- SOURCE ID - 7 octet ID of Intermediate System (with zero Circuit ID)
generating this Sequence Numbers PDU.
- START LSP ID - 8 octet ID of first LSP in the range covered by this
Complete Sequence Numbers PDU.
- END LSP ID - 8 octet ID of last LSP in the range covered by this
Complete Sequence Numbers PDU.
- VARIABLE LENGTH FIELDS - fields of the form:
No. of Octets
+--------------------------------+
| CODE | 1
+--------------------------------+
| LENGTH | 1
+--------------------------------+
| VALUE | LENGTH
+--------------------------------+
Any codes in a received CSNP that are not recognised are ignored.
Currently defined codes are:
7 LSP Entries -- This may appear multiple times. The option fields,
if they appear more than once, shall appear sorted into ascending
LSPID order.
x CODE - 9
x LENGTH - total length of the value field.
x VALUE - a list of LSP entries of the form:
No. of Octets
+--------------------------------+
| REMAINING LIFETIME | 2
+--------------------------------+
| LSP ID | 8
+--------------------------------+
| LSP SEQ NUMBER | 4
+--------------------------------+
| CHECKSUM | 2
+--------------------------------+
: :
: :
+--------------------------------+
| REMAINING LIFETIME | 2
+--------------------------------+
| LSP ID | 8
+--------------------------------+
| LSP SEQ NUMBER | 4
+--------------------------------+
| CHECKSUM | 2
+--------------------------------+
7 REMAINING LIFETIME - Remaining Lifetime of LSP.
7 LSP ID - 8 octet ID of the LSP to which this entry refers.
7 LSP SEQ NUMBER - Sequence number of LSP.
7 CHECKSUM - Checksum reported in LSP.
The entries shall be sorted into ascending LSPID order (the LSP
number octet of the LSPID is the least significant octet).
B.2 Level 2 Complete Sequence Numbers PDU
No. of Octets
+--------------------------------+
| INTRA-DOMAIN ROUTEING | 1
| PROTOCOL DISCRIMINATOR |
+--------------------------------+
| LENGTH INDICATOR | 1
+--------------------------------+
| VERSION/PROTOCOL ID EXT | 1
+--------------------------------+
| RESERVED | 1
+--------------------------------+
| R | R | R | TYPE | 1
+--------------------------------+
| VERSION | 1
+--------------------------------+
| ECO | 1
+--------------------------------+
| USER ECO | 1
+--------------------------------+
| PDU LENGTH | 2
+--------------------------------+
| SOURCE ID | 7
+--------------------------------+
| START LSP ID | 8
+--------------------------------+
| END LSP ID | 8
+================================+====================
| VARIABLE LENGTH FIELDS | VARIABLE
+--------------------------------+
- INTRADOMAIN ROUTEING PROTOCOL DISCRIMINATOR - architectural constant
- LENGTH INDICATOR - Header Length in octets (33.)
- VERSION/PROTOCOL ID EXTENSION - 1
- RESERVED - transmitted as 0, ignored on receipt
- TYPE (bits 1 through 5) - 25. Note bits 6, 7 and 8 are Reserved,
which means they are transmitted as 0 and ignored on receipt.
- VERSION - 1
- ECO - transmitted as zero, ignored on receipt
- USER ECO - transmitted as zero, ignored on receipt
- PDU LENGTH - Entire Length of this PDU, in octets, including header
- SOURCE ID - 7 octet ID of Intermediate System (with zero Circuit ID)
generating this Sequence Numbers PDU.
- START LSP ID - 8 octet ID of first LSP in the range covered by this
Complete Sequence Numbers PDU.
- END LSP ID - 8 octet ID of last LSP in the range covered by this
Complete Sequence Numbers PDU.
- VARIABLE LENGTH FIELDS - fields of the form:
No. of Octets
+--------------------------------+
| CODE | 1
+--------------------------------+
| LENGTH | 1
+--------------------------------+
| VALUE | LENGTH
+--------------------------------+
Any codes in a received CSNP that are not recognised are ignored.
Currently defined codes are:
7 LSP Entries -- this may appear multiple times. The option fields,
if they appear more than once, shall appear sorted into ascending
LSPID order.
x CODE - 9
x LENGTH - total length of the value field.
x VALUE - a list of LSP entries of the form:
No. of Octets
+--------------------------------+
| REMAINING LIFETIME | 2
+--------------------------------+
| LSP ID | 8
+--------------------------------+
| LSP SEQ NUMBER | 4
+--------------------------------+
| CHECKSUM | 2
+--------------------------------+
: :
: :
+--------------------------------+
| REMAINING LIFETIME | 2
+--------------------------------+
| LSP ID | 8
+--------------------------------+
| LSP SEQ NUMBER | 4
+--------------------------------+
| CHECKSUM | 2
+--------------------------------+
7 REMAINING LIFETIME - Remaining Lifetime of LSP.
7 LSP ID - 8 octet ID of the LSP to which this entry refers.
7 LSP SEQ NUMBER - Sequence number of LSP.
7 CHECKSUM - Checksum reported in LSP.
The entries shall be sorted into ascending LSPID order (the LSP
number octet of the LSPID is the least significant octet).
B.3 Level 1 Partial Sequence Numbers PDU
No. of Octets
+--------------------------------+
| INTRA-DOMAIN ROUTEING | 1
| PROTOCOL DISCRIMINATOR |
+--------------------------------+
| LENGTH INDICATOR | 1
+--------------------------------+
| VERSION/PROTOCOL ID EXT | 1
+--------------------------------+
| RESERVED | 1
+--------------------------------+
| R | R | R | TYPE | 1
+--------------------------------+
| VERSION | 1
+--------------------------------+
| ECO | 1
+--------------------------------+
| USER ECO | 1
+--------------------------------+
| PDU LENGTH | 2
+--------------------------------+
| SOURCE ID | 7
+================================+====================
| VARIABLE LENGTH FIELDS | VARIABLE
+--------------------------------+
- INTRADOMAIN ROUTEING PROTOCOL DISCRIMINATOR - architectural constant
- LENGTH INDICATOR - Header Length in octets (17.)
- VERSION/PROTOCOL ID EXTENSION - 1
- RESERVED - transmitted as 0, ignored on receipt
- TYPE (bits 1 through 5) 26. Note bits 6, 7 and 8 are Reserved,
which means they are transmitted as 0 and ignored on receipt.
- VERSION - 1
- ECO - transmitted as zero, ignored on receipt
- USER ECO - transmitted as zero, ignored on receipt
- PDU LENGTH - Entire Length of this PDU, in octets, including header
- SOURCE ID - 7 octet ID of Intermediate system (with zero Circuit ID)
generating this Sequence Numbers PDU.
- VARIABLE LENGTH FIELDS - fields of the form:
No. of Octets
+--------------------------------+
| CODE | 1
+--------------------------------+
| LENGTH | 1
+--------------------------------+
| VALUE | LENGTH
+--------------------------------+
Any codes in a received PSNP that are not recognised are ignored.
Currently defined codes are:
7 LSP Entries - this may appear multiple times. The option fields,
if they appear more than once, shall appear sorted into ascending
LSPID order.
x CODE - 9
x LENGTH - total length of the value field.
x VALUE - a list of LSP entries of the form:
No. of Octets
+--------------------------------+
| REMAINING LIFETIME | 2
+--------------------------------+
| LSP ID | 8
+--------------------------------+
| LSP SEQ NUMBER | 4
+--------------------------------+
| CHECKSUM | 2
+--------------------------------+
: :
: :
+--------------------------------+
| REMAINING LIFETIME | 2
+--------------------------------+
| LSP ID | 8
+--------------------------------+
| LSP SEQ NUMBER | 4
+--------------------------------+
| CHECKSUM | 2
+--------------------------------+
7 REMAINING LIFETIME - Remaining Lifetime of LSP.
7 LSP ID - 8 octet ID of the LSP to which this entry refers.
7 LSP SEQ NUMBER - Sequence number of LSP.
7 CHECKSUM - Checksum reported in LSP.
The entries shall be sorted into ascending LSPID order (the LSP number
octet of the LSPID is the least significant octet).
B.4 Level 2 Partial Sequence Numbers PDU
No. of Octets
+--------------------------------+
| INTRA-DOMAIN ROUTEING | 1
| PROTOCOL DISCRIMINATOR |
+--------------------------------+
| LENGTH INDICATOR | 1
+--------------------------------+
| VERSION/PROTOCOL ID EXT | 1
+--------------------------------+
| RESERVED | 1
+--------------------------------+
| R | R | R | TYPE | 1
+--------------------------------+
| VERSION | 1
+--------------------------------+
| ECO | 1
+--------------------------------+
| USER ECO | 1
+--------------------------------+
| PDU LENGTH | 2
+--------------------------------+
| SOURCE ID | 7
+================================+====================
| VARIABLE LENGTH FIELDS | VARIABLE
+--------------------------------+
- INTRADOMAIN ROUTEING PROTOCOL DISCRIMINATOR - architectural constant
- LENGTH INDICATOR - Header Length in octets (17.)
- VERSION/PROTOCOL ID EXTENSION - 1
- RESERVED - transmitted as 0, ignored on receipt
- TYPE (bits 1 through 5) - 27. Note bits 6, 7 and 8 are Reserved,
which means they are transmitted as 0 and ignored on receipt.
- VERSION - 1
- ECO - transmitted as zero, ignored on receipt
- USER ECO - transmitted as zero, ignored on receipt
- PDU LENGTH - Entire Length of this PDU, in octets, including header
- SOURCE ID - 7 octet ID of Intermediate system (with zero Circuit ID)
generating this Sequence Numbers PDU.
- VARIABLE LENGTH FIELDS - fields of the form:
No. of Octets
+--------------------------------+
| CODE | 1
+--------------------------------+
| LENGTH | 1
+--------------------------------+
| VALUE | LENGTH
+--------------------------------+
Any codes in a received PSNP that are not recognised are ignored.
Currently defined codes are:
7 LSP Entries -- this may appear multiple times. The option fields,
if they appear more than once, shall appear sorted into ascending
LSPID order.
x CODE - 9
x LENGTH - total length of the value field.
x VALUE - a list of LSP entries of the form:
No. of Octets
+--------------------------------+
| REMAINING LIFETIME | 2
+--------------------------------+
| LSP ID | 8
+--------------------------------+
| LSP SEQ NUMBER | 4
+--------------------------------+
| CHECKSUM | 2
+--------------------------------+
: :
: :
+--------------------------------+
| REMAINING LIFETIME | 2
+--------------------------------+
| LSP ID | 8
+--------------------------------+
| LSP SEQ NUMBER | 4
+--------------------------------+
| CHECKSUM | 2
+--------------------------------+
7 REMAINING LIFETIME - Remaining Lifetime of LSP.
7 LSP ID - 8 octet ID of the LSP to which this entry refers.
7 LSP SEQ NUMBER -Sequence number of LSP.
7 CHECKSUM - Checksum reported in LSP.
The entries shall be sorted into ascending LSPID order (the LSP
number octet of the LSPID is the least significant octet).
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