As per Relevance of the word registered, we have this rfc below:

---

Network Working Group D. Oran,
Request for Comments: 1142 Digital Equipment Corp
February 1990


OSI IS-IS Intra-domain Routing

Status of this

This RFC is a republication of ISO DP 10589 as a service to
Internet community. This is not an Internet standard
Distribution of this memo is unlimited


NOTE: This is a bad ASCII version of this document. The
document is the PostScript file, which has the diagrams in place
Please use the PostScript version of this memo


ISO/IEC DIS 10589

Information technology Telecommunications and information
between systems Interme diate system to Intermediate
Intra-Domain routeing exchange protocol for use in Conjunction
the Protocol for providing the Connectionless- mode Network
(ISO 8473) Technologies de l'information Communication de donnies
ichange d'information entre systhmes Protocole intra-domain de
d'un systhme intermediare ` un systhme intermediare `
conjointement avec le protocole fournissant le service de riseau
mode sans connexion (ISO 8473) UDC 00000.000 : 000.0000000000
Descriptors


Introduction
1 Scope and Field of Application 1
2 References 1
3 Definitions 2
4 Symbols and Abbreviations 3
5 Typographical Conventions 4
6 Overview of the Protocol 4
7 Subnetwork Independent Functions 9
8 Subnetwork Dependent Functions 35
9 Structure and Encoding of PDUs 47
10 System Environment 65
11 System Management 67
12 Conformance 95
Annex A PICS Proforma 99
Annex B Supporting Technical Material 105
Annex C Implementation Guidelines and Examples 109
Annex D Congestion Control and Avoidance 115



This Protocol is one of a set of International Standards produced
facilitate the interconnection of open systems. The set of
covers the services and protocols re quired to achieve
interconnection. This Protocol is positioned with respect to
related standards by the layers defined in the ISO 7498 and by
structure defined in the ISO 8648. In particular, it is a protocol
the Network Layer. This protocol permits Intermediate Systems within
routeing Domain to exchange configuration and routeing information
facilitate the operation of the route ing and relaying functions
the Network Layer. The protocol is designed to operate in
conjunction with ISO 9542 and ISO 8473. ISO 9542 is used to
connectivity and reachability between End Systems and Inter
Systems on individual Subnetworks. Data is carried by ISO 8473.
related algo rithms for route calculation and maintenance are
described. The intra-domain ISIS routeing protocol is intended
support large routeing domains consisting of combinations of
types of subnetworks. This includes point-to-point links,
links, X.25 subnetworks, and broadcast subnetworks such as ISO 8802
LANs. In order to support large routeing domains, provision is
for Intra-domain routeing to be organised hierarchically. A
domain may be administratively divided into areas. Each
resides in exactly one area. Routeing within an area is referred to
Level 1 routeing. Routeing between areas is referred to as Level 2
routeing. Level 2 Intermediate systems keep track of the paths
destination areas. Level 1 Intermediate systems keep track of
routeing within their own area. For an NPDU destined to another area
a Level 1 Intermediate system sends the NPDU to the nearest level 2
in its own area, re gardless of what the destination area is. Then
NPDU travels via level 2 routeing to the destination area, where
again travels via level 1 routeing to the destination End System

Information

Telecommunications and information exchange between
Intermediate system to Intermediate system Intra-Domain
exchange protocol for use in Conjunction with the Protocol
providing the Connectionless-mode Network Service (ISO 8473)

1 Scope and Field of

This International Standard specifies a protocol which is used
Network Layer entities operating ISO 8473 in In termediate Systems
maintain routeing information for the purpose of routeing within
single routeing domain. The protocol herein described relies upon
provision of a connectionless-mode underlying service.11See ISO 8473
and its Addendum 3 for the mechanisms necessary to realise
service on subnetworks based on ISO 8208, ISO 8802, and the OSI
Link Service

This Standard specifies:

a)procedures for the transmission of configuration and
routeing information between network entities
ing in Intermediate Systems within a single routeing
domain;

b)the encoding of the protocol data units used for the
transmission of the configuration and routeing
mation;

c)procedures for the correct interpretation of protocol
control information; and

d)the functional requirements for implementations
claiming conformance to this Standard

The procedures are defined in terms of:

a)the interactions between Intermediate system Network
entities through the exchange of protocol data units;
and

b)the interactions between a Network entity and an
derlying service provider through the exchange of
subnetwork service primitives

c)the constraints on route determination which must be
observed by each Intermediate system when each has
a routeing information base which is consistent with
the others

2

2.1 Normative

The following standards contain provisions which, through reference
this text, constitute provisions of this Interna tional Standard.
the time of publication, the editions in dicated were valid.
standards are subject to revision, and parties to agreements based
this International Stan dard are encouraged to investigate
possibility of apply ing the most recent editions of the
listed below. Members of IEC and ISO maintain registers of
valid International Standards. ISO 7498:1984, Information
systems Open Systems Interconnection Basic Reference Model.
7498/Add.1:1984, Information processing systems Open
Interconnection Basic Reference Model Addendum 1: Connectionless-
Transmission. ISO 7498-3:1989, Information processing systems
Systems Interconnection Basic Reference Model Part 3: Naming
Addressing. ISO 7498-4:1989, Information processing systems
Systems Interconnection Basic Reference Model Part 4:
Framework. ISO 8348:1987, Information processing systems
communications Network Service Definition. ISO 8348/Add.1:1987,
Information processing systems Data communications Network
Definition Addendum 1: Connectionless-mode transmission.
8348/Add.2:1988, Information processing systems Data
Network Service Definition Addendum 2: Network layer addressing.
8473:1988, Information processing systems Data communications
for providing the connectionless-mode network service.
8473/Add.3:1989, Information processing systems Telecommunications
information exchange
systems Protocol for providing the connectionless
mode network service Addendum 3: Provision of the
underlying service assumed by ISO 8473 over
subnetworks which provide the OSI data link service
ISO 8648:1988, Information processing systems Open
Systems Interconnection Internal organisation of the
Network Layer
ISO 9542:1988, Information processing systems
communications and information exchange between
tems End system to Intermediate system Routeing
change protocol for use in conjunction with the protocol
for providing the connectionless -mode network service
(ISO 8473).
ISO 8208:1984, Information processing systems Data
communications X.25 packet level protocol for Data
terminal
ISO 8802:1988, Information processing systems
communications and information exchange between
tems Local area networks
ISO/TR 9575:1989, Information technology
munications and information exchange between systems
OSI Routeing Framework
ISO/TR 9577:1990, Information technology
munications and information exchange between systems
Protocol Identification in the Network Layer
ISO/IEC DIS 10165-4:, Information technology Open
systems interconnection Management Information
ices Structure of Management Information Part 4:
Guidelines for the Definition of Managed Objects
ISO/IEC 10039:1990, IPS-T&IEBS MAC Service
tion

