State PDUs throughout the domain (or in the case of
Level 1, throughout the area).
The basic mechanism is flooding, in which each Intermedi
ate system propagates to all its neighbour Intermediate sys
tems except that neighbour from which it received the
PDU. Duplicates are detected and dropped.
Link state PDUs are received from the Receive Process.
The maximum size control PDU (Link State PDU or Se
quence Numbers PDU) which a system expects to receive
shall be Receive
LSP
Buffer
Size octets. (i.e. the Update
process must provide buffers of at least this size for the re
ception, storage and forwarding of received Link State
PDUs and Sequence Numbers PDUs.) If a control PDU
larger than this size is received, it shall be treated as if it
had an invalid checksum (i.e. ignored by the Update Proc
ess and a corruptedLSPReceived notification generated).
Upon receipt of a Link State PDU the Update Process shall
perform the following functions:
a)Level 2 Link State PDUs shall be propagated on cir
cuits which have at least one Level 2 adjacency.
b)Level 1 Link State PDUs shall be propagated on cir
cuits which have at least one Level 1 adjacency or at
least one Level 2 adjacency not marked Level 2
only.
c)When propagating a Level 1 Link State PDU on a
broadcast subnetwork, the IS shall transmit to the
multi-destination subnetwork address AllL1IS.
d)When propagating a Level 2 Link State PDU on a
broadcast subnetwork, the IS shall transmit to the
multi-destination subnetwork address AllL2IS.
NOTE When propagating a Link State PDU on a
general topology subnetwork the Data Link Address
is unambiguous (because Link State PDUs are not
propagated across Dynamically Assigned circuits).
e)An Intermediate system receiving a Link State PDU
with an incorrect LSP Checksum or with an invalid
PDU syntax shall
1)log a circuit notification, corruptedLSPRe
ceived,
2)overwrite the Checksum and Remaining Lifetime
with 0, and
3)treat the Link State PDU as though its Remaining
Lifetime had expired (see 7.3.16.4.)
f)A Intermediate system receiving a Link State PDU
which is new (as identified in 7.3.16) shall
1)store the Link State PDU into Link State database,
and
2)mark it as needing to be propagated upon all cir
cuits except that upon which it was received.
g)When a Intermediate system receives a Link State
PDU from source S, which it considers older than the
one stored in the database for S, it shall set the
SRMflag for S's Link State PDU associated with the
circuit from which the older Link State PDU was re
ceived. This indicates that the stored Link State PDU
needs to be sent on the link from which the older one
was received.
h)When a system receives a Link State PDU which is
the same (not newer or older) as the one stored, the In
termediate system shall
1)acknowledge it if necessary, as described in 7.3.17,
and
2)clear the SRMflag for that circuit for that Link
State PDU.
i)A Link State PDU received with a zero checksum
shall be treated as if the Remaining Lifetime were 0.
The age, if not 0, shall be overwritten with 0.
The Update Process scans the Link State Database for Link
State PDUs with SRMflags set. When one is found, pro
vided the timestamp lastSent indicates that it was propa
gated no more recently than min
i
mum
LSP
Trans
mis
sion
Int
er
val, the IS shall
a)transmit it on all circuits with SRMflags set, and
b)update lastSent.
7.3.15 Manipulation of SRM and SSN Flags
For each Link State PDU, and for each circuit over which
routeing messages are to be exchanged (i.e. not on DA cir
cuits), there are two flags:
Send Routeing Message (SRMflag) if set, indicates that
Link State PDU should be transmitted on that cir
cuit. On broadcast circuits SRMflag is cleared as
soon as the LSP has been transmitted, but on non-
broadcast circuits SRMflag is only cleared on recep
tion of a Link State PDU or Sequence Numbers
PDU as described below.
SRMflag shall never be set for an LSP with se
quence number zero, nor on a circuit whose exter
nalDomain attribute is True (See 7.3.15.2).
Send Sequence Numbers (SSNflag) if set, indicates that
information about that Link State PDU should be in
cluded in a Partial Sequence Numbers PDU trans
mitted on that circuit. When the Sequence Numbers
PDU has been transmitted SSNflag is cleared. Note
that the Partial Sequence Numbers PDU serves as an
acknowledgement that a Link State PDU was re
ceived.
SSNflag shall never be set on a circuit whose ex
ternalDomain attribute is True.
7.3.15.1 Action on Receipt of a Link State PDU
When a Link State PDU is received on a circuit C, the IS
shall perform the following functions
a)Perform the following PDU acceptance tests:
1)If the LSP was received over a circuit whose ex
ternalDomain attribute is True, the IS shall dis
card the PDU.
2)If the ID Length field of the PDU is not equal to
the value of the IS's routeingDomainIDLength,
the PDU shall be discarded and an iDField
LengthMismatch notification generated.
3)If this is a level 1 LSP, and the set of areaRe
ceivePasswords is non-null, then perform the
following tests:
i)If the PDU does not contain the Authentica
tion Information field then the PDU shall be
discarded and an authenticationFailure no
tification generated.
ii)If the PDU contains the Authentication In
formation field, but the Authentication
Type is not equal to Password, then the
PDU shall be accepted unless the IS imple
ments the authenticatiion procedure indicated
by the Authentication Type. In this case
whether the IS accepts or ignores the PDU is
outside the scope of this International Stan
dard.
iii)Otherwise, the IS shall compare the password
in the received PDU with the passwords in the
set of areaReceivePasswords, augmented
by the value of the areaTransmitPassword.
If the value in the PDU matches any of these
passwords, the IS shall accept the PDU for
further processing. If the value in the PDU
does not match any of the above values, then
the IS shall ignore the PDU and generate an
authenticationFailure notification.
4)If this is a level 2 LSP, and the set of domainRe
ceivePasswords is non-null, then perform the
following tests:
i)If the PDU does not contain the Authentica
tion Information field then the PDU shall be
discarded and an authenticationFailure no
tification generated.
ii)If the PDU contains the Authentication In
formation field, but the Authentication
Type is not equal to Password, then the
PDU shall be accepted unless the IS imple
ments the authenticatiion procedure indicated
by the Authentication Type. In this case
whether the IS accepts or ignores the PDU is
outside the scope of this International Stan
dard.
iii)Otherwise, the IS shall compare the password
in the received PDU with the passwords in the
set of domainReceivePasswords, aug
mented by the value of the domainTransmit
Password. If the value in the PDU matches
any of these passwords, the IS shall accept the
PDU for further processing. If the value in the
PDU does not match any of the above values,
then the IS shall ignore the PDU and generate
an authenticationFailure notification.
b)If the LSP has zero Remaining Lifetime, perform the
actions described in 7.3.16.4.
c)If the source S of the LSP is an IS or pseudonode for
which all but the last octet are equal to the systemID
of the receiving Intermediate System, and the receiv
ing Intermediate System does not have that LSP in its
database, or has that LSP, but no longer considers it to
be in the set of LSPs generated by this system (e.g. it
was generated by a previous incarnation of the sys
tem), then initiate a network wide purge of that LSP as
described in 7.3.16.4.
d)If the source S of the LSP is a system (pseudonode or
otherwise) for which the first ID Length octets are
equal to the systemID of the receiving Intermediate
system, and the receiving Intermediate system has an
LSP in the set of currently generated LSPs from that
source in its database (i.e. it is an LSP generated by
this Intermediate system), perform the actions de
scribed in 7.3.16.1.
e)Otherwise, (the source S is some other system),
1)If the LSP is newer than the one in the database, or
if an LSP from that source does not yet exist in the
database:
i)Store the new LSP in the database, overwriting
the existing database LSP for that source (if
any) with the received LSP.
ii)Set SRMflag for that LSP for all circuits
other than C.
iii)Clear SRMflag for C.
iv)If C is a non-broadcast circuit, set SSNflag
for that LSP for C.
v)Clear SSNflag for that LSP for the circuits
other than C.
2)If the LSP is equal to the one in the database (same
Sequence Number, Remaining Lifetimes both zero
or both non-zero, same checksums):
i)Clear SRMflag for C.
ii)If C is a non-broadcast circuit, set SSNflag
for that LSP for C.
3)If the LSP is older than the one in the database:
i)Set SRMflag for C.
ii)Clear SSNflag for C.
When storing a new LSP, the Intermediate system shall first
ensure that it has sufficient memory resources to both store
the LSP and generate whatever internal data structures will
be required to process the LSP by the Update Process. If
these resources are not available the LSP shall be ignored.
It shall neither be stored nor acknowledged. When an LSP
is ignored for this reason the IS shall enter the Waiting
State. (See 7.3.19).
When attempting to store a new version of an existing LSP
(with the same LSPID), which has a length less than or
equal to that of the existing LSP, the existing LSP shall be
removed from the routeing information base and the new
LSP stored as a single atomic action. This ensures that such
an LSP (which may be carrying the LSP Database Overload
indication from an overloaded IS) will never be ignored as
a result of a lack of memory resources.
7.3.15.2 Action on Receipt of a Sequence Numbers
PDU
When a Sequence Numbers PDU (Complete or Partial, see
7.3.17) is received on circuit C the IS shall perform the fol
lowing functions:
a)Perform the following PDU acceptance tests:
1)If the SNP was received over a circuit whose ex
ternalDomain attribute is True, the IS shall dis
card the PDU.
2)If the ID Length field of the PDU is not equal to
the value of the IS's routeingDomainIDLength,
the PDU shall be discarded and an iDField
Length
Mismatch notification generated.
3)If this is a level 1 SNP and the set of areaRe
ceivePasswords is non-null, then perform the
following tests:
i)If the PDU does not contain the Authentica
tion Information field then the PDU shall be
discarded and an authenticationFailure no
tification generated.
ii)If the PDU contains the Authentication In
formation field, but the Authentication
Type is not equal to Password, then the
PDU shall be accepted unless the IS imple
ments the authenticatiion procedure indicated
by the Authentication Type. In this case
whether the IS accepts or ignores the PDU is
outside the scope of this International Stan
dard.
iii)Otherwise, the IS shall compare the password
in the received PDU with the passwords in the
set of areaReceivePasswords, augmented
by the value of the areaTransmitPassword.
If the value in the PDU matches any of these
passwords, the IS shall accept the PDU for
further processing. If the value in the PDU
does not match any of the above values, then
the IS shall ignore the PDU and generate an
authenticationFailure notification.
4)If this is a level 2 SNP, and the set of domainRe
ceivePasswords is non-null, then perform the
following tests:
i)If the PDU does not contain the Authentica
tion Information field then the PDU shall be
discarded and an authenticationFailure no
tification generated.
ii)If the PDU contains the Authentication In
formation field, but the Authentication
Type is not equal to Password, then the
PDU shall be accepted unless the IS imple
ments the authenticatiion procedure indicated
by the Authentication Type. In this case
whether the IS accepts or ignores the PDU is
outside the scope of this International Stan
dard.
iii)Otherwise, the IS shall compare the password
in the received PDU with the passwords in the
set of domainReceivePasswords, aug
mented by the value of the domainTransmit
Password. If the value in the PDU matches
any of these passwords, the IS shall accept the
PDU for further processing. If the value in the
PDU does not match any of the above values,
then the IS shall ignore the PDU and generate
an authenticationFailure notification.
b)For each LSP reported in the Sequence Numbers
PDU:
1)If the reported value equals the database value and
C is a non-broadcast circuit, Clear SRMflag for C
for that LSP.
2)If the reported value is older than the database
value, Clear SSNflag, and Set SRMflag.
3)If the reported value is newer than the database
value, Set SSNflag, and if C is a non-broadcast
circuit Clear SRMflag.
4)If no database entry exists for the LSP, and the re
ported Remaining Lifetime, Checksum and Se
quence Number fields of the LSP are all non-
zero, create an entry with sequence number 0 (see
7.3.16.1), and set SSNflag for that entry and cir
cuit C. Under no circumstances shall SRMflag be
set for such an LSP with zero sequence number.
NOTE - This is because possessing a zero sequence
number LSP is semantically equivalent to having no
information about that LSP. If such LSPs were
propagated by setting SRMflag it would result in an
unnecessary consumption of both bandwidth and
memory resources.
c)If the Sequence Numbers PDU is a Complete Se
quence Numbers PDU, Set SRMflags for C for all
LSPs in the database (except those with zero sequence
number or zero remaining lifetime) with LSPIDs
within the range specified for the CSNP by the Start
LSPID and End LSPID fields, which were not men
tioned in the Complete Sequence Numbers PDU (i.e.
LSPs this system has, which the neighbour does not
claim to have).
7.3.15.3 Action on expiration of Complete SNP
Interval
The IS shall perform the following actions every
CompleteSNPInterval seconds for circuit C:
a)If C is a broadcast circuit, then
1)If this Intermediate system is a Level 1 Designated
Intermediate System on circuit C, transmit a com
plete set of Level 1 Complete Sequence Numbers
PDUs on circuit C. Ignore the setting of SSNflag
on Level 1 Link State PDUs.
If the value of the IS's areaTransmitPassword
is non-null, then the IS shall include the Authenti
cation Information field in the transmitted
CSNP, indicating an Authentication Type of
Password and containing the areaTransmit
Password as the authentication value.
2)If this Intermediate system is a Level 2 Designated
Intermediate System on circuit C, transmit a com
plete set of Level 2 Complete Sequence Numbers
PDUs on circuit C. Ignore the setting of SSNflag
on Level 2 Link State PDUs.
If the value of the IS's domainTransmitPass
word is non-null, then the IS shall include the
Authentication Information field in the trans
mitted CSNP, indicating an Authentication Type
of Password and containing the domainTrans
mitPassword as the authentication value.
A complete set of CSNPs is a set whose startLSPID
and endLSPID ranges cover the complete possible
range of LSPIDs. (i.e. there is no possible LSPID
value which does not appear within the range of one
of the CSNPs in the set). Where more than one CSNP
is transmitted on a broadcast circuit, they shall be
separated by an interval of at least min
i
mum
Broad
cast
LSP
TransmissionInterval seconds.
NOTE An IS is permitted to transmit a small number
of CSNPs (no more than 10) with a shorter separation in
terval, (or even back to back), provided that no more
than 1000/minimum
Broad
cast
LSP
Trans
mis
sion
Int
er
val CSNPs are transmitted in any one second period.
b)Otherwise (C is a point to point circuit, including non-
DA DED circuits and virtual links), do nothing.
CSNPs are only transmitted on point to point circuits
at initialisation.
7.3.15.4 Action on expiration of Partial SNP
Interval
The maximum sized Level 1 or Level 2 PSNP which may
be generated by a system is controlled by the values of
originating
L1
LSP
Buf
fer
Size or originating
L2
LSP
Buffer
Size respectively. An Intermediate system shall per
form the following actions every partialSNPInterval sec
onds for circuit C with jitter applied as described in 10.1:
a)If C is a broadcast circuit, then
1)If this Intermediate system is a Level 1 Intermedi
ate System or a Level 2 Intermediate System with
manual
L2
Only
Mode False, but is not a
Level 1 Designated Intermediate System on circuit
C, transmit a Level 1 Partial Sequence Numbers
PDU on circuit C, containing entries for as many
Level 1 Link State PDUs with SSNflag set as will
fit in the PDU, and then clear SSNflag for these
entries. To avoid the possibility of starvation, the
scan of the LSP database for those with SSNflag
set shall commence with the next LSP which was
not included in the previous scan. If there were no
Level 1 Link State PDUs with SSNflag set, do
not transmit a Level 1 Partial Sequence Numbers
PDU.
If the value of the IS's areaTransmitPassword
is non-null, then the IS shall include the Authenti
cation Information field in the transmitted
PSNP, indicating an Authentication Type of
Password and containing the areaTransmit
Password as the authentication value.
2)If this Intermediate system is a Level 2 Intermedi
ate System, but is not a Level 2 Designated Inter
mediate System on circuit C, transmit a Level 2
Partial Sequence Numbers PDU on circuit C, con
taining entries for as many Level 2 Link State
PDUs with SSNflag set as will fit in the PDU,
and then clear SSNflag for these entries. To avoid
the possibility of starvation, the scan of the LSP
database for those with SSNflag set shall com
mence with the next LSP which was not included
in the previous scan. If there were no Level 2 Link
State PDUs with SSNflag set, do not transmit a
Level 2 Partial Sequence Numbers PDU.
If the value of the IS's domainTransmitPass
word is non-null, then the IS shall include the
Authentication Information field in the trans
mitted PSNP, indicating an Authentication Type
of Password and containing the domainTrans
mitPassword as the authentication value.
b)Otherwise (C is a point to point circuit, including non-
DA DED circuits and virtual links)
1)If this system is a Level 1 Intermediate system,
transmit a Level 1 Partial Sequence Numbers PDU
on circuit C, containing entries for as many Level
1 Link State PDUs with SSNflag set as will fit in
the PDU, and then clear SSNflag for these en
tries. To avoid the possibility of starvation, the
scan of the LSP database for those with SSNflag
set shall commence with the next LSP which was
not included in the previous scan. If there were no
Level 1 Link State PDUs with SSNflag set, do
not transmit a Partial Sequence Numbers PDU.
If the value of the IS's areaTransmitPassword
is non-null, then the IS shall include the Authenti
cation Information field in the transmitted
PSNP, indicating an Authentication Type of
Password and containing the areaTransmit
Password as the authentication value.
2)If this system is a Level 2 Intermediate system,
transmit a Level 2 Partial Sequence Numbers PDU
on circuit C, containing entries for as many Level
2 Link State PDUs with SSNflag set as will fit in
the PDU, and then clear SSNflag for these en
tries. To avoid the possibility of starvation, the
scan of the LSP database for those with SSNflag
set shall commence with the next LSP which was
not included in the previous scan. If there were no
Level 2 Link State PDUs with SSNflag set, do
not transmit a Partial Sequence Numbers PDU.
If the value of the IS's domainTransmitPass
word is non-null, then the IS shall include the
Authentication Information field in the trans
mitted PSNP, indicating an Authentication Type
of Password and containing the domainTrans
mitPassword as the authentication value.
7.3.15.5 Action on expiration of Minimum LSP
Transmission Interval
An IS shall perform the following actions every min
i
mum
LSP
Trans
mis
sion
Int
er
val seconds with jitter applied as
described in 10.1.
a)For all Point to Point circuits C transmit all LSPs that
have SRMflag set on circuit C, but do not clear the
SRMflag. The SRMflag will subsequently be
cleared by receipt of a Complete or Partial Sequence
Numbers PDU.
The interval between two consecutive transmissions of the
same LSP shall be at least min
i
mum
LSP
Trans
mis
sion
Int
er
val. Clearly, this can only be achieved precisely by keep
ing a separate timer for each LSP. This would be an unwar
ranted overhead. Any technique which ensures the interval
will be between min
i
mum
LSP
Trans
mis
sion
Int
er
val and
2 * min
i
mum
LSP
Trans
mis
sion
Int
er
val is acceptable.
7.3.15.6 Controlling the Rate of Transmission on
Broadcast Circuits
The attribute min
i
mum
Broad
cast
LSP
Trans
mis
sion
Inter
val indicates the minimum interval between PDU arri
vals which can be processed by the slowest Intermediate
System on the LAN.
Setting SRMflags on an LSP for a broadcast circuit does
not cause the LSP to be transmitted immediately. Instead
the Intermediate system shall scan the LSP database every
min
i
mum
Broad
cast
LSP
Trans
mis
sion
Int
er
val (with
jitter applied as described in 10.1), and from the set of LSPs
which have SRMflags set for this circuit, one LSP shall be
chosen at random. This LSP shall be multicast on the cir
cuit, and SRMflags cleared.
NOTE - In practice it would be very inefficient to scan the
whole database at this rate, particularly when only a few
LSPs had SRMflags set. Implementations may require ad
ditional data structures in order to reduce this overhead.
NOTE - An IS is permitted to transmit a small number of
LSPs (no more than 10) with a shorter separation interval,
(or even back to back), provided that no more than
1000/min
i
mum
Broad
cast
LSP
Trans
mis
sion
Int
er
val LSPs
are transmitted in any one second period.
In addition, the presence of any LSPs which have been re
ceived on a particular circuit and are queued awaiting proc
essing shall inhibit transmission of LSPs on that circuit.
However, LSPs may be transmitted at a minimum rate of
one per second even in the presence of such a queue.
7.3.16 Determining the Latest Information
The Update Process is responsible for determining, given a
received link state PDU, whether that received PDU repre
sents new, old, or duplicate information with respect to
what is stored in the database.
It is also responsible for generating the information upon
which this determination is based, for assigning a sequence
number to its own Link State PDUs upon generation, and
for correctly adjusting the Remaining Lifetime field upon
broadcast of a link state PDU generated originally by any
system in the domain.
7.3.16.1 Sequence Numbers
The sequence number is a 4 octet unsigned value. Sequence
numbers shall increase from zero to (SequenceModulus
- 1). When a system initialises, it shall start with sequence
number 1 for its own Link State PDUs.55It starts with 1 rather than 0
so that the value 0 can be reserved to be guaranteed to be less than
the sequence number of any actually generated Link State
PDU. This is a useful property for Sequence Numbers PDUs.
The sequence numbers the Intermediate system generates
for its Link State PDUs with different values for LSP num
ber are independent. The algorithm for choosing the num
bers is the same, but operationally the numbers will not be
synchronised.
If an Intermediate system R somewhere in the domain has
information that the current sequence number for source S
is greater than that held by S, R will return to S a Link State
PDU for S with R's value for the sequence number. When S
receives this LSP it shall change its sequence number to be
the next number greater than the new one received, and
shall generate a link state PDU.
If an Intermediate system needs to increment its sequence
number, but the sequence number is already equal to
SequenceModulus 1, the notification attempt
To
Ex
ceed
Maximum
Se
quence
Num
ber shall be generated and
the Routeing Module shall be disabled for a period of at
least MaxAge + ZeroAgeLifetime, in order to be sure
that any versions of this LSP with the high sequence num
ber have expired. When it is re-enabled the IS shall start
again with sequence number 1.
7.3.16.2 LSP Confusion
It is possible for an LSP generated by a system in a previ
ous incarnation to be alive in the domain and have the same
sequence number as the current LSP.
To ensure database consistency among the Intermediate
Systems, it is essential to distinguish two such PDUs. This
is done efficiently by comparing the checksum on a re
ceived LSP with the one stored in memory.
If the sequence numbers match, but the checksums do not
and the LSP is not in the current set of LSPs generated by
the local system, then the system that notices the mismatch
shall treat the LSP as if its Remaining Lifetime had expired.
It shall store one of the copies of the LSP, with zero written
as the Remaining Lifetime, and flood the LSP.
If the LSP is in the current set of LSPs generated by the lo
cal system then the IS shall change the LSP's sequence
number to be the next number greater than that of the re
ceived LSP and regenerate the LSP.
7.3.16.3 Remaining Lifetime field
When the source generates a link state PDU, it shall set the
Remaining Lifetime to MaxAge.
When a system holds the information for some time before
successfully transmitting it to a neighbour, that system shall
decrement the Remaining Lifetime field according to the
holding time. Before transmitting a link state PDU to a
neighbour, a system shall decrement the Remaining Life
time in the PDU being transmitted by at least 1, or more
than 1 if the transit time to that neighbour is estimated to
be greater than one second. When the Remaining Lifetime
field reaches 0, the system shall purge that Link State PDU
from its database. In order to keep the Intermediate Sys
tems' databases synchronised, the purging of an LSP due to
Remaining Lifetime expiration is synchronised by flooding
an expired LSP. See 7.3.16.4.
If the RemainingLifetime of the received LSP is zero it
shall be processed as described in 7.3.16.4. If the Remain
ing Lifetime of the received LSP is non-zero, but there is an
LSP in the database with the same sequence number and
zero Remaining Lifetime, the LSP in the database shall be
considered most recent. Otherwise, the PDU with the larger
sequence number shall be considered the most recent.
If the value of Remaining Lifetime is greater than
MaxAge, the LSP shall be processed as if there were a
checksum error.
7.3.16.4 LSP Expiration Synchronisation
When the Remaining Lifetime on an LSP in memory be
comes zero, the IS shall
a)set all SRMflags for that LSP, and
b)retain only the LSP header.
c)record the time at which the Remaining Lifetime for
this LSP became zero. When ZeroAgeLifetime has
elapsed since the LSP Remaining Lifetime became
zero, the LSP header shall be purged from the data
base.
NOTE - A check of the checksum of a zero Remaining Life
time LSP succeeds even though the data portion is not pre
sent
When a purge of an LSP with non-zero Remaining Lifetime
is initiated, the header shall be retained for MaxAge.
If an LSP from source S with zero Remaining Lifetime is
received on circuit C :
a)If no LSP from S is in memory, then the IS shall
1)send an acknowledgement of the LSP on circuit C,
but
2)shall not retain the LSP after the acknowledgement
has been sent.
b)If an LSP from S is in the database, then
1)If the received LSP is newer than the one in the da
tabase (i.e. received LSP has higher sequence
number, or same sequence number and database
LSP has non-zero Remaining Lifetime) the IS
shall:
i)overwrite the database LSP with the received
LSP, and note the time at which the zero Re
maining Lifetime LSP was received, so that
after ZeroAgeLifetime has elapsed, that LSP
can be purged from the database,
ii)set SRMflag for that LSP for all circuits other
than C,
iii)clear SRMflag for C,
iv)if C is a non-broadcast circuit, set SSNflag
for that LSP for C, and
v)clear SSNflag for that LSP for the circuits
other than C.
2)If the received LSP is equal to the one in the data
base (i.e. same Sequence Number, Remaining
Lifetimes both zero) the IS shall:
i)clear SRMflag for C, and
ii)if C is a non-broadcast circuit, set SSNflag
for that LSP for C.
3)If the received LSP is older than the one in the da
tabase (i.e. received LSP has lower sequence num
ber) the IS shall:
i)set SRMflag for C, and
ii)clear SSNflag for C.
c)If this system (or pseudonode) is S and there is an un-
expired LSP from S (i.e. its own LSP) in memory,
then the IS:
1)shall not overwrite with the received LSP, but
2)shall change the sequence number of the un-
expired LSP from S as described in 7.3.16.1,
3)generate a new LSP; and
4)set SRMflag on all circuits.
7.3.17 Making the Update Reliable
The update process is responsible for making sure the latest
link state PDUs reach every reachable Intermediate System
in the domain.
On point-to-point links the Intermediate system shall send
an explicit acknowledgement encoded as a Partial Sequence
Numbers PDU (PSNP) containing the following informa
tion:
a)source's ID
b)PDU type (Level 1 or 2)
c)sequence number
d)Remaining Lifetime
e)checksum
This shall be done for all received link state PDUs which
are newer than the one in the database, or duplicates of the
one in the database. Link state PDUs which are older than
that stored in the database are answered instead by a newer
link state PDU, as specified in 7.3.14 above.
On broadcast links, instead of explicit acknowledgements
for each link state PDU by each Intermediate system, a spe
cial PDU known as a Complete Sequence Numbers PDU
(CSNP), shall be multicast periodically by the Designated
Intermediate System. The PDU shall contain a list of all
LSPs in the database, together with enough information so
that Intermediate systems receiving the CSNP can compare
with their LSP database to determine whether they and the
CSNP transmitter have synchronised LSP databases. The
maximum sized Level 1 or Level 2 Sequence Numbers
PDU which may be generated by a system is controlled by
the values of originating
L1
LSP
Buf
fer
Size or originat
ingL2LSPBufferSize respectively. In practice, the infor
mation required to be transmitted in a single CSNP may be
greater than will fit in a single PDU. Therefore each CSNP
carries an inclusive range of LSPIDs to which it refers. The
complete set of information shall be conveyed by transmit
ting a series of individual CSNPs, each referring to a subset
of the complete range. The ranges of the complete set of
CSNPs shall be contiguous (though not necessarily trans
mitted in order) and shall cover the entire range of possible
LSPIDs.
The LAN Level 1 Designated Intermediate System shall
periodically multicast complete sets of Level 1 CSNPs to
the multi-destination address AllL1ISs. The LAN Level 2
Designated Intermediate System shall periodically multicast
complete sets of Level 2 CSNPs to the multi-destination ad
dress AllL2ISs.
Absence of an LSPID from a Complete Sequence Numbers
PDU whose range includes that LSPID indicates total lack
of information about that LSPID.
If an Intermediate system, upon receipt of a Complete Se
quence Numbers PDU, detects that the transmitter was out
of date, the receiver shall multicast the missing information.
NOTE - Receipt of a link state PDU on a link is the same as
successfully transmitting the Link State PDU on that link, so
once the first Intermediate system responds, no others will,
unless they have already transmitted replies.
If an Intermediate system detects that the transmitter had
more up to date information, the receiving Intermediate sys
tem shall multicast a Partial Sequence Numbers PDU
(PSNP), containing information about LSPs for which it has
older information. This serves as an implicit request for the
missing information. Although the PSNP is multicast, only
the Designated Intermediate System of the appropriate level
shall respond to the PSNP.
NOTE - This is equivalent to the PSNP being transmitted di
rectly to the Designated Intermediate System, in that it
avoids each Intermediate System unnecessarily sending the
same LSP(s) in response. However, it has the advantage of
preserving the property that all routeing messages can be re
ceived on the multi-destination addresses, and hence by a
LAN adapter dedicated to the multi-destination address.
When a non-broadcast circuit (re)starts, the IS shall:
a)set SRMflag for that circuit on all LSPs, and
b)send a Complete set of Complete Sequence Numbers
PDUs on that circuit.
7.3.18 Validation of Databases
An Intermediate System shall not continue to operate for an
extended period with corrupted routeing information. The
IS shall therefore operate in a fail-stop manner. If a failure
is detected, the Intermediate system Network entity shall be
disabled until the failure is corrected. In the absence of an
implementation-specific method for ensuring this, the IS
shall perform the following checks at least every max
i
mum
LSPGenerationInterval seconds:
a)On expiration of this timer the IS shall re-check the
checksum of every LSP in the LSP database (except
those with a Remaining Lifetime of zero) in order to
detect corruption of the LSP while in memory. If the
checksum of any LSP is incorrect, the notification
corruptedLSPDetected shall be logged, and as a
minimum the entire Link State Database shall be de
leted and action taken to cause it to be re-acquired.
One way to achieve this is to disable and re-enable the
IS Network entity.
NOTE On point to point links, this requires at least
that a CSNP be transmitted.
b)On completion of these checks the decision process
shall be notified of an event (even if any newly gener
ated LSPs have identical contents to the previous
ones). This causes the decision process to be run and
the forwarding databases re-computed, thus protecting
against possible corruption of the forwarding data
bases in memory, which would not otherwise be de
tected in a stable topology.
c)The IS shall reset the timer for a period of
maximumLSPGenerationInterval with jitter ap
plied as described in 10.1.
7.3.19 LSP Database Overload
As a result of network mis-configuration, or certain transi
tory conditions, it is possible that there may be insufficient
memory resources available to store a received Link State
PDU. When this occurs, an IS needs to take certain steps to
ensure that if its LSP database becomes inconsistent with
the other ISs', that these ISs do not rely on forwarding
paths through the overloaded IS.
7.3.19.1 Entering the Waiting State
When an LSP cannot be stored, the LSP shall be ignored
and Waiting State shall be entered. A timer shall be started
for waitingTime seconds, and the Intermediate System
shall generate and flood its own LSP with zero LSP number
with the LSP Database Overload Bit set. This prevents
this Intermediate system from being considered as a for
warding path by other Intermediate Systems.
It is possible that although there are sufficient resources to
store an LSP and permit the operation of the Update Proc
ess on that LSP, the Decision Process may subsequently re
quire further resources in order to complete. If these re
sources are not available, the Intermediate system shall then
(i.e. during the attempt to run the Decision Process) enter
Waiting State until such time as they are available and
waitingTime seconds have elapsed since the last LSP was
ignored by the Update Process.
An implementation shall partition the available memory re
sources between the Level 1 and Level 2 databases. An
overload condition can therefore exist independently for
Level 1 or Level 2 (or both). The status attributes l1State
and l2State indicate the condition for the Level 1 and
Level 2 databases respectively. On entering Level 1 Wait
ing State the IS shall generate the lSP
L1
Data
base
Over
load notification, and on entering Level 2 Waiting State
the IS shall generate the lSP
L2
Data
base
Over
load notifi
cation.
7.3.19.2 Actions in Level 1 Waiting State
While in Level 1 waiting state
a)If a Link State PDU cannot be stored, the IS shall ig
nore it and restart the timer for waitingTime seconds.
b)The IS shall continue to run the Decision and For
warding processes as normal.
c)When the waitingTime timer expires, the IS shall:
1)Generate an lSP
L1
Data
base
Over
load (recov
ered) notification.
2)Clear the LSP Database Overload bit in its own
Level 1 LSP with zero LSP number and re-issue it.
3)Set the l1State to On.
4)Resume normal operation.
7.3.19.3 Actions in Level 2 Waiting State
While in Level 2 waiting state
a)If a Link State PDU cannot be stored, the IS shall ig
nore it and restart the timer for waitingTime seconds.
b)The IS shall continue to run the Decision and For
warding processes as normal.
c)When the waitingTime timer expires, the IS shall:
1)Generate an lSP
L2
Data
base
Over
load (recov
ered) notification.
2)Clear the LSP Database Overload bit in its own
Level 2 LSP with zero LSP number and re-issue it.
3)Set the l2State to On.
4)Resume normal operation.
7.3.20 Use of the Link State Database
The only portion of the database relevant to the Decision
Process is the data portion of the Link State PDUs.
The Update Process additionally uses the fields Sequence
Number, Remaining Lifetime, and variable SRMflag.
The Remaining Lifetimes in the stored link state PDUs can
either be periodically decremented, or converted upon re
ceipt into an internal timestamp, and converted back into a
Remaining Lifetime upon transmission.
7.3.20.1 Synchronisation with the Decision Process
Since the Update Process and the Decision Process share
the Link State Database, care must be taken that the Update
Process does not modify the Link State Database while the
Decision Process is running.
There are two approaches to this. In one approach, the De
cision Process signals when it is running. During this time,
the Update Process queues incoming Link State PDUs, and
does not write them into the Link State Database. If more
Link State PDUs arrive than can fit into the queue allotted
while the Decision Process is running, the Update Process
drops them and does not acknowledge them.
Another approach is to have two copies of the Link State
Database one in which the Decision Process is comput
ing, and the other in which the Update Process initially cop
ies over the first database, and in which all new Link State
PDUs are written. Additionally, depending on the hashing
scheme, it is likely that a second copy of the address hash
table will be required, so that the Update Process can do a
rehash occasionally for efficiency.
When the Decision Process is ready to run again, it locks
the new copy of the Link State Database, leaving the Up
date Process to copy over the information into the first area,
and write new updates while the Decision Process runs
again.
The advantage of the first approach is that it takes less
memory. The advantage of the second approach is that Link
State PDUs will never need to be dropped.
NOTE - If the decision process is implemented according to
the specification in C.2, a finer level of parallelism is possi
ble, as described below.
Arrival of a Link State PDU for a system before that system
has been put into TENT is permitted. The new Link State
PDU is used when that system is eventually put into TENT.
Similarly, arrival of a new Link State PDU for a system af
ter that system has been put into PATHS is permitted. That
system has already been completely processed. The arrival
of the new Link State PDU is noted and the decision process
re-executed when the current execution has completed. An
in-progress execution of the decision process shall not be
abandoned, since this could prevent the decision process
from ever completing.
Arrival of a Link State PDU for a system between that sys
tem being put on TENT and being transferred to PATHS
shall be treated as equivalent to one of the previous two
cases (for example, by buffering, or taking some corrective
action).
7.3.20.2 Use of Buffers and Link Bandwidth
Implementations shall have a buffer management strategy
that does not prevent other clients of the buffering service
from acquiring buffers due to excessive use by the Update
Process. They shall also ensure that the Update Process
does not consume all the available bandwidth of links. In
particular no type of traffic should experience starvation for
longer than its acceptable latency. Acceptable latencies are
approximately as follows:
-Hello traffic Hello timer W 0.5
-Data Traffic 10 seconds.
NOTE - The first of these requirements can be met by re
stricting the Update process to the use of a single buffer on
each circuit for transmission. This may also cause the sec
ond requirement to be met, depending on the processor
speed.
7.3.21 Parameters
MaxAge This is the amount of time that may elapse
since the estimated origination of the stored Link
State PDU by the source before the LSP is consid
ered expired. The expired LSP can be deleted from
the database after a further ZeroAgeLifetime has
expired. MaxAge shall be larger than maximum
LSP
Generation
Interval, so that a system is not
purged merely because of lack of events for report
ing Link State PDUs.
MaxAge is an architectural constant equal to 20
minutes.
ZeroAgeLifetime - This is the minimum amount of time
for which the header of an expired LSP shall be re
tained after it has been flooded with zero Remaining
Lifetime. A very safe value for this would be
2 W MaxAge. However all that is required is that
the header be retained until the zero Remaining Life
time LSP has been safely propagated to all the
neighbours.
ZeroAgeLifetime is an architectural constant with
a value of 1 minute.
maximumLSPGenerationInterval This is the maxi
mum amount of time allowed to elapse between gen
eration of Link State PDUs by a source. It shall be
less than MaxAge.
Setting this parameter too fast adds overhead to the
algorithms (a lot of Link State PDUs). Setting this
parameter too slow (and not violating constraints)
causes the algorithm to wait a long time to recover
in the unlikely event that incorrect Link State infor
mation exists somewhere in the domain about the
system.
A reasonable setting is 15 minutes.
minimumLSPGenerationInterval This is the minimum
time interval between generation of Link State
PDUs. A source Intermediate system shall wait at
least this long before re-generating one of its own
Link State PDUs.
Setting this too large causes a delay in reporting new
information. Setting this too small allows too much
overhead.
A reasonable setting is 30 seconds.
min
i
mum
LSP
Trans
mis
sion
Int
er
val This is the amount
of time an Intermediate system shall wait before fur
ther propagating another Link State PDU from the
same source system.
Setting this too large causes a delay in propagation
of routeing information and stabilisation of the
routeing algorithm. Setting this too small allows the
possibility that the routeing algorithm, under low
probability circumstances, will use too many re
sources (CPU and bandwidth).
Setting min
i
mum
LSP
Trans
mis
sion
Int
er
val greater
than minimumLSPGenerationInterval makes no
sense, because the source would be allowed to gen
erate LSPs more quickly than they'd be allowed to
be broadcast. Setting min
i
mum
LSP
Trans
mis
sion
Int
er
val smaller than min
i
mum
LSP
Generation
Inter
val is desirable to recover from lost LSPs.
A reasonable value is 5 seconds.
CompleteSNPInterval This is the amount of time be
tween periodic transmissions of a complete set of
Sequence Number PDUs by the Designated Interme
diate system on a broadcast link. Setting this too low
slows down the convergence of the routeing algo
rithm when Link State PDUs are lost due to the
datagram environment of the Data Link layer on the
broadcast link.
Setting this too high results in extra control traffic
overhead.
A reasonable value is 10 seconds.
7.4 The Forwarding Process
The forwarding process is responsible both for transmitting
NPDUs originated by this system, and for forwarding
NPDUs originated by other systems
7.4.1 Input and Output
INPUT
-NPDUs from the ISO 8473 protocol machine
-PDUs from Update Process
-PDUs from Receive Process
-Forwarding Databases (Level 1 and 2) one for each
routeing metric
OUTPUT
-PDUs to Data Link Layer
7.4.2 Routeing Metric Selection
The Forwarding process selects a forwarding database for
each NPDU to be relayed based on:
-the level at which the forwarding is to occur: level 1
or level 2; and
-a mapping of the ISO 8473 QoS Maintenance field
onto one of the Intermediate system's supported route
ing metrics.
The former selection is made by examining the Destination
Address field of the NPDU.
The latter selection is made as follows:
a)If the QoS Maintenance field is not present in the
NPDU, then the IS shall select the forwarding data
base calculated for the default metric.
b)If the QoS Maintenance field is present, the IS shall
examine bits 7 and 8 of the parameter value octet. If
these two bits specify any combination other than 1
1 (meaning globally unique QoS), then the IS shall
select the forwarding database calculated for the de
fault metric, otherwise
c)The IS shall select a forwarding database by mapping
the values of bits 3, 2 and 1 of the parameter value as
shown below in table 1 and shall proceed as follows:
1)If the IS does not support the selected routeing
metric, the IS shall forward based upon the default
metric;
2)If the forwarding database for one of the optional
routeing metrics is selected and the database either
does not contain an entry for the Destination Ad
dress in the NPDU being relayed, or contains an
entry indicating that the destination is unreachable
using that metric, then the IS shall attempt to for
ward based upon the default metric;
3)Otherwise, forward based on the selected optional
metric.
Table 1 - QoS Maintenance bits to routeing
metric mappingsSelected Routeing Metric
bit 3
bit 2
bit 1
expense metric
0
0
0
default metric
0
0
1
expense metric
0
1
0
delay metric
1
0
0
error metric
0
1
1
delay metric
1
0
1
error metric
1
1
1
default metric
1
1
0
7.4.3 Forwarding Decision
7.4.3.1 Basic Operation
Let DEST = the Network Layer destination address of the
PDU to be forwarded, or the next entry in the source route