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


                OSI IS-IS Intra-domain Routing Protocol

Status of this Memo

   This RFC is a republication of ISO DP 10589 as a service to the
   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 official
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 exchange
between systems Interme diate 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) Technologies de l'information Communication de donnies et
ichange d'information entre systhmes Protocole intra-domain de routage
d'un systhme intermediare ` un systhme intermediare ` utiliser
conjointement avec le protocole fournissant le service de riseau en
mode sans connexion (ISO 8473) UDC 00000.000 : 000.0000000000
Descriptors:

Contents
        Introduction            iv
        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

Introduction

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

Information technology

Telecommunications and information exchange between systems
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)

1 Scope and Field of Application

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

This Standard specifies:

a)procedures for the transmission of configuration and
routeing information between network entities resid
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 infor
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 un
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 References

2.1  Normative References

The following standards contain provisions which, through reference in
this text, constitute provisions of this Interna tional Standard.  At
the time of publication, the editions in dicated were valid. All
standards are subject to revision, and parties to agreements based on
this International Stan dard are encouraged to investigate the
possibility of apply ing the most recent editions of the standards
listed below.  Members of IEC and ISO maintain registers of currently
valid International Standards.  ISO 7498:1984, Information processing
systems Open Systems Interconnection Basic Reference Model.  ISO
7498/Add.1:1984, Information processing systems Open Systems
Interconnection Basic Reference Model Addendum 1: Connectionless-mode
Transmission.  ISO 7498-3:1989, Information processing systems Open
Systems Interconnection Basic Reference Model Part 3: Naming and
Addressing.  ISO 7498-4:1989, Information processing systems Open
Systems Interconnection Basic Reference Model Part 4: Management
Framework.  ISO 8348:1987, Information processing systems Data
communications Network Service Definition.  ISO 8348/Add.1:1987,
Information processing systems Data communications Network Service
Definition Addendum 1: Connectionless-mode transmission.  ISO
8348/Add.2:1988, Information processing systems Data communications
Network Service Definition Addendum 2: Network layer addressing.  ISO
8473:1988, Information processing systems Data communications Protocol
for providing the connectionless-mode network service.  ISO
8473/Add.3:1989, Information processing systems Telecommunications and
information exchange between
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  Tele
communications and information exchange between sys
tems  End system to Intermediate system Routeing ex
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 equipment
ISO 8802:1988, Information processing systems  Tele
communications and information exchange between sys
tems  Local area networks.
ISO/TR 9575:1989, Information technology   Telecom
munications and information exchange between systems
 OSI Routeing Framework.
ISO/TR 9577:1990, Information technology   Telecom
munications and information exchange between systems
 Protocol Identification in the Network Layer.
ISO/IEC DIS 10165-4:, Information technology  Open
systems interconnection  Management Information Serv
ices  Structure of Management Information Part 4:
Guidelines for the Definition of Managed Objects.
ISO/IEC 10039:1990, IPS-T&IEBS  MAC Service Defini
tion.

2.2 Other References

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 In
formation, Computer Networks, Dec. 1983. Also in IEEE
INFOCOM 83, April 1983.

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

3 Definitions

3.1 Reference Model definitions

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

a)Network Layer
b)Network Service access point
c)Network Service access point address
d)Network entity
e)Routeing
f)Network protocol
g)Network relay
h)Network protocol data unit

3.2 Network Layer architecture
definitions

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


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

3.3 Network Layer addressing
definitions

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


a)Subnetwork address
b)Subnetwork point of attachment
c)Network Entity Title
3.4 Local Area Network Definitions
 This International Standard makes use of the following
terms defined in ISO 8802:
a)Multi-destination address
b)Media access control
c)Broadcast medium
3.5 Routeing Framework Definitions
 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 Definitions
For the purposes of this International Standard, the follow
ing definitions apply:
3.6.1
Area: A routeing subdomain which maintains de
tailed routeing information about its own internal
composition, and also maintains routeing informa
tion which allows it to reach other routeing subdo
mains. It corresponds to the Level 1 subdomain.
3.6.2
Neighbour: An adjacent system reachable by tra
versal of a single subnetwork by a PDU.
3.6.3
Adjacency: A portion of the local routeing infor
mation which pertains to the reachability of a sin
gle neighbour ES or IS over a single circuit.
Adjacencies are used as input to the Decision Proc
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 informa
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 du
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 Interme
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 sup
ports an arbitrary number of End systems and In

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 sys
tems and Intermediate systems, but does not sup
port a convenient multi-destination connectionless
trans

