mented?
12.1.2.j
C.1
O: Yes No
Forward
ingRate
How many ISO 8473 PDUs can the im
plementation forward per second?
12.2.5.1.b
M
PDUs/sec
L2 ISCount
How many Level 2 ISs does the imple
mentation support?
12.2.5.1.
C.1
N =
call
Estab
lish
ment
Met
ricIncrement
Are non-zero values of the call
Estab
lish
ment
Met
ricIncrement supported?
12.1.2.u.3
C.2
O: Yes No
L1 ISCount
How many Level 1 ISs does the imple
mentation support?
12.2.5.1.
M
N =
ReversePath
Cache
Is the 8208 Reverse Path Cache sup
ported?
12.1.2.u.4
C.2
O: Yes No
ErrorMetric
Is path computation based on the Error
metric implemented?
7.2.2
O
O: Yes No
ISO 10589:19xx
PICS Proforma: Item
References
Status
N/A
Support
C.1if L2IS then O else
C.2if 8208 then O else
ID field
Length
What values of the routeingDomain
ID
Length are supported by this imple
mentation?
7.1.1
M
Values =
Is the value Se
table by System
Man
agement?
Yes No
PDU Authen
tication
Is PDU Authentication based on Pass
words implemented?
12.1.2.z
O
O: Yes No
ISO 10589:19xx (continued)
Annex B
Supporting Technical Material
(This annex is informative)
B.1 Matching of Address Prefixes
The following example shows how address prefixes may be
matched according to the rules defined in 7.1.4.
The prefix
37-123
matches both the full NSAP addresses
37-1234::AF< and
37-123::AF<
which are encoded as
3700000000001234AF< and
3700000000000123AF<
respectively.
This can be achieved by first converting the address to be
compared to an internal decoded form (i.e. any padding, as
indicated by the particular AFI, is removed), which corre
sponds to the external representation of the address. The
position of the end of the IDP must be marked, since it can
no longer be deduced. This is done by inserting the semi-
octet F after the last semi-octet of the IDP. (There can be
no confusion, since the abstract syntax of the IDP is deci
mal digits).
Thus the examples above become in decoded form
371234FAF< and
37123FAF<
and the prefix 37-123 matches as a leading sub-string of
both of them.
For comparison purposes the prefix is converted to the in
ternal decoded form as above.
B.2 Addressing and Routeing
In order to ensure the unambiguous identification of Net
work and Transport entities across the entire OSIE, some
form of address administration is mandatory. ISO
8348/Add.2 specifies a hierarchical structure for network
addresses, with a number of top-level domains responsible
for administering addresses on a world-wide basis. These
address registration authorities in turn delegate to sub-
authorities the task of administering portions of the address
space. There is a natural tendency to repeat this sub-
division to a relatively fine level of granularity in order to
ease the task of each sub-authority, and to assign responsi
bility for addresses to the most localised administrative
body feasible. This results in (at least in theory) reduced
costs of address administration and reduced danger of mas
sive address duplication through administrative error. Fur
thermore, political factors come into play which require the
creation of sub-authorities in order to give competing inter
ests the impression of hierarchical parity. For example at
the top level of the ISO geographic address space, every
country is assigned an equally-sized portion of the address
space even though some countries are small and might in
practice never want to undertake administration of their
own addresses. Other examples abound at lower levels of
the hierarchy, where divisions of a corporation each wish to
operate as an independent address assignment authority
even though this is inefficient operationally and may waste
monumental amounts of potential address space.
If network topologies and traffic matrices aligned naturally
with the hierarchical organisation of address administration
authorities, this profligate use of hierarchy would pose little
problem, given the large size (20 octets) of the N-address
space. Unfortunately, this is not usually the case, especially
at higher levels of the hierarchy. Network topologies may
cross address administration boundaries in many cases, for
example:
-Multi-national Corporations with a backbone network
that spans several countries
-Community-of-interest networks, such as academic or
research networks, which span organisations and ge
ographies
-Military networks, which follow treaty alignments
rather than geographic or national administrations
-Corporate networks where divisions at times operate
as part of a contractor's network, such as with trade
consortia or government procurements.
These kinds of networks also exhibit rich internal topolo
gies and large scale (105 systems), which require sophisti
cated routeing technology such as that provided by this In
ternational Standard. In order to deploy such networks ef
fectively, a considerable amount of address space must be
left over for assignment in a way which produces efficient
routes without undue consumption of memory and
bandwidth for routeing overhead11This is just a fancy way of saying
that hierarchical routing, with its natural effect on address
assignment, is a mandatory requirement for such net
works.
.
Similarly important is the inter-connection of these net
works via Inter-domain routeing technology. If all of the as
signment flexibility of the addressing scheme is exhausted
in purely administrative hierarchy (at the high-order end of
the address) and in Intra-Domain routeing assignment (at
the low end of the address) there may be little or no address
space left to customise to the needs of inter-domain routing.
The considerations for how addresses may be structured for
the Intra- and Inter-domain cases are discussed in more de
tail in the following two clauses.
B.2.1 Address Structure for Intra-domain
Routeing
The IS-IS Intra-domain routeing protocol uses a preferred
addressing scheme. There are a number of reasons the de
signers of this protocol chose to specify a single address
structure, rather than leaving the matter entirely open to the
address assignment authorities and the routeing domain ad
ministrators:
a)If one address structure is very common and known a
priori, the forwarding functions can be made much
faster;
b)If part of the address is known to be assigned locally
to an end system, then the routeing can be simpler, use
less memory, and be potentially faster, by not having
to discriminate based on that portion of the address.
c)If part of the address can be designated as globally
unique by itself (as opposed to only the entire address
having this property) a number of benefits accrue:
1)Errors in address administration causing duplicate
addresses become much less likely
2)Automatic and dynamic NSAP address assignment
becomes feasible without global knowledge or
synchronisation
3)Routeing on this part of the address can be made
simple and fast, since no address collisions will oc
cur in the forwarding database.
d)If a part of the address can be reserved for assignment
purely on the basis of topological efficiency (as op
posed to political or address administration ease), hier
archical routeing becomes much more memory and
bandwidth efficient, since the addresses and the topol
ogy are in close correspondence.
e)If an upper bound can be placed on the amount of ad
dress space consumed by the Intra-domain routeing
scheme, then the use of address space by Inter-domain
routeing can be made correspondingly more flexible.
The preferred address format of the Intra-domain ISIS
protocol achieves these goals by being structured into two
fixed-sized fields as follows shown in figure 91#ID#81Used by level 1
routeingKey:Used by level 2 routeingID
SEL
HO-DSP
IDP
IDP Initial Domain Part
HO-DSP High Order Domain Specific Part
ID System Identifier
SEL NSAP Selector
Figure 9 - Preferred Address Format
below:
The field marked IDP in the figure is precisely the IDP
specified in ISO 8348/Add.2. The field marked HO-DSP
is that portion of the DSP from ISO 8348/Add.2 whose
structure, assignment, and meaning are not specified or
constrained by the Intra-domain ISIS routeing protocol.
However, the design presumes that the routeing domain ad
ministrator has at least some flexibility in assigning a por
tion of the HO-DSP field. The purpose and usage of the
fields specified by the Intra-domain ISIS routeing protocol
is explained in the following paragraphs.
B.2.1.1 The IDP + HO-DSP
Since the Intra-domain ISIS protocol is customised for op
eration with ISO 8473, all addresses are specified to use the
preferred binary encoding of ISO 8348/Add.2.
B.2.1.2 The Selector (SEL) Field
The SEL field is intended for two purposes. Its main use is
to allow for multiple higher-layer entities in End systems
(such as multiple transport entities) for those systems which
need this capability. This allows up to 256 NSAPs in a sin
gle End system. The advantage of reserving this field exclu
sively for local system administration the Intra-domain
routing functions need not store routeing information about,
nor even look at this field. If each individual NSAP were
represented explicitly in routing tables, the size of these ta
bles would grow with the number of NSAPs, rather than
with the number of End systems. Since Intra-domain rout
ing routes to systems, explicit recording of each NSAP
brings no efficiency benefit and potentially consumes large
amounts of memory in the Intermediate systems.
A second use for the SEL field is in Intermediate systems.
Certain ISIS functions require that PDUs be encapsulated
and sent to the Network Entity in an Intermediate system
rather than to an NSAP and upward to a Transport entity.
An example of this is the Partition Repair function of this
International Standard. In order to use a level 2 path as if it
were a single subnetwork in a level 1 area, PDUs are encap
sulated and addressed to an IS on the other side of the parti
tion11This is a gross oversimplification for the purpose of
illustrating the need for the SEL field. See 7.2.10.
. By reserving certain values of the SEL field in Inter
mediate systems for direct addressing of Intermediate sys
tem Network entities, the normal addressing and relaying
functions of other Intermediate systems can be transpar
ently used for such purposes.
B.2.1.3 The Identifier (ID) Field
The ID field is a flat, large identifier space for identifying
OSI systems. The purpose of this field is to allow very fast,
simple routeing to a large (but not unconstrained) number
of End systems in a routeing domain. The Intra-Domain IS
IS protocol uses this field for routeing within a area. While
this field is only required to be unambiguous within a single
area, if the values are chosen to be globally unambiguous
the Intra-domain ISIS design can exploit this fact in the
following ways.
First, a certain amount of parallelism can be obtained dur
ing relaying. An IS can be simultaneously processing the ID
field along with other fields (i.e. IDP, HO-DSP). If the ID
is found in the forwarding table, the IS can initiate forward
ing while checking to make sure that the other fields have
the expected value. Conversely, if the ID is not found the
IS can assume that either the addressed NSAP is unreach
able or exists only in some other area or routeing domain.
In the case where the ID is not globally unique, the for
warding table can indicate this fact and relaying delayed
until the entire address is analysed and the route looked up.
Second, a considerable savings can be obtained in manual
address administration for all systems in the routeing do
main. If the ID is chosen from the ISO 8802 48-bit address
space, the ID is known to be globally unique. Furthermore,
since LAN systems conforming to ISO 8802 often have
their 48-bit MAC address stored in ROM locally, each sys
tem can be guaranteed to have a globally unambiguous
NET and NSAP(s) without centralised address administra
tion at the area level.22Note, however, that the use of the ISO 8802
addresses does not avoid the necessity to run ISO 9542 or to maintain
tables mapping NSAP addresses to
MAC (i.e. SNPA) addresses on the ISO 8802 subnetwork. This is because
there is no guarantee that a particular MAC address is always enabled (the LAN
controller may be turned off) or that a system has only a single MAC address.
This not only eliminates administra
tive overhead, but also drastically reduces the possibility of
duplicate NSAP addresses, which are illegal, difficult to di
agnose, and often extremely difficult to isolate.
An alternative to a large, flat space for the lowest level of
routeing would be to hierarchically subdivide this field to
allow more levels of routeing within a single routeing do
main. The designers of the Intra-domain ISIS protocol
considered that this would lead to an inferior routeing archi
tecture, since:
a)The cost of memory in the ISs was sufficiently reason
able that large (e.g. 104 system) areas were quite fea
sible, thus requiring at least 2 octets per level to ad
dress
b)Two levels of routeing within a routeing domain were
sufficient (allowing domains of 106107 systems) be
cause it was unlikely that a single organisation would
wish to operate and manage a routeing domain much
larger than that.
c)Administrative boundaries often become the dominant
concern once routeing domains reach a certain size.
d)The additional burdens and potential for error in man
ual address assignment were deemed serious enough
to permit the use of a large, flat space.
B.3 Use of the HO-DSP field in
Intra-domain routeing
Use of a portion of the HO-DSP field provides for hierar
chical routeing within a routeing domain. A value is as
signed to a set of ISs in order to group the ISs into a single
area for the usual benefits of hierarchical routeing:
a)Limiting the size of routeing tables in the ISs;
b)conserving bandwidth by hierarchical summarisation
of routeing information;
c)designating portions of the network which are to have
optimal routeing within themselves; and
d)moderate firewalling of portions of the routeing do
main from failures in other portions.
It is important to note that the assignment of HO-DSP val
ues is intended to provide the routeing domain administra
tor with a mechanism to optimise the routeing within a
large routeing domain. The Intra-domain ISIS designers
did not intend the HO-DSP to be entirely consumed by
many levels of address registration authority. Reserving the
assignment of a portion of the HO-DSP field to the route
ing domain administrator also allows the administrator to
start with a single assigned IDP+HO-DSP and run the
routing domain as a single area. As the routeing domain
grows, the routeing domain administrator can then add ar
eas without the need to go back to the address administra
tion authority for further assignments. Areas can be added
and re-assigned within the routeing domain without involv
ing the external address administration authority.
A useful field to reserve as part of the HO-DSP would be 2
octets,permitting up to 65,536 areas in a routeing domain.
This is viewed as a reasonable compromise between route
ing domain size and address space consumption. The field
may be specified as flat for the same reasons that the ID
field may be flat.
B.3.1 Addressing considerations for
Inter-domain Routeing
It is in the Inter-domain arena where the goals of routeing
efficiency and administrative independence collide most
strongly. Although the OSI Routeing Framework explicitly
gives priority in Inter-domain routeing to considerations of
autonomy and firewalls over efficiency, it must be feasible
to construct an Inter-Domain topology that both produces
isolable domains and relays data at acceptable cost. Since
no routeing information is exchanged across domain
boundaries with static routeing, the practicality of a given
Inter-domain topology is essentially determined by the size
of the routeing tables that are present at the boundary ISs. If
these tables become too large, the memory needed to store
them, the processing needed to search them, and the
bandwidth needed to transmit them within the routeing do
main all combine to disallow certain forms of
interconnection.
Inter-domain routeing primarily computes routes to other
routeing domains33This International Standard also uses static
Inter-domain tables for routeing to individual End systems across
dynamically assigned circuits, and also to
End systems whose addresses do not conform to the address construction rules.
. If there is no correspondence between
the address registration hierarchy and the organisation of
routeing domains (and their interconnection) then the task
of static table maintenance quickly becomes a nightmare,
since each and every routeing domain in the OSIE would
need a table entry potentially at every boundary IS of every
other routeing domain. Luckily, there is some reason to be
lieve that a natural correspondence exists, since at least at
the global level the address registration authorities fall
within certain topological regions. For example, most of the
routeing domains which obtained their IDP+HO-DSP
from a hierarchy of French authorities are likely to reside in
France and be more strongly connected with other routeing
domains in France that with routeing domains in other
countries.
There are enough exceptions to this rule, however, to be a
cause for concern. The scenarios cited in B.2 all exist today
and may be expected to remain common for the foreseeable
future. Consider as a practical case the High Energy Phys
ics Network (HEPnet), which contains some 17000 End
systems, and an unknown number of intermediate systems44The number of
ISs is hard to estimate since some ISs and links are in fact shared
with other networks, such as the similarly organised NASA Space
Physics network, or SPAN.
.
This network operates as a single routeing domain in order
to provide a known set of services to a known community
of users, and is funded and cost-justified on this basis. This
network is international in scope (at least 10 countries in
North America, Europe, and the far east) and yet its topol
ogy does not map well onto existing national boundaries.
Connectivity is richer between CERN and FERMIlab, for
example than between many points within the U.S.
More importantly, this network has rich connectivity with a
number of other networks, including the PDNs of the vari
ous countries, the NSFnet in the U.S., the international
ESnet (Energy Sciences Network), the general research
Internet, and military networks in the U.S. and elsewhere.
None of these other networks shares a logical part of the
NSAP address hierarchy with HEPnet55It is conceivable that ISO would
sanction such networks by assigning a top-level IDI from the ISO
non-geographic AFI, but this is unlikely and would
only exacerbate the problem if many such networks were assigned
top-level registrations.
. If the only method
of routing from the HEPnet to these other networks was to
place each within one and only one of the existing registra
tion authorities, and to build static tables showing these re
lationships, the tables would clearly grow as O(n2).
It seems therefore, that some means must be available to as
sign addresses in a way that captures the Inter-Domain to
pology, and which co-exists cleanly with both the adminis
trative needs of the registration authorities, and the algo
rithms employed by both the Intra- and Inter-domain
routeing protocols. As alluded to in an earlier clause, it
seems prudent to leave some portion of the address space
(most likely from the HO-DSP part) sufficiently undefined
and flexible that various Inter-domain topologies may be
efficiently constructed.
Annex C
Implementation Guidelines and Examples
(This annex is informative)
C.1 Routeing Databases
Each database contains records as defined in the following
sub-clauses. The following datatypes are defined.
FROM CommonMgmt IMPORT NSAPAddress,
AddressPrefix, BinaryAbsoluteTime;
PDU Type
lspID = ARRAY [0..7] OF Octet;
systemID = ARRAY [0..5] OF Octet;
octetTimeStamp = BinaryAbsoluteTime;
C.1.1 Level 1 Link State Database
This database is kept by Level 1 and Level 2 Intermediate
Systems, and consists of the latest Level 1 Link State PDUs
from each Intermediate System (or pseudonode) in the area.
The Level 1 Link State PDU lists Level 1 links to the Inter
mediate System that originally generated the Link State
PDU.
RECORD
adr: lspID; (* 8 octet ID of LSP originator
*)
type: (Level1IntermediateSystem,
AttachedLevel2IntermediateSystem,
UnattachedLevel2IntermediateSystem);
seqnum: [0..SequenceModulus 1];
LSPage: [0..MaxAge]; (*Remaining Lifetime *)
expirationTime: TimeStamp;
(*Time at which LSP age
became zero (see 7.3.16.4). *)
SRMflags: ARRAY[1..(maximumCircuits +
maximumVirtualAdjacencies)]
OF BOOLEAN;
(*Indicates this LSP to be sent on this circuit. Note
that level 2 Intermediate systems may send level 1
LSPs to other partitions (if any exist). Only one level
2 Intermediate system per partition does this. For
level 1 Intermediate Systems the array is just
maximumCircuits long. *)
SSNflags: ARRAY[1..maximumCircuits +
maximumVirtualAdjacencies]
OF BOOLEAN;
(*Indicates that information about this LSP shall be
included in the next partial sequence number PDU
transmitted on this circuit. *)
POINTER TO LSP; (*The received LSP *)
END;
C.1.2 Level 2 Link State Database
This database is kept by Level 2 Intermediate Systems, and
consists of the latest Level 2 Link State PDUs from each
Level 2 Intermediate System (or pseudonode) in the do
main. The Level 2 Link State PDU lists Level 2 links to the
Intermediate System that originally generated the Link
State PDU.
RECORD
adr: lspID; (* 8 octet ID of LSP originator *)
type: (AttachedLevel2IntermediateSystem,
UnattachedLevel2IntermediateSystem);
seqnum: [0..SequenceModulus 1];
LSPage: [0..MaxAge]; (*Remaining Lifetime *)
expirationTime: TimeStamp;
(*Time at which LSP age
became zero (see 7.3.16.4). *)
SRMflags: ARRAY[1..(maximumCircuits)] OF
BOOLEAN;
(*Indicates this LSP to be sent on this circuit. *)
SSNflags: ARRAY[1..maximumCircuits] OF
BOOLEAN;
(*Indicates that information about this LSP must be
included in the next partial sequence number PDU
transmitted on this circuit. *)
POINTER TO LSP; (*The received LSP *)
END;
C.1.3 Adjacency Database
This database is kept by all systems. Its purpose is to keep
track of neighbours.
For Intermediate systems, the adjacency database comprises
a database with an entry for each:
-Adjacency on a Point to Point circuit.
-Broadcast Intermediate System Adjacency. (Note that
both a Level 1 and a Level 2 adjacency can exist be
tween the same pair of systems.)
-Broadcast End system Adjacency.
-potential SVC on a DED circuit (max
i
mum
SVC
Adja
cencies for a DA circuit, or 1 for a Static cir
cuit).
-Virtual Link Adjacency.
Each entry contains the parameters in Clause 11 for the Ad
jacency managed object. It also contains the variable used
to store the remaining holding time for each Adjacency
IDEntry and NETEntry entry, as defined below.
IDEntry = RECORD
ID: systemID;
(* The 6 octet System ID of a neighbour End system
extracted from the SOURCE ADDRESS field of its
ESH PDUs. *)
entryRemainingTime: Unsigned [1..65535]
(* The remaining holding time in seconds for this
entry. This value is not accessible to system
management. An implementation may choose to
implement the timer rules without an explicit
remainingTime being maintained. For example by
the use of asynchronous timers. It is present here in
order to permit a consistent description of the timer
rules. *)
END
NETEntry = RECORD
NET: NetworkEntityTitle;
(* The NET of a neighbour Intermediate system
as reported in its IIH PDUs. *)
entryRemainingTime: Unsigned [1..65535]
(* The remaining holding time in seconds for this
entry. This value is not accessible to system
management. An implementation may choose to
implement the timer rules without an explicit
remainingTime being maintained. For example by
the use of asynchronous timers. It is present here in
order to permit a consistent description of the timer
rules. *)
END;
C.1.4 Circuit Database
This database is kept by all systems. Its purpose is to keep
information about a circuit. It comprises an AR
RAY[1..maximumCircuits].
Each entry contains the parameters in Clause 11 for a Cir
cuit managed object (see 11.3). It also contains the remain
ingHelloTime (WordUnsigned [1..65535] seconds) vari
able for the Circuit. This variable not accessible to system
management. An implementation may choose to implement
the timer rules without an explicit remainingHelloTime
being maintained. For example by the use of asynchronous
timers. It is present here in order to permit a consistent de
scription of the timer rules. Additionally, for Circuits of
type X.25 Static Outgoing or X.25 DA, it contains the
recallCount (Unsigned[0..255]) variable for the Circuit.
This variable is not accessible to system management. It
used to keep track of recall attempts.
C.1.5 Level 1 Shortest Paths Database
This database is kept by Level 1 and Level 2 Intermediate
Systems (unless each circuit is Level 2 Only). It is com
puted by the Level 1 Decision Process, using the Level 1
Link State Database. The Level 1 Forwarding Database is a
subset of this database.
RECORD
adr: systemId; (*6 octet ID of destination system *)
cost: [1..MaxPathMetric];
(*Cost of best path to destination system *)
adjacencies: ARRAY[1..max
i
mum
Path
Splits]
OF POINTER TO Adjacency;
(*Pointer to adjacency for forwarding to system adr
*)
END;
C.1.6 Level 2 Shortest Paths Database
This database is kept by Level 2 Intermediate Systems. It is
computed by the Level 2 Decision Process, using the
Level 2 Link State Database. The Level 2 Forwarding Data
base is a subset of this database.
RECORD
adr: AddressPrefix; (*destination prefix *)
cost: [1..MaxPathMetric];
(*Cost of best path to destination prefix *)
adjacencies: ARRAY[1..max
i
mum
Path
Splits]
OF POINTER TO Adjacency;
(*Pointer to adjacency for forwarding to prefix adr
*)
END;
C.1.7 Level 1 Forwarding Database
This database is kept by Level 1 and Level 2 Intermediate
Systems (unless each circuit is Level 2 Only). It is used
to determine where to forward a data NPDU with destina
tion within this system's area. It is also used to determine
how to reach a Level 2 Intermediate System within the area,
for data PDUs with destinations outside this system's area.
RECORD
adr:systemId;
(*6 octet ID of destination system. Destination
0 is special, meaningnearest level 2
Intermediate system *)
splits: [0..max
i
mum
Path
Splits];
(* Number of valid output adj's for reachingadr
(0 indicates it is unreachable) *)
nextHop: ARRAY[1..max
i
mum
Path
Splits] OF
POINTER TO adjacency;
(*Pointer to adjacency for forwarding to destination
system *)
END;
C.1.8 Level 2 Forwarding Database
This database is kept by Level 2 Intermediate systems. It is
used to determine where to forward a data NPDU with des
tination outside this system's area.
RECORD
adr: AddressPrefix; (*address of destination area.
*)
splits: [0..max
i
mum
Path
Splits];
(*Number of valid output adj's for reaching adr
(0 indicates it is unreachable) *)
nextHop: ARRAY[1..max
i
mum
Path
Splits] OF
POINTER TO adjacency;
(*Pointer to adjacency for forwarding to destination
area. *)
END;
C.2 SPF Algorithm for Computing
Equal Cost Paths
An algorithm invented by Dijkstra (see references) known
as shortest path first (SPF), is used as the basis for the
route calculation. It has a computational complexity of the
square of the number of nodes, which can be decreased to
the number of links in the domain times the log of the num
ber of nodes for sparse networks (networks which are not
highly connected).
A number of additional optimisations are possible:
a)If the routeing metric is defined over a small finite
field (as in this International Standard), the factor of
log n may be removed by using data structures which
maintain a separate list of systems for each value of
the metric rather than sorting the systems by logical
distance.
b)Updates can be performed incrementally without re
quiring a complete recalculation. However, a full up
date must be done periodically to recover from data
corruption, and studies suggest that with a very small
number of link changes (perhaps 2) the expected com
putation complexity of the incremental update exceeds
the complete recalculation. Thus, this International
Standard specifies the algorithm only for the full up
date.
c)If only End system LSP information has changed, it is
not necessary to re-compute the entire Dijkstra tree for
the IS. If the proper data structures exist, End Systems
may be attached and detached as leaves of the tree and
their forwarding information base entries altered as
appropriate
The original SPF algorithm does not support load splitting
over multiple paths. The algorithm in this International
Standard does permit load splitting by identifying a set of
equal cost paths to each destination rather than a single
least cost path.
C.2.1 Databases
PATHS This represents an a
cyclic directed graph of
shortest paths from the system S performing the cal
culation. It is stored as a set of triples of the form
aN,d(N),{Adj(N)}q, where:
N is a system Identifier. In the level 1 algorithm, N is
a 7 octet ID. For a non-pseudonode it is the 6 octet
system ID, with a 0 appended octet. For a
pseudonode it is a true 7 octet quantity, comprised of
the 6 octet Designated Intermediate System ID and
the extra octet assigned by the Designated Interme
diate System. In the level 2 algorithm it is either a
7 octet Intermediate System or pseudonode ID (as in
the level 1 algorithm), or it is a variable length ad
dress prefix (which will always be a leaf, i.e. End
system, in PATHS).
d(N) is N's distance from S (i.e. the total metric
value from N to S).
{Adj(N)} is a set of valid adjacencies that S may use
for forwarding to N.
When a system is placed on PATHS, the path(s)
designated by its position in the graph is guaranteed
to be a shortest path.
TENT This is a list of triples of the form
aN,d(N),{Adj(N)}q, where N, d(N) and {Adj(N)} are
as defined above for PATHS.
TENT can intuitively be thought of as a tentative
placement of a system in PATHS. In other words,
the triple aN,x,{A}q in TENT means that if N were
placed in PATHS, d(N) would be x, but N cannot be
placed on PATHS until it is guaranteed that no path
shorter than x exists.
The triple aN,x,{A,B}q in TENT means that if N
were placed in PATHS, d(N) would be x via either
adjacency A or B
NOTE - As described above, (see 7.2.6), it is suggested that
the implementation keep the database TENT as a set of lists
of triples of the form a*,Dist,*q, for each possible distance
Dist. In addition it is necessary to be able to process those
systems which are pseudonodes before any non-
pseudonodes at the same distance Dist.
C.2.2 Use of Metrics in the SPF Calculation
Internal metrics are not comparable to external metrics.
Therefore, the cost of the path from N to S for external
routes (routes to destinations outside of the routing domain)
may include both internal and external metrics. The cost of
the path from N to S (called d(N) below in database
PATHS) may therefore be maintained as a two-
dimensioned vector quantity (specifying internal and exter
nal metric values). In incrementing d(N) by 1, if the internal
metric value is less than the maximum value
MaxPathMetric, then the internal metric value is incre
mented by one and the external metric value left un
changed; if the internal metric value is equal to the maxi
mum value MaxPathMetric, then the internal metric value
is set to 0 and the external metric value is incremented by 1.
Note that this can be implemented in a straightforward
manner by maintaining the external metric as the high order
bits of the distance.
NOTE - In the code of the algorithm below, the current path
length is held in a variable tentlength. This variable is a
two-dimensional quantity tentlength=(internal,external)
and is used for comparing the current path length with d(N)
as described above.
C.2.3 Overview of the Algorithm
The basic algorithm, which builds PATHS from scratch,
starts out by putting the system doing the computation on
PATHS (no shorter path to SELF can possibly exist).
TENT is then pre-loaded from the local adjacency data
base.
Note that a system is not placed in PATHS unless no
shorter path to that system exists. When a system N is
placed in PATHS, the path to each neighbour M of N,
through N, is examined, as the path to N plus the link from
N to M. If aM,*,*q is in PATHS, this new path will be
longer, and thus ignored.
If aM,*,*q is in TENT, and the new path is shorter, the old
entry is removed from TENT and the new path is placed in
TENT. If the new path is the same length as the one in
TENT, then the set of potential adjacencies {adj(M)} is set
to the union of the old set (in TENT) and the new set
{adj(N)}. If M is not in TENT, then the path is added to
TENT.
Next the algorithm finds the triple aN,x,{Adj(N)}q in
TENT, with minimal x.
NOTE - This is done efficiently because of the optimisation
described above. When the list of triples for distance Dist is
exhausted, the algorithm then increments Dist until it finds a
list with a triple of the form a*,Dist,*q.
N is placed in PATHS. We know that no path to N can be
shorter than x at this point because all paths through sys
tems already in PATHS have already been considered, and
paths through systems in TENT will have to be greater than
x because x is minimal in TENT.
When TENT is empty, PATHS is complete.
C.2.4 The Algorithm
The Decison Process Algorithm must be run once for each
supported routeing metric. A Level 1 Intermediate System
runs the algorithm using the Level 1 LSP database to com
pute Level 1 paths. In addition a Level 2 Intermediate Sys
tem runs the algorithm using the Level 2 LSP database to
compute Level 2 paths.
If this system is a Level 2 Intermediate System which sup
ports the partition repair optional function the Decision
Process algorithm for computing Level 1 paths must be run
twice for the default metric. The first execution is done to
determine which of the area's manual
Area
Addresses
are reachable in this partition, and elect a Partition Desig
nated Level 2 Intermediate System for the partition. The
Partition Designated Level 2 Intermediate System will de
termine if the area is partitioned and will create virtual
Level 1 links to the other Partition Designated Level 2 In
termediate Systems in the area in order to repair the Level 1
partition. This is further described in 7.2.10.
Step 0: Initialise TENT and PATHS to empty. Initialise
tentlength to (0,0).
(tentlength is the pathlength of elements in TENT
we are examining.)
a)Add aSELF, 0, Wq to PATHS, where W is a special
value indicating traffic to SELF is passed up to Trans
port (rather than forwarded).
b)Now pre-load TENT with the local adjacency data
base. (Each entry made to TENT must be marked as
being either an End system or an Intermediate System
to enable the check at the end of Step 2 to be made
correctly.) For each adjacency Adj(N), (including
Manual Adjacencies, or for Level 2 enabled Reach
able Addresses) on enabled circuits, to system N of
SELF in state Up, compute
d(N) = cost of the parent circuit of the adjacency
(N), obtained from metrick, where k = one of de
fault metric, delay metric, monetary metric, er
ror metric.
Adj(N) = the adjacency number of the adjacency
to N
c)If a triple aN,x,{Adj(M)}q is in TENT, then:
If x = d(N), then Adj(M) , {Adj(M)} H Adj(N).
d)If there are now more adjacencies in {Adj(M)} than
max
i
mum
Path
Splits, then remove excess adjacen
cies as described in 7.2.7.
e)If x < d(N), do nothing.
f)If x > d(N), remove aN,x,{Adj(M)}q from TENT and
add the triple aN,d(N),Adj(N)q.
g)If no triple aN, x,{Adj(M)}q is in TENT, then add aN,
d(N),Adj(N)q to TENT.
h)Now add any systems to which the local Intermediate
system does not have adjacencies, but which are men
tioned in neighbouring pseudonode LSPs. The adja
cency for such systems is set to that of the Designated
Intermediate System.
i)For all broadcast circuits in state On, find the LSP
with LSP number zero and with the first 7 octets of
LSPID equal to the LnCircuitID for that circuit (i.e.
pseudonode LSP for that circuit). If it is present, for
all the neighbours N reported in all the LSPs of this
pseudonode which do not exist in TENT add an entry
aN,d(N),Adj(N)q to TENT, where
d(N) = metrick of the circuit.
Adj(N) = the adjacency number of the adjacency to the
DR.
j)Go to Step 2.
Step 1: Examine the zeroth Link State PDU of P, the sys
tem just placed on PATHS (i.e. the Link State PDU with
the same first 7 octets of LSPID as P, and LSP number
zero).
a)If this LSP is present, and the LSP Database Over
load bit is clear, then for each LSP of P (i.e. all the
Link State PDUs with the same first 7 octets of LSPID
as P, irrespective of the value of LSP number) com
pute
dist(P,N) = d(P) + metrick(P,N).
for each neighbour N (both Intermediate System and
End system) of the system P. If the LSP Database
Overload bit is set, only consider the End system
neighbours of the system P. d(P) is the second ele
ment of the triple
aP,d(P),{Adj(P)q
and metrick(P,N) is the cost of the link from P to N as
reported in P's Link State PDU
b)If dist(P,N) > MaxPathMetric, then do nothing.
c)If aN,d(N),{Adj(N)}q is in PATHS, then do nothing.
NOTE d(N) must be less than dist(P,N), or else N
would not have been put into PATHS. An additional san
ity check may be done here to ensure d(N) is in fact less
than dist(P,N).
d)If a triple aN,x,{Adj(N)}q is in TENT, then:
1)If x = dist(P,N), then Adj(N) , {Adj(N)} H
Adj(P).
2)If there are now more adjacencies in {Adj(N)} than
max
i
mum
Path
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