2.2 Other

The following references are helpful in describing some of
the routeing algorithms:

McQuillan, J. et. al., The New Routeing Algorithm for the
ARPANET, IEEE Transactions on Communications, May
1980.

Perlman, Radia, Fault-Tolerant Broadcast of Routeing
formation, Computer Networks, Dec. 1983. Also in IEEE
INFOCOM 83, April 1983.

Aho, Hopcroft, and Ullman, Data Structures and
rithms, P204208 Dijkstra algorithm

3

3.1 Reference Model

This International Standard makes use of the following
terms defined in ISO 7498:

a)Network
b)Network Service access
c)Network Service access point
d)Network
e)
f)Network
g)Network
h)Network protocol data

3.2 Network Layer architecture


This International Standard makes use of the following
terms defined in ISO 8648:


a)
b)End
c)Intermediate
d)Subnetwork
e)Subnetwork Access Protocol
f)Subnetwork Dependent Convergence Protocol
g)Subnetwork Independent Convergence

3.3 Network Layer addressing


This International Standard makes use of the following
terms defined in ISO 8348/Add.2:


a)Subnetwork
b)Subnetwork point of
c)Network Entity
3.4 Local Area Network
This International Standard makes use of the following
terms defined in ISO 8802:
a)Multi-destination address
b)Media access
c)Broadcast
3.5 Routeing Framework
This document makes use of the following terms defined in
ISO/TR 9575:
a)Administrative Domain
b)Routeing Domain
c)Hop
d)Black hole


3.6 Additional
For the purposes of this International Standard, the
ing definitions apply:
3.6.1
Area: A routeing subdomain which maintains
tailed routeing information about its own internal
composition, and also maintains routeing
tion which allows it to reach other routeing
mains. It corresponds to the Level 1 subdomain.
3.6.2
Neighbour: An adjacent system reachable by
versal of a single subnetwork by a PDU.
3.6.3
Adjacency: A portion of the local routeing
mation which pertains to the reachability of a
gle neighbour ES or IS over a single circuit
Adjacencies are used as input to the Decision
ess for forming paths through the routeing domain
A separate adjacency is created for each neighbour
on a circuit, and for each level of routeing (i.e.
level 1 and level 2) on a broadcast circuit
3.6.4
Circuit: The subset of the local routeing
tion base pertinent to a single local SNPA.
3.6.5
Link: The communication path between two
neighbours.
A Link is up when communication is possible
between the two SNPAs
3.6.6
Designated IS: The Intermediate system on a
LAN which is designated to perform additional
ties. In particular it generates Link State PDUs on
behalf of the LAN, treating the LAN as a
pseudonode.
3.6.7
Pseudonode: Where a broadcast subnetwork has n
connected Intermediate systems, the broadcast
subnetwork itself is considered to be a
pseudonode.
The pseudonode has links to each of the n
diate systems and each of the ISs has a single link
to the pseudonode (rather than n-1 links to each of
the other Intermediate systems). Link State PDUs
are generated on behalf of the pseudonode by the
Designated IS. This is depicted below in figure 1.
3.6.8
Broadcast subnetwork: A subnetwork which
ports an arbitrary number of End systems and

termediate systems and additionally is capable of
transmitting a single SNPDU to a subset of these
systems in response to a single SN_UNITDATA
request.
3.6.9
General topology subnetwork: A subnetwork
which supports an arbitrary number of End
tems and Intermediate systems, but does not
port a convenient multi-destination connectionless


mission facility, as does a broadcast




work.
3.6.10
Routeing Subdomain: a set of Intermediate
tems and End systems located within the same
Routeing domain
3.6.11
Level 2 Subdomain: the set of all Level 2
mediate systems in a Routeing domain
4 Symbols and Abbreviations
4.1 Data
PDU Protocol Data
SNSDU Subnetwork Service Data
NSDU Network Service Data
NPDU Network Protocol Data
SNPDU Subnetwork Protocol Data

4.2 Protocol Data
ESH PDU ISO 9542 End System Hello Protocol Data
Unit
ISH PDU ISO 9542 Intermediate System Hello Protocol
Data
RD PDU ISO 9542 Redirect Protocol Data
IIH Intermediate system to Intermediate system
Hello Protocol Data
LSP Link State Protocol Data Unit
SNP Sequence Numbers Protocol Data
CSNP Complete Sequence Numbers Protocol Data

PSNP Partial Sequence Numbers Protocol Data


4.3
AFI Authority and Format
DSP Domain Specific
IDI Initial Domain
IDP Initial Domain
NET Network Entity
NSAP Network Service Access
SNPA Subnetwork Point of

