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

Splits, then remove excess adja
cencies, as described in 7.2.7.
3)If x < dist(P,N), do nothing.
4)If x > dist(P,N),  remove aN,x,{Adj(N)}q from 
TENT and add  aN,dist(P,N),{Adj(P)}q.
e)If no triple aN, x,{Adj(N)}q is in TENT, then add aN, 
dist(P,N),{P}q to TENT.
Step 2: If TENT is empty, stop, else:
a)Find the element aP,x,{Adj(P)}q,  with minimal x as 
follows:
1)If an element a*,tentlength,*q 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 ten
tlength and repeat  Step 2. 
2)Remove aP,tentlength,{Adj(P)}q from TENT.
3)Add aP,d(P),{Adj(P)}q  to PATHS.
4)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 aAREA.P, d(P), {adj(P)}q 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 Level 2 LSP 
and appending P's ID.
5)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 and the set of area ad
dresses with zero cost. 
 
C.3 Forwarding Process
C.3.1 Example pseudo-code for the forwarding 
procedure described in 7.4.3
This procedure chooses, from the Level 1 forwarding data
base  if level is level1, or from the Level 2 forwarding 
database  if level is level2, an adjacency on which to for
ward PDUs for destination dest. A pointer to the adjacency 
is returned in adj, and the procedure returns the value 
True. If no suitable adjacency exists the procedure returns 
the value False, in which case a call should be made to 
Drop(Destination Address Unreachable, octetNumber).
If queue length values are available to the forwarding proc
ess, the minimal queue length of all candidate circuits is 
chosen, otherwise, they are used in round robin fashion.
PROCEDURE Forward(
level: (level1, level2),  
dest: NetworkLayerAddress, 
VAR adj: POINTER TO adjacency) : 
BOOLEAN
 
VAR  
adjArray: ARRAY OF 
ForwardingDatabaseRecords; 
temp, index, minQueue: CARDINAL; 
 
BEGIN 
(*Set adjArray to appropriate database} *) 
IF level = level1 THEN 
adjArray := level1ForwardingDatabase 
ELSE 
adjArray := level2ForwardingDatabase 
END;
 (*Perform appropriate hashing function to obtain an 
index into the database *)
 IF Hash(level, dest, index) THEN 
IF adjArray[index].splits > 0 THEN
(*Find minimum queue size for all equal cost 
paths *)
minQueue := MaxUnsigned;
temp := adjArray[index].lastChosen + 1; 	
(*start off after last time *)
FOR i := 1 TO adjArray[index].splits DO
(*for all equal cost paths to dest *)
IF temp > adjArray[index].splits THEN
(*after end of valid entries, wrap to first 
*)
temp := 1
ELSE
temp := temp + 1
END;
IF 
QueueSize(adjArray[index].nextHop[temp]) 
< minQueue THEN
minQueue := 
QueueSize(adjArray[index].nextHop[tem
p]);
adj := adjArray[index].nextHop[temp];
adjArray[index].lastChosen := temp;
END;
Forward := true
END;
 
ELSE
Forward := false (*There must be at least one 
valid output adjacency *)
END
ELSE 
Forward := false (*Hash returned destination 
unknown *)
END 
END forward; 
 
 
Annex D 
Congestion Control and Avoidance
(This annex is informative) 
 
D.1 Congestion Control
The transmit management subroutine handles congestion 
control. Transmit management consists of the following 
components:
Square root limiter. Reduces buffer occupancy 
time per PDU by using a square root limiter algo
rithm. The square root limiter also queues PDUs for 
an output circuit, and prevents buffer deadlock by 
discarding PDUs when the buffer pool is exhausted. 
Clause D.1.1 specifies the Square Root Limiter 
Process. 
Originating PDU limiter. Limits originating NPDU 
traffic when necessary to ensure that transit NPDUs 
are not rejected. An originating NPDU is an NPDU 
resulting from an NSDU from the Transport at this 
ES. A transit NPDU is an NPDU from another sys
tem to be relayed to another destination ES.
Flusher. Flushes PDUs queued for an adjacency that 
has gone down.
Information for higher layer (Transport) congestion control 
procedures is provided by the setting of the congestion ex
perienced bit in the forwarded data NPDUs.
D.1.1 Square Root Limiter
The square root limiter discards a data NPDU by calling the 
ISO 8473 discard PDU function with the reason  PDU 
Discarded due to Congestion when the number of data 
NPDUs on the circuit output queue exceeds the discard 
threshold, Ud.  Ud is given as follows:=
where:
Nb = Number of Routeing Layer buffers 
(maximumBuffers) for all output circuits.
Nc = Number of active output circuits (i.e. Circuits in state 
On).
The output queue is a queue of buffers containing data 
NPDUs which have been output to that circuit by the for
warding process, and which have not yet been transmitted 
by the circuit. It does not include NPDUs which are held 
by the data link layer for the purpose of retransmission.
Where a data NPDU is to be fragmented by this Intermedi
ate system over this circuit, each fragment shall occupy a 
 
separate buffer and shall be counted as such in the queue 
length. If the addition of all the buffers required for the 
fragmentation of a single input data NPDU would cause the 
discard threshold for that queue to be exceeded, it is recom
mended that all those fragments (including those which 
could be added without causing the threshold to be ex
ceeded) be discarded. 
D.1.2 Originating PDU Limiter
TEMPORARY NOTE - Strictly this function is an End Sys
tem function. However it is closely coupled to the routeing 
function, particularly in the case of real systems which are 
performing the functions of both an Intermediate System 
and an End System (i.e. systems which can both initiate and 
terminate data NPDUs and perform relaying functions). 
Therefore, until a more appropriate location for this infor
mation can be determined, this function is described here. 
The originating PDU limiter first distinguishes between 
originating NPDUs and transit NPDUs. It then imposes a 
limit on the number of buffers that originating NPDUs can 
occupy on a per circuit basis. In times of heavy load, origi
nating NPDUs may be rejected while transit NPDUs con
tinue to be routed. This is done because originating NPDUs 
have a relatively short wait, whereas transit NPDUs, if re
jected, have a long wait  a transport retransmission period. 
The originating PDU limiter accepts as input:
-An NSDU received from Transport Layer 
-A transmit complete signal from the circuit for an ISO 
8473 Data PDU.
The originating PDU limiter produces the following as out
put:
-PDU accepted 
-PDU rejected 
-Modifications to originating PDU counter
There is a counter, N, and an originating PDU limit, 
originatingQueueLimit, for each active output circuit. 
Each N is initialised to 0. The originatingQueueLimit is 
set by management to the number of buffers necessary to 
prevent the circuit from idling. 
D.1.3 Flusher
The flusher ensures that no NPDU is queued on a circuit 
whose state is not ON, or on a non-existent adjacency, or 
one whose state is not  Up. 
 
D.2 Congestion Avoidance
D.2.1 Buffer Management
The Forwarding Process supplies and manages the buffers 
necessary for relaying. PDUs shall be discarded if buffer 
thresholds are exceeded. If the average queue length on the 
input circuit or the forwarding processor or the output cir
cuit exceeds QueueThreshold, the congestion experi
enced bit shall be set in the QoS maintenance option of the 
forwarded data PDU (provided the QoS maintenance option 
is present). 
 

Security Considerations

  Security issues are not discussed in this memo.

Author's Address

   David R. Oran
   Digital Equipment Corporation
   LKG 1-2/a 19
   550 King Street
   Littleton, MA 01460

   Email: Oran@Oran.enet.dec.com

   Phone:  (508) 4866-7377