Digital PDFs

AA-X435A-TK

December 2000

140 pages

Original

1.4MB

Document:	DECnet Digital Network Architecture Phase IV Routing Layer Functional Description
Order Number:	AA-X435A-TK
Revision:	000
Pages:	140
Original Filename:	http://decnet.ipv7.net/docs/dundas/aa-x435a-tk.pdf

OCR Text

rsoftGare

DECnet Digital Network Architecture
Phase IV
Routing Layer Functional Specification
Order No. AA-X435A-TK

December 1983
This document specifies the functions, interfaces, and protocols for implementing that part of the Digital Network Architecture that models the
software controlling the routing of messages within DECnet communications networks.

SUPERSESSIONIUPDATE INFORMATION: This is a new manual
VERSION:

2.0.0

To order additional copies of this document, contact your local
Digital Equipment Corporation Sales Office.
b

digital equipment corporation magnard, massachusetts

First Printing, December 1983

The information in this document is subject to change without notice and should not be construed as a
commitment by Digital Equipment Corporation. Digital Equipment Corporation assumes no responsibility
for any errors that may appear in this document.
The software described in this document is furnished under a license and may only be used or copied in
accordance with the terms of such license.
No responsibility is assumed for the use or reliability of software on equipment that is not supplied by
DIGITAL or its affiliated companies.

The postage-prepaid READER'S COMMENTS form on the last page of this document requests the user's
critical evaluation to assist us in preparing future documentation.

The following are trademarks of Digital Equipment Corporation:

DIGITAL
DEC
PDP
DECUS
UNDBUS
COMPUTER LABS

COMTEX
DDT
DECCOMM
ASSIST-11
VAX
DECnet
DATATRIEVE

DECsystem-10
DECtape
DIBOL
EDUSY STEM
FLIP CHIP
FOCAL
INDAC

LAB-8
DECSYSTEM-20
RTS-8
VMS
IAS
TRAX

MASSBUS
OMNIBUS
OS/8
PHA
RSTS

Rsx

TYPESET-8
TYPESET-11
TMS-11
ms-10
SBI
PDT

Distributed Systems Publications typeset this manual using DIGITAL'S
TMS-11 Text Management System.
MGTPEALL

Page 3

Table of Contents
CONTENTS

. . . . . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 86
. . . . . . . . . . . . . . . . . . 10
. .. 12
.
.
.
.
. . . . . . . . .. 13
14
15
. . . . . .. .. .. .. .. .. .. .. .. .. .. .. .. .. 15
15
. . .. .. .. .. .. .. .. .. .. .. .. .. .. 18
.. .. .. .. .. .. .. .. .. .. .. .. .. .. 18
18
19
. . . . . . . . . . . 19

INTRODUCTION
FUNCTIONAL DESCRIPTION
Designscope
Relationship To DIGITAL Network Architecture
Routing Layer Environment Requirements
Routing Layer Characteristics
Routing Layer Control Functional Organization
Routing
Decision Process
Update Process
Forwarding Process
ReceiveProcess
Congestion Control
Packet Lifetime Control
Loop Detector
Node Listener
NodeTalker
INTERFACES
Network Management Layer Interface
Data Link Layer Interface
End Communications Layer Interface
Routing Layer Initialization Interface
DETAILED ROUTING SPECIFICATION
Routing Parameters
Routing Data Base (in Level 1 And Level 2
Routers)
Area Routing Data Base In Level 2 Routers
Forwarding Data Base In Level 1 And Level 2
Routers
Area Forwarding Data Base (level 2 Routers Only)
Data Base Protection
DecisionProcess
Decision Controller
Decision Algorithms
Decision Process Events And Actions
Update Process
UpdateAlgorithm
Forwarding Process

. . . . . . . . . . . . . . . 19
19
. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 20
. . . . . . . . . . . . . . . . . . . . 20
. . . . . . . 20
. . . . . . . . . . . 27
. . .. .. .. .. .. 30
32
. . . . . . . . . . 35
. . . . . . . . . . . . . . . 35
. . . . . . . . . . . . . . . . . .. .. .. 43
38
. . . . . . . . . . . . . . . . . . . . 45

46
.
.
.
.
.
.
.
.
.
.
.
.
.
.
47
. . . . . . . . . . . . . . . . 47
. . . . . . . . . . . . . 48
. . . . . . . . .. .. .. .. .. 48
52
. . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 57
58

58
. .. .. .. .. .. .. .. .. .. .. . .. .. .. .. .. 60
Loop Detector Process . . . . . . . . . . . . . 60
DETAILED CONGESTION CONTROL SPECIFICATION . . . . 61
Square Root Limiter . . . . . . . . . . . . . . 6 2
Originating Packet Limiter . . . . . . . . . . . 62
Flusher . . . . . . . . . . . . . . . . . . . . 63
Packet Size Checker . . . . . . . . . . . . . . 6 3
ROUTING LAYER INITIALIZATION SUBLAYER . . . . . . 63
Version Skew . . . . . . . . . . . . . . . . . . 6 3
INITIALIZATION SUBLAYER: DDCMP OR X.25 . . . . . . 64
Receive Process

. . .. .. .. .. .. .. .. .. .. .. .. 64
65
.
.
.
.
.
.
.
.
.
.
.
. . . . . . . . . . . . .. .. 666655

Node Listener Process
Node Listener Controller
Node Listener Algorithm
Node Talker Process
Routing Layer Initialization Circuit States
Routing Layer Initialization Circuit Events

. .

Page 4

Table of Contents
Routing Layer Initialization Operation And
Message Requirements
Routing Layer Initialization State Table And
Diagram
Closing Down
ADDITIONAL INITIALIZATION SUBLAYER FOR
Incoming Call Control
Error Control
Fragmentation. Assembly And Blocking
Closing Down
INITIALIZATION SUBLAYER: ETHERNET
Routers
Ethernet Router Hello Messages
DesignatedRouter
When To Transmit Router Hellos
Closing-Down
Database Of Endnodes
Multiple Areas On An Ethernet
Endnodes
Ethernet Endnode Hello Messages
Designated Router's Ethernet Router Hello
Message
On-Ethernet Cache
Filling. In "next Hop"
In Packet Headers
.
MESSAGES
Message Format Notation
Reserved Fields
Optional Padding
Short Data Packet Format
Long Data Packet Format
Initialization Message
Verification Message
Hello And Test Messaqe
Level 1 Routing ~ e s s a q e
Level 2 outing blessage
Ethernet Router Hello Message
Ethernet Endnode Hello Message

............
. . .. .. .. .. .. .. .. .. .. .. .. ..
. . . . .. .. .. .. .. .. ..
. . . . . . . . . . .. ..
. . . . . . . . . . . . .. ..
. . . . . . .. ..
. . . . .. .. .. .. .. .. ..
. . . . . . . . . . . . .. ..
.

. . . . . .. .. .. . . . . . . . .

.........
.. .. .. ..
. ..

APPENDIX A

ROUTES. ADDRESSES. AND NAMES

APPENDIX B

ROUTING SUBSETS AND TOPOLOGIES

. . . . . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. BB-1
.1
. . . . .. ... ... ... ... ... ... ... ... ... ... B-2
B-2
. . . .. ......: .. .. .. .. .. .. .. .. .. . B-3
B-3
B-4

NODETYPES
TOPOLOGICAL CONCEPTS
DECNET TOPOLOGICAL PRINCIPLES
ENDNODE RESTRICTIONS
ETHERNET ROUTER RESTRICTIONS
LARGERNETWORKS
HIERARCHICALNETWORKS

Page 5

Table of Contents
APPENDIX C
C.O.1
C.0.2

NONROUTING OPERATION
C-1
. . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. C-1

Receive Module
Interfaces

APPENDIX D

PHASE I 1 1 COMPATIBILITY

APPENDIX E

ROUTING LAYER COUNTERS AND EVENTS

. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. E-7
E-1
.
.
.
.
. . . . . . . . . . . . . . . . . . . . . . E-9

SOURCE EVENTS
COUNTERS
EVENTS
APPENDIX F

ALGORITHMS AND MODELS

. . . . . . . . F-1
. . . . . . . .. .. .. .. .. .. .. .. .. F-2
. F-3
F-4

CIRCUIT COST ASSIGNMENT ALGORITHM
BUFFERMANAGEMENT
POSSIBLE BUFFER MANAGEMENT MODEL
DETAILS OF CHARGING AND CREDITING AGAINST QUOTAS
APPENDIX G

BUFFER SIZES

APPENDIX H

GLOSSARY

APPENDIX I

REVISION HISTORY

I 1
1.1.1
1.1.2
1.1.3
1.1.4
1.1.5
1.1.6

1.1.7
1.1.8

. . . . . . . . . . . . . . 1-1
1-1
. . .. .. .. .. .. .. .. .. .. .. .. .. .. .. 1-1
. . . . . . . . . . . 1-2
. . . . . . . . . . . . . . 1-1
. . . . . . . . . . . . . . . . . . . 1-2
Phase I 1 Support Removed . . . . . . . . . . . . 1-2
X.25 . . . . . . . . . . . . . . . . . . . . . . 1-2
Miscellaneous . . . . . . . . . . . . . . . . . 1-3

CHANGES FROMPHASE 1 1 1
Ethernet Support
Hierarchical Routing
Segmented Routing Messages
Terminologychanges
Clean-ups

Introduction
1.0

Page 6

INTRODUCTION

This document describes the
structure, functions,
interfaces,
protocols, and algorithms for implementing the Routing Layer. The
Routing Layer is the part of the DIGITAL Network Architecture that
models the software (or hardware) controlling the routing of messages,
called packets, within DECnet communications networks.
A DECnet network is a family of software modules, data bases, and
hardware components typically used to tie DIGITAL systems together for
resource sharing, distributed
computation, or
remote
system
communication.
DECnet network implementations follow the DIGITAL
Network Architecture (DNA) model.
DNA is a layered structure. Modules in each layer perform distinct
functions.
Equivalent modules within the same layer in both the same
and different nodes communicate using protocols.
A node is an
implementation of the DNA Session Control Layer. Usually a single
computer is associated with one node.
Protocols are the messages
exchanged by modules and the rules governing the message exchanges.
Modules in functionally different layers of DNA interface using either
subroutine
calls or a system-dependent method.
This document
describes these interfaces in the format of calls to subroutines.
The routing described in this document is Phase IV DECnet routing. I t
is the major function of the Routing Layer. DIGITAL'S routing is
intended for users with networks consisting of any combin'ation of
point-to-point links, X . 2 5 links, multipoint links, and Ethernets.
Phase IV DECnet routing is hierarchical, in order to support large
networks.
A large network is partitioned by the network manager into
"areas". Each node resides in exactly one area.
Routing within an
area is referred to as "level 1 routing". Routing between areas is
referred to as "level 2 routing". Level 2 routers keep track of the
paths to destination areas. Level 1 routers keep track only of the
routing within their own area, and keep track of the nearest level 2
router within their area. When a level 1 router receives a packet for
forwarding to a foreign area, it sends the packet to the nearest level
2 router.
Then the packet travels via level 2 routing to the
destination area, where it again travels via level 1 routing to the
destination node.
Phase IV DECnet is upwards compatible with Phase 1 1 1 DECnet.
Thus there are the following types of nodes in Phase IV:
1.

IV endnodes -- These nodes deliver packets to other nodes and
receive packets from other nodes, but do not route packets
through. They differ from Phase I 1 1 endnodes in that they
include an Initialization Sublayer for the Ethernet, and
support hierarchical addressing in the layers above the
Rout ing Layer.

Introduction

Page 7

IV level 1 routers -- These nodes deliver and receive packets
from other nodes, and route packets from other source nodes
through to other destination nodes. They route directly to
nodes within their own area, and route towards a level 2
router when the destination node is in a different area.
IV level 2 routers -- These nodes act as IV level 1 routers
in addition to acting as a node in the subnet consisting of
level 2 routers. A node in the level 2 subnet routes towards
a destination area.
I 1 1 routers -- These nodes deliver and receive packets from
other nodes within their own area, and route packets from
other source nodes through to other destination nodes in
their own area. These nodes do not include an Initialization
Sublayer for the Ethernet, and thus cannot support the
Ethernet.

I 1 1 endnodes -- These nodes deliver packets to other nodes
and receive packets from other nodes, but do not route
packets
through.
These
nodes
do
not
include
an
Initialization Sublayer for the Ethernet, and thus cannot
support the Ethernet.

Networks that include endnodes, and/or that consist of more than
area, are restricted in how the nodes can be interconnected.

one

In Phase IV a node's address is a 16 bit number, the top 6 bits of
which define the area, and the bottom 10 bits of which give an address
within an area.
A glossary at the end of this
terms.

document

defines many

Routing

Layer

This document is intended for readers familiar
with
computer
communications and with DECnet. The primary audience is those who are
implementing DECnet systems. However, it may also be of interest to
those who want to know the details of the Routing Layer design. The
other current DNA functional specifications are:
DNA Data Access Protocol (DAP) Functional
5.6.0, Order No. A A - K ~ T K

Specification, version

DNA DiqiFal Data
Communications
Message
Protocol
(DDCMP)
Functional ~pecif<cation,Version 4.1.0, Order No. AA-K175A-TK
DNA Ethernet -Data Link Functional
Order No. AA-Y298A-TK

Specification, Version

1.0.0,

DNA Ethernet Node Product Architecture
1.0.0, Order No. AA-X440A-TK

Specification, Version

DNA Maintenance
-

Specification,

Operations Functional
3.0.0, Order No. AA-X436A-TK

Version

Page 8

Introduction
DNA Network Management Functional Specification, Version
-

4.0.0,

Order No. AA-X437A-TK

DNA Network Services Protocol Functional Specification, Version
4.0.0, Order No. AA-X439A-TK

DNA Session Control Functional Specification, Version 1.0.0, Order
NO. AA-K182A-TK

The Ethernet - A Local Area Network - -Data Link Layer and Physical
Layer
Specifications, Version 2.0, m g i t a l , Intel, and
Xerox), Order No. AA-K759B-TK

The DECnet DIGITAL Network Architecture (Phase IV) General Description
(Order No.
AA-N149A-TC) provides an overview of the network
of
the
functional
architecture and an introduction to
each
specifications.

2.0

FUNCTIONAL DESCRIPTION

The Routing Layer routes messages in DECnet networks and manages the
message packet flow. A packet is a unit of data to be routed from a
source node to a destination node. The Routing Layer consists of two
sublayers:
1.

Control. The Control Sublayer supplies full-duplex packet
transmission between any pair of nodes. It is independent of
the specific Data Link Layer below it, except for knowing
about two generic types of links:
1.

non-broadcast links, which include DDCMP
DDCMP multipoint, and X.25, and

point-to-point,

broadcast links, which include the Ethernet.

the
physical
and
The Routing Control Sublayer masks
topological
characteristics of the network from higher
layers. It consists,of the following components:

Routing

Congestion control

Packet lifetime control

Initialization. The Routing Initialization Sublayer masks
the characteristics of the Data Link Layers from the Routing
Control Sublayer. It consists of the following components:
o

Initialization

Functional Descript-ion
o

Page 9

Physical circuit monitor

The Routing Initialization Sublayer controls the
Layer and is Data Link Layer dependent.

Data

Link

The Routing Layer components provide the following functions.
I

Routing. The routing function determines packet paths. A path is the
sequence of connected nodes between a source node and a destination
node. When the Routing Layer receives a packet, the routing component
refers to a data base that is periodically updated by Routing Layer
modules in adjacent nodes. The routing component uses information in
this data base to determine if a path to a destination exists, and, if
so, what the next hop in the path is.
The routing component then
forwards the packet to its destination. If more than one path exists
to a destination, the routing component ascertains the best path.
The combined knowledge of all the Routing Layer modules of all the
nodes in a network is used to ascertain the existence of a path, and
route the packet to its destination.
The routing component at a
routing node has the following specific functions:
o

It extracts and interprets the route header in a packet.

It performs packet forwarding based on the destination.

It manages the characteristics of the path.
If a
link fails on a path, it find,s an alternate route.

It interfaces with the Routing Initialization Sublayer to
receive reports concerning a circuit or node that has failed
or the subsequent recovery of a circuit or node.

It returns packets addressed to unreachable nodes to the End
Communications Layer (ECL), if requested to do so by ECL. A
node is unreachable if it is unknown, or the path to it
exceeds the maximum hops of the network.
A hop is the
logical distance between two adjacent nodes. Maximum hops is
a Routing Layer parameter that is equal to the maximum path
length in the network.

Congestion control.
packet
switching
route-through).

node