4.4
DA Dynamically
DED Dynamically Established Data
DTE Data Terminal
ES End
IS Intermediate
L1 Level 1
L2 Level 2
LAN Local Area
MAC Media Access
NLPID Network Layer Protocol
PCI Protocol Control
QoS Quality of
SN
SNAcP Subnetwork Access
SNDCP Subnetwork Dependent Convergence
SNICP Subnetwork Independent Convergence

SRM Send Routeing
SSN Send Sequence Numbers
SVC Switched Virtual
5 Typographical
This International Standard makes use of the following
pographical conventions
a)Important terms and concepts appear in italic type
when introduced for the first time
b)Protocol constants and management parameters appear
in sansSerif type with multiple words run together.
The first word is lower case, with the first character of
subsequent words capitalised
c)Protocol field names appear in San Serif type with
each word capitalised
d)Values of constants, parameters, and protocol fields
appear enclosed in double quotes

6 Overview of the
6.1 System
There are the following types of system
End Systems: These systems deliver NPDUs to other
tems and receive NPDUs from other systems, but do
not relay NPDUs. This International Standard does
not specify any additional End system functions
yond those supplied by ISO 8473 and ISO 9542.
Level 1 Intermediate Systems: These systems deliver and
receive NPDUs from other systems, and relay
NPDUs from other source systems to other
tion systems. They route directly to systems within
their own area, and route towards a level 2
diate system when the destination system is in a
ferent area
Level 2 Intermediate Systems: These systems act as Level 1
Intermediate systems in addition to acting as a
tem in the subdomain consisting of level 2 ISs.
tems in the level 2 subdomain route towards a
nation area, or another routeing domain
6.2 Subnetwork
There are two generic types of subnetworks supported
a)broadcast subnetworks: These are multi-access
subnetworks that support the capability of addressing
a group of attached systems with a single NPDU, for
instance ISO 8802.3 LANs
b)general topology subnetworks: These are modelled as
a set of point-to-point links each of which connects
exactly two systems
There are several generic types of general topology
subnetworks
1)multipoint links: These are links between more
than two systems, where one system is a primary
system, and the remaining systems are secondary
(or slave) systems. The primary is capable of direct
communication with any of the secondaries, but
the secondaries cannot communicate directly
among themselves.
2)permanent point-to-point links: These are links
that stay connected at all times (unless broken, or
turned off by system management), for instance
leased lines or private links
3)dynamically established data links (DEDs): these
are links over connection oriented facilities, for
stance X.25, X.21, ISDN, or PSTN networks
Dynamically established data links can be used in one
of two ways
i)static point-to-point (Static): The call is
lished upon system management action and

cleared only on system management action (or
failure).
ii)dynamically assigned (DA): The call is
lished upon receipt of traffic, and brought
down on timer expiration when idle. The
dress to which the call is to be established is
determined dynamically from information in
the arriving NPDU(s). No ISIS routeing
PDUs are exchanged between ISs on a DA
cuit
All subnetwork types are treated by the Subnetwork
pendent functions as though they were connectionless
subnetworks, using the Subnetwork Dependent
gence functions of ISO 8473 where necessary to provide a
connectionless subnetwork service. The Subnetwork
pendent functions do, however, operate differently on
connectionless and connection-oriented subnetworks
6.3
A single organisation may wish to divide its Administrative
Domain into a number of separate Routeing Domains.
This has certain advantages, as described in ISO/TR 9575.
Furthermore, it is desirable for an intra-domain routeing
protocol to aid in the operation of an inter-domain routeing
protocol, where such a protocol exists for interconnecting
multiple administrative domains
In order to facilitate the construction of such multi-domain
topologies, provision is made for the entering of static
inter-domain routeing information. This information is
vided by a set of Reachable Address Prefixes entered by
System Management at the ISs which have links which
cross routeing domain boundaries. The prefix indicates that
any NSAPs whose NSAP address matches the prefix may
be reachable via the SNPA with which the prefix is
ated. Where the subnetwork to which this SNPA is
nected is a general topology subnetwork supporting
namically established data links, the prefix also has
ated with it the required subnetwork addressing
information, or an indication that it may be derived from
the destination NSAP address (for example, an X.121 DTE
address may sometimes be obtained from the IDI of the
NSAP address).
The Address Prefixes are handled by the level 2 routeing
gorithm in the same way as information about a level 1 area
within the domain. NPDUs with a destination address
matching any of the prefixes present on any Level 2
mediate System within the domain can therefore be relayed
(using level 2 routeing) by that IS and delivered out of the
domain. (It is assumed that the routeing functions of the
other domain will then be able to deliver the NPDU to its
destination.)
6.4
Within a routeing domain that conforms to this standard,
the Network entity titles of Intermediate systems shall be
structured as described in 7.1.1.
All systems shall be able to generate and forward data
PDUs containing NSAP addresses in any of the formats
specified by ISO 8348/Add.2. However, NSAP addresses

of End systems should be structured as described in 7.1.1 in
order to take full advantage of ISIS routeing. Within such
a domain it is still possible for some End Systems to have
addresses assigned which do not conform to 7.1.1, provided
they meet the more general requirements of
ISO 8348/Add.2, but they may require additional
tion and be subject to inferior routeing performance
6.5 Functional
The intra-domain ISIS routeing functions are divided into
two
-Subnetwork Independent Functions
-Subnetwork Dependent
6.5.1 Subnetwork Independent
The Subnetwork Independent Functions supply full-duplex
NPDU transmission between any pair of neighbour
tems. They are independent of the specific subnetwork or
data link service operating below them, except for
ing two generic types of subnetworks:
-General Topology Subnetworks, which include
HDLC point-to-point, HDLC multipoint, and
cally established data links (such as X.25, X.21, and
PSTN links), and
-Broadcast Subnetworks, which include ISO 8802
LANs
The following Subnetwork Independent Functions are