mission facility, as does a broadcast sub

net

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

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


4.3 Addresses
AFI     Authority and Format Indicator
DSP     Domain Specific Part
IDI     Initial Domain Identifier
IDP     Initial Domain Part
NET     Network Entity Title
NSAP    Network Service Access Point
SNPA    Subnetwork Point of Attachment

4.4 Miscellaneous
DA      Dynamically Assigned
DED     Dynamically Established Data link
DTE     Data Terminal Equipment
ES      End System
IS      Intermediate System
L1      Level 1
L2      Level 2
LAN     Local Area Network
MAC     Media Access Control
NLPID   Network Layer Protocol Identifier
PCI     Protocol Control Information
QoS     Quality of Service
SN      Subnetwork
SNAcP   Subnetwork Access Protocol
SNDCP   Subnetwork Dependent Convergence Protocol
SNICP   Subnetwork Independent Convergence Proto
col
SRM     Send Routeing Message
SSN     Send Sequence Numbers Message
SVC     Switched Virtual Circuit
5 Typographical Conventions
This International Standard makes use of the following ty
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 Protocol
6.1 System Types
There are the following types of system:
End Systems: These systems deliver NPDUs to other sys
tems and receive NPDUs from other systems, but do
not relay NPDUs. This International Standard does
not specify any additional End system functions be
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 destina
tion systems. They route directly to systems within
their own area, and route towards a level 2 Interme
diate system when the destination system is in a dif
ferent area.
Level 2 Intermediate Systems: These systems act as Level 1
Intermediate systems in addition to acting as a sys
tem in the subdomain consisting of level 2 ISs. Sys
tems in the level 2 subdomain route towards a desti
nation area, or another routeing domain.
6.2 Subnetwork Types
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 in
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 estab
lished upon system management action and

cleared only on system management action (or
failure).
ii)dynamically assigned (DA): The call is estab
lished upon receipt of traffic, and brought
down on timer expiration when idle. The ad
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 cir
cuit.
All subnetwork types are treated by the Subnetwork Inde
pendent functions as though they were connectionless
subnetworks, using the Subnetwork Dependent Conver
gence functions of ISO 8473 where necessary to provide a
connectionless subnetwork service. The  Subnetwork De
pendent functions do, however, operate differently on
connectionless and connection-oriented subnetworks.
6.3 Topologies
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 pro
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 associ
ated. Where the subnetwork to which this SNPA is con
nected is a general topology subnetwork supporting dy
namically established data links, the prefix also has associ
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 al
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 Inter
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 Addresses
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 configura
tion and be subject to inferior routeing performance.
6.5  Functional Organisation
The intra-domain ISIS routeing functions are divided into
two groups
-Subnetwork Independent Functions
-Subnetwork Dependent Functions
6.5.1 Subnetwork Independent Functions
The Subnetwork Independent Functions supply full-duplex
NPDU transmission between any pair of neighbour sys
tems. They are independent of the specific subnetwork or
data link service operating below them, except for recognis
ing two generic types of subnetworks:
-General Topology Subnetworks, which include
HDLC point-to-point, HDLC multipoint, and dynami
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 iden
tified
-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 route
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 follow
ing specific functions:
7It extracts and interprets the routeing PCI in an
NPDU.
7It performs NPDU forwarding based on the desti
nation address.
7It manages the characteristics of the path. If a sys
tem or link fails on a path, it finds an alternate
route.
7It interfaces with the subnetwork dependent func
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 un
reachable or when the NPDU would have needed

to be segmented and the NPDU requested no seg
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 characteris
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 to
7Determine neighbour Network entity title(s) and
SNPA address(es)
7Determine the SNPA address(s) of operational In
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 es
tablished data links
6.6 Design Goals
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 com
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 route
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 ad
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 dis

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 effi
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 toler
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 con
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 perform
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 compo
nent prevents buffer deadlock.
-Very Large Domains. With hierarchical routeing, and
a very large address space, domains of essentially un
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 physi
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 Trans
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 parti
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 is
not used here because of possible confusion with the more general usage
of the term to
indicate path cost according to any routeing metric.
, and residual error probability of ISO 8473
are support