Congestion control manages the buffers at each
node
(that
is, at each node that permits

Packet lifetime control. Packet lifetime control bounds the number of
nodes a packet can visit.
Initialization.
functions:
0

The Initialization component supplies the

following

It identifies the adjacent node and the adjacent node's Routing
Layer.

Functional Description
o

Page 10

It performs node verification, if required.

Physical circuit monitor.
the Data Link Layer.

2.1

This component monitors errors detected

Design Scope

The Routing Layer supports the following design requirements:
Deliverability. It accepts and delivers packets addressed to
reachable destinations and rejects packets addressed to
unreachable destinations.
Adaptability. It adapts to topological changes, but not to
traffic changes.
(Topological changes are changes in the
configuration of active circuits and nodes in a network.
Traffic changes are changes in the load on circuits in a
network. )
Promptness. The period of adaptation to topological changes
in the network is a reasonable function of the network
diameter (that is, the maximum logical distance between
network nodes) and circuit speeds.
Efficiency.
efficient.
overhead.

The Routing Layer is both processing and memory
I t does not create excessive routing traffic

Robustness. The Routing Layer recovers from transient errors
such as lost or temporarily incorrect routing messages. I t
tolerates imprecise parameter settings.
Stability. The Routing Layer stabilizes in finite time to
'good routes," provided no continuous topological changes or
continuous data base corruptions occur.
Operator control.
An operator can control many routing
functions via parameter changes, and inspect parameters,
counters, and routes. Routing, however, will not depend on
operator input for correct behavior.
Simplicity. The Routing Layer is sufficiently
permit performance tuning and failure isolation.

simple

Maintainability. The Routing Layer provides mechanisms to
detect, isolate, and repair most common errors that may
affect the routing computation and data bases.

Functional Description

Page 11

Verification
of
compatibility.
The
Rout i ng
Initialization Sublayer prevents
incompatible
algorithms from coexisting in the network.

Layer
routing

Heterogeneity. The Routing Layer operates over a mixture of
network node types, communication circuits, and topologies.
In particular, it supports point-to-point, multipoint, and
multiaccess.

outing Layer
Support of subsets.
The
support a subset of the routing functions.

allows nodes

Extensibility.
The Routing Layer accommodates increased
routing functions, leaving earlier functions as a subset.
Evolution. The Routing Layer allows orderly transition from
algorithm to algorithm without shutting down an entire
network.
Deadlock Prevention.
The congestion
control
component
prevents deadlock, the condition in which the Routing Layer
fails to deliver data.
Independence. Congestion control does not depend on
for effective operation.

routing

Duplicate message reduction.
The packet lifetime control
algorithm
significantly
reduces the risk of the user
receiving duplicate messages.
Large networks. With hierarchical routing, the Routing Layer
supports networks of several thousand nodes.
The following are not within the scope of Phase IV Routing Layer:
Traffic adaptation. The Routing
traffic flow automatically.

Layer

does

not

react

Traffic service classes.
The Routing Layer
does
not
distinguish among different classes of traffic in route
determination.
Source-destination routing.
The Routing Layer
determine routes by source as well as destination.

does

not

Gross operator failure. The Routing Layer does not attempt
to protect the network from operator actions, such as
removing a circuit or a node, that may disconnect the
network.
Guaranteed delivery. The Routing Layer does
delivery of all offered packets.

not

guarantee

11-11

II Â £
X
C
I

*r-1

I
I
I

1-1 I
I
I
1 - 4 1
I (01
I U l
I 'r-1 I
I VII
1 i s 1
A
I
I a, I
I
I

.-.,

Functional Description
A

Page 13

brief description of each DNA layer follows:
1.

User Layer. The highest layer, the User Layer supports user
services and programs.

Network Management Layer. Modules in the Network Management
Layer provide user control over and access to network
parameters and counters. These modules also furnish up-line
dumping, down-line loading, and testing functions. This
layer is the only layer that has direct access to each lower
layer for control purposes.

Network Application
Layer.
Modules
in
the
Network
Application Layer support network functions, such as remote
file access and file transfer, used by the two higher layers.

Session Control Layer. The Session Control Layer defines the
system-dependent aspects of logical link communication, which
allows controlled data movement between network nodes.

End Communications Layer.
The End Communications Layer
defines
the system-independent aspects of logical link
communication.

Routing Layer. Modules in the outing Layer
between source and destination nodes.

Data Link Layer. The Data Link Layer defines the protocol
concerning data integrity and physical channel management.

Physical Link Layer. The Physical Link Layer encompasses a
part of the device driver for each communications device plus
the communications hardware itself.
The hardware includes
interface devices, modems, and the communication lines. This
layer controls the end-to-end transmission of data.

route messages

Each DNA layer uses the services of the layer below it. In addition,
Network Management provides a control interface to all the DNA layers
below it. User and Network ~pplicationLayer modules can interface
directly with Session Control.

2.3

Routing Layer Environment Requirements

The Routing Layer requires guarantees from the operating
End Communications Layer, and the Data Link Layer.
The required operating system guarantees are:

system,

the

Functional Description

Page 14

Priority scheduling such that
minimum processing guarantees

A quota of buffers to the Routing Layer sufficient to perform
routing and packet lifetime control functions

Access to
expiration

timer

the

Routing

notification

Layer

receives

specific

timer

The End Conununications Layer must guarantee the return of a buffer
within a short, bounded amount of time. Otherwise, the Routing Layer
may discard packets received for ECL if ECL exceeds a quota.
The required Data Link Layer guarantees for point-to-point links are:
Provision that both source and destination
start-up before message exchange can occur

nodes

complete

Detection of remote start-up
Provision that no old messages be received after start-up
complete
Masking of transient errors in order to prevent
corruption

packet

data

Provision for not duplicating or corrupting packets
Packet sequentiality ensuring that, if a packet has been
received, all previously sent packets have been received
Reporting of failures and degraded circuit conditions
The required Data Link Layer guarantees for Ethernets are:

2.4

Provision for not corrupting packets

Packet sequentiality ensuring that, if
received, no previously sent packet
received

a packet has been
will be subsequently

Routing Layer Characteristics

The Routing Layer possesses the following characteristics:
o

Variable delay. There is a variable delay time.
Delay is
defined as the time between receipt of a packet from ECL at a
source node and delivery of that packet to ECL at a
destination node.

Functional Description

2.5

Page 15

Nonsequential delivery. The Routing Layer does not guarantee
delivery of packets to ECL at the destination node in the
same sequence in which they were received from ECL at the
source node.

Packet integrity. The
misdeliver a packet.

Routing

Layer

will

not

modify

Routing Layer Control Functional Organization

The Routing Layer Control Sublayer components can be broken down into
more specific functional components. These are described briefly here
and in detail below.

2.5.1

Routing -

The Routing processes and data bases are:
o

Decision Process

Update Process

Forwarding Process

Receive Process

Routing data base

Forwarding data base

each
2.5.1.1 Decision Process - This process selects routes to
destination in the network. It consists of a connectivity algorithm
that maintains path lengths and a traffic assignment algorithm that
maintains path costs. Path length is the number of hops along a path
between two nodes. Circuit cost is a nonzero, positive integer value
associated with using a circuit, and path cost is the sum of the
circuit costs along a path between two nodes.

Functional Description

Page 16

When a routing node receives a Routing Message (a type of Routing
Layer control message) from an adjacent node, the routing node
executes the Decision Process.
Execution of the Decision Process
results in the determination of <circuit, neighbor> pairs (known as
adjacencies) along which to forward packets and
possibly
the
conclusion
that
on,e or more particular destination nodes are
unreachable.
Ã

The system manager must set several of the parameters in the Routing
data base that the Decis-ion Process uses. These include maximum
address, maximum number of areas (in level 2 nodes), maximum cost,
maximum hops, maximum circuits, circuit costs, maximum total broadcast
end-node adjacencies, maximum total broadcast router adjacencies, and
maximum broadcast router adjacencies for each broadcast circuit. The
values of the cost parameters are arbitrary. Appendix F suggests an
algorithm for determining circuit costs.
The values of the other
parameters depend on the specific topology of the network.
I f these
values are not set correctly, the decision algorithms will not work
correctly.
The figure below shows a sample network, consisting of a single area,
and depicts some of the Routing terms.
The glossary contains
definitions of these and other Routing Layer terms.

Functional Description

Page 1 7

1 hop

I
I 2
I

--Legend:
= node

= circuit
= c i r c u i t cost
= hop

1 Node A wants t o send a packet t o node D.
1 possible paths.

There a r e t h r e e

1
1
I

* 7 is t h e lowest p a t h c o s t ; node A t h e r e f o r e r o u t e s t h e packet t o
node D v i a t h i s path.

Figure 2 .

Routing Terms

Functional Description

Page 18

2.5.1.2
Update Process - This process constructs and
propagates
A Routing Message contains path cost and path
Routing Messages.
length for all destinations.
The Update Process sends Routing
Messages to adjacent nodes after determining that certain conditions
are met. General characteristics of the Update Process are:

. nodes
Level 1 Routing Messages are sent to adjacent routing
within the node's home area
. Level
2 Routing Messages are sent to adjacent level 2
routing nodes
. within
Level 1 Routing Messages contain information on all nodes
the home area
. Level
2 Routing Messages contain information about all
areas
. Routing
Message transmission is event-driven with periodic
backup
. The
routing update algorithm maintains an upper limit on
routing traffic overhead
2.5.1.3
Forwarding Process - This process supplies and. manages the
buffers necessary to support packet route-through to all destinations.
It performs a table lookup to determine the output adjacency to use
for forwarding to a given destination, reformats packets between short
and long format if necessary, strips off the area fields when
forwarding to a Phase I 1 1 node, fills in the area fields when
receiving from a Phase I11 node, and marks intra-Ethernet packets.

2.5.1.4
Receive Process - The Receive Process inspects a packet's
route header and dispatches the packet to an appropriate Routing Layer
Control component or to the End Communications Layer (ECL).

Functional Description

Page 19

2.5.2
Congestion Control - The Congestion Control component manages
buffers by limiting the maximum number of packets on the transmit
queue for a circuit.
Congestion Control regulates the ratio of
packets
received directly
from ECL to route-through packets.
Congestion Control also checks the packet size for each packet to be
sent.

Packet Lifetime Control - The packet lifetime control component
2.5.3
requires three processes:
1.

Loop Detector

Node Listener

Node Talker

Loop Detector - This process prevents
excessive packet
looping.
It counts the number of nodes a packet has visited and
removes a packet when it exceeds the visit limit.

2.5.3.1

Node Listener - This process determines that a minimum amount
2.5.3.2
of activity has occurred between this node and an adjacent node. It
also determines if the identity of the adjacent node has changed.
violations of the minimum activity audit .result in the declaration
that the adjacency between the nodes is down.
On non-broadcast circuits, Hello Messages need to be sent only in the
absence of other traffic, to ensure that a minimum amount of activity
occurs. On broadcast circuits, Hello Messages need to be sent
periodically regardless of other forms of traffic.

Functional Description

Page 20

2.5.3.3
Node Talker - This process provides the minimum activity for
each adjacent Node Listener.
It places an artificial load on theadjacency so failures can be detected. The Node Talker and Listener
provide for detection of adjacent Routing Layer halt and adjacent node
identity change.

3.0

INTERFACES

This section describes the three external Routing Layer interfaces:
1.

Network Management Layer interface

Data Link Layer interface

End Communications Layer interface

In addition, this section describes the single internal Routing
interface, Initialization Sublayer.

Layer

The interfaces take the format of calls to subroutines, as follows:
FUNCTION (input ; output)
Each call represents a specific function. An implementation
required to code the interface as calls to subroutines.

not

The following symbols are used throughout the document:
o

not equal to

less than or equal to

greater than or equal to

much greater than

SQRT ( x )

the square root of

CEILING(x1 the least integer greater than or equal to x

3.1

Network Management Layer Interface

This interface allows Network Management to control and observe the
Routing Layer interactively.
Network Management can exert indirect
control over the Routing Layer via parameter changes.
The following
Network Management functions form a set of primitive functions that

Interfaces

Page 21

can be used to construct more complex functions.

READ SELF PARAMETERS (;parameters)
This function gives the values
Parameters are:

the

node's parameters.

. Routing-State
-- Routing Layer operating, or terminated,
requiring problem correction and initialization

. Net-Management-State
-- ON or OFF. Setting this parameter
to "ON" from "OFFn forces Routing to initialize all its
data bases.

. which
ID, top 6 bits of which is HOMEAREA, bottom 10 bits of
is Tid, node within area
. NN -- highest node number within the area
. NA
(in level 2 routers only), highest area number in the
network
. NC -- number of circuits supported by this node
. NBRA
-- number of Broadcast Router ~djacencies (BRAS)
supported by this node
. NBEA
-- number of Broadcast Endnode ~djacencies (BEAS)
supported by this node
. Maxh
-- Maximum hops possible in a path to a reachable
destination within an area
. Maxc
-- Maximum cost possible in a path to a reachable
destination within an area
. AMaxh
-- (in level 2 routers only), maximum hops possible
in a path to a reachable area
. AMaxc
-- (in level 2 routers only), maximum cost possible
in a path to a reachable area
. Maxv -- Maximum visits allowable for a packet

. Tl
-- Background timer for routing updates on non-broadcast
circuits

. BCT1
-- Background timer for routing updates on broadcast
circuits
. Routing
Type -- Phase IV area router, Phase IV router,
Phase IV nonrouting

Page 2 2

Interfaces

. Routing
Version -- the current routing version, ECO, and
user ECO
. BS
-- Buffer size -- Six greater than the maximum buffer
size
for use by Routing, excluding Routing Layer Header and
excluding Data Link Layer header. (Note -- the added 6
bytes are for historical compatibility with Phase 111, when
the Buffer size parameter included Routing Layer header,
which was 6 bytes at the time.)

. SS
-- Segment size -- Six greater than the maximum segment
size to be used by ECL. SS must be less than or equal to
BS. It will usually be equal to BS. It may be
BS while the buffer sizes in the network
increased or decreased.

less than
are being

. NB -- maximum number of buffers for forwarding
. Subaddresses
nodes with X . 2 5 Data Link Mapping only)
-- the range--of (in
local DTE subaddresses that are acceptable
on an X . 2 5 circuit for an incoming call

SET SELF PARAMETER (PARAMETER, VALUE; status)
This function sets the parameter PARAMETER to VALUE.
The
parameters supported are those enumerated above in the READ
SELF PARAMETERS call.
The returned status is:

. success
. unknown parameter
. illegal value

READ SELF COUNTER ( ; counters)
This function gives the values of the node's
counters,
maintained by the Routing Layer. Appendix E describes these
counters in detail.
Counters are:

. node unreachable packet loss
. aged packet loss
. node out-of-range packet loss

Interfaces

Page 23

. oversized packet loss

. packet format error
. partial routing update loss
. verification reject
READ AND CLEARISELF COUNTERS ( ; counters)
This function returns the same values as
It zeroes all counters upon completion

READ

SELF

COUNTERS.

READ CIRCUIT PARAMETERS (CIRCUIT; status, parameters)
This function gives the values of the CIRCUIT'S parameters.
These parameters are described more fully in Section 4.2.
The returned status is one of:

. success
. unknown circuit
Parameters are:

. Type (Ethernet, X.25, DDCMP)
. Net-Management-State (ON or OFF)
. State (as determined by Initialization Sublayer)
. Cost
. Hello Timer

. Recall Timer
. Originating Packet Limiter (OPL)
. Type Specific Information
o

For Ethernet, the type specific information is:

NR -- Number of BRAS allowed on this Ethernet

Priority -- the router's priority to be
Router

~esignated

Page 24

Interfaces

Designated Router -- the ID of the router currently
chosen to be Designated Router on this Ethernet

For X . 2 5 ,

the type specific information is:

Port State -- supplied by the X.25 Data Link Layer

Blocking -- indicates if blocking can
this node

done

- Negotiated Blocking -- indicates if neighbor

by
also

requested blocking

- Maximum Recalls -trials permitted
before halting

the maximum number of call
from the Data Link Start state

Recall Count -- the number of call attempts that
have been made to try to initialize a virtual
circuit. This is reset by the operator turning the
circuit on.

VC Type -- ty e of virtual circuit:

. PVC (permanent virtual circuit)
. incoming switched virtual circuit
. outgoing switched virtual circuit
- VC name.
address.

For an SVC, a network
For a PVC, a PVC name.

name

and

SET CIRCUIT PARAMETER (CIRCUIT, PARAMETER, VALUE; status)
This function sets the parameter PARAMETER in circuit
to VALUE.
The returned status is:

. success
. unknown circuit
. unknown parameter
. illegal value

DTE

CIRCUIT

Interfaces

Page 25

READ CIRCUIT COUNTERS (CIRCUIT; status, counters)
This function gives the values of the counters maintained by
the Routing Layer for the specified circuit. Counters are
described more fully in Appendix E.
The returned status is one of:

. success
. unknown circuit
Counters are:

. Transit ("Route-Through") Packets Received
. Transit Packets Sent
. Terminating
Packets Received (packets received from other
nodes addressed to this node)
. Originating
Packets Sent (packets from this node addressed
to other nodes)

. Transit Congestion Loss
. Terminating Congestion Loss
. Circuit Down
. Initialization Failure
In addition, for X . 2 5 circuits, there
counter:

is the

type

specific

. Corruption
Loss -- a count of the data errors detected for
this circuit
READ AND CLEAR CIRCUIT COUNTERS (CIRCUIT; status, counters)
This function returns the same values as READ CIRCUIT COUNTERS.
It zeroes the counters upon completion.

READ NODE PARAMETERS (NODE; parameters)
This function gives the values of
Routing for the specified node.

parameters maintained

If the local node type is a level 1 router, and the specified
node is in another area, the values of parameters maintained by
Routing for the special destination # O f meaning "nearest level

Page 2 6

Interfaces
2 router" are given.

Parameters are:

. Reachability Flag
. Output Circuit [and NextHop, for Ethernets only] to NODE
. Hops of minimum cost path to NODE
. Cost of minimum cost path to NODE
READ AREA PARAMETERS (AREA; parameters)
This function gives the values of the parameters maintained by
Routing for the specified area. This function is implemented
in level 2 routers only. Parameters are:

. Reachability Flag

. Output Circuit [and NextHop, for Ethernets only] to AREA
. Hops of minimum cost path to AREA
. Cost of minimum cost path to AREA
READ ADJACENCY PARAMETERS (ADJACENCY; parameters)
This function gives the values of the parameters maintained by
Routing for the specified adjacency.
An adjacency is a
<circuit, node ID> pair.
The argument "adjacency" is an
adjacency # in the Routing Data Base.
Parameters are:

. In Use Flag
. Node ID
. Node Type, one of:
. Level 1 router
. Level 2 router
. Phase IV endnode

. Phase I11 router

Interfaces

Page 27

. Phase I 1 1 endnode
circuit
Listen Timer
neighbor's blocksize

READ EVENT ( ;
Return:

event)
the oldest event in the Routing Layer's internal event
queue

The Routing Layer maintains an internal event queue into which
it places events.
Events are described in ~ppendixE. This
function reads the oldest event in the queue.

CLEAR EVENTS
Returns:

none

This function clears
internal event queue.

3.2

all

events

from

the

outing

Layer's

Data Link Layer Interface

This interface, between the Routing Layer's . Initialization Sublayer
and the Data Link Layer, consists of commands to and responses from
the Data Link Layer. The interface supports the exchange of data,
control, and error information.
Data is information to be sent or
received by the Data Link Layer protocol.
Its description usually
consists of a starting buffer address and a length or character count,
or a chain of addresses and counts. The control information starts
and stops the protocol.
The error information reports circuit
conditions. The functions of the interface, described as calls, are
as follows:

Page 28

Interfaces
TRANSMIT (circuit, buffer, [Next~op], [more data to follow])
Returns:

none

This function gives a
transmission.

message

the

Data

Link

Layer

for

On a broadcast circuit,
supplied.
The parameter
non-broadcast circuit.

the parameter "NextHopn must be
"NextHopn is not supplied on a

"More data
cir'cuits.

follow"

flag

specified only

X.25

CHECK TRANSMIT BUFFER (buffer)
Returns:

buffer is still queued
buffer is returned to the Routing Layer

This function returns information about the transmit buffer.

INITIALIZE CIRCUIT (circuit)
Returns:

none

This function causes the Data Link protocol to
circuit.

initialize

the

In the case of the Ethernet, Data Link padding must be enabled.
Also, Routing must tell the Data Link Layer to enable the
protocol type PROT-TYPE, and the multicast ID ALL-ROUTERS ( i f
the local node is a router), or the multicast ID ALL-ENDNODES
(if the local node is an endnode).
In the case of X.25, tHis tells the Data ink Layer that if the
virtual
circuit is in the UNSYNC state, send a "reset
confirmation", and if the virtual circuit is in the RUNNING
state, send a "reset" packet. I f the virtual circuit is in the
cleared state, a call must be initiated.

STOP circuit (circuit)
Returns:

none

This function halts the Data Link operation on
circuit.

the

specified

Interfaces

Page 29

For X . 2 5 circuits, this means send a "clearn packet on a .
Switched Virtual CircuitI and send a nresetn packet on a
Permanent Virtual Circuit.

STATUS (circuit; status)
Returns:

off
running
initializing

This function returns the Data Link state of the circuit.
If
the Data Link modules provide additional states (for example, a
maintenance state), they are treated as the OFF state.

READ ERROR COUNTERS (circuit; error counters)
Returns:

error counter values (valuerstatus)

This function returns the values of
counters, and notification if error
exceeded.

the Data Link error
thresholds have been

SUPPLY RECEIVE BUFFER (buffer; status)
Ret.urns: buffer accepted
buffer rejected
This function provides an empty buffer to the Data Link modules
for receipt of the next sequential message.

CHECK RECEIVE BUFFER
followl, status)
Returns:

(buffer;

circuit,

[ ~ r e v ~ o p ][more
~
data

no packet received
packet received, buffer returned

This function returns the above information about
buffer.

the

receive

The PrevHop value is returned when a packet is received on a
broadcast circuit.
The PrevHop value is not returned when a
packet is received on a non-broadcast circuit.

Page 30

Interfaces
The "more data
circuits.

3.3

follown flag

returned only

X.25

End Communications Layer Interface

This interface, between the End Communications Layer and the Routing
LayerI consists of commands to and responses from the Routing Layer.
The commands and responses exchange data and control information.
Data is information that the Routing Layer sends or receives.
The
data description is a destination addressI source address, buffer
address and length of data.
Destination and source addresses are
two-byte integer numbers with the most significant 6 bits being the
area number, and the least significant 10 bits being the address
within the area. The Routing Layer uses node addresses onlyI not node
namesI which are resolved at a higher layer.
Control information starts or stops transmission and reception of data
and regulates the data flow to a reachable destination.
The functions of the interface, described as calls, are as follows:

TWSMIT
buffer 1

(destination, return

Returns:

flag,

~ c i r c ~ i t , [ N e x t H o pTryhard,
~~~

buffer is queued
buffer is not queued and is returned to ECL

his function sends a packet.
The return flag indicates whether or not ECL wants the packet
returned
if
the
destination is unreachable or becomes
unreachable before the Routing Layer can deliver the packet.
If the flag is set to "true" (~oolean),the Routing Layer
attempts to return the contents of the buffer to ECL as a
"received packet." If the flag is not set, the Routing Layer
discards the packet. The Routing Layer returns the buffer
after ECL issues the CHECK TRANSMIT BUFFER call (described
next 1

Circuit, selected by the End Communications LayerI is either
unspecified or a valid circuit. If the circuit is a broadcast
circuit, NextHop must also be specified.
For circuit level
loopback testing, the End Communications Layer must specify a
OtherwiseI the Routing
circuit, and if required, a NextHop.
Layer determines the adjacency.

Interfaces

Page 31

TryHardI if set, tells the Routing Layer to flush any cache
entries for the destination. Currently the only cache entries
are in endnodes attached to broadcast circuits.

CHECK TRANSMIT BUFFER (buffer)
Returns:

buffer still queued
buffer returned to ECL

This function checks the status of a previously queued transmit
buffer.
It returns the buffer to ECL after any of the
following:
o

The buffer is copied into a Routing Layer buffer.

The packet is transmitted.

The packet is discarded because the destination
unreachable and the return flag is not set.

The packet contents are transferred to a receive buffer
because the destination is unreachable and the return
flag is set.

SUPPLY RECEIVE BUFFER (buffer)
Returns:

buffer queued for receive by the Routing Layer
buffer not queued for receive by the Routing Layer

This function queues a receive buffer to the Routing Layer.

CHECK RECEIVE BUFFER (sourceI circuitI [ ~ r e v ~ o p ]buffer)
,
Returns:

buffer remains queued by the Routing Layer
buffer returned to End Communications Layer with
source node address (buffer contains a normal packet)
buffer returned to End Communications Layer
contains
a
"return
to sender" packet
Functional Specification)

(buffer
ECL

This function checks the status of a previously queued receive
buffer. It returns the buffer if the packet was received or if
the node is unreachable and the return flag is set.
The
circuit variable returns a valid circuit number (or a value for
an internal link) for each received packet.
For packets

Page 32

Interfaces

received over a broadcast circuit, PrevHop is set to the node
number of the node which forwarded the packet to this node.

Returns:

blocksize

This function informs ECL of the maximum blocksize the Routing
Layer can handle, not including routing header. ECL should not
transmit any packets larger than this size.
This value is equal to 6 less than the Segment Size
parameter set by network management.

3.4

(SS) SELF

Routing Layer Initialization Interface

This interface, between the Routing Layer Control Sublayer and the
Routing Layer Initialization Sublayer, supports the routing events
defined in Section 4 . 7 . 3 . The interface consists of commands to and
responses from the Routing Layer Initialization Sublayer.

TRANSMIT (adjacency, buffer)
Returns:

none

This function transmits a buffer containing a packet.

CHECK TRANSMIT BUFFER (buffer? status)
Returns:

buffer still queued
buffer returned to user

This function polls a buffer containing a packet that has been
I f the packet has been
sent with the TRANSMIT function.
transmitted, the buffer is returned to Routing Layer Control.
If the packet has not yet .been transmitted, a message is
returned indicating that the buffer is queued.

Interfaces

Page 33

STATUS (circuit; status)
Returns:

off
initializing
circuit accepted by Routing Layer Initialization
running; current value of circuit cost

This function returns the status of the circuit.
The off,
initializing, and running states correspond to Data Link Layer
states. For Ethernetst the only valid states are "off" and
"running."

STATUS (adjacency; status)
Returns:

unused entry
in use;
node ID, node
circuit for that adjacency

typel and

corresponding

This function returns the status of the adjacency.

REINITIALIZE (circuit)
Returns:

none

This function turns the circuit off and initializes the circuit
in such a manner that messages previously received in the
circuit will be discarded.

SUPPLY RECEIVE BUFFER (buffer; status)

Returns:

buffer accepted
buffer rejected

This function provides a receive buffer to
Initialization so that it can receive a packet.

CHECK RECEIVE BUFFER (buffer; statusl adjacency)

Returns:

no packet received
packet received, buffer returned

Routing

Layer

Interfaces

Page 34

This function polls the status of a buffer that the Routing
Layer Control has just supplied with the SUPPLY RECEIVE BUFFER
function. Upon receiving a packet into the buffer, the Routing
Layer Initialization returns the buffer to the Routing Layer
Control.

SUPPLY CIRCUIT UP COMPLETE (circuit)
Returns:

none

This function informs the Routing Layer Initialization that the
Decision Process recognizes that a circuit is up.- (The process
has completed its circuit up event algorithm.)

SUPPLY CIRCUIT DOWN COMPLETE (circuit)
Returns:

none

This function informs the Routing Layer Initialization that the
Decision Process recognizes that a circuit is down. (The
process has completed its circuit down event algorithm.)

SUPPLY BROADCAST ADJACENCY UP COMPLETE (adjacency)
Returns:

none

This function informs the Routing Layer Initialization that the
Decision Process recognizes that an adjacency on a broadcast
circuit is up. (The process has completed its adjacency up
event algorithm.)

SUPPLY BROADCAST ADJACENCY DOWN COMPLETE (adjacency)
Returns:

none

This function informs the Routing Layer Initialization that the
Decision Process recognizes that an adjacency on a broadcast
circuit is down. (The process has completed its adjacency down
event algorithm.)

Page 35

Detailed Routing Specification
4.0

DETAILED ROUTING SPECIFICATION

The routing
processes:

function

consists of

Routing data base

Forwarding data base

Decision Process

Update Process

the

following

data

bases

and

o Forwarding Process
o

4.1

Receive Process

Routing Parameters

The following parameters are settable via Network Management:
NN -- Maximum node number within the area
NA -- Maximum area number (For level 2 routers only)
NC -- Number of circuits supported by this node
NBRA -- Number of broadcast router adjacencies
this node

supported

NBEA -- Number of broadcast endnode adjacencies supported
this node

NR -- Number of broadcast router adjacencies allowed on a
given Ethernet (settable separately,for each Ethernet). The
sum of all the NR for circuits in Net-Management-State ON
cannot exceed NBRA.
Maxh -- Maximum hops possible in a path to a reachable node
within the area, suggested value twice the worst-case longest
path length in hops.
Maxc -- Maximum cost possible in a path to a
within the area, suggested value Maxh*Maxl.

reachable

node

AMaxh -- (level 2 routers only) -- Maximum hops possible in a
path
to
a reachable area, suggested value twice the
worst-case longest path length in hops.

Detailed Routing Specification

Page 36

10.

AMaxc -- (level 2 routers only) -- Maximum cost possible in a
path to a reachable area, suggested value AMaxh*Maxl.

11.

outing assumes
Maxv -- Maximum visits for a packet before
the packet is looping, suggested value is Maxh + k, where
1 < k <=Maxh

12.

Tl -- Background frequency timer for non-broadcast circuits;
maximum time period for exchanging Routing Messages with
adjacent node on a non-broadcast circuit.
The purpose of
this timer is to recover from database corruption. Suggested
value is 10 minutes.

13.

BCT1 -- Background frequency timer for broadcast circuits;
maximum time period between broadcasted Routing Messages on
the Ethernet. The purpose of this timer is to recover from
lost packets on the Ethernet. Suggested value is 10 seconds.

14.

T3 -- Hello timer.

Settable separately for each circuit.

The following are implementation parameters that are not settable
Network Management:

via

T2 -- Rate control frequency timer:
minimum time period
before another Routing Message can be sent. Suggested value
is 1 second.

CACHETIMEOUT -- amount of time Ethernet endnodes leave a
cache entry in the On-Ethernet Cache without traffic which
confirms the entry's correctness before erasing the cache
entry (See Ethernet Initialization Sublayer).
Suggested
value is 1 minute.

The following parameters are architectural constants:
1.

Infh = 31.

Max!

T3MULT -- The multiple of the neighbor's Hello Timer (on a
non-broadcast circuit) at which your Listen Timer should be
set (i.e., T4 <-- neighbor's T3*T3MULT).

BCT3MULT -- The multiple of the neighbor's Hello Timer (on a
broadcast circuit) at which your Listen Timer should be set
(i.e., T4 <-- neighbor's T3*BCT3MULT).

-- Maximum cost assignable to a circuit, 25.

Detailed Routing Specification
6.

Page 37

HIORD -- The 32 bit quantity to be prefixed to the 16-bit
node address to form the 48 bit Ethernet physical address.
HIORD = AA-00-04-00.
Therefore, if the node address is A1-A2, with A1 the least
significant byte, then the formed 48 bit Ethernet physical
address will be AA-00-04-00-A1-A2.

ALL-ROUTERS -- the multicast ID "All ~outers".
ALL-ROUTERS = AB-00-00-03-00-00.

ALL-ENDNODES -- the multicast ID "All Endnodes".
ALL-ENDNODES = AB-00-00-04-00-00.

PROT-TYPE -Ethernet.

the

protocol

type

used

Routing

the

PROT-TYPE = 60-03.
10.

DRDELAY -- the number of seconds an Ethernet
before declaring itself Designated Router

router

waits

DRDELAY = 5.

The following relationships exist between the above parameters:
1.

NN >= actual maximum address within iirea
NN < 1024

NA >= actual maximum area number (for level 2 routers only)
NA < 64

Maxh >= actual maximum path length in an area
Maxh <= 30

Maxc >= (actual maximum network path length) X (Maxi)
Maxc <= 1022

Maxv >= actual maximum path length in the entire network
Maxv <= 63

AMaxh >= actual maximum path length to any area
AMaxh <= 30

AMaxc >= actual maximum path cost to any area
AMaxc <= 1022

Detailed Routing Specification

4.2

Page 38

T3 <= 8191 (to ensure that it fits into a
multiplied by BCT3MULT or T3MULT)

16-bit

word

when

Routing Data Base (in Level 1 And Level 2 Routers)

The routing data base contains routing data summarized in Table 1.
The Network Management action of setting the Net-Management-State SELF
parameter to ON from OFF initializes the data base.
This is a
prerequisite to normal node operation. Table 1 also shows the initial
values of the data.
Table 1
Level 1 Routing Data Base
Symbo 1

Description

Adj
Circuits
HOP
Cost
Minhop

Adjacency Data Base
Circuits Data Base
Network connectivity matrix
Cost matrix
Network minimum connectivity
vector
Minimum traffic assignment
vector
Send Routing Message flags
Routing Layer identification
Home Area

Initial value

.......................................................

Mincost
Srm
Tid
HomeArea

Infc

All entries in Hop are initialized to Infh, and all

entries in Cost are initialized to Infc, except
Hop(Tid.0) and Cost(Tid,O) are initialized to 0.
This value is supplied as a SELF parameter
by Network Management.

**
.......................................................

A description of each element of the data base follows.
Adjacency Vector. This contains information about each adjacency.
entry consists of Adj(i),
where:
Adj(i)

contains the information:

Detailed Routing Specification

Page 39

state
(unused
entry,
initialization, up)

currently

nodeID -- neighbor ID

type -- neighbor node type -- Types are:

undergoing

. Level 1 router
1

. Level 2 router
. Phase IV endnode
. Phase 1 1 1 router

. Phase -111 endnode
. No
neighbor -- Adjacency is one of the broadcast
circuits
circuit -- circuit corresponding to this adjacency
Circuits vector.

blocksize requested by neighbor
neighbor's Hello Timer (T3, if neighbor is Phase 111)
time of last' Hello heard from neighbor
priority -- (BRAS only), neighbor
priority on that Ethernet
an integer in the range
adjacency

broadcast

router's

1-<NC+NBRA+NBEA> representing

Note: NC counts all broadcast circuits plus neighbors on
non-broadcast circuit.^, NBRA counts all router adjacencies
on Ethernet, and NBEA counts all endnode neighbors on
Ethernet.
Adjacencies 1 through NC are in one-to-one correspondence
with the circuits. Adjacencies [ N C + ~ ]through [NC+NBRAI
are reserved for Broadcast Router Adjacencies.
(So that
columns in the Hop and Cost matrices can correspond
exactly with the first NC+NBRA adjacencies.)

his contains information about
Circuits Vector.
entry consists of Circuit(i1,
where:

each

circuit.

Page 40

Detailed Routing Specification
Contains the information:
1.

type of circuit (~thernet,X.25, DDCMP)

state (e.9.
off, running, initializing, etc.)
determined by Initialization Sublayer

cost

datalink blocksize
envelope >

(up to

and

including

Routing

Note that on Ethernet circuits, the datalink blocksize
must be greater than or equal to BS-6 (the buffer size
SELF parameter set by network management minus 6) plus
the overhead in the routing envelope in long data
packet format.
On DDCMP circuits, the datalink blocksize must be
greater than or equal to BS-6 plus the overhead in the
routing envelope in short data packet format.
5.

Hello Timer (T3)

last time Hello issued on this circuit

Recall Timer -- Amount of time Routing should
before reinitializing the Data Link Layer

OPL -- Originating Packet Limit

counters

10.

type specific information

wait

. For Ethernet, the type specific information is:
1.

NR -- Number of BRAS allowed on this Ethernet

Priority -- the
Designated Router

Designated Router -- the ID of the router
currently chosen to be Designated Router on
this Ethernet

router's priority

. For X.25, the type specific information is:
1.

Port State -- supplied by the X.25
Layer

Blocking -- indicates
requested by this node

Data

blocking

will

Link
be

Detailed Routing Specification

Page 41

Negotiated Blocking -- indicates
also requested blocking

neighbor.

Maximum Recalls -- the maximum number of call
attempts permitted from the Data Link start
state before halting
Recall Count -- the number of call attempts
that have been made to try to initialize a
virtual circuit.
This is reset
by
the
operator turning the circuit on.
VC Type -- type of virtual circuit:

. PVC (permanent virtual circuit)
. incoming switched virtual circuit
. outgoing switched virtual circuit
VC name.
address.

For an SVC, a network name and a DTE
For a PVC, a PVC name.

is an integer in the range 1-NC representing a circuit.

Network connectivity matrix (Hop). This contains information on the
path lenqth to each destination over each circuit or BRA. An entry
consists of Hop(i,j),
where:
Hop(i,j)

represents the path lenqth from this Routing Layer to
destination, with the following values:
Value

Meaning

Self
Adjacent node
Other reachable nodes
Unreachable node

2-Maxh
Infh

the

is an integer in the range 0-NN representing a destination
address.
Destination
0 is the special destination
"nearest level 2 routern.
is an integer in the range 0-<NC+NBRA> representing self,
a circuit, or an Ethernet router adjacency.

Page 42

Detailed Routing Specification
Value

Meaning

Self
0
1-NC
circuit in Circuit(j1
[~C+ll-[NC+NBRA] Broadcast Router Adjacency in Adj(j)

Traffic assignment matrix (Cost). This contains information on the
path cost to each destination over each adjacency. This information
determines which adjacency to use for traffic to a destination.
An
entry consists of Cost(i,j),
where:
Cost(i,j) represents the path cost from this Routing
destination, with the following values:

Layer

Value

Meaning

0
1-Maxc
Infc

Self
Path cost to other reachable nodes
Unreachable nodes

the

is an integer in the range 0-NN representing a destination
address.
is an integer in the range 0-<NC+NBRA> representing self,
a circuit, or a Broadcast Router Adjacency as in the Hop
matrix.

Minimum network connectivity vector (Minhop).
This summarizes the
path length information contained in the Hop table. An entry consists
of Minhop(i),
where:
Minhop(i1 represents the path length via the adjacency yielding the
least cost path from this Routing Layer to the destination
node, with the following values:
Value

Meaning

0'
1
2-Maxh
Infh

Self
Path length to adjacent node
Path length to other reachable nodes
Node unreachable

is an integer in the range 0-NN representing a destination
address.

Detailed Routing Specification

Page 43

Minimum traffic assignment vector (Mincost). This summarizes the path
cost information contained in the Cost table. An entry consists of
Mincost(i),
where:
Mincost(i) Represents the smallest cost from this Routing
the destination, with the following values:

Layer

Value

Meaning

0
1-Maxc
Infc

Self
Smallest cost to other reachable nodes
Unreachable node

is an integer in the range 0-NN representing a destination
address.
Send Routing Message flags (Srm). The Srm flags extend permission to
the Update Process to send a Routing Message about a given destination
The Update Process determines the actual
on a given circuit.
propagation rules. An entry consists of Srm(i,j),
where:
Srm(i,j) indicates whether or not a Routing Message should
about destination i to circuit j.
i

sent

is an integer in the range 0-NN representing a destination
is an integer in the range 1-NC representing
on which to send the message

the

circuit

Routing Layer Identification (Tid). This contains the bottom ten bits
of the value set by Network Management in the ID parameter of the SELF
parameters.

Home Area (Home~rea). This contains the top 6 bits of the value
by Network Management in the ID parameter of the SELF parameters.

4.3

set

Area Routing Data Base In Level 2 Routers

The routing data base in level 2 routers contains routing data on
destination areas as summarized in Table 2. This database, like the
routing database described in section 4.1, is initialized by the
Network Management SET NODE STATE ON function.

Page 44

Detailed Routing Specification
Table 2
Area Routing Data
Description

Symbo1

--------------.-----------------------

AHOP,
AMinhop1
ACost
AMincost
ASrm
AttachedFlg

Area Hop Information
Area Minimum Hops
Area Cost Information
Area Minimum Cost
Area Send Routing Msg
Other Areas Reachable

* All entries in AHop are set to Infh, and all entries in ACost
are set to Infc upon initialization, except that AHop(HomeArea,O)
and ACost(HomeArea.0) are initialized to 0.

.................................................................

A description of each element of the area database follows.
Area Hop Information (AHop). This contains information on the number
of hops to each destination area via each adjacency. An entry
consists of AHop(i,j), where:
mop( i,j ) represent's the number of hops to destination
adjacency j

area

via

is an integer in the range 1-NA representing's destination
area
is an integer in the range 0-<NC+NBRA> representing the
attached area (0). a circuit (1-NC), or a broadcast router
adjacency ([Nc+~]-[NC+NBRA])

Area Minimum Hops (Winhop). This summarizes the information in AHop.
An entry consists of AMinhop(i), where:
\

AMinhop(i) represents the path length
along the path of least
destination area

in hops via the adjacency
cost from this node to the

is an integer in the range 1-NA representing a destination
area.

Area Cost Information (ACost). This contains information on the cost
to each destination area via each adjacency. An entry consists of
ACost ( i,j 1 , ,where:
ACost(i,j) represents the path cost to destination
circuit or broadcast router adjacency j .

area

via

Detailed Routing Specification
i

Page 45

is an integer in the range 1-NA representing a destination
area
is an integer in the range 0-<NC+NBRA> representing the
attached area (01, a circuit (1-NC), or a broadcast router
adjacency ([Nc+~]-[NC+NBRA])

Area Minimum Cost (wincost).
This summarizes the
ACost. An entry consists of AMincost(i), where

information

AMincost(i) represents the smallest cost via any adjacency from this
node to the destination area
i

is an integer in the range 1-NA representing a destination
area.

Area Send Routing Message flags (~Srm). The ASrm flags extend
permission to the Update Process to send a Level 2 Routing Message
about a given destination area on a given circuit. The Update Process
determines the actual propagation rules.
An entry consists of
~Srm(i,j), where:
~Srm(i,j)-- Indicates whether or not a Level 2 Routing Message
should be sent about destination area i to circuit j.
i

is an integer in the range 1-NA representing an area
is an integer in the range 1-NC representing
on which to send the message

Other Areas Reachable Flag (~ttached~lg).~ndicatesother
reachable if true.

4.4

the

circuit

areas

are

Forwarding Data Base In Level 1 And Level 2 Routers

The information in this data base indicates whether or not a
destination is reachable and, if reachable, what adjacency to use to
get there. This data base consists of two vectors, as follows:
Reachability vector (~each). This indicates whether or not
destination is reachable. An entry consists of ~each(i), where:

the

~each(i) is either True (reachable) or False (unreachable)
i

is an integer in the - range 0-NN
representing
the
destination node address. Destination #0 is the special
destination "nearest level 2 router".

Page 46

Detailed Routing Specification

Output adjacencies (OA). This identifies the adjacency on which to
forward a packet to a destination. An entry consists of OA(i), where:
OA(~)

represents the adjacency to be used when forwarding a
packet to destination i. OA contains one of the following
values :
Value

Meaning

0
Deliver to a Routing Layer user at this node
1-<NC+NBRA+NBEA>
An adjacency on which to forward
a packet
is an integer in the range 0-NN representing a destination
node address.
Destination #0 is the special destination
"nearest level*2 router".

4.5

Area Forwarding Data Base (level 2 Routers Only)

The information in this data base indicates whether or not a
destination area is reachable, and if reachable, what adjacency to use
to get there. This data base consists of two vectors, as follows:
Area Reachability Vector ( ~ ~ e a c h ) .This indicates whether or not the
destination area is reachable. An entry consists of AReach(i), where:
A~each(i) is either True (reachable) or False (unreachable)

is an integer in the range 1-NA representing a destination
area

Area Output Adjacencies (AOA).
This indentifies the adjacency on
which to forward a packet to a destination area. An entry consists of
AOA(i), where
AOA( i 1

represents the adjacency to be
packet to destination area i.
Value

used

when

forwarding

Meaning

0
Home Area--Use level 1 Forwarding Information
1-<NC+NBRA+NBEA>
An adjacency on which to forward
a packet

is an integer in the range 1-NA representing a destination
area.

Detailed Routing Specification
4.6

Page 47

Data Base Protection

A memory failure, a corrupted Routing Message, or a software error can
corrupt a routing data base.
Such corruptions cause a transient
disruption of packet delivery. If the corruption is transient, the
routing data bases stabilize to correct routes. If the corruption is
continuous, the routing data bases remain in a transient incorrect
state. Two conditions are necessary for self-stabilization:

4.7

The Routing
Messages.

Layer

Column 0 of the Cost and Hop matrices (in other words, the
values relating to self) cannot be corrupted. For level 2
routers, column 0 of the AHop and ACost matrices similarly
cannot be corrupted.

must

periodically

propagate

Routing

Decision Process

The Decision Process selects paths and maintains the routing and
forwarding data bases.
The following events serve as input to the
Decision Process:
Operator command to set Net-Management-State to ON from OFF.
Adjacency down
Adjacency up
Circuit down
Circuit up
Routing Message received
Operator command to change circuit cost
Operator command to change parameters Maxh or Maxc
Timer expiration
The Decision Process produces the following output:
o

~odificationsto the routing data base

Page 48

Detailed Routing Specification
o

Modifications to the forwarding data base

4.7.1 Decision Controller - The
functions:

controller

management

performs

necessary

following

receive

Routing

Performs buffer
Messages.

Supports Routing Layer initialization (Section 7).

Checks for valid Routing Message.
has :

the

valid

Routing

Message

valid checksum

A valid Routing Layer control header

If the Routing Message is not valid, then an adjacency down
event
on
an Ethernet, or a circuit down event on a
point-to-point link is generated, and the Routing Message is
discarded and recorded. A valid Routing Message is processed
I f the Routing
through end of message or end of table.
Message is too long (that is, length beyond end of table),
then the controller examines the overrun.
The data in the
overrun
portion
of
the
message
must contain values
corresponding to Infh in the hop fields and to Infc in the
cost fields.
If not, then the controller finds the highest
node number for which the values are not infc/infh, and logs
an event.
o

4.7.2

Updates the forwarding data base

Decision Algorithms -

The Decision Process contains an algorithm for computing the minimum
cost path.
It then computes the path length of that path, and sets
the reachability vector, Reach, according to whether the cost and hops
of the path found are within the set limits. It also sets the output
adjacency vector, OA, to the adjacency which is the next hop of the
minimum cost path for each destination.
The following subroutines represent the decision algorithms. They are
followed by a description of the action that the decision module takes
for each event received.

Detailed Routing Specification
Subroutine:
;
;

Rowrnin(~, I, minimum, VECT)

This routine determines the minimum for row I of
Matrix M and stores the column number in VECT(I).
Matrix M
Integer 1,minimum
Vector VECT
minimum = "big number"
FOR j = 0 to NC+NBRA DO
BEGIN
IF (~(1,j)< minimum
OR ((M(1,j) = minimum) AND
( A D J ( J ) . ~ O ~ ~>IADJ(VECT(I)).~O~~ID))
D
THEN
minimum = M(I,j)
VECT(1) = j
END IF
END

Subroutine:

~inimize(1,~,V,P1,P2,~~~~)

This routine determines entries.for vector V,
containing the minimum of each row of matrix M I
and passes to Rowrnin the vector VECT in which to store the
resulting output adjacency number.
Integer I
Matrix M
Vector V
Parameters Pi, P2
Vector VECT
Rowmin(M,Ilminimum,VECT)

IF (minimum > PI) THEN minimum = P2
V(I) = minimum
ENDIF

Page 49

Detailed Routing Specification
Subroutine:

Page 50

Routes(FirstDest, ~ a s t ~ e s t )

; This routine determines the reachability and output adjacency
; for each destination in the range FirstDest to LastDest
; within the area, with destination # 0 the nearest level 2 router.

INTEGER OLD-HOP, OLD COST
FOR i = ~ i r s t ~ e s t tLastDest
o
DO
OLD HOP = MINHOP (i)
OLDCOST = MINCOST ( i )
~inimize(row i f Cost, Mincost, Maxc, Infc, OA)
Col = OA(i)
Minhopti) = Hop(i,Col)
IF Minhopti) > Maxh THEN Set Minhop(i) = Infh
;now set OA to adjacency rather than column
IF Col <= NC AND Circuit(Col).Type=Ethernet THEN ;need
;to convert to BEA
Search for BEA with node ID i
set OA(i) to that BEA
IF (Minhop(i) = Infh OR Mincost(i) = Infc) THEN
BEG IN
Reach( i) = False
Minhopti) = Infh
Mincost(i) = Infc
END
ELSE Reach(i) = True
ENDIF
IF(MINHOP(i) < > OLDHOP OR MINCOST(i) < > OLDCOST
THEN for each k from 1 to NC
Set Srm(i,k)
END IF
ENDDO

Detailed Routing Specification

Page 51

~ubroutine:A~outes(FirstArea,LastArea)
; This routine determines the reachability and output adjacency
; for each area in the range FirstArea to 1astArea.

Integer OLD-HOP, OLD-COST
FOR i = FirstArea to LastArea
DO
OLD HOP = AMinhop (i)
OLDCOST = AMincost (i)
~inimize(row i, ACost, AMincost, AMaxc, Infc, AOA)
Col = AOA(i)
AMinhop(i) = ~ ~ o p ( i , C o l )
IF AMinhop(i1 > AMaxh THEN
Set Winhop( i) = -1nfh
;note in this case Col is the Adjacency, since a BEA cannot
;be a path to a different area
IF (AMinhop(i) = Infh OR AMincost (i) = Infc)
THEN
BEG IN
~Reach(i) = False
AMinhop(i1 = Infh
AMincost(i) = Infc
END
ELSE AReach(i) = True
ENDIF
1-F (AMinhop(i1 <> OLD HOP OR AMincost(i) <> OLD-COST
THEN FOR j = 1 t o NC
IF ~dj(j).Type=level 2 router
OR Circuit(j).Type=~thernet
THEN Set ASrm(i,j)
END1 F
ENDDO
;set value of AttachedFlg and ~op(O.0) and cost(0,O)
AttachedFlg=False
Hop(O,O)=lnfh
Cost(O,O)=Infc
FOR i = 1 to NA
IF ~Reach(i)=True AND i < > HomeArea THEN
~op(0,0)=0
Cost(0,0)=0
AttachedFlg=True
END IF
ENDFOR
CALL ~outes(0,O) ;to calculate for nearest attached
;level 2 router

Page 52

Detailed Routing Specification
Subroutine:
;

;

Check

This routine detects any corruption of column 0 in the
Hop, Cost, AHop and ACost matrices.

BEGIN
;first check column 0 of Hop and Cost
Check that Hop (Tid.0) and Cost (Tid.0) = 0
IF a level 2 router AND AttachedFlg = True
Check that Hop(O.0) and Cost (0,O) = 0
IF a level 2 router AND AttachedFlg = False
Check that Hop(O.0) = Infh and Cost (0,O) = Infc
FOR i = 0 to NN
UNLESS (i = Tid OR (i = 0 AND node is level 2 router))
Check that Hop (i.0) = Infh
AND Cost (i,0) = Infc
;now check column 0 of AHop and ACost
IF a level 2 router
FOR I = 1 to NA
IF HomeArea = i
Check that AHop (i.0) = 0 and ACost (i,0) = 0
ELSE
Check that AHop(i.0) = Infh and ACost(i.0) = Infc
ENDIF
IF any check fails, then
.
Terminate the Routing Layer
END I F
IF both checks are successful,'then
EXIT
END I F
END

Decision Process Events And Actions -

4.7.3
A.

Operator command to set Net-Management-State to ON from OFF.
1.

Tell Ethernet Daea Link the physical address consisting
of Bl-B2-B3-B4-BS-B6, where B1-B2-B3-B4 are the four
bytes of HIORD, with Bl the most significant byte, and
B5-B6 is ID, with B5 the least significant byte of ID.

Initialize Routing databases

Set ~op(Tid,O)=O and Cost(Tid,O)=O

2
IF
a
level
ACost(HorneArea)=O

Call Routes (0,NN)

router,

set

~~op(~ome~rea)=O,

Detailed Routing Specification
6.

IF a level 2 router, call ~Routes(1.N~)

Broadcast adjacency j down (note that if j <= NC,
is a circuit down event)
1.

Page 53

the

event

IF ( N C + ~ )<= j <= (NC+NBRA), then ;adjacency j is a BRA
a.

Set each entry in column "jn of Hop matrix to Infh.
IF a level 2 router, set each entry in column "jn of
AHop matrix to Infh.

Set each entry in column "jn of Cost matrix to Infc.
IF a level 2 router, set each entry in column "j" of
ACost matrix to Infc.

IF local node type is level 2, and node type
adjacency j is level 2, call ARoutes(1,~~)

Call Routes(0,~N)

IF NC+NBRA < j, THEN ;adjacency j is a BEA
NODEID <-- Adj(j).NodeID
k <-- circuit pointed to in Adj(j)
Set Hop(NODEID,k-1 .= Infh
Set Cost(N0DEID.k) = Infc
Call R~u~~s(NODEID,NODEID)

Supply "adjacency down
Sublayer

completen

Initialization

Broadcast adjacency j up
1.

IF (NC+l) <= j < = (NC+NBRA) ;j is BRA
CIRC <= ~dj(j).Circuit
FOR i = 0 to NN, Set Srm(i,CIRC)
2
router,
IF local
node
is
a
level
~dj(j).Type=level 2
FOR i = 1 to NA, Set A S ~ ~ ( ~ , C I R C )

AND

IF NC+NBRA < j, THEN ;j is BEA
NODEID <-- ~dj(j).Node~D
k <-- Adj ( j ) .Circuit
Set Hop(NODEID,k) = 1
Set Cost(NODEID,k) = cost of Circuit(k1
Call Rou~~~(NODEID,NODEID)

Supply "adjacency up complete" to Initialization Sublayer

Page 54

Detailed Routing Specification
D.

Circuit j down
1.

Call Check.

Set each entry in column "j" of Hop matrix to Infh.
IF a level 2 router, set each entry in column "j" of AHop
matrix to Infh.

Set eachentry in column "j" of Cost matrix to Infc.
IF a level 2 router, set each entry in column "j"
ACost matrix to Infc.

FOR each adjacency k pointing to circuit j
Declare broadcast adjacency k down

IF local node type is level 2 router
Call ~Routes(1,N~).

Call ~ou.tes(0,NN).

Supply "circuit
Sublayer.

down

complete"

Initialization

Circuit j up
Case 1: Circuit j is a non-broadcast circuit
number as determined by Initialization Sublayer

with

k=node

Hop(k, j)=l

IF ~ircuit(j).~ostis not > 0 THEN the Routing
terminates.

Layer

Cost(k,j)=~ircuit(j).Cost

Call ~outes(k.k)

Call Check.

IF Adj(j).Type=endnode, THEN

Set Srm(i,j) FOR i = 0 to NN

IF
local
node
type
is
level
2
router,
Adj(j).Type=level 2, set ASrm(i,j) FOR i = 1 to NA

Supply "circuit up complete" to Initialization Sublayer.

Case 2:
1.

Circuit j is a broadcast circuit

Call Check

AND

Detailed Routing specification

Page 55

IF Circuit(j).Cost
terminates.

FOR i = 0 to NN, set Srm (i,j)

is not >

0 THEN

the

Routing

Layer

IF local node type is level 2 router, set ~ ~ r m ( i , jFOR
) i
1 to NA

5.
F.

Supply "circuit up complete" to Initialization Sublayer.

Levelll Routing Message received on adjacency j, 1 <= j <=
(NC+NBRA).
The Routing Message contains destinations in set

Call Check.

Copy hop subfield of Routing Message for each i in set S,
onto row i , column "j" of Hop matrix.

Add 1 to Hop (i,j) for each i in set S.

Copy cost subfield of Routing Message for each i
S, onto row i, column "j" of Cost matrix.

IF Cost of Circuit pointed to by adjacency j is not > 0,
THEN the Routing Layer terminates. Otherwise, add that
cost to Cost (i,j) for each i in set S.

FOR each i in set S, Call R~utes(i.i)~

set

Level 2 Routing Message received on adjacency j (level 2
routers only). The Routing Message contains areas in set S o
1.

Call Check.

Copy hop subfield of Routing Message, for each i
S, onto row i , column " j " of AHop matrix.

set

Add 1 to AHop (i,j) for each i in set S.

Copy cost subfield of Routing Message, for each i in
S, onto row i , column "j" of ACost matrix.

set

IF Cost of Circuit pointed to by adjacency j is not
greater than 0, then the Routing Layer terminates.
Otherwise, add that cost to Cost (i,j) for each i in set

FOR each i in set S, Call ~Routes(i,i).

Detailed Routing Specification
H.

Page 56

Circuit j cost change
Call Check.
Calculate the difference between the new cost and the old
cost for circuit j. Note that the new cost and the old
cost must both be greater than 0, otherwise the Routing
Layer terminates.
Add this difference to each entry in column "j" of
matrix.

Cost

IF circuit type is broadcast, add this difference to each
entry in each column k of the Cost matrix, where k is a
broadcast router adjacency with circuit=j
Call Routes(0,NN).
IF local node is level 2 router, add this difference
each entry in column "j" of the ACost matrix.

IF local node is level 2 router and the circuit type is
broadcast, add this difference to each entry of the ACost
matrix for each column k, where k is a broadcast router
adjacency with circuit=j
IF local node is level 2 router, call ARoutes(1,NA).
I.

Maxh, Maxc, AMaxh, or AMaxc change
1.

Call Check.

Call ~outes(0,NN)

IF local node type is level 2 router, Call ARoutes(1,NA)

Tl Timer expires

Call Check.

FOR j = 1 to NC
a.

IF Circuit(j).Type=nonbroadcast, AND
Adj(j).Type=router (level 1, level 2, or
THEN
FOR i = 0 to NN, Set Srm(i,j)
IF local node is level 2 router AND
Adj(j).Type=level 2, AND
Adj(j).Circuit.~ype=nonbroadcast THEN
FOR i = 1 to NA, Set ASrm(i,j)

Phase

111)

Detailed Routing Specification

Call Routes(0,~~).

IF local node is level 2, Call ~ ~ o u t e s ( 1 , ~ ~ )

BCT1 Timer expires
1.

4.8

Page 57

Call Check.

IF ~ircuit(j).~ype=broadcast,THEN
FOR i = 0 to NN, Set Srm(i,j)

IF local node is level 2 router AND
IF Circuit(j).Type=broadcast, THEN
FOR i = 1 to NA, Set ~Srm(i,j)

Update Process

The Update Process propagates Routing Messages and determines their
content. It consists of an algorithm and a format module. The Update
Process accepts the following as input:
o

The minimum hop vector, Minhop

The minimum cost vector, Mincost

The area minimum hop vector, AMinhop

The area minimum cost vector, AMincost

The Send Routing Message flags, Srm

The Area Send Routing Message flags, ASrm

The Update Process produces a Routing Message for an adjacent node
output.

Detailed Routing Specification

Page 58

Update Algorithm - A Level 1 Routing Message containing a given
set of destinations is sent on a circuit j when a buffer is available
from the quota given to the Routing Process for Update use, AND at
least T2 has elapsed since the last transmission of a Routing Message
containing the same destinations on circuit j, AND some Srm(i,j) is
set, for at least one i in that set of destinations.

4.8.1

A Level 2 Routing Message is sent on a circuit j when a buffer is
available from the quota given to the Routing Process for Update use,
AND at least T2 has elapsed since the last transmission of a Routing
Message containing those areas on circuit j, AND some ASrm(i,j) is
set, for at least one i in that set of areas.
Any algorithm that sends, as a minimum, all information flagged by the
Srm and ASrm flags can be used. (An algorithm may send more data than
this to simplify the algorithm or reduce the data storage for Srm
flags.
When the circuit is of type Ethernet, the Routing Message is
the multicast ID "all routers".

sent

Care must be taken that no nodes, areas, or circuits are starved. For
example, an algorithm that does not scan through all circuits and
destination (nodes or areas) before restarting, might never reach some
circuit or destination.
Care must also be taken that systematic ordering of the transmitted
segments does not cause the same segments to always be lost. For
example, on an Ethernet, if all segments are sent, one after another,
in rapid succession, the last segments might be lost with high
probability. Thus, on Ethernets, each time a periodic complete
Routing Message is sent, the segments should be cycled through, so
that each segment gets a chance to be the first segment.
The T2 timer is intended to be restarted on a circuit after all
destinations with Srm or ASrm flags set during one pass through are
transmitted on that circuit.
On a point-to-point circuit, a Routing Message may be as long as the
neighbor's blocksize.
On an Ethernet circuit, a Routing Message may
be as long as the minimum blocksize of all BRAS on that circuit.

4.9

Forwarding Process

The Forwarding Process supplies and manages the buffers necessary
route-through.
Packets are discarded if buffer thresholds
exceeded.

for
are

Detailed Routing Specification

Page 59

Packet formats, and names of fields, are described in Section 10.
Data packets can be in one of three formats:
1.

long format

short format

Phase I 1 1 format

Packets in long format have bit 2 of the FLAGS byte=l.
Packets in
short format or Phase I 1 1 format have bit 2 of the FLAGS byte=O.
Phase IV nodes are required to be able to receive short format on
point-to-point circuits, and long format on Ethernet circuits. They
should transmit short format on point-to-point circuits, and long
format on Ethernet circuits. They must receive and transmit Phase 1 1 1
format to Phase 1 1 1 adjacencies.
Packets in all three formats have bit 6 ("Future versionV)=0.
but do not log packets received with bit6 = 1.

is card

Discard and log (as "message format error") short packets (in other
words, packets with less than a packet route header) and packets with
an invalid route header (including packets in short format received on
an Ethernet circuit, if this node cannot handle such packets, or
packets received in long format on a point-to-point circuit, i f this
node cannot handle such packets).
If the incoming adjacency is a Phase I 1 1 endnode or router, if the top
6 bits of Destination ID=0, fill in "HomeArea" in the top 6 bits of
Destination ID. I f the top 6 bits of Source ID are 0, fill in
'HomeArea" in the Source ID field.
If the source and destination are attached Ethernet endnodes, on
same Ethernet, set the intra-Ethernet bit.

the

If the destination is in a foreign area, and the local node type is a
level 1 router, or the local node type is a level 2 router and
AttachedFlg=False, then forward based on O A ( 0 ) .
I f the destination is in a foreign area, and the local node type is a
level 2 router and AttachedFlg=True, then forward based on AOA(foreign
area).
I f the adjacency the packet is to be forwarded on has node type Phase
I 1 1 router or Phase 1 1 1 endnode, clear the area field in the
Destination ID. I f the area in Source ID is "HomeArea", clear that as
well. I f the area in Source ID is not "HomeArea" and the ~estination
is the next node, and the Destination's node type is "Phase I 1 1
router" or "Phase I 1 1 endnode", do not forward the packet. Instead
drop the packet or return it to sender, as with an unreachable
destination.

Page 60

Detailed Routing Specification

I f the destination is unreachable, and "return to sender requested" is
set, set "return to senderw, clear "return to sender requested",
switch the destination and source ID fields, and forward the packet
towards the new destination (the previous source). Otherwise, drop
the packet.

If the circuit the packet is to be forwarded on is an Ethernet, and
the packet is in short format, then reformat the packet to long
format. If the "intra-Ethernet bitw is set, clear the bit unless the
packet is to be forwarded onto the same circuit from which it was
received.
When originating a
intra-Ethernet bit.

packet

Ethernet,

always

set

the

If the circuit the packet is to be forwarded on is point-to-point, and
the packet is in long format, check that the first 4 bytes of D-ID and
S-ID are set to HIQRD. Drop the packet and log (as "message format
error") if they are not. Reformat the packet to short format.

4.10

Receive Process

The Receive Process receives packets from the Data Link Layer.
then passes the packet to the appropriate process, as follows:

4.11

Packet Type

Process

Routing Message

Decision Process

Hello Message

Node Listener Process

Packet for Self

End Communications Layer

Packet for other
destination

forwarding Process

Loop Detector Process

The loop detector limits the number of nodes that a packet can visit.
It increments the node visit field in the packet route header by one.
The loop defector discards the packet if 'this number exceeds the
maximum node visit limit, Maxv. Note that the parameter Maxv must
always be greater than or equal to the parameter Maxh.

Detailed Routing Specification

Page 61

The algorithm the loop detector executes when it receives a packet
the following:
Add 1 to node visit field in packet route header.

IF ((node visit > Maxv) and ("return to sender" is not set))
If "return to sender requested" is set,
set "return to sender"
clear "return to sender requested"
reverse source and destination
forward the packet towards the (new) destination.
Else drop the packet and record
END IF
IF ((node visit > 2 * ~ a x v )and ("return to sender" is set))
Discard packet and record
END I F

5.0

DETAILED CONGESTION CONTROL SPECIFICATION

The transmit management subroutine handles
congestion
Transmit management consists of the'following components:

control.

Square root limiter. Reduces buffer occupancy time per packet
by using a square root limiter algorithm (Appendix F). The
square root limiter also queues packets for an output circuit,
and prevents buffer deadlock by discarding packets when the
buffer pool is exhausted. Section 5.1 specifies the Square
Root Limiter Process.

Originating packet limiter. Limits originating packet traffic
when
necessary to ensure that transit packets are not
rejected. An originating packet is a packet from the ECL at
this node. A transit packet is a packet from another node to
be routed through to another destination node.

Flusher. Flushes packets queued for
gone down.

Packet size checker. Resolves differences between packet size
and Data Link receive blocksize.

adjacency

that

has

Page 62

Detailed Congestion Control Specification
5.1

Square Root Limiter

The square root limiter discards a transit packet or rejects an
originating packet when the output circuit queue exceeds the discard
threshold, Ud. Ud is given as follows:
Ud = CEILING (NB/ SQRT(NC))
where:

Number of Routing Layer buffers for all output circuits.

NC = Number of active output circuits.

5.2

Originating Packet Limiter

The originating packet limiter first distinguishes between originating
packets and transit packets. It then imposes a limit on the number of
buffers that originating packets can occupy on a per circuit basis.
In times of heavy load, originating packets may be rejected while
transit packets continue to be routed.
This is done
because
originating packets have a relatively short wait, whereas transit
packets, if rejected, have a long wait -- a retransmission period.
The originating packet limiter accepts as input:
o

A packet received from End Communications Layer

A transmit complete from the
Communications Layer packet

Data

Link

Layer

for

End

The originating packet limiter produces the following as output:
o

Packet accepted

Packet rejected

Modifications to originating packet counter

There is a counter, N, and an originating packet limit, OPL, for each
active output circuit.
Each N is initialized to 0. Each OPL is
initialized to the number of buffers necessary to prevent the circuit
from idling.

Detailed Congestion Control Specification
5.3

Page 63

Flusher

The flusher ensures that no packet is queued on a circuit whose
is not RUN, or on a nonexistent adjacency.

5.4

state

Packet Size Checker

The packet size checker checks the size of each packet that it is
about to queue on an output adjacency. This includes packets from
both the End Communications Layer at this node and transit packets.
When
the packet size exceeds the Data Link receive blocksize
(established during Routing Layer initialization), the packet size
checker discards the packet and records the event. Endnodes on a
broadcast circuit are not required to have a packet size checker.

6.0

ROUTING LAYER INITIALIZATION SUBLAYER

The Initialization Sublayer masks the characteristics of the different
kinds of Data Link Layers from the Control Sublayer. The only two
broadcast
or
types of circuits the Control Sublayer sees is
non-broadcast.
In Phase IV, the only type of supported broadcast circuit is the
Ethernet.
The only types of supported non-broadcast circuits are
DDCMP point-to-point, DDCMP multipoint, and X . 2 5 .

6.1

Version Skew

In initialization with an adjacent node, a node must drop and ignore
Initialization Messages with higher version numbers. The version
number check must be done before looking at any of the other fields in
the
Initialization Message, since higher version Initialization
Messages might not be compatible with lower version messages.
It is the responsibility of the node with the higher version number to
note that it has a neighbor with a lower version number, and if the
node with the higher version number knows about the earlier protocol,
that node must start sending Initialization Messages with the lower
version number. If the node with the higher version number does not
know about the earlier protocol, an initialization failure, version
skew event is logged.

Page 64

Routing Layer Initialization Sublayer

In comparing version numbers, the version number byte is the only byte
compared.
The ECO number byte and the User ECO number byte are not
accessed during the comparison.

7.0

INITIALIZATION SUBLAYER:

DDCMP OR X . 2 5

The Routing Layer initialization is a start-up procedure between two
adjacent nodes.
The procedure involves exchanging Routing Layer
Initialization Messages and possibly Routing Layer
Verification
Messages.
This exchange identifies the nodes to each other and
provides additional node information. This section describes:

7.1

The Routing Layer Initialization circuit states

The Routing Layer Initialization circuit events

The Routing Layer
requirements

The Routing Layer Initialization state table and diagram

Initialization operation

and

message

Node Listener Process

The Node Listener Process detects node failures. The process consists
of a controller and an algorithm module. The Node Listener accepts
the following as input:
o

Hello Message received

Any message received 'on a non-broadcast circuit

Timer pulse received

The Node Listener Process produces the following as output:
o

Modifications to the adjacency data base

Initialization Sublayer: DDCMP or X , , 2 5

Page 65

7.1 .1 Node Listener Controller - The Node Listener Controller manages.
the buffers necessary for receiving Hello Messages. It also checks
for valid Hello Messages. A valid Hello Message contains a valid
Routing Layer control header and valid data. If the Hello Message is
not valid, then a circuit down event is generated, and the Hello
Message is recorded and discarded.

7.1.2 Node
Listener
Algorithm - The
Node
Listener
algorithm
determines when the adjacent node is no longer talking. Such a node
is considered down. Consequently, the circuit is reinitialized.
The
following describes the algorithm for handling each Node Listener
event.

Hello Message or any message received on adjacency j
1.

Reset T4 by:
Set TEMP = T3
If ~dj(j).~ype=PhaseIV router or endnode
Set TEMP = neighbor's Hello Timer
Endif
Set T4 = TEMP*T3MULT

If received message is Hello, check that TEST DATA is all
octal 252

Timer pulse
1.

Decrement T4

IF (T4 <= 0 1 , then
Reset T4
Set circuit state to CR ("circuit rejected.")
END I F

7.2

Node Talker Process

The Node Talker propagates Hello Messages.
to an adjacent node when:

It sends a

Hello

Message

Initialization Sublayer: DDCMP or X . 2 5

Page 66

T3 has elapsed since the last transmission of any message.

A circuit has come up.

The Node Talker can be interlocked with the Decision and Update
Processes. When either Decision or Update fails, then the Node Talker
ceases.

7.3

Routing Layer Initialization Circuit States

The Routing Layer Initialization circuit states are:
(Symbol) State

Description

(Ru) RUN

The Routing Layer can use the circuit to
transmit packets between two nodes.

(CR) CIRCUIT REJECTED

The circuit is degraded.
To
avoid
excessive packet delay the circuit will
be declared down. The Routing Decision
Process has not yet processed a circuit
down event.

(DS) DATA LINK START

The circuit is undergoing
Layer initialization.

Data

Link

(RI) ROUTING LAYER INITIALIZE The circuit has successfully undergone
Data Link initialization and is waiting
a
Rout ing
Layer
to
receive
Initialization Message.
(RV) ROUTING LAYER VERIFY

A valid Routing Layer Initialization
Message
has been received for this
circuit
and
the
circuit
requires
verification.

(RC) ROUTING LAYER COMPLETE

The Routing Layer has completed a valid
exchange of Routing Layer Initialization
and possibly Routing Layer Verification
Messages.

(OF) OFF

The Routing Layer
cannot
use
the
circuit.
The Routing Decision Process
has not yet processed a circuit down
event.

(HA) HALT

The Routing Layer cannot use the circuit. A circuit down event is required.

Initialization Sublayer; DDCMP or X . 2 5
7.4

Page 67

Routing Layer Initialization Circuit Events

The Routing Layer Initialization circuit events are as follows:
(Symbol) Description
(nri)

The Routing Layer received
Initialization Message.

valid

new

Routing

Layer

(nrv)

The 'Routing Layer received
Verification Message.

valid

new

Routing

Layer

(rt)

The Routing Layer timed out.

(sc

The Routing Layer received a start complete notification (in
other words, a transition from the initializing state to the
running state) from the Data Link Layer.

(ste)

The Routing Layer received a start notification (in other
words, a transition from any state to the stop state) or
threshold error notification from the Data Link Layer.
In the case of X . 2 5 , a start notification is given by the
Data Link Layer upon receipt of a "Clear Indication" or
"Reset" packet, or when a data error is observed.

(opo

Operator turned circuit on.

(opf)

Operator turned circuit off.

(im)

The Routing Layer received an invalid
Routing
Initialization Message or an unexpected message.

(re)

The Routing Layer received a reject complete from
circuit rejection component of the circuit monitor.

( cdc )

The Routing Layer Initialization r.eceived a circuit down
complete event from the Decision Process in the Routing
Layer Control Sublayer.

( cue

The Routing Layer Initialization received a circuit up
complete event from the Decision Process in the Routing
Layer Control Sublayer.

Layer
the

When the Data Link Layer has initialized, a timer starts.
I f the
timer expires before the circuit accepted state is reached, then the
circuit is reinitialized. If the timer expires after the circuit
accepted state is reached, then the timer is ignored.

Page 68

Initialization Sublayer: DDCMP or X . 2 5
7.5

Routing Layer ~nitializationOperation And Message Requirements

The actions required of the Routing Layer Initialization
'Routing Layer Initialization State Table" following are:

the

Issue reinitialize command to the Data Link Layer
Recall Timer.

Issue stop to the Data Link Layer.

Send a valid Routing Layer Initialization Message.

Send a valid Routing Layer Verification Message.

valid Routing
characteristics:

Layer

Initialization Message

has

and

the

start

following

A valid Routing Layer control header with node
than or equal to this node's NN

address

less

If this node is a level 1 router, then the neighbor's home
area must match HomeArea, unless the neighbor is Phase 1 1 1

If this node is a level 2 router, then the neighbor's home
area must match HomeArea unless the neighbor node type is
level 2 router or Phase I11

A received Data Link blocksize greater than or equal to the
maximum (Routing Message size of Routing Message containing
NN nodes if neighbor is Phase 111 router, Hello Message size,

246)

An acceptable routing version (see section on Version Skew!

A valid Routing Layer Verification Message has
with the function value.

7.6

value

that

agrees

Routing Layer Initialization State Table And Diagram

The following table shows all the possible state transitions from the
Routing Layer's viewpoint at a single node. It also shows the events
that cause the state changes and the actions the Routing Layer
Initialization takes, if any, upon the occurrence of an event. The
numbers in the "actions" column correspond to those in the list of
actions above.

Initialization Sublayer: DDCMP or X . 2 5

Page 69

Routing Layer Initialization State Table
This table shows each possible new state and action relating to the
occurrence of each event in each state. The actions are shown by a
slash ( / I followed by the number of the action. A dash ( - ) signifies
no action. The actions numbers are defined above.

Old State
RI
RV

CR/-

DS/1

OF/-

HA/-

Event

ste

DS/1

* NOTE
There are four possible new state/action sets for this transition, as
follows:
1.

Action: 4;
New
received message;

state:
RV;
Verification requested
verification required by this node.

Action: 4; New
received message;

state:
RC;
Verification requested in
verification not required by this node.

Action: - * New state: RV; Verification not requested
received message; verification required by this node.

Action: - ,- New state: RC; Verification not requested in
received message; verification not required by this node.

Initialization Sublayer: DDCMP or X.25

Page 70

The Routing Decision Process generates circuit down events in the
states CR and OF. It generates a circuit up event in the state RC.
Once the Recall Timer is set, it must expire before
reinitialize command is given to the Data Link Layer.

another

The following figure shows the Routing Layer state transitions.

Legend:

---1
I
Note:

----

contains symbol representing Routing Initialization
state

These state transitions are not guaranteed.

initialization Sublayer: DDCMP or X.25
7.7

Page 71

Closing Down

If at all possible, before a router is brought down, it should
reinitialize the Data Link Layer, causing its neighbor to bring down
the circuit without unnecessary delay. In the case of DDCMP, the
Routing Layer should command DDCMP to put out a DDCMP Start. In the
case of an X.25 SVC, the Routing Layer should command X.25 to do a
Clear of the circuit. In the case of an X.25 PVC, the Routing Layer
should command X.25 to do a Reset of the circuit.

8.0

ADDITIONAL INITIALIZATION SUBLAYER FOR X.25

8.1

Incoming Call Control

If the circuit parameter VC Name is set by network management for a
circuit of type incoming SVC, then Routing should reject an incoming
call unless the DTE address and network name match those in VC Name.

8.2

Error Control

Error Control is introduced to detect possible corruption of data
within the public data net. A 16 bit cyclic redundancy check word
based on the CRC-16 polynomial is prefixed to each Routing Layer
datagram. The check character is generated on the message as a string
of bits beginning with the LSB of the message ending with the MSB of
the message.
(Note- A Routing Layer datagram may traverse the X.25 net as a number
of X.25 packets as described below.) Received datagrams are checked
for data errors. I f an error is found, it is accounted for, by
incrementing the error counter in the Circuit database, the datagram
is discarded, and the event is treated as -an "ste" event by the
Initialization
Layer.
This
will
cause
the
circuit to be
reinitialized.

8.3

Fragmentation, Assembly And Blocking

Fragmentation of Routing Layer datagrams may be required if the Public
Data network requires a smaller packet size than that of DECnet. This
poses a twofold problem.
1.

The Routing Layer datagram must be fragmented into multiple
packets before transmission and reassembled on receipt.

Page 7 2

Additional ~nitializationSublayer for X.25
2.

Transmitting the Routing Layer datagram in multiple packets
may require additional buffer capacity depending on the
characteristics of the lower level implementation.
This
increase in the buffer requirement is due to the 5 byte X.25
packet header.

The buffer problem above is not solved here as it is implementation
dependent.
A particular implementation may solve this, for example,
by dedicating a fixed number of fragmentation/assembly buffers per
virtual circuit or via hardware capable of supplying packet headers
from separate buffers.
The maximum packet size supported on a particular virtual circuit will
be set via Network Management.
The actual packet size will be
negotiated when the circuit is established and will be stored in the
circuit data base. Fragments of datagrams will be transmitted across
the data link interface sequentially. All but the last packet will
specify "more data to follow" in the TRANSMIT call. Similarly,
receive packets will be checked for "more data to follow" and
assembled into Routing Layer datagrams before being forwarded to Error
Control.
In some instances, blocking of multiple Routing datagrams within a
single X.25 packet may be motivated by vendor facilities and tariffs.
When X.25 vendors support large packet sizes, improvements in cost and
responsiveness may be obtained by blocking.
(Blocking is also
somewhat motivated by the presence of ECL control messages.)
Blocking is enabled or disabled via the Network Management interface.
It may be desirable to disable blocking when operating at small packet
sizes. Negotiation is performed at Routing Layer initialization to
determine whether blocking will be used on a given virtual circuit.
When blocking has been enabled by network management, the "blocking
requested" bit
in
the
"TIINFO" field of the Routing Layer
Initialization Message is set.
Blocking is used if both sides have requested it.
When blocking is in use, Routing Layer datagrams are viewed as a
serial stream of data (fragmentation procedures discussed above are
not used). A header is prefixed to the datagram (including the CRC
generated by the error control function) and it is placed in an X.25
packet assembly buffer. Datagrams are loaded into packet assembly
buffers until full. In general filling assembly buffers will require
fragmenting datagrams. The figure below shows the mapping of the
Routing Layer data stream onto the X.25 data stream.
Routing Layer datagrams
data stream

---------- >
2
1
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
x
6

X.25
X
I

Frames Routing Layer datagrams
Frames X . 2 5 packets

Additional Initialization Sublayer for X.25

Page 73

The header that is prefixed to the datagram is a two byte field
is a count of the number of bytes used to frame the datagram.
The message formats for datagrams are illustrated below
cases of blocking not enabled and blocking enabled.

for

which

the

two

BC - 16 bit byte count of Routing Layer datagram and CRC
DG - Routing Layer datagram
In both cases fragmentation may occur at any point in the message.
Efficient implementation of a blocking facility requires a buffer
management policy sensitive to the blocking operation. A specific
policy is not required by the architecture as it will not impact
correct operation.
Under light load conditions, a decision must be
made as to whether to pass a partially filled packet across the X.25
packet level interface or to wait in anticipation of additional data
to fill the packet. Policies may require a timer to perform this
function.
However, the policy recommended here is independent of a
timer. The policy is basically to buffer as few X.25 packets as
possible in X . 2 5 level 3 (one or two). The Routing Layer supplies
packets to level 3 only as the short queue permits, thereby retaining
the data as long as possible without sacrificing efficiency. This
policy will have the property of being cost efficient under moderate
to heavy loading and always being responsive.

8.4

Closing Down

It is costly to keep attempting to bring an X.25 circuit up if it is
not usable.
Thus a retry counter is maintained for Routing Layer
time-outs (rt Initialization circuit event) and X.25 Data Link Layer
Start Notifications (ste Initialization circuit event). When in state
DS, if actions rt or ste occur MAXIMUM RECALLS in a row, the
transition is made to the OF state, requiring operator intervention to
bring the circuit back up.

Initialization Sublayer: Ethernet
9.0

INITIALIZATION SUBLAYER:

9.1

Routers

9.1.1

Page 74

ETHERNET

Ethernet Router Hello Messages -

Routers broadcast Ethernet Router Hello Messages to the multicast ID
'all routers".
These contain the transmitting router's ID, T3, and
PRIORITY, plus a list containing information about the other routers
the transmitting router has heard from "recently enough" (described
below), and provided that the number of routers does not exceed NR.
Each entry in the list contains a router's ID, that router's PRIORITY,
and a bit indicating whether that router includes the transmitting
router in its Ethernet Router Hello Messages.
When a new router NEWROUTER is heard from, and NR and NBRA are not
exceeded, NEWROUTER is included in future Ethernet Router Hello
Messages by this node. An adjacency slot is set aside for NEWROUTER,
on an adjacency numbered between [ N C + ~ ]and [NC+NBRA]. The state of
the adjacency is set to "initializing", until it is known that the
communication between this node and NEWROUTER is two-way.
When NEWROUTER reports this node's ID in its Ethernet Router Hello
Messages, the adjacency's state is changed to "up", and an adjacency
up event is generated.
A separate Listen Timer is kept for each Ethernet neighbor. The value
of the Listen Timer is BCT3MULT * neighbor's T3 as reported in its
Hello Messages in the TIMER field. If a neighbor is not heard from in
that time, it is purged from the database and an adjacency down event
is generated.
If a Hello is received from neighbor OLDROUTER, and this node's ID is
no longer in OLDROUTER'S Hello Message, the adjacency's state is
changed to "initializing", and an adjacency down event is generated.

I f a router already has heard from NR routers on an Ethernet, and a
new router issues an Ethernet Router Hello Message, the router with
lowest priority is purged from the database (or the new router is
ignored, if its priority is lowest). If more than one router has the
lowest priority, the router with the lowest ID is purged.
(An
Ethernet address is treated in numerical comparisons as an unsigned 48
bit integer, with the first byte transmitted, and the leftmost byte as
written, treated as the least significant byte.) If an old router must
be purged, an adjacency down event is generated for the adjacency
occupied by the old router.
After the Control Sublayer issues an "adjacency down complete", then
an adjacency up event is generated for that adjacency number with the
new neighbor.

Initialization Sublayer: Ethernet

Page 75

Designated Router -

9.1.2

The Designated Router is the highest priority router, with numerically
highest ID breaking ties.
The set of all routers to be considered
includes all routers in the area on that circuit in the "up" or
"initializin'g" states. (See Section 9.1.1 for definition of numerical
comparison of Ethernet addresses.)
A new router must not declare itself to be the Designated Router until
DRDELAY*T2 has transpired.

The Designated Router periodically broadcasts its Ethernet
Hello Message additionally to the multicast ID "all endnodes".

Router

When To Transmit Router Hellos -

9.1.3

An Ethernet Router Hello Message is sent immediately when the
has been turned on.

circuit

It is also sent when at least T2 has transpired since the last
transmission of a Router Hello Message on this circuit by this node
and either:
1.

BCT3 has expired

the contents of the next Hello Message to be transmitted
would differ from the contents of the previous Hello Message
transmitted by this node, or

this node ha$ decided to become Designated Router

For maximum
Sending of a Hello Message should restart T2 and T3.
performance in the case of a clock with fine granularity, these should
be restarted only after successful transmission of the Hello Message
by the Data Link Layer.

9.1.4

Closing Down -

If at all possible, before a router is brought down, it should issue
an empty Ethernet Router Hello Message, which will cause all routers
receiving this message to bring down their adjacencies to the
departing router, without unnecessary delay.

Initialization Sublayer: Ethernet
9.1.5

Page 76

Database Of Endnodes -

An endnode is entered into the adjacency database, on an adjacency
between [NC+NBRA+~] and [NC+NBRA+NBEA] when a hello is received from
the endnode, provided there is room (not more than NBEA endnodes have
been heard from).
An adjacency up event is generated on that
ad jacency

timer is set for the value BCT3MULT times the timer reported in the
endnode's Ethernet Endnode Hello Message. If another Hello is not
received from the endnode before that timer expires, the endnode is
purged from the database, provided that the Control Sublayer has
issued an "adjacency up complete" on this adjacency (otherwise the
adjacency will be cleared as soon as the "adjacency up complete is
received from the Control Sublayer).

When the adjacency is cleared, the Control Sublayer is informed of an
"adjacency down" event, and the adjacency can be reused after an
"adjacency down complete" is received from the Control Sublayer.

9.1.6

Multiple Areas On An Ethernet -

If there are multiple areas on an Ethernet, routers must
control traffic from other areas.

filter

out

When a level 1 router receives an endnode or router hello on an
Ethernet, it checks that the area field in the ID equals "HomeArea".
If not, the packet is dropped without being logged. Thus a level 1
router will not keep any adjacencies from other areas.
A level 2 router must keep adjacencies to other level 2 routers,
besides the adjacencies in its own area. A level 2 router drops
without logging any Ethernet Endnode Hello Messages it receives from
other areas, and any Ethernet Router Hello Messages from level 1
routers (node type in IINFO field indicates level 1 router) in other
areas.
When a level 2 router R receives an Ethernet Router Hello Message from
a level 2 router A in another area, it does not drop the packet. R
does include A in its adjacency database. R also includes A in E-LIST
in its Ethernet Router Hello Messages. However, R does not include A
in R's calculation of Designated Router for the Ethernet.

~nitializationSublayer: Ethernet
9.2

Page 77

Endnodes

9.2.1

Ethernet Endnode Hello Messages -

Endnodes broadcast Ethernet Endnode Hello Messages to the multicast ID
"all routers" when they first come up, and periodically thereafter,
with period T3.

9.2.2 Designated Router's Ethernet Router Hello Message - When an
Ethernet Router Hello Message is received by an endnode, ID is checked
to ensure that it is in the endnode's area. If the area field in ID
does not equal "HomeArea", the packet is dropped without being logged.
Otherwise, ID is copied into the endnode's ROUTERID variable, T4 is
set to BCT3MULT times the value in HELLOTIME, and an adjacency up
event is generated.
If ROUTERID had a value different from ID, an adjacency down event is
generated, followed by an adjacency up event. I f T4 expires without
receipt of a Designated Router's Ethernet Router Hello Message,
ROUTERID is erased and an adjacency down event is generated.

9.2.3

On-Ethernet Cache -

The endnode maintains a cache of destinations with which it is in
contact and which are on the Ethernet. An entry for A is made i f a
packet is received with the "intra-Ethernet bit" set, from source A.
An entry for A is erased if:

9.2.4

the Routing Layer user gives the Routing Layer a packet
destination A and the directive "Tryhard"

with

no traffic is received from A validating the cache entry for
CACHETIMEOUT (a parameter), (i.e. no packet is received that
would have created an entry for A in the cache as per the
rules above)

is the least recently used cache entry, and the room in the
cache is needed for a new entry

Filling In "next Hop" In Packet Headers -

On transmission of a packet for destination A, fill in the next hop in
the Ethernet header according to the rules:
1.

if A is in the cache, send to A

Page 78

Initialization Sublayer: Ethernet

10.0

else if ROUTERID is filled in, send to ROUTERID

else send to A

MESSAGES

This section describes the message formats of the Routing
protocol. There are two types of Routing Layer messages:
o

Layer

Packet route header -- This is used for ECL segments, which
may require forwarding. There are two possible formats for
data packet route headers:
1.

short format (identical to Phase I 1 1 format)

long format

Routing Layer control -- These control Routing Layer routing
and initialization functions. On non-broadcast circuits the
types of Routing Layer control messages are:
1.

Initialization Message

Verification Message

Hello and Test Message

Level 1 Routing Message

Level 2 Routing Message

On broadcast circuits the

types

messages are:

Ethernet Router Hello Message

Ethernet Endnode Hello Message

Level 1 Routing Message

Level 2 Routing Message

Routing

Layer

control

Messages
10.1

Page 79

Message Format Notation

The following notation is used to describe the messages:
FIELD (LENGTH) : CODING

Description of field

where:
FIELD

is the name of the field.

(LENGTH) is the length of the field, one of:

COD ING

number meaning the number of 8-bit bytes.

A number followed by a "B" meaning the number of bits.

The letters "I-nn meaning an image field, with n being a
number that specifies the maximum length of 8-bit bytes
in the image. The image is preceded by a 1-byte count
of the length of the remainder of the field. Image
fields are variable length and may be null (count = 0 ) .
All eight bits of each byte are information bits.

represents the type of coding used, one of:
1.

= Binary.

Bit map.

Each bit has independent meaning.

= Constant.

NULL = Interpretation is data dependent.

Fields in separate messages with identical names are the same field
and have identical meanings. All numeric values are decimal unless
otherwise noted. All header fields and data bytes are transmitted low
order or least significant bit first on the data line unless otherwise
noted. Multiple byte fields are transmitbed low order or least
significant byte first.

10.2

Reserved Fields

Reserved fields in all received packets are ignored and transmitted as
0, except that reserved bits set in received data packets to be
forwarded are passed along unchanged. If translating between long and
short format, a reserved bit which was set in a field to be dropped is
dropped along with the field to be dropped.

Messages
10.3

Page 80

Optional Padding

All Routing Layer messages except Initialization can be padded.
Padding can be used when communicating with Phase IV nodes, but must
not be used when communicating with adjacent Phase 111 nodes.
If the top bit of the first byte is set, the remainder of the first
byte is a count of the number of pad bytes, including the first byte.
The total length of a message, including the padding, must not exceed
the neighbor's blocksize. If the neighbor's blocksize is unknown ( a s
in the case of Ethernet endnodes), then the maximum total pad sequence
length is 7.-

Messages
10.4

Page 81

Short Data Packet Format

The packet route header in short format is as follows:

Bit

Definition

0-2

SFPD s 2, meaning short format
RQR (Return to Sender Request)
1 indicates try to return
0 indicates discard
RTS
Return to Sender
1 => packet is on return trip
Reserved
Version, set to 0
PF oad field = 0 indicating
no padding follows

----------

--3
4
5
6

DSTNODE ( 2 ) : B

the destination node address

SRCNODE (2) : B

the source node address

FORWARD (1) :

information useful in the forwarding of the
message. The format of this field is as follow

+-+---+-------

Bit:

16 1 5 - 0 1

+
Set to: 1 0 1 0 1 VISIT I
+---+---+------+
+-+---+-------

VISIT (6B) :

the count of the number of
nodes visited by this packet

Page 82

Messages
10.5

Long Data Packet Format

Bit

---

Definition

0-2
3

LFDP = 6, meaning long format
RQR (Return to Sender Request)
1 indicates try to return
0 indicates discard
RTS
Return to Sender
1 => packet is on return trip
Intra-Ethernet packet
.
Version, set to 0
discarded if 1
PF pad field = 0 indicating
no padding follows

5
6
7

----------

D-AREA (1) : B

Reserved

D-SUBAREA (1) : B

Reserved

D-ID (6) : B

Destination ID (first 4 bytes
must be set to HIORD)

S-AREA (1) : B

Reserved

S-SUBAREA (1) : B

Reserved

S-ID (6) : B

Source ID (first 4 bytes must be
set to HIORD)

NL2 ( 1 ) : B

Next level 2 router, reserved

VISIT-CT (1) : B

Visit Count (0)

S-CLASS (1) : BM

Service Class, reserved

PT (1) : B

Protocol Type, reserved

Messages
10.6

Page 83

Initialization Message

FLAGS (1) : BM

the Routing Layer
following format:

control

flag, with

the

Bit

---

Definition

0
1-3
4-6
7

1 indicates Control Packet
Type = 0
Reserved
PF pad field = 0 indicating
no padding follows

----------

SRCNODE (2) : B

the identification of the source node's Routing
Layer, containing the value ID as set by Network
Management in the SELF parameters.

TIINFO ( 1 ) : BM

Routing Layer information on node type
and service requests, as follows:

NTYPE (2B) :

the Routing Layer node type:
0 Reserved
1 level 2 router
2 level 1 router
3 endnode

VERIF (1B) :

BLO (1B) : BM
BLKSIZE (2) : B

Routing Layer Verification
Message required if this bit
is set.
Blocking Requested if this bit
is set.

the maximum Data Link Layer receive block size
this node will accept.
(includes Routing header, excludes Data Link header)

Messages

TIVER ( 3 ) :

Page 84
B

the Routing Layer version, with
format:

the

following

Byte 1 -- version number ( 2 (00000010 binary))
Byte 2 -- ECO number (0 (00000000 binary))
Byte 3 -- user ECO number (0 (00000000 binary))
TIMER ( 2 ) :

RESERVED (1-64)

Hello Timer, in seconds
A reserved field containing a count of 0.

Messages
10.7

Page 85

Verification Message

FLAGS (1) : BM

the Routing Layer control flag, with the
following format:

0
1-3
4-6
7

1 indicates Control Packet
Type = 1
Reserved
PF pad field = 0 indicating
no padding follows

SRCNODE ( 2 ) : B

the identification of the source node's Routing
Layer, containing the value ID as set by Network
Management in the SELF parameters.

FCNVAL (1-64) : B

the function value.

Page 86

Messages
10.8

Hello And Test Message

FLAGS (1) : BM

the Routing Layer
following format:

flag, with

the

Bit

Definition

0
1-3
4-6
7

1 indicates Control Packet
Type = 2
Reserved
PF pad field = 0 indicating
no padding follows

---

SRCNODE (2) : B

control

----------

the identification of the source node's Routing
Layer, containing the value ID as set by Network
Management in the SELF parameters.

TEST DATA (1-128) : B

a sequence of 0 to 128 bytes of data used
to test the circuit.

Each byte is 252 octal.

Messages
10.9

Page 87

Level 1 Routing Message

Level 1 Routing Message contains one or more segments, each
referring to COUNT destinations starting with STARTID.

segment

Destination # 0 is understood to mean "nearest level 2 router".

FLAGS ( 1 ) :

the Routing Layer control flag, with the
following format:

Bit

---

Definition

0
1-3
4-6
7

1 indicates Control Packet
Type = 3
Reserved
PF pad field = 0 indicating
no padding follows

SRCNODE ( 2 ) :

RES (1) : B

reserved field of 1 byte

----------

the identification of the source node's Routing
Layer, containing the value ID as set by Network
Management in the SELF parameters.

SEGMENT is of the FORM:

COUNT (2) : B

the number of IDS in the RTGINFO segment

STARTID ( 2 ) : B

the first ID reported in the Routing Message,
with the top 6 bits (the area bits) set to 0

CHECKSUM (2) : B a check on the routing data base, and a check to
ensure Phase IV Routing Messages not be mistaken for Phase I 1 1 Routing
Messages, as well as a check of the message. I t is a one's complement

Messages

Page 88

add starting with the first SEGMENT and continuing until the CHECKSUM.
To ensure that a Phase IV Routing Message will be distinguished from a
Phase 1 1 1 Routing Message, the sum on the Phase IV Routing Message is
initialized to 1.

Page 89

Messages
10.10

Level 2 Routing Message

A Level 2 Routing Message contains one or more segments, each
referring to COUNT areas starting with STARTAREA.

FLAGS (1) : BM

the Routing Layer control flag, with the
following format:

Bit

---

Definition

0
1-3

1 indicates Control Packet
Type = 4
Reserved
PF pad field = 0 indicating
no padding follows

4-6

SRCNODE (2) : B

RES (1) : B

segment

----------

the identification of the source node's Routing
Layer, containing the value'ID as set by Network
Management in the SELF parameters.

A reserved field of 1 byte

SEGMENT is of the FORM:

COUNT ( 2 )

: B

the number of areas in,the RTGINFO segment

STARTAREA (2) : B
RTGINFO : BM

The first area reported in the Routing Message
with the top 10 bits 0 (area is a 6 bit quantity

Hops and cost to a destination area, in the format

Messages

Page 90

T o ensure that a Phase IV Routing Message will be distinguished from a
Phase I 1 1 Routing Message, the sum o n the Phase IV Routing Message is
initialized to 1.

Messages
10.11

Page 91

Ethernet Router Hello Message

FLAGS (1) : BM

the Routing Layer control flag, with the
following format:

+
1 6 1 5 1 4 1 3 1 2 1 1 1 0 l

+----+---+---+---+---+---+---+---

Bit:

+----+---+---+---+---+---+---+---

Set to:

1 PF 1

RES

TYPE

+----+---+---+---+-----------+---

1 1 1
+

Bit

---

Definition

0
1-3
4-6
7

1 indicates Control Packet
Type = 5
Reserved
PF pad field = 0 indicating
no padding follows

----------

TIVER (3) : B

the Routing Layer version,
with the following format:
Byte 1 -- version number ( 2 )
Byte 2 -- ECO number (0)
Byte 3 -- user ECO number (0)

ID (6) : B

the system ID of the transmitter

IINFO ( 1 ) :

flags
Definition

----------

2=level 1 router
l=level 2 router
Verification Required flag ( 0
on the Ethernet)
Reject Flag, Reserved
Verification Failed, Reserved
No Multicast Traffic Accepted
O=accepts multicast
Blocking Requested Flag (0 on
Ethernet)
Reserved
BLKSIZE (2) : B

maximum Data Link Layer receive
block size -- (Includes Routing
header, excludes Data Link header)

Page 92

Messages
PRIORITY ( 1 ) : B

router's priority

AREA (1) : B

reserved

TIMER (2) : B

Hello Timer in seconds

MPD(1):

reserved

E-LIST (1-244)

list of router states for logical
Ethernets on this physical Ethernet
The format of each list item is:

NAME (7) : B
R/S-LIST (1-236)

logical Ethernet name, reserved
list of router/state pairs. The
format of each list item is:

router ID
ROUTER (6) : B
priority and state
PRISTATE (1) : BM
State:
1 means known 2-way, 0
Bit 7:
otherwise
Bits 0-6: Priority: This router's priority
Note:

E-LIST will always contain a single entry of the format:
1.

NAME = 0

R/S-LIST = list of router/state pairs

Messages
10.12

Page 93

Ethernet Endnode Hello Message

FLAGS (1) :

the Routing Layer control flag, with the
following format:

0
1-3
4-6
7

TIVER (3) :

1 indicates Control Packet
Type = 6
Reserved
PF pad field = 0 indicating
no padding follows

the
version,
with
following format:

the

Byte 1 -- version number (2)
Byte 2 -- ECO number (0)
Byte 3 -- user ECO number ( 0 )
ID (6) :

IINFO (1) :

ID of the transmitting node. The first
4 bytes must be set to HIORD.
The bottom 2 bytes are the Phase IV
address (ID) assigned to the node,.
BM

flags

0,1
2

3
4
5
6

the node type (value 3, for
endnode )
Verification Required flag (0
on the Ethernet)
Reject Flag, Reserved
Verification Failed, Reserved
No Multicast Traffic Accepted
O=accepts multicast
Blocking Requested Flag (0 on
Ethernet)
Reserved

Page 94 .

Messages
BLKSIZE (2) :

maximum Data Link Layer receive
block size -- (Includes Routing
header, excludes Data Link header)

AREA (1) : B

reserved

SEED (8) :

the verification seed ( 0 )

NEIGHBOR (6) :

neighbor's system ID, ID of
Designated Router on Ethernets
(0 if no Designated Router)

TIMER ( 2 ) : B

Hello Timer, in seconds

MPD (1) :

DATA (1-128) :

reserved
B

A sequence of 0 to 128 bytes of
data used to test the circuit.
Each byte is 252 octal.

APPENDIX A
ROUTES, ADDRESSES, AND NAMES

This appendix explains the relationship between addresses and names in
a network.
The Routing Layer identifies nodes in a network by unique numbers
(addresses).
However, it is often more convenient for users to
identify nodes by an alphabetic or alphanumeric name.
In addition,
several users at one node may each wish to identify network nodes by
different names. Moreover, users may not want to use only names that
are unique within the network. Thus a problem arises as to how to
bind node names to node addresses in a network.
The solution is to use names that are unique within a node . (locally
unique) and addresses that are unique within the network (globally
unique). The following rules apply:
o

The Routing Layer knows nodes only by their addresses.

Names are assigned individually on
(local) and are unique within a node.

The local naming function (name to address directory) is not
necessarily a one-to-one function. In other words, alias node
names may be assigned to a node name as long as overall local
uniqueness is preserved.

node-by-node

basis

This solution has the following advantages:
o

Aliases are not global. When networks merge, there is no need
to change local aliases.

It preserves the correspondence between names and addresses.

It avoids the complex problem of maintaining duplicate
of a distributed data base in an automatic function.

~t avoids network maintenance problems related to name and
address directories. Incorrect directories affect only local

copies

ROUTES, ADDRESSES, AND NAMES

Page A-2

users.
This solution imposes some responsibilities on network managers.
The
local network manager must ensure the local directories preserve
uniqueness of names. The central network manager must ensure the
directories 'preserve uniqueness of addresses.

APPENDIX B
ROUTING SUBSETS AND TOPOLOGIES

This appendix defines routing and nonrouting nodes in terms of their
composition, and outlines topological considerations that must be made
when planning network configurations.

B. 1

NODE TYPES

In Phase IV there are the following types of nodes:

. Level 2 routers

. Level 1 routers
. Phase I11 routers
. Phase IV endnodes
. Phase 1 1 1 endnodes

B.2

TOPOLOGICAL CONCEPTS

Network topology involves two
logical connectivity.

concepts:

physical

Physical connectivity defines rules for connecting

connectivity

and

network

nodes

Page B-2

ROUTING SUBSETS AND TOPOLOGIES
physical circuits.
A node's position in the network may be restricted.

T w o nodes are physically connected if they are connected by a sequence
of active circuits.
Two nodes are logically connected if they can communicate.

B.3

DECNET TOPOLOGICAL PRINCIPLES

The following are goals:

. Logical connectivity should equal physical connectivity.
. Any subset of a legal topology should be a legal topology.
B.4

ENDNODE RESTRICTIONS

An endnode must be attached to the network by at most one circuit.
If an endnode is attached to another endnode via a non-broadcast
circuit, the entire network consists of those two endnodes, and no
other nodes can be added to the network.
When there are Ethernets in the network, the sum of the number of
endnodes on Ethernets attached to common routers cannot exceed the
number of Broadcast Endnode Adjacencies that each of the common
routers can handle.
For example:
Ethernet #1
--------------+----------------------------------------+----

1
Ethernet #2
I -----+---------------I
I
I
R1---+
R3
I
Ethernet #3

----+---------+----------------------

I
R2
1

Ethernet #4

Suppose in this network the number of BEAs Rl can handle
R2 can handle R2.NBEAI and R3 can handle R3.NBEA.

Rl.NBEA,

Page B-3

ROUTING SUBSETS AND TOPOLOGIES

Suppose there are El endnodes on Ethernet #1, E2 endnodes on ~thernet
#2, E3 endnodes on Ethernet #3, and E4 endnodes on Ethernet #4.
Then

. El+E2+E3 must be less than or equal to Rl.NBEA.
. E3+E4 must be less than or equal to R2.NBEA
. E2 must be less than or equal to R3.NBEA
B.5

ETHERNET ROUTER RESTRICTIONS

The sum of the number of routers on Ethernets attached to router R
cannot exceed R's parameter NBRA.
The number of routers on an
Ethernet to which router R is connected cannot exceed R's parameter NR
for that Ethernet.
There is a large amount of control traffic overhead
routers on Ethernets. This is due to two causes:

associated

Each router on the Ethernet frequently issues
Messages, as well as Ethernet Router Hello Messages.

Routing

The control traffic associated with the temporary looping
property of the routing algorithm, as nodes countto realize
the unreachability of unreachable nodes, is proportional to
the square of the number of routers on the Ethernet.

Thus there is some practical limit to the number of routers that
coexist on an Ethernet.

B.6

with

can

LARGER NETWORKS

In Phase 111, a legal network was restricted in size to the number of
nodes that fit in a Routing Message. With segmented Routing Messages,
this node limit is no longer necessary.
However, depending on the
application, performance will no longer be acceptable above some
network size. Also, memory restrictions also impose a maximum network
size.
Phase 111 nodes cannot deal with segmented Routing Messages. Thus the
number of nodes a Phase 111 node can handle is limited by the number
of nodes that fit in a Routing Message of the size supported by the
blocksize of that node's circuits. In a mixed Phase III/IV network, a
Phase 1 1 1 node cannot communicate with nor be included on a path to a
node with node number higher than the Phase I 1 1 node can handle.

ROUTING SUBSETS AND TOPOLOGIES

Page B-4

If the rule that "any subset of a legal topology is a legal topology".
is to hold, any network containing Phase 111 nodes must not contain
node numbers higher than any router's capacity.

B.7

HIERARCHICAL NETWORKS

When a Phase IV network is hierarchical, additional topological
restrictions apply and it is not possible to satisfy the rule that
'any subset of a legal topology is a legal topology." Thus logical
connectivity may not equal physical connectivity.
The rules for a hierarchical network are:
1.

Each node belongs toexactly one of the areas.
Note that
this applies to Phase I 1 1 nodes as well. Although Phase I 1 1
nodes are not told an area number by network management, they
must be logically associated with a single area, and must not
have any circuits outside that area.

Only level 2 routers are allowed to have
other areas.

Each area must be physically intact, i.e. there must exist a
path totally internal to the area between each pair of nodes .
in the area.

The subnet consisting of level 2 routers must
intact.

neighbor

nodes

physically

Phase I11 routing node cannot communicate with nodes in other areas,
nor can it be on a path between two Phase IV nodes in different areas.
Thus, for each area, the subnet consisting of the Phase IV nodes in
that area must be physically intact.
A

It is strongly recommended for performance reasons that all
routers and endnodes on an Ethernet be in the same area.

level

APPENDIX C
NONROUTING-OPERATION

This section describes the routing operation for nonrouting nodes on
non-broadcast circuits.
The operation of routing nodes, and the
operation of nonrouting nodes on broadcast circuits, are covered in
the body of the specification.

C.O.1

Receive Module

The Node Listener processes a packet upon receipt. The Node Listener
then passes the packet or discards it, depending on whether it is a
packet for self or any other message. I f the packet is a Routing
Message, the Node Listener discards it.
When transmitting to a node other than self, the node sends the packet
out over the only circuit available, unless the adjacent node is an
endnode, not the destination. Otherwise, the node returns or discards
the packet, deoending on the packet route header option.

C.0.2
Ã

Interfaces

The ECL and Data
Nonrouting nodes
except:

Link interfaces are as described for routers.
support the entire Network Management interface

READ NODE PARAMETERS
READ AREA PARAMETERS
READ ADJACENCY PARAMETERS
Inapplicable SELF parameters are:

NONROUTING OPERATION

. NBRA
. NBEA
. Maxh
. Maxc
. Maxv

. Tl

. BCT1
Inapplicable SELF counters are:

. node unreachable packet loss
. aged packet loss
. node out-of-range packet loss
. partial routing update loss
Inapplicable CIRCUIT counters are:

. transit packet received
. transit packet sent
. transit congestion loss

Page C-2

APPENDIX D
PHASE I11 COMPATIBILITY

Phase I11 nodes cannot appear on broadcast circuits. Thus there is no
Phase I11 compatibility problem with broadcast adjacencies.
On non-broadcast circuits, if an Initialization Message is received
with TIVER 1.3.0, the adjacency is marked as Phase I 1 1 router or
endnode, and an Initialization Message with TIVER 1.3.0, and in Phase
I 1 1 format, is sent to the Phase I 1 1 neighbor. Since Phase I 1 1
routers cannot receive segmented Routing Messages, the Data Link
blocksize in the received Initialization Message must be large enough
to accommodate an entire Phase I 1 1 Routing Message.
Otherwise,
initialization failure is logged, and the circuit is not brought up.
The Hello Timer in the adjacency is set to T3, since a Phase I 1 1
neighbor does not report the value of its Hello Timer in control
messages.
When Routing Messagesare received from the Phase I 1 1 neighbor, they
are treated as Phase I 1 1 format. When Routing Messages are sent to a
Phase I11 neighbor, they are sent in Phase I 1 1 format. The field for
"nearest level 2 routern is not sent, and the Routing Message cannot
be segmented. To ensure that nodes do not confuse Phase I 1 1 and Phase
IV Routing Messages, the checksum is computed differently.
Phase I 1 1 and Phase IV data packet formats are the same, except that
Phase I 1 1 nodes will not know how to interpret the area field in the
source and destination addresses. Thus a Phase IV node must strip off
the destination area field (which will of course be equal to the home
area if a packet is routed through a Phase I 1 1 node) before forwarding
the packet to the Phase I11 neighbor. In addition, for "return to
sender" to work with a Phase I11 neighbor, the source area field is
stripped off as well, provided that the source area is equal to home
area.
When a data packet is received from a Phase I11 neighbor, home area is
written into the destination area field, and home area is written into
the source area field, provided that it is 0.
Note that the Phase I11 functional specification specifies that Phase
I 1 1 nodes must check the SRCNODE field in the data packet header and
drop the packet if SRCNODE is out of range. This would cause a Phase
I 1 1 node to drop a packet that arrived from a different area. Thus

PHASE I11 COMPATIBILITY

Page D-2

any Phase I11 nodes that perform that check must be patched or removed
from the network before a multiple area Phase IV network can be
implemented.
I f a Phase I11 router, or chain of connected Phase 1 1 1 routers,
connects to' two different areas, these areas become merged into one
area, disrupting operation of nodes in the different areas which have
the same low order node IDS. To prevent this problem, which might
occur due to inadvertent connection of two nodes, node verification is
used.
For example, if each node is assigned a password which is area
specific, this area leakage can be prevented.

To enforce password usage, Phase IV routers not in area 1 must require
Specifically, matching of
verification from Phase 1 1 1 routers.
non-null passwords is required before bringing up such a circuit.
Individual passwords on each circuit, or the ability to enable
verification on a per circuit or per node basis is required for level
2 routers, so that passwords can be assigned according to the above
recommendation.

APPENDIX E
ROUTING LAYER COUNTERS AND EVENTS

These
This appendix specifies the Routing Layer counters and events.
provide Network Management with a means to detect and isolate certain
failures. The events and counters described in this Appendix relate
generally to Routing Layer activities, congestion, faults, topological
changes, and verification (security) violations. Counters and events
related to packet modification, misdelivery, or duplication, which ECL
can detect, are not specified here.
In the following discussion, the term fault refers to the cause of
problem. The term error refers to a manifestation of a fault.

Routing Layer counters and events capture sufficient information to
detect and isolate single faults. Multiple faults are detected, but
only isolated when it is cost effective to do so.

E.1

SOURCE EVENTS

A source event is any event that may result in incrementing a counter
or logging an event. Several source events may cause a single counter
to increment. Similarly, several source events may produce a single
generic event for logging.
Source events are classified in two ways: by event manifestation and
by cause.
The primary classification is by event manifestation.
Within each event manifestation category are subcategories of specific
source events. Each of these specific source events has a particular
cause.
The
following
three
tables
describe
source
event
manifestations, causes, and source events. Table 4 defines each event
manifestation category. Table 5 defines each source event cause.
Table 6 defines each source event along with its event manifestation
category and probable cause. The abbreviations in Table 6 are defined

ROUTING LAYER COUNTERS AND EVENTS

Page E-2

in Table 5.
Table 4
Source Event ~anifestations
Event Manifestation

Definition

Data Movement

This group of source events reflects
the movement
of data through the
Routing Layer.

Congestion

This group of source events reflects
the discarding of data packets due to
Routing Layer congestion.

Data Packet Discarded

This group of source events reflects
the discarding of data packets due to a
fault.

Message Format Error

The format of the message is in error.

Partial Routing Update Loss This source
event
represents the
receipt of a Routing Message that is
too long to process so that
some
information
from
the
message
is
discarded.
Circuit Down

This group of source events represents
the detection of a circuit failure.

Adjacency Down

This group of source events represents
a loss of connection to an adjacent
node.

Initialization Failure

This group of source events represents
a
failure
to
initialize with an
adj acent node.

Verification Reject

This source
receipt
of
Message.

Circuit Up

This source
event
represents
the
successful initialization of a circuit.

Adjacency Up

This source
event
represents
successful
initialization with
adjacent node.

Node Reachability Change

This group of source events represents
a change in node reachability (between
reachable and unreachable.

Adjacency Reject

This group of source events represents
this node being forced to reject an
adjacency.

event
represents
the
an invalid Verification

the
an

Page E-3

ROUTING LAYER COUNTERS AND EVENTS
Table 5
Source Event Causes

(Symbol)

(L)

Cause

Explanat ion

Activity

The normal activity of
Layer in moving data.

Congestion

The
resource
limit
condition,
detected
by Routing that causes
Routing to discard normal data.

System Fault

Failures of either
hardware
or
software
and
undetected circuit
failures, excluding circuit faults.

Operator Initiated

Events directly caused by the action
of an operator, including failure of
an operator
to
set
parameters
harmon ious
correctly
for
the
operation
of
multiple
nodes.
Typical operator faults include a
node's maximum address that is too
small or an adjacent node's ID that
is too large.

Topological Change

Modifications
in
topology
that
result
in
a node changing its
reachability status.

Verification Violation

The detected attempt of a node to
initialize without providing the
expected verification information.

Circuit Fault

the

Routing

The detected failure of a circuit.
circuit fault does not necessarily
result in a topological change.

ROUTING LAYER COUNTERS AND EVENTS

Page E-4

Table 6
Source Events

....................................................................
I

! Source
! Event
! Event
! Manifestation ! Number

!
!
! Probable !
! Cause
! Definition

!
I

l--------------------------------------------------------------------t

! Data Movement
!
!
!

!
!

!
I

! A data packet is received
f
! from an adjacency for another!
! node in the network.
!
!
I
! A data packet from another
!
! node in the network is sent !
! over an adjacency.
!
I
!
! A data packet is received
I
! from an adjacency for this
!
! node's ECL.
I
!
I
! A data packet from this
I
! node's ECL is sent over an
!
! adjacency.
I

I--------------------------------------------------------------------.I

! Congestion
!

1
!

!
I

I
I

!
I

! A transit data packet is
! discarded for congestion
! reasons.

! A terminating packet is
! discarded due to the
! inability of ECL to process
! packets fast enough.

I
I

!
!

I--------------------------------------------------------------------I

! Data Packet
! Discarded
!

Destination node is
unreachable.

Packet is too old.

!
!
I

!
!

I
I

Destination node is
out of range.

Received data packet is too
large to forward due to the
blocksize of the data link
that would be used.

!
!
!

!
I

-----Ã‘--Ã‘-----Ã‘------Ã‘.----------------Ãˆ----------------------Ã‘1

(continued on next page)

Page E-5

ROUTING LAYER COUNTERS AND EVENTS
Table 6 (Cont.)
Source Events

....................................................................
I

! Source

! Event
! Event
! Manifestation ! Number

!
! Probable
! Cause

!
!
! Definition

I
I
I

! Received long Routing
! Message with reachable node
! number greater than this
! node's NN.

I--------------------------------------------------------------------I

! Partial Rout- !'
! ing Update
I
!
! Loss
I

I
I

l--------------------------------------------------------------------l

! Circuit Down
!
!

Data link synchronization
lost.

Data link threshold error
detected.

I
I

Data Corruption detected in

!
!
!

X . 2 5 net.

Circuit rejection algorithm
rejected circuit (for reason
other than threshold error).

I
I
I

! Adjacency Down!
I
!
I
!
t
!
!
!
!
!
!
!
!
!
I
!
!
!
!
I
!
I
I
!

15.1

Node Listener timeout.

Node Listener received
invalid data.

Unexpected control (Initialization or Verification)
message received.

Routing Message received
with checksum error.

Node id from Routing or
Hello Message not the
expected one.

15.2

!
!
I

I
I

!
!
I

!
!

Hello received indicating
connectivity became 1-way

!
!
I

ROUTING LAYER COUNTERS AND EVENTS

Page E-6

Table 6 (Cont.)
Source Events

Initialization!
Failure
!

~ k r i ication
f
Message not
received in timeout period.

Data link synchronization
lost.

!
!

I
I

Data link threshold error
detected.

I
I

Version skew detected.

Node id in received Initiali- !
zation Message too large.
I

!
!

Block size in received IniI
tialization Message too small.!

I
I

Invalid verification seed
value in received
Initialization Message.

!
I

Password required from Phase
I 1 1 node

!
I

Unexpected message received.

Area mismatch.

!
I--------------------------------------------------------------------I

! Verification
! Reject

Invalid verification
received.

!
!

! Circuit useable

!
!

I--------------------------------------------------------------------I

! Circuit Up

29.1

I--------------------------------------------------------------------I

! AdjacencyUp

!
29.2
!
L
! Initialization with neighbor
I
I
I
I complete
.--------------------------------------------------------------------'
(continued on next page)

ROUTING LAYER COUNTERS AND EVENTS

Page E-7

Table 6 (Cont.)
Source Events

E.2

COUNTERS

The Routing
There are two types of counters -- node and circuit.
Layer maintains one node counter for each of the defined node
counters. The Routing Layer maintains one circuit counter per circuit
for each of the defined circuit counters. Node counters count source
events attributed to topological changes, faults, and verification
violation.
Circuit counters count source events attributed to
activity, congestion, and faults.
The node and circuit counters are defined below. Each counter relates
to a source event number. Refer to the glossary for definitions of
terminating, originating, and transit packets. A packet is received
when it passes from the Data Link Layer to the Routing Layer. A
packet is sent when it passes from the Routing Layer to the Data Link
Layer.

ROUTING LAYER COUNTERS AND EVENTS

Pace E-8

Node Counters

! Counter
! Name

! Counter
! Width

! Source
! Events
! Included

!
!

! node unreachable packet loss

!16bits

!
!
!
!
!

I-----------------------------------------------------------------l

! aged packet loss
! node out-of-range packet
!
! oversized packet loss

loss

! packet format,error

! partial routing update loss
!
! verification reject

8bits
8bits
8bits

!
!
!
!
!

!
!
t

8bits

8 bits

Page E-9

ROUTING LAYER COUNTERS AND EVENTS
Circuit Counters

.................................................................
! Counter
! Width

! Source
! Events
! Included

! transit packet received

!32bits

! 1

!
!

!
! 2
!
! 3
!

!
!
!

!
! Counter
! Name

I
I

l-----------------------------------------------------------------l

transit packet sent
terminating packet received

!
!
!

originating packet sent

!32bits

! 4
!

transit congestion loss

!
!

terminating congestion loss*
circuit down

initialization failure

!
!

! 32 bits
I

!
!
!

32 bits

corruption loss (X.25 only)

I
I

! 5
!

!16bits

! 6

!
!
!
!
!
I

16 bits

!
!

8 bits
8 bits

8bits

! 13 - 15
!
! 20 - 27.1
!
! 14.1
I

.................................................................

I
I

!
!
I
I
I

* Only required in the implementations in which ECL does not guarantee
Routing that it will process a terminating packet (thereby freeing the
buffer holding the packet) in a short, bounded period of time.

E. 3

EVENTS

Network Management groups some of the source events (Section E.1)
together
for
logging.
The DNA Network Management Functional
Specification specifies this logging operation. When a source event
to be logged occurs, the Routing Layer identifies it by type,
time-stamps it, and places it in a n internal Routing event queue.
If
the event queue is full, Routing discards the newest event in the
queue and replaces it with an "event(s) lost" event.

ROUTING LAYER COUNTERS AND EVENTS

Page E-10

!
! Node unreachable packet loss
I

! Aged packet loss
!
! Node out-of-range packet loss

!
!

! Oversized packet

loss

! Message format error

!
!
!
!

adj, packet header !

! packet header

adj, packet header !

! 13-15

! adj, packet header !
!
!
! adj, packet header !
! highest node address!
I
!
! adjacency
!

! Circuit down
!
! Adjacency down

!15.1-17 !

adj, packet header !

! Partial routing update loss
!
!

!
!

Circuit down - circuit fault

! Circuit down - operator

!15.1-17

adj, packet header !
1

initiated

fault

!
! Initialization failure - operator
!
initiated
!
!
! Initialization failure - software
!
! Verification reject

adj, packet header !

! Adjacency down - operator initiated ! 19
I
!
! Initialization failure - circuit
! 20-22
I

I
I

! adj, packet
!
! circuit

header !

I
I

!23-26.1 ! adjacency, pkt hdr, !
I
! received version
!
I
! (23 only)
!
I

! 27
!
! 28

I
!
! adj, packet header !
!
I
! circuit, node ID
!
! from message
!
!
I
! adjacency
I

!
! Circuit up
!
! Adjacency up
!

!
!
!

! Node reachability change

30,31

! adjacency
I
!
I
! node address, state !

!
!
!
!

34-35

! area (level 2)

! Area reachability change
I

! Adjacency reject
I

29.1

29.2

32.1-33! adj, exceeded param.!
I

ROUTING LAYER COUNTERS AND EVENTS

Page E-11

A logged event of a single type that can result from more
than one source event also contains a reason code to specify
the source event.

"Packet header" denotes the first 6 bytes ( 4 8 bits) of a
Routing Layer message in short format, and the first 21 bytes
for packets in long format.

"Adjacency" is logged as <circuit, node ID>

"Adjacency up" is logged as "Circuit Up", and "Adjacency
DownW1islogged as "Circuit Down" on point-to-point circuits.

APPENDIX F
ALGORITHMS AND MODELS

This appendix describes algorithms and models pertaining to:
Circuit cost

. Buffer management

F.1

CIRCUIT COST ASSIGNMENT ALGORITHM

The assignment of cost to circuits can reflect both delay and
throughput
data.
Delay
data can include transmission delay,
propagation delay, processing delay, and retransmission delay.
Delay
data does not include queuing delay. Throughput data can include
circuit bandwidth, circuit overhead,
and
processor
bandwidth.
Throughput data does not include actual traffic overhead. Basically,
it is desirable to avoid a circuit cost assignment algorithm with high
sensitivity to traffic fluctuations, thereby producing a condition
where routes change to accommodate traffic changes and the new traffic
flow causes new route changes, and so on.
circuit cost assignment occurs as a result of a node generation or
an Initialization module.
An operator can always override any
assignment.

One such assignment is based on circuit bandwidth and is as follows:
1 where bandwidth x >= 100,000 bits/second
F(x) = [100,00/x] for 4,000 bits/second < x < 100,000 bits/sec
25 where x < = 4,000 bits/second

ALGORITHMS AND MODELS

Page F-2

where x is circuit bandwidth (bits/sec)

F.2

BUFFER MANAGEMENT

When no buffers are available for receiving packets from a circuit,
store and forward deadlock can occur. Deadlock can be avoided by
insuring that at least one buffer is available per circuit, or a
buffer can be made available without requiring.additiona1 resources.
Such deadlock avoidance can require discarding packets.
When receive buffers are not available quickly enough, a circuit can
go down unnecessarily at the Data Link Layer. It is much better for
the Routing Layer to discard a packet than for a circuit to go down.
The Routing Layer should not initialize unless it can obtain at least
the minimum number of receive buffers for each circuit. I f an
implementation obtains these buffers from a shared system buffer pool,
then the minimum number must be permanently allocated from the pool by
the Routing Layer when it initializes.
They can, of course, be
returned when Routing halts.
The only time a circuit may be allowed to go below its minimum number
of buffers is when the system can guarantee that a receive buffer can
be allocated to the circuit soon enough in the future to prevent the
circuit from going down. This means that if the system has run out of
free buffers and is down to the minimum number of receive buffers for
each circuit, then:

. Aanother
received data packet that would normally be forwarded on
circuit must be discarded.
. Aprocessed.
received Routing control message can and should
be
. A received data packet for this node should be given to ECL

only if ECL is known to be able to return the buffer in a
short, bounded period of time.
Otherwise, discard the
packet.

Compute the minimum number of receive buffers required for a given
circuit for the circuit speed and an estimate of the maximum time that
Routing (or possibly ECL) can take to process a received message.

ALGORITHMS AND MODELS
F.3

Page F-3

POSSIBLE BUFFER MANAGEMENT MODEL

Routing has a common pool of buffers that can transmit or receive. I f
the implementation of ECL in a system is known to be unable to make
the guarantee of short, bounded processing of received data packets,
then Routing must limit the number of outstanding, received packets
that ECL can hold onto simultaneously (provided that ECL and Routing
are sharing a common buffer pool).
This is best done by a fixed
quota.
Setting this quota to the square root limit used by the congestion
control algorithm is acceptable, but other values may be used as well.
If a quota is used, then any packets discarded due to the ECL quota
being filled must be counted.
The Routing Layer buffer quota provided by the system is divided
the following buffer quotas:

into

Decision (0)
Update (1 sufficient; 1 per circuit recommended)
Node Listener (0)
Node Talker (1)
Forwarding (at least 1 per circuit;
12-15 per terrestrial
circuit and 30 - 35 per satellite circuit recommended).
A separate receive quota for each circuit (depends on
of circuit -- at least 1, 2, or 3 recommended).

speed

If an implementation is constructed using a single buffer
pool
that the Routing Layer shares with other system
processes, and if the Routing Layer does not do any actual
data moving from one buffer to another, then all buffers
containing data to be transmitted are either obtained from
ECL or are receive buffers that contain data packets that are
being forwarded.
The rules above and the. congestion control
algorithms
adequately define the use of these buffers. However, note
the following:
First, the square root limit is defined to be the number of
buffers available for forwarding divided by the square root
of the number of circuits. The number of buffers available
for forwarding should not include the minimum number of
receive buffers, nor should it include ECL's quota, i f such a
quota exists.
Second, in such a model, a single buffer beyond the minimum
number of receive buffers and a single ECL transmit buffer
are sufficient to allow the Routing Layer to run correctly
without starving a circuit for receive buffers. In general,

ALGORITHMS AND MODELS
for adequate performance
required.

F.4

Page F-4
additional

buffers

will

also

DETAILS OF CHARGING AND CREDITING AGAINST QUOTAS

All buffers not free will be charged against a specific quota.
The
quota will never be exceeded except possibly for a brief instant while
a Routing process frees the buffer by consuming the information or by
discarding a packet.
A quota is charged for a buffer upon the following events:
1.

A buffer is moved from one Routing module
receiving quota is charged.

A buffer is supplied by ECL that contains input data.

A free buffer is seized by a process to send a Routing
control message.

free buffer is assigned to
reception on a specific circuit.

the

Data

Link

Layer

for

another.

The

Layer

A quota is credited for a buffer upon the following events:
1.

Transmission of a buffer is completed by the Data Link Layer.
(The quota is credited whether or not the transmission was
successful.)

A buffer is moved from one Routing Layer module
The sending quota is credited.

another.

A process consumes the contents of a Routing
message and returns the empty buffer.

Layer

control

A process discards a packet and returns the buffer.

ECL issues a successful CHECK RECEIVE command.

APPENDIX G
BUFFER SIZES

There are two SELF parameters set by network management:
1.

Buffer Size (,BS)

ECL Segment Size (SS)

The buffer size is 6 greater than the size of buffers Routing uses for
forwarding, not including routing header or datalink header.
The ECL segment size is reported by Routing to ECL. It equals SS-6.
SS-6 is the maximum size segment the ECL is allowed to pass to
Routing. NSP requires SS-6 to be at least of some minimal size. (The
size of the maximum length CI Message, with maximum length connect
data required by the Session Layer.)
Usually, BS=SS. However, when the network buffer size is being
changed, BS may be greater than SS. BS can never be less than SS.
Thus to expand the buffer sizes in the network, each node's BS must be
increased, one at a time.
When all nodes' BS parameters are
increased, then each node's SS can be increased, one at a time.
Similarly, to shrink the buffer sizes in the network, each node's SS
must be decreased, one at a time. When all nodes' SS parameters are
decreased, then each node's BS can be decreased, one at a time.
Note that BS and SS do not include route header overhead.
They do,
however, include an extra 6 bytes for compatibility with Phase 111.
There are two formats of route header in Phase IV -- long format and
short format.
The overhead in long format is greater than the
overhead in short format.
For each circuit, there is a datalink blocksize, which includes route
header overhead.
Thus for Ethernet circuits, the datalink blocksize
must be greater than or equal to B S minus 6 plus the route header
overhead in long data packet format. For DDCMP circuits, the datalink
blocksize must be greater than or equal to BS minus 6 plus the route
header overftead in short format.

BUFFER SIZES

Page G-2

For each adjacency, there is a negotiated datalink blocksize, which is
the smaller blocksize requested by either end. For adjacencies on
non-X.25 circuits, the negotiated blocksize must be greater than or
equal to BS minus 6 plus the route overhead (long format for
Ethernets, short format for point-to-point circuits).
Also, if the
node type of the adjacency is Phase I11 router, the negotiated
blocksize must be large enough to fit an entire Routing Message, since
Phase I11 routers cannot accept a segmented Routing Message.
Since the X . 2 5 Initialization Sublayer performs fragmentation and
reassembly, the datalink blocksize on X.25 circuits does not need to
meet the above constraints.

APPENDIX H
GLOSSARY

adjacency -- a [circuit, node^^] pair. An Ethernet with n
attached nodes represents n-1 adjacencies to a router on that
Ethernet. A router attached to another router via n circuits
has n adjacencies to the second router.

aged packet -- a packet that has exceeded the maximum
of visits.

BEA (broadcast endnode adjacency) -- an endnode connected to
the same Ethernet as this node. The term also applies to the
state information a router associates with the adjacency.

BRA (broadcast router adjacency) -- a router connected to the
same Ethernet as this node. The term also applies to the
state information a router associates with the adjacency. If
the same router is attached to more than one common Ethernet
as this node, that router appears as a BRA on each common
Ethernet.

broadcast circuit -- a circuit on which multiple nodes are
connected, and there exists a method for transmitting a
packet which will be received by multiple receivers.

circuit -- one of the following:

number

. an Ethernet
. a DDCMP link

. an
attachment to one of the nodes in a DDCMP multipoint
link.
In other words, in a DDCMP multipoint link with n
nodes, the router which is the control station on
link has n-1 circuits for that multipoint link.

that

. an
X . 2 5 circuit -- if there are n nodes reachable to a
router via an X . 2 5 network, that X . 2 5 network represents
n circuits for that router.

Page H-2

GLOSSARY
congestion -- The condition that arises when
many packets to be queued.

there

are

too

datagram -- A unit of data passed between the Routing Layer
and the End Communications Layer. When a route header is
added, it becomes a packet.
Designated Router -- the router on the Ethernet chosen to
perform additional duties, such as informing the endnodes on
the Ethernet of the existence and identity of the Ethernet
routers. The router chosen is the one with highest priority,
with highest ID breaking ties.
end node -- A nonrouting node.
error -- The manifestation of a fault.
event -- Occurrences that are logged for recording by Network
Management. Events result from occurrences of source events.
fault -- The cause of a
Routing Layer modules.

problem

the

operation of

hop -- The logical distance between two adjacent nodes
network.
initialization -- A start-up procedure between
nodes.

two

the
in

adjacent

logical connectivity -- The ability of nodes to communicate.
multiaccess channel -- A special type of broadcast circuit on
which the channel is shared on a contention basis.
nonbroadcast circuit -- Any circuit other than a broadcast
circuit.
For example, a multipoint DDCMP circuit is not a
broadcast circuit because a packet cannot be received by more
than one node.
originating packet -Communications Layer.

packet

from

this

node's

End

packet -- A unit of data to be routed from a source node to a
destination node.
When stripped of its route header and
passed to the End Communications Layer, it becomes
a
datagram.
packet looping -- A condition where a packet revisits a node.
path -- The route
destination node.

path cost -- The sum
between two nodes.

packet
the

takes

from

source

circuit

costs

along

node
a

path

GLOSSARY

Page H-3
path length -- the number of hops along a
nodes.

path

physical connectivity -- The result of nodes
to each other via active circuits and nodes.

between

being

two

attached

reachable node -- a node to which a routing node believes
can direct a packet.
received packet -- a packet received by this
Layer from the Data Link Layer

node's Routing

route-through -- packet switching.
routing -- Directing data message packets from
to destination nodes.

source

nodes

sent packet -- a packet passed from this node's Routing Layer
to the Data Link Layer.
source event -- a specified occurrence in this node's Routing
Layer that may cause a counter to be incremented or an event
to be logged.
terminating packet -- A
node.

packet

whose destination

this

topology -- The physical arrangement and relationships of
interconnected nodes and circuits in a network.' A legal
topology satisfies the requirements of this specification.
transit packet -- a packet arriving at this node
source node and destined for another node.
unreachable node -- a
determined that the
network.

node
path

from

to which a routing node has
exceeds the maximum hops of the

APPENDIX I
REVISION HISTORY

1.1

CHANGES FROM PHASE 111

1.1.1

Ethernet Support
1.

The concept of lines became
circuits.

An N1 Initialization Sublayer was added.

Extra routing timers and. Hello Timer parameters were
due to the different characteristics of the N1.

1.1.2

two

concepts--adjacencies

and

added

Hierarchical Routing
1.

Code and parameters for level 2

Code and parameters in level 1 routers was added for dealing
with interarea packets and "nearest level 2 router".

1.1.3

router,^ was

added.

Segmented Routing Messages
1.

Srm flags made into a matrix.

Code added for dealing with segmented Routing Messages.

REVISION HISTORY
1.1.4

Page 1-2

Terminology Changes
1.

Transport => Routing (state names and state actions involving
word Transport changed also)

Phase IV => Phase V

3E => Phase IV

NSP => ECL (End Communications Layer)

Self vector removed. Open and Close calls removed

Select Process removed

MinHops algorithm changed to reflect hops of chosen path

Hello Timer communication, and setting
function of neighbor's Hello Timer

Buffer size bug fixed, enabling buffer sizes to be migrated

Line Rejection algorithm removed

Useless or Wrong diagrams removed

Listen

Timer

8. Extensible fields changed to single byte fields
9.

Formats of packets complete (rather than kept in
as before)

10.

Lots of editing to get it in machinable shape.

1.1.6

Phase I1 Support Removed

1.1.7

X.25

Data Link mapping spec merged in

Verification as done removed

X.25 version number removed

two

places

Page 1-3

REVISION HISTORY
1.1.8

Miscellaneous
1.

Appendix on buffers added

Parameter ECL segment size added

Redefined arithmetic comparison of
leftmost byte be least significant

Changed word "top" to
bytes

discussing

Fixed b u g ~ l e v e l2 routers initialize HOP(O,O) and
to 0 and also check it in CHECK

COST(O,O)

Reserved field of a byte added to Routing Messages
alignment

for

Check for
Process.

Priority of BRA neighbor added into Adjacency database

All mention of N1 was changed to Ethernet

10.

Optional padding added to all Routing Messages

11.

Speed up and clarify Ethernet initialization

12.

Graceful going down messages for Ethernet, X.25, and DDCMP

13.

Hello Timer-2 bytes

14.

BCT3MULT changed to 3 from 8

15.

Upper limits placed on
AMaxh, Maxv, NN, NA

values

16.

Packet formats renamed
Process rewritten for
format

"long" and "short" -- Forwarding
when to receive and transmit in each

17.

Circuit parameter "Recall Timer" added

18.

In Initialization Sublayer, action "start timer" clarified to
be "start Recall Timer". Also, note added that Recall Timer
must expire before Data Link Layer reinitialized.

19.

OPL (originating packet limiter), put into the circuits
database.
Text of section 5.2 states that it is set by
network management

"first" when

S-ID done

only

when

addresses

necessary

have

address

word

Forwarding

T3, Maxc, Maxh,

AMaxc,

REVISION HISTORY

Page 1-4

20.

Link Dependent Sublayer of X . 2 5 to specify that if VC name
set on incoming switched virtual circuit, number must match
or call rejected

21.

Changes for detached level 2 router to act as level 1 router

22.

Forwarding Size renamed Buffer Size, and increased by 6 to be
compatible with Phase 111. ECL Segment Size decreased by 6
when being reported to ECL, so that its value can equal BS,
yet be a sensible value for ECL.

23.

Circuit down, corruption loss, and initialization failure
counters changed from 16 to 8 bits, to be compatible with
network management. Adjacency down counter removed.

24.

Numerical comparison of Ethernet addresses clarified
Packet formats reorganized. 1st byte named FLAGS instead of
sometimes FLAGS, RTFLG, or CTLFLG.
Limit of
Algorithm

size of

Routing

Message

specified

Update

Enabling of multiple areas on Ethernets
Adjacency up/down for Designated Router by endnodes
Look only at 1 byte of version number when comparing
numbers
Note that adjacency
point-to-point links

events

Routing Type
Management

added

logged

SELF

ECL interface--source removed
removed from RECEIVE

circuit

parameters
from

set

version

events

Network

TRANSMIT, destination

Rowmin changed to make routing deterministic by using node ID
for breaking ties
Rules for intra-Ethernet bit changed to be originating nodes
always set, and routers keep it on when forwarding onto same
circuit
Endnodes on Ethernets not required to have
checker (no adjacency database necessarily)

packet

size

Verification required of phase I 1 1 routers to
leakage

prevent

area

No-checking of reserved bits

REVISION HISTORY
38.

Page 1-5

Inter-area packet not forwarded to destination Phase I 1 1 node

DECnet Digital Network Architecture Phase IV
Routing Layer Functional Speciticatlon
AA-X435A-T K

READER'S COMMENTS
NOTE: This form is for document comments only. DIGITAL will use comments submitted on this form at the
company's discretion. If you require a written reply and are eligible to receive one under Software
Performance Report (SPR) service, submit your comments on an SPR form.

Did you fmd this manual understandable, usable, and well-organized? Please make suggestions for improvement.

Did you find errors in this manual? If so, specify the error and the page number.

Please indicate the type of userlreader that you most nearly represent.
0

Assembly language programmer
Higher-level language programmer
Occasional programmer (experienced)
User with little programming experience
Student programmer
Other (please specify)

Street
City

State

Zip Code
or
Country

1
-!

if Mailed in the

United States

BUSINESS REPLY MAIL
FIRST CLASS PERMIT N0.33 MAYNARD MASS
POSTAGE WILL BE PAID BY ADDRESSEE

SOFTWARE DOCUMENTATION
1925 ANDOVER STREET TWlE07
TEWKSBURY, MASSACHUSETTS 01876

11
I

-1
-1

-1

-1
-I
-1
- 1

-1

-- 11
-1
I
I

- - - - Do Not Tear - Fold Here and Tape - - - - - - - - - - - - - - - - - -7
i
t
I

I
I
I
I