-Routeing. The routeing function determines NPDU
paths. A path is the sequence of connected systems
and links between a source ES and a destination ES
The combined knowledge of all the Network Layer
entities of all the Intermediate systems within a
ing domain is used to ascertain the existence of a path,
and route the NPDU to its destination. The routeing
component at an Intermediate system has the
ing specific functions
7It extracts and interprets the routeing PCI in an
NPDU.
7It performs NPDU forwarding based on the
nation address.
7It manages the characteristics of the path. If a
tem or link fails on a path, it finds an alternate
route.
7It interfaces with the subnetwork dependent
tions to receive reports concerning an SNPA
which has become unavailable, a system that has
failed, or the subsequent recovery of an SNPA or
system.
7It informs the ISO 8473 error reporting function
when the forwarding function cannot relay an
NPDU, for instance when the destination is
reachable or when the NPDU would have needed

to be segmented and the NPDU requested no
mentation
-Congestion control. Congestion control manages the
resources used at each Intermediate system.
6.5.2 Subnetwork Dependent Functions
The subnetwork dependent functions mask the
tics of the subnetwork or data link service from the
subnetwork independent functions. These include
-Operation of the Intermediate system functions of
ISO 9542 on the particular subnetwork, in order
7Determine neighbour Network entity title(s) and
SNPA address(es)
7Determine the SNPA address(s) of operational
termediate systems
-Operation of the requisite Subnetwork Dependent
Convergence Function as defined in ISO 8473 and its
Addendum 3, in order to perform
7Data link initialisation
7Hop by hop fragmentation over subnetworks with
small maximum SNSDU sizes
7Call establishment and clearing on dynamically
tablished data
6.6 Design
This International Standard supports the following design
requirements. The correspondence with the goals for OSI
routeing stated in ISO/TR 9575 are noted
-Network Layer Protocol Compatibility. It is
patible with ISO 8473 and ISO 9542. (See clause 7.5
of ISO/TR 9575),
-Simple End systems: It requires no changes to end
systems, nor any functions beyond those supplied by
ISO 8473 and ISO 9542. (See clause 7.2.1 of ISO/TR
9575),
-Multiple Organisations: It allows for multiple
ing and administrative domains through the provision
of static routeing information at domain boundaries.
(See clause 7.3 of ISO/TR 9575),
-Deliverability It accepts and delivers NPDUs
dressed to reachable destinations and rejects NPDUs
addressed to destinations known to be unreachable.
-Adaptability. It adapts to topological changes within
the routeing domain, but not to traffic changes, except
potentially as indicated by local queue lengths. It
splits traffic load on multiple equivalent paths. (See
clause 7.7 of ISO/TR 9575),
-Promptness. The period of adaptation to topological
changes in the domain is a reasonable function of the
domain diameter (that is, the maximum logical

tance between End Systems within the domain) and
Data link speeds. (See clause 7.4 of ISO/TR 9575),
-Efficiency. It is both processing and memory
cient. It does not create excessive routeing traffic
overhead. (See clause 7.4 of ISO/TR 9575),
-Robustness. It recovers from transient errors such as
lost or temporarily incorrect routeing PDUs. It
ates imprecise parameter settings. (See clause 7.7 of
ISO/TR 9575),
-Stability. It stabilises in finite time to good routes,
provided no continuous topological changes or
tinuous data base corruptions occur.
-System Management control. System Management
can control many routeing functions via parameter
changes, and inspect parameters, counters, and routes.
It will not, however, depend on system management
action for correct behaviour.
-Simplicity. It is sufficiently simple to permit
ance tuning and failure isolation.
-Maintainability. It provides mechanisms to detect,
isolate, and repair most common errors that may affect
the routeing computation and data bases. (See clause
7.8 of ISO/TR 9575),
-Heterogeneity. It operates over a mixture of network
and system types, communication technologies, and
topologies. It is capable of running over a wide variety
of subnetworks, including, but not limited to: ISO
8802 LANs, ISO 8208 and X.25 subnetworks, PSTN
networks, and the OSI Data Link Service. (See clause
7.1 of ISO/TR 9575),
-Extensibility. It accommodates increased routeing
functions, leaving earlier functions as a subset.
-Evolution. It allows orderly transition from algorithm
to algorithm without shutting down an entire domain
-Deadlock Prevention. The congestion control
nent prevents buffer deadlock
-Very Large Domains. With hierarchical routeing, and
a very large address space, domains of essentially
limited size can be supported. (See clause 7.2 of
ISO/TR 9575),
-Area Partition Repair. It permits the utilisation of
level 2 paths to repair areas which become partitioned
due to failing level 1 links or ISs. (See clause 7.7 of
ISO/TR 9575),
-Determinism. Routes are a function only of the
cal topology, and not of history. In other words, the
same topology will always converge to the same set of
routes.
-Protection from Mis-delivery. The probability of
mis-delivering a NPDU, i.e. delivering it to a
port entity in the wrong End System, is extremely low.

-Availability. For domain topologies with cut set
greater than one, no single point of failure will
tion the domain. (See clause 7.7 of ISO/TR 9575),
-Service Classes. The service classes of transit delay,
expense22Expense is referred to as cost in ISO 8473. The latter term
not used here because of possible confusion with the more general
of the term to
indicate path cost according to any routeing metric
, and residual error probability of ISO 8473
are supported through the optional inclusion of
ple routeing metrics
-Authentication. The protocol is capable of carrying
information to be used for the authentication of
mediate systems in order to increase the security and
robustness of a routeing domain. The specific
nism supported in this International Standard
ever, only supports a weak form of authentication
ing passwords, and thus is useful only for protection
against accidental misconfiguration errors and does
not protect against any serious security threat. In the
future, the algorithms may be enhanced to provide
stronger forms of authentication than can be provided
with passwords without needing to change the PDU
encoding or the protocol exchange machinery
6.6.1 Non-
The following are not within the design scope of the intra
domain ISIS routeing protocol described in this
tional Standard
-Traffic adaptation. It does not automatically modify
routes based on global traffic load
-Source-destination routeing. It does not determine
routes by source as well as destination
-Guaranteed delivery. It does not guarantee delivery
of all offered NPDUs.
-Level 2 Subdomain Partition Repair. It will not
ise Level 1 paths to repair a level 2 subdomain
tion. For full logical connectivity to be available, a
connected level 2 subdomain is required
-Equal treatment for all ES Implementations. The
End system poll function defined in 8.4.5 presumes
that End systems have implemented the Suggested ES
Configuration Timer option of ISO 9542. An End
tem which does not implement this option may
ence a temporary loss of connectivity following
tain types of topology changes on its local
subnetwork
6.7 Environmental
For correct operation of the protocol, certain guarantees are
required from the local environment and the Data Link
Layer.
The required local environment guarantees are
a)Resource allocation such that the certain minimum
source guarantees can be met,

1)memory (for code, data, and buffers
2)processing
See 12.2.5 for specific performance levels required for

b)A quota of buffers sufficient to perform routeing
tions
c)Access to a timer or notification of specific timer
ration;
d)A very low probability of corrupting data
The required subnetwork guarantees for point-to-point links
are:
a)Provision that both source and destination systems
complete start-up before PDU exchange can occur
b)Detection of remote start-up
c)Provision that no old PDUs be received after start-up
is complete
d)Provision that no PDUs transmitted after a particular
startup is complete are delivered out of sequence
e)Provision that failure to deliver a specific subnetwork
SDU will result in the timely disconnection of the
subnetwork connection in both directions and that this
failure will be reported to both systems;
f)Reporting of other subnetwork failures and degraded
subnetwork conditions
The required subnetwork guarantees for broadcast links are
a)Multicast capability, i.e., the ability to address a subset
of all connected systems with a single PDU
b)The following events are low probability, which
means that they occur sufficiently rarely so as not to
impact performance, on the order of once per
sand
1)Routeing PDU non-sequentiality,
2)Routeing PDU loss due to detected corruption;
3)Receiver overrun
c)The following events are very low probability,
which means performance will be impacted unless
they are extremely rare, on the order of less than one
event per four
1)Delivery of NPDUs with undetected data
tion;
2)Non-transitive connectivity, i.e. where system A
can receive transmissions from systems B and C,
but system B cannot receive transmissions from
system C.

The following services are assumed to be not available
from broadcast links
a)Reporting of failures and degraded subnetwork
tions that result in NPDU loss, for instance receiver
failure. The routeing functions are designed to account
for these failures
6.8 Functional Organisation of
Subnetwork Independent

The Subnetwork Independent Functions are broken down
into more specific functional components. These are
scribed briefly in this sub-clause and in detail in clause 7.
This International Standard uses a functional decomposition
adapted from the model of routeing presented in clause 5.1
of ISO/TR 9575. The decomposition is not identical to that
in ISO/TR 9575, since that model is more general and not
specifically oriented toward a detailed description of intra
domain routeing functions such as supplied by this
col

The functional decomposition is shown below in figure 2.
6.8.1
The routeing processes are:
-Decision Process
-Update
NOTE this comprises both the Information Collection
and Information Distribution components identified in
ISO/TR 9575.
-Forwarding Process
-Receive
6.8.1.1 Decision
This process calculates routes to each destination in the
main. It is executed separately for level 1 and level 2
ing, and separately within each level for each of the
ing metrics supported by the Intermediate system. It uses
the Link State Database, which consists of information

from the latest Link State PDUs from every other
diate system in the area, to compute shortest paths from this
IS to all other systems in the area 9in figure 2. The
Link State Data Base is maintained by the Update Process
Execution of the Decision Process results in the
tion of [circuit, neighbour] pairs (known as adjacencies),
which are stored in the appropriate Forwarding Information
base 10 and used by the Forwarding process as paths
along which to forward NPDUs
Several of the parameters in the routeing data base that the
Decision Process uses are determined by the
tion. These include
-maximum number of Intermediate and End systems
within the IS's area
-maximum number of Intermediate and End system
neighbours of the IS, etc.,
so that databases can be sized appropriately. Also
ters such as
-routeing metrics for each circuit; and
-timers
can be adjusted for enhanced performance. The complete
list of System Management set-able parameters is listed in
clause 11.
6.8.1.2 Update Process
This process constructs, receives and propagates Link State
PDUs. Each Link State PDU contains information about the
identity and routeing metric values of the adjacencies of
the IS that originated the Link State PDU.
The Update Process receives Link State and Sequence
Numbers PDUs from the Receive Process 4in figure
2. It places new routeing information in the routeing
mation base 6 and propagates routeing information to
other Intermediate systems 7and 8 .
General characteristics of the Update Process are:
-Link State PDUs are generated as a result of
cal changes, and also periodically. They may also be
generated indirectly as a result of System
ment actions (such as changing one of the routeing
metrics for a circuit).
-Level 1 Link State PDUs are propagated to all
mediate systems within an area, but are not
gated out of an area.
-Level 2 Link State PDUs are propagated to all Level 2
Intermediate systems in the domain
-Link State PDUs are not propagated outside of a
main.

-The update process, through a set of System
ment parameters, enforces an upper bound on the
amount of routeing traffic overhead it generates
6.8.1.3 Forwarding
This process supplies and manages the buffers necessary to
support NPDU relaying to all destinations.
It receives, via the Receive Process, ISO 8473 PDUs to be
forwarded 5 in figure 2.
It performs a lookup in the appropriate33The appropriate
Database is selected by choosing a routeing metric based on fields
the QoS Maintenance option of ISO 8473.
Forwarding
base 11 to determine the possible output adjacencies
to use for forwarding to a given destination, chooses one
adjacency 12, generates error indications to ISO 8473
14 , and signals ISO 9542 to issue Redirect PDUs
13.
6.8.1.4 Receive
The Receive Process obtains its inputs from the following

-received PDUs with the NPID of Intra-Domain
ing 2 in figure 2,
-routeing information derived by the ESIS protocol
from the receipt of ISO 9542 PDUs 1;
-ISO 8473 data PDUs handed to the routeing function
by the ISO 8473 protocol machine 3.
It then performs the appropriate actions, which may involve
passing the PDU to some other function (e.g. to the
warding Process for forwarding 5).
7 Subnetwork Independent

This clause describes the algorithms and associated
bases used by the routeing functions. The managed objects
and attributes defined for System Management purposes are
described in clause 11.
The following processes and data bases are used internally
by the subnetwork independent functions. Following each
process or data base title, in parentheses, is the type of
tems which must keep the database. The system types are
L2 (level 2 Intermediate system), and L1 (level 1
mediate system). Note that a level 2 Intermediate system is
also a level 1 Intermediate system in its home area, so it
must keep level 1 databases as well as level 2 databases.

Processes
-Decision Process (L2, L1)
-Update Process (L2, L1)
-Forwarding Process (L2, L1)
-Receive Process (L2, L1)
Databases
-Level 1 Link State data base (L2, L1)
-Level 2 Link State data base (L2)
-Adjacency Database (L2, L1)
-Circuit Database (L2, L1)
-Level 1 Shortest Paths Database (L2, L1)
-Level 2 Shortest Paths Database (L2)
-Level 1 Forwarding Databases one per routeing
metric (L2, L1)
-Level 2 Forwarding Database one per routeing
metric (L2)
7.1 Addresses
The NSAP addresses and NETs of systems are variable
length quantities that conform to the requirements of ISO
8348/Add.2. The corresponding NPAI contained in ISO
8473 PDUs and in this protocol's PDUs (such as LSPs and
IIHs) must use the preferred binary encoding; the
ing syntax for this information may be either abstract binary
syntax or abstract decimal syntax. Any of the AFIs and
their corresponding DSP syntax may be used with this
tocol
7.1.1 NPAI Of Systems Within A Routeing
Domain
Figure 3 illustrates the structure of an encoded NSAP
dress or NET.

The structure of the NPAI will be interpreted in the
ing way by the protocol described in this international
dard:
Area Address
address of one area within a routeing domain a
variable length quantity consisting of the entire high
order part of the NPAI, excluding the ID and SEL
fields, defined below.
ID System identifier a variable length field from 1 to
8 octets (inclusive). Each routeing domain
ing this protocol shall select a single size for the ID
field and all Intermediate systems in the routeing
main shall use this length for the system IDs of all
systems in the routeing domain.
The set of ID lengths supported by an
tion is an implementation choice, provided that at
least one value in the permitted range can be
cepted. The routeing domain administrator must
sure that all ISs included in a routeing domain are
able to use the ID length chosen for that domain.
SEL NSAP Selector a 1-octet field which acts as a
lector for the entity which is to receive the PDU(this
may be a Transport entity or the Intermediate system
Network entity itself). It is the least significant (last)
octet of the NPAI
7.1.2 Deployment of Systems
For correct operation of the routeing protocol defined in
this international standard, systems deployed in a routeing
domain must meet the following requirements
a)For all systems
1)Each system in an area must have a unique
temID: that is, no two systems (IS or ES) in an
area can use the same ID value.
2)Each area address must be unique within the global
OSIE: that is, a given area address can be
ated with only one area.
3)All systems having a given value of area address
must be located in the same area.

b)Additional Requirements for Intermediate systems:
1)Each Level 2 Intermediate system within a
ing domain must have a unique value for its ID
field: that is, no two level 2 ISs in a routeing
main can have the same value in their ID fields.
c)Additional Requirements for End systems:
1)No two End systems in an area may have
dresses that match in all but the SEL fields.
d)An End system can be attached to a level 1 IS only if
its area address matches one of the entries in the
cent IS's



Addresses parameter
It is the responsibility of the routeing domain's
tive authority to enforce the requirements of 7.1.2. The
tocol defined in this international standard assumes that
these requirements are met, but has no means to verify
compliance with them
7.1.3 Manual area addresses
The use of several synonymous area addresses by an IS is
accommodated through the use of the management
ter



Addresses. This parameter is set locally
for each level 1 IS by system management; it contains a list
of all synonymous area addresses associated with the IS,
cluding the IS's area address as contained in its own NET.
Each level 1 IS distributes its



Addresses in
its Level 1 LSP's Area Addresses field, thus allowing
level 2 ISs to create a composite list of all area addresses
supported within a given area. Level 2 ISs in turn advertise
the composite list throughout the level 2 subdomain by
cluding it in their Level 2 LSP's Area Addresses field,
thus distributing information on all the area addresses
ciated with the entire routeing domain. The procedures for
establishing an adjacency between two level 1 ISs require
that there be at least one area address in common between
their two



Addresses lists, and the
dures for establishing an adjacency between a level 1 Is and
an End system require that the End system's area address
must match an entry in the IS's



Addresses
list. Therefore, it is the responsibility of System
ment to ensure that each area address associated with an IS
is included: in particular, system management must ensure
that the area addresses of all ESs and Level 1 ISs adjacent
to a given level 1 IS are included in that IS's




Addresses list
If the area address field for the destination address of an
8473 PDU or for the next entry in its source routeing
field, when present is not listed in the parameter


Addresses of a level 1 IS receiving the PDU, then the
destination system does not reside in the IS's area. Such
PDUs will be routed by level-2 routeing
7.1.4 Encoding of Level 2
When a full NSAP address is encoded according to the
ferred binary encoding specified in ISO 8348/Add.2, the

IDI is padded with leading digits (if necessary) to obtain the
maximum IDP length specified for that AFI
A Level 2 address prefix consists of a leading sub-string of
a full NSAP address, such that it matches a set of full
NSAP addresses that have the same leading sub-string.
However this truncation and matching is performed on the
NSAP represented by the abstract syntax of the NSAP
dress, not on the encoded (and hence padded) form.11An example
prefix matching may be found in annex B, clause B.1.

Level 2 address prefixes are encoded in LSPs in the same
way as full NSAP addresses, except when the end of the
prefix falls within the IDP. In this case the prefix is directly
encoded as the string of semi-octets with no padding.
7.1.5 Comparison of
Unless otherwise stated, numerical comparison of addresses
shall be performed on the encoded form of the address, by
padding the shorter address with trailing zeros to the length
of the longer address, and then performing a numerical
comparison
The addresses to which this precedure applies include
NSAP addresses, Network Entity Titles, and SNPA
dresses
7.2 The Decision
This process uses the database of Link State information to
calculate the forwarding database(s), from which the
warding process can know the proper next hop for each
NPDU. The Level 1 Link State Database is used for
lating the Level 1 Forwarding Database(s), and the Level 2
Link State Database is used for calculating the Level 2
warding Database(s).
7.2.1 Input and

-Link State Database This database is a set of
mation from the latest Link State PDUs from all
known Intermediate systems (within this area, for
Level 1, or within the level 2 subdomain, for Level 2).
This database is received from the Update Process
-Notification of an Event This is a signal from the
Update Process that a change to a link has occurred
somewhere in the domain

-Level 1 Forwarding Databases one per routeing

-(Level 2 Intermediate systems only) Level 2
ing Databases one per routeing
-(Level 2 Intermediate systems only) The Level 1
cision Process informs the Level 2 Update Process of
the ID of the Level 2 Intermediate system within the
area with lowest ID reachable with real level 1 links

(as opposed to a virtual link consisting of a path
through the level 2 subdomain)
-(Level 2 Intermediate systems only) If this
ate system is the Partition Designated Level 2
mediate system in this partition, the Level 2 Decision
Process informs the Level 1 Update Process of the
values of the default routeing metric to and ID of the
partition designated level 2 Intermediate system in
each other partition of this area.
7.2.2 Routeing
There are four routeing metrics defined, corresponding to
the four possible orthogonal qualities of service defined by
the QoS Maintenance field of ISO 8473. Each circuit
nating from an Intermediate system shall be assigned a
value for one or more of these metrics by System
ment. The four metrics are as follows
a)Default metric: This is a metric understood by every
Intermediate system in the domain. Each circuit shall
have a positive integral value assigned for this metric.
The value may be associated with any objective
tion of the circuit, but by convention is intended to
measure the capacity of the circuit for handling traffic,
for example, its throughput in bits-per-second. Higher
values indicate a lower capacity
b)Delay metric: This metric measures the transit delay
of the associated circuit. It is an optional metric, which
if assigned to a circuit shall have a positive integral
value. Higher values indicate a longer transit delay
c)Expense metric: This metric measures the monetary
cost of utilising the associated circuit. It is an optional
metric, which if assigned to a circuit shall have a
tive integral value22The path computation algorithm utilised in
International Standard requires that all circuits be assigned
positive value for a metric. Therefore, it is
not possible to represent a free circuit by a zero value of the
metric. By convention, the value 1 is used to indicate a free circuit
. Higher values indicate a larger
monetary expense
d)Error metric: This metric measures the residual error
probability of the associated circuit. It is an optional
metric, which if assigned to a circuit shall have a non
zero value. Higher values indicate a larger probability
of undetected errors on the circuit
NOTE - The decision process combines metric values by
simple addition. It is important, therefore, that the values of
the metrics be chosen accordingly
Every Intermediate system shall be capable of calculating
routes based on the default metric. Support of any or all of
the other metrics is optional. If an Intermediate system
ports the calculation of routes based on a metric, its update
process may report the metric value in the LSPs for the
sociated circuit; otherwise, the IS shall not report the
ric
When calculating paths for one of the optional routeing
metrics, the decision process only utilises LSPs with a
value reported for the corresponding metric. If no value is

associated with a metric for any of the IS's circuits the
tem shall not calculate routes based on that metric
NOTE - A consequence of the above is that a system
able via the default metric may not be reachable by another
metric
See 7.4.2 for a description of how the forwarding process
selects one of these metrics based on the contents of the
ISO 8473 QoS Maintenance option
Each of the four metrics described above may be of two
types: an Internal metric or an External metric. Internal
metrics are used to describe links/routes to destinations
ternal to the routeing domain. External metrics are used to
describe links/routes to destinations outside of the routeing
domain. These two types of metrics are not directly
rable, except the internal routes are always preferred over
external routes. In other words an internal route will always
be selected even if an external route with lower total cost
exists
7.2.3 Broadcast
Instead of treating a broadcast subnetwork as a fully
nected topology, the broadcast subnetwork is treated as a
pseudonode, with links to each attached system. Attached
systems shall only report their link to the pseudonode. The
designated Intermediate system, on behalf of the
pseudonode, shall construct Link State PDUs reporting the
links to all the systems on the broadcast subnetwork with a
zero value for each supported routeing metric33They are set to
metric values since they have already been assigned metrics by
link to the pseudonode. Assigning a non-zero value in the
pseudonode LSP would have the effect of doubling the actual value

The pseudonode shall be identified by the sourceID of the
Designated Intermediate system, followed by a non-zero
pseudonodeID assigned by the Designated Intermediate
system. The pseudonodeID is locally unique to the
nated Intermediate system
Designated Intermediate systems are determined separately
for level 1 and level 2. They are known as the LAN Level 1
Designated IS and the LAN Level 2 Designated IS
tively. See 8.4.4.
An Intermediate system may resign as Designated
diate System on a broadcast circuit either because it (or it's
SNPA on the broadcast subnetwork) is being shut down or
because some other Intermediate system of higher priority
has taken over that function. When an Intermediate system
resigns as Designated Intermediate System, it shall initiate a
network wide purge of its pseudonode Link State PDU(s)
by setting their Remaining Lifetime to zero and performing
the actions described in 7.3.16.4. A LAN Level 1
nated Intermediate System purges Level 1 Link State PDUs
and a LAN Level 2 Designated Intermediate System purges
Level 2 Link State PDUs. An Intermediate system which
has resigned as both Level 1 and Level 2 Designated
mediate System shall purge both sets of LSPs

When an Intermediate system declares itself as designated
Intermediate system and it is in possession of a Link State
PDU of the same level issued by the previous Designated
Intermediate System for that circuit (if any), it shall initiate
a network wide purge of that (or those) Link State PDU(s)
as above
7.2.4
Two Intermediate systems are not considered neighbours
unless each reports the other as directly reachable over one
of their SNPAs. On a Connection-oriented subnetwork
(either point-to-point or general topology), the two
diate systems in question shall ascertain their neighbour
lationship when a connection is established and hello PDUs
exchanged. A malfunctioning IS might, however, report
other IS to be a neighbour when in fact it is not. To detect
this class of failure the decision process checks that each
link reported as up in a LSP is so reported by both
mediate systems. If an Intermediate system considers a link
down it shall not mention the link in its Link State PDUs
On broadcast subnetworks, this class of failure shall be
tected by the designated IS, which has the responsibility to
ascertain the set of Intermediate systems that can all
municate on the subnetwork. The designated IS shall
clude these Intermediate systems (and no others) in the
Link State PDU it generates for the pseudonode
ing the broadcast subnetwork
7.2.5 Multiple LSPs for the same
The Update process is capable of dividing a single logical
LSP into a number of separate PDUs for the purpose of
conserving link bandwidth and processing (see 7.3.4). The
Decision Process, on the other hand, shall regard the LSP
with LSP Number zero in a special way. If the LSP with
LSP Number zero and remaining lifetime > 0, is not present
for a particular system then the Decision Process shall not
process any LSPs with non-zero LSP Number which may
be stored for that system.
The following information shall be taken only from the LSP
with LSP Number zero. Any values which may be present
in other LSPs for that system shall be disregarded by the
Decision Process
a)The setting of the LSP Database Overload bit.
b)The value of the IS Type field.
c)The Area Addresses option
7.2.6 Routeing Algorithm
The routeing algorithm used by the Decision Process is a
shortest path first (SPF) algorithm. Instances of the
rithm are run independently and concurrently by all
mediate systems in a routeing domain. Intra-Domain
ing of a PDU occurs on a hop-by-hop basis: that is, the
gorithm determines only the next hop, not the complete
path, that a data PDU will take to reach its destination. To
guarantee correct and consistent route computation by
every Intermediate system in a routeing domain, this
national Standard depends on the following properties

a)All Intermediate systems in the routeing domain
verge to using identical topology information;
b)Each Intermediate system in the routeing domain
erates the same set of routes from the same input
pology and set of metrics
The first property is necessary in order to prevent
tent, potentially looping paths. The second property is
essary to meet the goal of determinism stated in 6.6.
A system executes the SPF algorithm to find a set of legal
paths to a destination system in the routeing domain. The
set may consist of
a)a single path of minimum metric sum: these are
termed minimum cost paths
b)a set of paths of equal minimum metric sum: these are
termed equal minimum cost paths;
c)a set of paths which will get a PDU closer to its
nation than the local system: these are called
stream paths
Paths which do not meet the above conditions are illegal
and shall not be used
The Decision Process, in determining its paths, also
tains the identity of the adjacency which lies on the first
hop to the destination on each path. These adjacencies are
used to form the Forwarding Database, which the
ing process uses for relaying PDUs
Separate route calculations are made for each pairing of a
level in the routeing hierarchy (i.e. L1 and L2) with a
ported routeing metric. Since there are four routeing metrics
and two levels some systems may execute multiple
stances of the SPF algorithm. For example
-if an IS is a L2 Intermediate system which supports all
four metrics and computes minimum cost paths for all
metrics, it would execute the SPF calculation eight
times
-if an IS is a L1 Intermediate system which supports all
four metrics, and additionally computes downstream
paths, it would execute the algorithm 4 W (number of
neighbours + 1) times
Any implementation of an SPF algorithm meeting both the
static and dynamic conformance requirements of clause 12
of this International Standard may be used. Recommended
implementations are described in detail in Annex C
7.2.7 Removal of Excess
When there are more than







Splits legal
paths to a destination, this set shall be pruned until only








Splits remain. The Intermediate system
shall discriminate based upon
NOTE - The precise precedence among the paths is
fied in order to meet the goal of determinism defined in 6.6.

-adjacency type: Paths associated with End system or
level 2 reachable address prefix adjacencies are
tained in preference to other
-metric sum: Paths having a lesser metric sum are
tained in preference to paths having a greater metric
sum. By metric sum is understood the sum of the
metrics along the path to the destination
-neighbour ID: where two or more paths are
ated with adjacencies of the same type, an adjacency
with a lower neighbour ID is retained in preference to
an adjacency with a higher neighbour id
-circuit ID: where two or more paths are associated
with adjacencies of the same type, and same
bour ID, an adjacency with a lower circuit ID is
tained in preference to an adjacency with a higher
cuit ID, where circuit ID is the value of
7ptPtCircuitID for non-broadcast circuits,
7l1CircuitID for broadcast circuits when running
the Level 1 Decision Process, and
7l2CircuitID for broadcast ci