Digital PDFs

AA-K180A-TK

October 1980

88 pages

Original

0.9MB

Document:	aa-k180a-tk
Order Number:	AA-K180A-TK
Revision:
Pages:	88
Original Filename:	http://decnet.ipv7.net/docs/dundas/aa-k180a-tk.pdf

OCR Text

Order No. AA-K180A-TK

DECnet
DIGITAL Network Architecture
Transport
Functional Specification
Version 1.3.0

DECnet
DIGITAL Network Architecture
(Phase Ill)
Transport
Functional Specification
Order No. AA-K180A-TK
Version 1.3.0

October 1980

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

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

digital equipment corporation maynard, massachusetts

First Printing, October 1980

This material may be copied, in whole or in part, provided that the
copyright notice below is included in each copy along with an
acknowledgment that the copy describes the Transport interfaces,
algorithms and protocols developed by Digital Equipment Corporation.
This material may be changed without notice by Digital Equipment
Corporation, and Digital Equipment Corporation is not responsible
for any errors which may appear herein.

1980 by Digital Equipment Corporation

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
UNIBUS
COMPUTER LABS
COMTEX
DDT
DECCOMM
ASSIST-11
VAX
DECnet
DATATRIEVE

DECsystem-10
DECtape
DIBOL
EDUSYSTEM
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
ITPS-10
SBI
PDT

CONTENTS

Page
INTRODUCTION
FUNCTIONAL DESCRIPTION
Design Scope
Relationship to DIGITAL Network Architecture
Transport Layer Environment Requirements
Transport Characteristics
Transport Control Functional Organization
Routing
Decision Process
Update Process
Forwarding Process
Receive and Select Processes
Congestion Control: Transmit Management Component
Packet Lifetime Control
Loop Detector
Node Listener
Node Talker
INTERFACES
Network Management Layer Interface
Data Link Layer Interface
Network Services Layer Interface
Transport Initialization Interface
DETAILED ROUTING SPECIFICATION
Routing Data Base
Forwarding Data Base
Data Base Protection
Decision Process
Decision Controller
Decision Algorithms
Update Process
Update Algorithm
Update Formatter
Forwarding Process
Receive Process
Select Process
DETAILED CONGESTION CONTROL SPECIFICATION
Square Root Limiter
Input Packet Limiter
Flusher
Packet Size Checker
DETAILED PACKET LIFETIME CONTROL SPECIFICATION
Packet Lifetime Control Data Base
Node Listener Process
Node Listener Controller
Node Listener Algorithm
Node Talker Process
Loop Detector Process
TRANSPORT INITIALIZATION SUBLAYER
Transport Initialization Line States
Transport Initialization Line Events
Transport Initialization Operation and Message
Requirements
iii

CONTENTS (Cont.)

Page
Transport Initialization State Table and Diagram
Line Rejection
Line Rejection Parameters and Variables
Line Rejection ~lgorithm
MESSAGES
Message Format Notation
Packet Route Header
Transport Control Messages
Transport Routing Message
Transport Hello and Test Message
Transport Initialization Message
Transport Verification Message
APPENDIX A
ROUTES, ADDRESSES, AND NAMES
APPENDIX B
ROUTING SUBSETS AND TOPOLOGIES
B.1
Routing and Nonrouting Nodes
B.2
Topological Concepts
B. 3
DECnet Topological Rule
~ . 4 Legal and Illegal Topologies
B.5
Nonrouting Operation
B.5.1
Select and Receive Modules
B.5.2 Interfaces
APPENDIX C
ROUTING PARAMETER SETTINGS
APPENDIX D
ROUTING EXAMPLES
APPENDIX E
TRANSPORT COUNTERS AND EVENTS
Source Events
E. 1
E.2
Counters
Events
E. 3
APPENDIX F
ALGORITHMS AND MODELS
F.1
Line Cost Assignment Algorithm
F.2
Square Root Limit Algorithm
F.3
Buffer Management
F.3.1 Possible Buffer Management Model
F.3.2
Details of Charging and Crediting Against Quotas
APPENDIX G
PHASE I1 COMPATIBILITY
GLOSSARY

49
50
50
50
50
51
52
52
52
53
54
59
59
65
66
68
68
68
69
69
70

71
73

FIGURES
FIGURE 1

Relationship of Transport to DNA
Transport Components and Their Functions
3
Routing Terms
4
Transport State Transitions
5
Example of a Legal Network Topology
6a Static Topology Routing Data Base Example
6b Routing Data Base -- Line Up Example
6c Routing Data Base -- Message Exchange Example
6d Routing Data Bases -- Example of Isolation of a Node
2

6
8
10
42
51
54
55
56
57

CONTENTS (Cont.)

Page
TABLES
TABLE

Routing Parameters Available to Each Routing Node
Routing Data Base
Transport Initialization State Table
Source Event Manifestations
Source Event Causes
Source Events
Node Counters
Line Counters
Transport Events

1.0

INTRODUCTION

This document describes the
structure,
functions,
interfaces,
protocols, and algorithms for implementing Transport. Transport 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 (Section 2.2).
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 I11 DECnet routing.
It is the major function of the Transport layer. DIGITAL'S routing is
intended for users with networks consisting of leased lines and local
multi-connected topologies (via twisted pair, coaxial cable, and so
on).
Phase I11 DECnet supports two types of routing and is also compatible
with Phase I1 DECnet. Thus there are three types of nodes in terms of
routing:
1.

Routing nodes. These deliver packets to other nodes, receive
packets from other nodes, and route packets from other source
nodes through to other destination nodes.

Nonrouting nodes. These deliver packets to other nodes and
receive packets from other nodes, but do not route packets
through.

Phase I1 nodes.
These deliver packets
packets from, adjacent nodes only.

to,

and

receive

Networks that include nonrouting and Phase I1 nodes are restricted in
how the nodes can be interconnected and which pairs can communicate.
Appendices B and G explain these restrictions.
A glossary at the end of this document defines many Transport terms.

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 Transport design. Other DNA
Phase I 1 1 functional specifications are:
DNA Data Access Protocol (DAP) Functional S~ecification, Version
5.6.0, Order No. AA-K177A-TK
DNA Digital Data Communications
Message
Protocol
(DDCMP)
Functional Specification, Version 4.1.0, Order No. AA-K175A-TK
DNA
Maintenance
Operat ions
Protocol
(MOP)
Functional
Specification, Version 2.1.0, Order No. A A - ~ 1 7 8 ~ - T K
DNA Network Management Functional Specification, Version
Order No. AA-K181A-TK
DNA Network Services (NSP) Functional
3.2.0, Order No. AA-K176A-TK
DNA Session Control Functional
Order No. AA-K182A-TK

Specification, Version

The following overview document for these specifications
introduction to the structure and functions of DNA.
DNA General Description, Order No.

2.0.0,

AA-K179A-TK

1.0.0,
is

2.0

FUNCTIONAL DESCRIPTION

T r a n s p o r t r o u t e s messages i n DECnet networks and manages t h e message
p a c k e t flow.
A packet i s a u n i t of d a t a t o be routed from a s o u r c e
node t o a d e s t i n a t i o n node. T r a n s p o r t a l s o p r e v e n t s o l d p a c k e t s from
c o r r u p t i n g t h e Network S e r v i c e s l a y e r . The T r a n s p o r t l a y e r c o n s i s t s
of two s u b l a y e r s :
1.

T r a n s p o r t c o n t r o l . The T r a n s p o r t c o n t r o l s u b l a y e r s u p p l i e s
f u l l - d u p l e x packet t r a n s m i s s i o n between any p a i r of nodes.
I t i s independent of t h e Data Link l a y e r below i t , and masks
t h e p h y s i c a l and t o p o l o g i c a l c h a r a c t e r i s t i c s of t h e network
from higher l a y e r s . I t c o n s i s t s of t h e f o l l o w i n g components:
Routing
Congestion c o n t r o l
Packet l i f e t i m e c o n t r o l

Transport i n i t i a l i z a t i o n .
The
Transport
initialization
s u b l a y e r masks t h e c h a r a c t e r i s t i c s of t h e Data Link l a y e r s
I t c o n s i s t s of
the
from t h e T r a n s p o r t c o n t r o l s u b l a y e r .
f o l l o w i n g components:
Initialization
P h y s i c a l l i n e monitor
The T r a n s p o r t i n i t i a l i z a t i o n s u b l a y e r c o n t r o l s t h e Data
l a y e r and i s Data Link l a y e r dependent.

The T r a n s p o r t components p r o v i d e t h e f o l l o w i n g f u n c t i o n s .
g i v e s a more d e t a i l e d d e s c r i p t i o n .

Link

Section 2.5

Routing. The r o u t i n g f u n c t i o n d e t e r m i n e s packet p a t h s . A p a t h i s t h e
sequence of connected nodes between a s o u r c e node and a d e s t i n a t i o n
node. When T r a n s p o r t r e c e i v e s a p a c k e t , t h e r o u t i n g component r e f e r s
t o a d a t a base t h a t is p e r i o d i c a l l y updated by T r a n s p o r t modules i n
a d j a c e n t nodes. The r o u t i n g component u s e s information i n t h i s d a t a
base t o determine i f a p a t h t o a d e s t i n a t i o n e x i s t s , and, i f s o , what
t h e next l i n e i n t h e p a t h i s . The r o u t i n g component t h e n forwards t h e
I f more t h a n one p a t h e x i s t s t o a
packet t o i t s d e s t i n a t i o n .
d e s t i n a t i o n , t h e r o u t i n g component a s c e r t a i n s t h e b e s t p a t h .
The combined knowledge of a l l t h e T r a n s p o r t modules of a l l t h e Phase
I11 nodes
i n a network a s c e r t a i n t h e e x i s t e n c e of a p a t h , and r o u t e
t h e p a c k e t t o i t s d e s t i n a t i o n . The r o u t i n g component a t a r o u t i n g
node h a s t h e f o l l o w i n g s p e c i f i c f u n c t i o n s :
I t e x t r a c t s and i n t e r p r e t s t h e r o u t e header i n a p a c k e t .

I t performs p a c k e t forwarding based on t h e d e s t i n a t i o n .
I t manages t h e c h a r a c t e r i s t i c s of t h e p a t h .
I f a node o r l i n e
f a i l s on a p a t h , i t f i n d s a bypass o r s e t of l i n e s t o

re-establish
I t interfaces

the path.

w i t h the Transport
initialization layer t o
r e c e i v e r e p o r t s concerning a l i n e o r node t h a t h a s f a i l e d o r
t h e subsequent recovery of a l i n e o r node.

It returns packets addressed to unreachable nodes to the
Network Services layer (NSP), if requested to do so by NSP. A
node is unreachable if 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 Transport parameter that is
equal to the maximum path length in the network.
It delivers packets between Phase I1 nodes and Phase I11
routing nodes.
( A Phase I1 node can deliver packets to and
receive packets from an adjacent Phase I11 node only.)
Congestion Control.
packet
switching
route-through) .

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

Packet Lifetime Control.
following functions:

Packet

lifetime

control

supplies

the

It bounds the number of nodes a packet can visit.

It detects the halting of adjacent nodes, thereby bounding the
time a packet can spend in a node that is halted before
continuing.
Initialization. The initialization component supplies
functions:
It identifies the
Transport layer.

adjacent

node

and

the

following

adjacent

node's

It performs node verification, if required.
Physical Line Monitor.
Data Link layer.

2.1

This component monitors errors detected by the

~ e s i g nScope

Transport supports the following design requirements:
1.

Deliverability. The routing component accepts and delivers
packets addressed to reachable destinations and rejects
packets addressed to unreachable destinations.

Adaptability. The routing component adapts to topological
changes, but not to traffic changes. (Topological changes
are changes in the configuration of active lines and nodes in
a network. Traffic changes are changes in the physical load
on lines in a network.)

Promptness. The periods of adaptation to topological changes
in the network are a reasonable function of the network
diameter (that is, the maximum logical distance between
network nodes) and line speeds.

Efficiency. Transport is both processing and core efficient.
It does not create excessive routing line overhead.

Robustness. Transport recovers from transient errors such as
lost or temporarily incorrect routing messages. Transport
tolerates imprecise parameter settings.

Stability. The routing component 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.
Transport is sufficiently
performance tuning and failure isolation.

simple

permit

Maintainability. Transport provides mechanisms to detect,
isolate, and repair most common errors that may affect the
routing computation and data bases.
Verification of compatibility.
Transport
initialization
prevents incompatible routing algorithms from coexisting in
the network.
Heterogeneity. Transport operates over a mixture of
node types, communication lines, and topologies.
Support of subsets. Transport allows
subset of the routing functions.

nodes

network

support

Extensibility.
Transport accommodates increased
functions, leaving earlier functions as a subset.

routing

Evolution.
Transport
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 Transport 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.
The following are not within the scope of Phase I 1 1 Transport:
Large networks.
The routing component does
networks of hundreds of nodes efficiently.

not

support

Traffic adaptation. The routing component does not react
traffic flow automatically.

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

does

not

Gross operator failure.
Transport does not attempt to
protect the network from operator actions, such as removing a
line or a node, that may disconnect the network.
Guaranteed delivery. The congestion control component
not guarantee delivery of all offered packets.

does

2.2

Relationship to DIGITAL Network Architecture

The DIGITAL Network Architecture (DNA) is a model that defines the
functional requirements of all DECnet implementations. The model is a
layered one. The Transport layer lies between the Network Services
layer and the Data Link layer, as shown in Figure 1.

Network Management Modules

Network
Management Layer

---- -----Network Application Modules

Network
Application Layer

.--------I

I
Session Control Modules
Session Control Layei

---------

I
Network Services Modules

Network Services Lay

Transport Modules
Transport Layer
1

-^^-1
Data Link Modules

Ã‘Ã‘Ã‘Ã

Physical Link Modt~lei

Data Link Laver

Physical Link Layer

Horizontal arrow: show direct access for control and examination of Parameters, counters, etc. Vertical and curved arrows show interfaces
between lavers for iormal user operations such as file access, down-line load, up-line dump, end-to-end looping, and logical link usage

Figure 1

Relationship of Transport to DNA

A brief description of each DNA layer follows:
1.

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

user

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.
Network Services layer. The Network Services layer defines
the system-independent aspects of logical link communication.
Transport layer.
Modules in the Transport
messages between source and destination nodes.

layer

route

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.
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 Application layer modules can interface
directly with Session Control.

2.3

Transport Layer Environment Requirements

The Transport layer requires guarantees from the operating system, the
Network Services layer, and the Data Link layer.
The required operating system guarantees are:
1.

Priority scheduling such
processing guarantees

A quota of buffers to Transport sufficient to perform routing
and packet lifetime control functions

Access to
expiration

timer

that

Transport

notification

receives

minimum

specific

timer

The Network Services layer must guarantee the return of a buffer
within a specified amount of time. Otherwise, Transport may discard
packets received for Network Services.
The required Data Link layer guarantees 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 line conditions

2.4

Transport C h a r a c t e r i s t i c s

The T r a n s p o r t l a y e r p o s s e s s e s t h e f o l l o w i n g c h a r a c t e r i s t i c s :
V a r i a b l e d e l a y . There is a v a r i a b l e d e l a y time.
Delay is
d e f i n e d a s t h e time between r e c e i p t of a p a c k e t from Network
S e r v i c e s a t a s o u r c e node and d e l i v e r y of t h a t p a c k e t t o
Network S e r v i c e s a t a d e s t i n a t i o n node.
Nonsequential d e l i v e r y . T r a n s p o r t does n o t g u a r a n t e e d e l i v e r y
of p a c k e t s t o Network S e r v i c e s a t t h e d e s t i n a t i o n node i n t h e
same sequence i n which t h e y were r e c e i v e d from Network
S e r v i c e s a t t h e s o u r c e node.
Packet i n t e g r i t y . Transport w i l l not
misdeliver a packet.

2.5

duplicate,

modify,

Transport Control Functional Organization

The T r a n s p o r t c o n t r o l s u b l a y e r components d e s c r i b e d a t t h e beginning
of S e c t i o n 2 can be broken down i n t o more s p e c i f i c f u n c t i o n a l
components. F i g u r e 2 shows t h e r e l a t i o n s h i p of t h e s e components and
t h e i r functions.
These a r e d e s c r i b e d b r i e f l y h e r e and i n d e t a i l i n
S e c t i o n s 4 , 5 , and 6 .
transmit
interface 10

-----N t w o r k STV-

LÃ§vÃ

receive
interface to
Network Services

------

Network Sew'ces

Transport Laver

---------

Contains'

Conuins:
Routing
information
(hop, coil,
routing flaw,
minhw vector.
mincat vector,
etc.1

that verify the

I
Ã

SÃ§lÃ§Proews
Â¥examinepacket route
header
reads Forwarding Data
Base

Â¥determineline to send
packet on
Â takes care of packets for
unreachable deitmations
drops incoming packets
if the queue 1s already
full

----I-

Dam Link L i y r
transmit interface

to Data Link layer

Fofwarding PiÂ supplies and manages
buffers few route-through
.rejects packets from
Network Service! if
queue is too full

0
outing

Â¥selectpaths
Â¥maintain Routing
Data Base
Â modifies Forwarding
Data Base

R f i v Pro receives packets
Â¥passethem to
appropriate process
adiscards packets that
have visited too many
nodes (Loop Detection1

Updxt. ProcÃ
propagates and maintains
content of routing

receive interface

transmit interfacÃ

to Dam Link laver

to Dau Link laver

L-d:

control flow
I - - - - - data flow

Figure 2

T r a n s p o r t Components and T h e i r F u n c t i o n s

2.5.1

Routing

- The r o u t i n g p r o c e s s e s and d a t a b a s e s a r e :

D e c i s i o n p r o c e s s ( S e c t i o n 2.5.1.1)
Update p r o c e s s ( S e c t i o n 2.5.1.2)
Forwarding p r o c e s s ( S e c t i o n 2.5.1.3)
Receive and s e l e c t p r o c e s s e s ( S e c t i o n 2.5.1.4)
Routing d a t a base ( s p e c i f i e d i n S e c t i o n 4)
Forwarding d a t a base ( s p e c i f i e d i n S e c t i o n 4)

This process s e l e c t s routes t o
each
2.5.1.1
Decision Process
d e s t i n a t i o n i n t h e network.
I t c o n s i s t s of a c o n n e c t i v i t y a l g o r i t h m
t h a t m a i n t a i n s p a t h l e n g t h s and a t r a f f i c assignment a l g o r i t h m t h a t
m a i n t a i n s p a t h c o s t s . Path l e n g t h i s t h e s u m of t h e hops along a p a t h
between two nodes. Line c o s t is a p o s i t i v e i n t e g e r v a l u e a s s o c i a t e d
w i t h using a l i n e , and p a t h c o s t is t h e s u m of t h e l i n e c o s t s along a
p a t h between two nodes.
When a r o u t i n g node r e c e i v e s a Routing message ( a t y p e of T r a n s p o r t
C o n t r o l message) from an a d j a c e n t node, t h e r o u t i n g node e x e c u t e s t h e
two d e c i s i o n a l g o r i t h m s . Execution of t h e two a l g o r i t h m s r e s u l t s i n
t h e d e t e r m i n a t i o n of l i n e s along which t o forward p a c k e t s and p o s s i b l y
t h e c o n c l u s i o n t h a t one or more p a r t i c u l a r d e s t i n a t i o n nodes a r e
unreachable.
The system manager m u s t s e t s e v e r a l of t h e p a r a m e t e r s i n t h e r o u t i n g
d a t a base t h a t t h e d e c i s i o n p r o c e s s uses. These i n c l u d e l i n e c o s t ,
maximum c o s t , maximum a d d r e s s , maximum l i n e s , and maximum hops.
The
v a l u e s of t h e c o s t p a r a m e t e r s a r e a r b i t r a r y . Appendix F s u g g e s t s an
algorithm for determining l i n e c o s t s .
The v a l u e s of t h e o t h e r
p a r a m e t e r s depend on t h e s p e c i f i c topology of t h e network.
I f these
v a l u e s a r e n o t s e t c o r r e c t l y , t h e d e c i s i o n a l g o r i t h m s w i l l n o t work
correctly.
F i g u r e 3 shows a sample network and d e p i c t s some of t h e r o u t i n g terms.
The g l o s s a r y c o n t a i n s d e f i n i t i o n s of t h e s e and o t h e r T r a n s p o r t terms.
In t h i s f i g u r e , t h e maximum hops f o r node A is 4 .

Legend:

= node

= physical line

= line cost
= hop

Node A wants to send a oacket to Node D. There are three oossible oaths.

PATH

@to@,@to@

1 PATH LENGTH 1

PATH COST

@+!]+!I

@to@

= 7*

3 hops

* 7 is the lowest path cost; Node A therefore routes the packet to Node 0 via this path.

Figure 3

Routing Terms

propagates
2.5.1.2
Update Process - This process constructs and
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:
Routing messages are sent to adjacent nodes only.
Routing messages contain information on all destination nodes.
Routing message transmission
backup.

event-dr iven with

The routing update algorithm maintains
routing line overhead.

lower

periodic
limit

his p r o c e s s s u p p l i e s and manages t h e
Forwarding P r o c e s s
2.5.1.3
b u f f e r s n e c e s s a r y t o s u p p o r t p a c k e t route-through t o a l l d e s t i n a t i o n s .

2.5.1.4
Receive and S e l e c t P r o c e s s e s - The r e c e i v e p r o c e s s i n s p e c t s a
p a c k e t ' s r o u t e header and d i s p a t c h e s t h e p a c k e t t o an a p p r o p r i a t e
T r a n s p o r t c o n t r o l component o r t o Network S e r v i c e s .
The s e l e c t
p r o c e s s performs t h e simple t a b l e lookup t o s e l e c t t h e o u t p u t l i n e f o r
t h e p a c k e t . When a d e s t i n a t i o n is u n r e a c h a b l e , s e l e c t e i t h e r r e t u r n s
t h e p a c k e t t o t h e sender or d i s c a r d s t h e p a c k e t , depending on t h e
o p t i o n e x e r c i s e d i n t h e packet r o u t e header.

This
2.5.2
Congestion C o n t r o l :
Transmit
Management
Component
manages b u f f e r s by l i m i t i n g t h e maximum number of p a c k e t s on a queue
for a line.
Transmit management r e g u l a t e s t h e r a t i o of p a c k e t s
r e c e i v e d d i r e c t l y from Network S e r v i c e s t o route-through p a c k e t s .
Transmit management a l s o checks t h e p a c k e t s i z e f o r each packet
received.

2.5.3
Packet L i f e t i m e
Control - This
component r e q u i r e s t h r e e p r o c e s s e s :
1.

Loop d e t e c t o r ( S e c t i o n 2.5.3.1)

Node l i s t e n e r ( S e c t i o n 2.5.3.2)

Node t a l k e r ( S e c t i o n 2.5.3.3)

packet

lifetime

control

2.5.3.1
Loop D e t e c t o r - T h i s p r o c e s s p r e v e n t s
excessive
packet
I t c o u n t s t h e number of
nodes a packet has v i s i t e d and
looping.
removes a p a c k e t when i t exceeds t h e v i s i t l i m i t .

2.5.3.2
Node L i s t e n e r - T h i s p r o c e s s d e t e r m i n e s t h a t a minimum amount
of a c t i v i t y h a s o c c u r r e d between t h i s node and an a d j a c e n t node.
It
a l s o d e t e r m i n e s i f t h e i d e n t i t y of t h e a d j a c e n t node has changed.
V i o l a t i o n s of t h e minimum a c t i v i t y a u d i t r e s u l t i n t h e d e c l a r a t i o n
t h a t t h e l i n e between t h e nodes is down.

2.5.3.3
Node T a l k e r - T h i s p r o c e s s p r o v i d e s t h e minimum a c t i v i t y f o r
each a d j a c e n t node l i s t e n e r .
I t p l a c e s an a r t i f i c i a l load on t h e
p h y s i c a l l i n e s o f a i l u r e s can be d e t e c t e d .
The node t a l k e r and
l i s t e n e r p r o v i d e f o r d e t e c t i o n of a d j a c e n t T r a n s p o r t h a l t and a d j a c e n t
node i d e n t i t y change.

3.0

INTERFACES

This section describes the three external Transport interfaces:
1.

Network Management layer interface (Section 3.1)

Data Link layer interface (Section 3.2)

Network Services layer interface (Section 3.3)

In addition, this section describes the single internal Transport
interface, Transport initialization (Section 3 . 4 ) .
The interfaces take the format of calls to subroutines, as follows:

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:

3.1

< >

not equal to

less than or equal to

greater than or equal to

SQRT

the square root of

Network Management Layer Interface

This interface allows Network Management to control and observe the
Transport layer interactively. Network Management can exert indirect
control over the Transport layer via parameter changes. The f0ll0~ing
Network Management functions form a set of primitive functions that
can be used to construct more complex functions.

READ NODE STATE (destination; reachability)
Returns:

destination reachable
destination unreachable

This function returns information indicating whether or
packet can get to a destination.

READ NODE TRANSPORT-STATE
Returns:

(;

not

~ransport-state)

Transport is initialized
Transport is terminated and requires
problem correction and initialization

This function allows the user to observe whether Transport
been initialized or terminated.

has

READ NODE HOPS (destination;

Returns:

hops)

for self

for an adjacent node

where 2 <= n <= [maximum hops] for
a reachable destination

where m < 0 for an unreachable destination

This function returns the number of hops between
destination along the path with the shortest length.

READ NODE COST (destination;

Returns:

self

cost)

where 1 <= n <= [maximum path cost] for
a reachable destination

where m < 0 for an unreachable destination

This function returns the sum of the line costs between
and destination along the path with the least cost.

READ NODE L I N E (destination;

Returns:

for Self

where 1 <= n <= [number of output lines]
for a reachable destination

where m < 0 for an unreachable destination

This function returns the
destination.

Return:

output

line

used

get

state)

the line state (Section 7)

This function returns the state of the line.

READ L I N E COST (line;

Return:

self

line)

READ L I N E STATE (line;

and

cost)

the local cost to use this line

This function returns the cost assigned to the line.

the

READ LINE COUNTERS (line; error counters)
Returns:

the values of the Transport line
counters

This function returns the current values for the counters
associated with this line.
Transport maintains one line
counter per physical link for each of the line counters,
defined in Appendix E. The line counters are as follows:
Transmit ("route through") packets received
Transmit packets sent
Arriving packets received (output packets from other
nodes addressed to this node)
Departing packets sent (input packets from this node
addressed to other nodes)
Transit congestion loss
Line down
Initialization failure

READ LINE BLOCKSIZE (line; blocksize)
Return:

the Data Link blocksize

This function returns the blocksize that the
requires.

READ NODE TYPE ( ;
Returns:

Data

Link

layer

type)

0 routing

1 nonrouting
2 Phase 1 1

This function returns the adjacent node type.

READ NODE MAXIMUM HOPS
Return:

(;

maximum hops)

the current value of the

maximum hops
This function returns the current value for the maximum hops
parameter.
Refer
to
the glossary for a comprehensive
definition of maximum hops.

READ NODE MAXIMUM COST (;
Return:

maximum cost)

the current value of the
maximum path cost

This function returns the current maximum path cost for the
Transport module.
Refer to the glossary for a comprehensive
definition of maximum cost.

READ NODE MAXIMUM ADDRESS
Return:

(;

maximum a d d r e s s )

t h e c u r r e n t v a l u e s e t f o r maximum a d d r e s s

T h i s f u n c t i o n r e t u r n s t h e h i g h e s t number o f a n y node
b e a d d r e s s e d by t h i s n o d e .

READ NODE MAXIMUM LINES
Return:

lines

that

the

version,

ECO,

and

t h e c u r r e n t v a l u e of
maximum l i n e s

READ NODE ROUTING VERSION

(;

number

routing version)

the current routing version

This function returns the current
u s e r ECO.

READ NODE ROUTING TIMER
Return:

can

maximum l i n e s )

(;

T h i s f u n c t i o n r e t u r n s t h e maximum
T r a n s p o r t module c a n s u p p o r t .

Return:

that

routing

routing timer)

(;

t h e c u r r e n t v a l u e of
t h e routing timer

T h i s f u n c t i o n r e t u r n s t h e c u r r e n t v a l u e of t h e
t h a t c a u s e s a r o u t i n g message t o be g e n e r a t e d .

READ NODE MAXIMUM VISITS
Return:

(;

routing

timer

maximum v i s i t s )

the current value for
maximum v i s i t s

This function returns the current value for the routing
p a r a m e t e r t h a t d e t e r m i n e s t h e maximum number o f n o d e s a p a c k e t
can v i s i t .
Refer t o t h e g l o s s a r y f o r
a
comprehensive
d e f i n i t i o n o f maximum v i s i t s .

READ NODE COUNTERS
Returns:

(;

node c o u n t e r s )

t h e c u r r e n t values of t h e
c o u n t e r s a s s o c i a t e d w i t h t h e node

T h i s f u n c t i o n r e t u r n s t h e c u r r e n t v a l u e s o f t h e node c o u n t e r s
m a i n t a i n e d by T r a n s p o r t . Appendix E d e s c r i b e s t h e s e c o u n t e r s
i n d e t a i l . The c o u n t e r s a r e a s f o l l o w s :

Node u n r e a c h a b l e p a c k e t l o s s
Aged p a c k e t l o s s
Node o u t - o f - r a n g e p a c k e t l o s s
Oversized packet l o s s
Packet format e r r o r
P a r t i a l routing update l o s s
Verification reject

SET LINE STATE (line, ON or OFF;
Returns:

status)

error value if line nonexistent
success

line set to ON causes the issuance of a start to the Data
Link layer. A line set to OFF causes the issuance of a stop to
the Data Link layer.

SET LINE COST (line, positive value;
Returns:

status)

error value if line nonexistent
or cost value nonpositive or beyond maximum cost
success

This function changes the line cost the routing algorithm uses.

SET NODE ROUTING PARAMETER (routing parameter value;
Value:

One of the following routing parameters,
above with the READ functions:
0

Returns:

status)
described

Maximum hops
Maximum cost
Maximum address
Maximum lines
Maximum visits
Routing timer

error message if value improper
or routing parameter non-existent
success

SET NODE STATE (transport identification, ON or OFF)
Returns:

none

With the ON parameter, this function forces Transport to
initialize all its data bases, and sets the line to an
appropriate state.
With the OFF parameter, this function forces a Transport
termination, issues a stop for each line, and places an OFF
event in Transport's internal event queue.
Appendix
E
describes
events.
Transport
layer termination has the
following effects:
1.

The decision process cannot process any events.

The update process cannot send any routing messages.

Network services
processed.

The select
packets.

and

interface
receive

requests

processes

cannot

forward

ZERO COUNTERS
Returns:

none

This function sets
Transport to zero.

Return:

line

and

node

counters

associated

with

the oldest event in Transport's internal event queue

Transport maintains an internal event queue into which it
places events.
Appendix E describes events. This function
reads the oldest event in the queue.

CLEAR EVENTS
Returns:

none

This function clears all events from Transport's internal event
queue.

3.2

Data Link Layer Interface

This interface, between Transport's initialization layer 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 line conditions.
The
functions of the interface, described as calls, are as follows:

TRANSMIT (line, buffer)
Returns:

none

This function gives a
transmission.

message

the

Data

Link

layer

CHECK TRANSMIT BUFFER (buffer)
Returns:

buffer is queued
buffer is returned to Transport

This function returns information about the transmit buffer.

for

INITIALIZE LINK ( l i n e )
Returns:

none

T h i s f u n c t i o n c a u s e s t h e Data Link p r o t o c o l t o
1i n k .

initialize

the

STOP LINK ( l i n e )
Returns:

none

T h i s f u n c t i o n h a l t s t h e Data Link o p e r a t i o n
line.

STATUS ( l i n e ;
Returns:

the

specified

status)
off
running
initializing

T h i s f u n c t i o n r e t u r n s t h e Data Link s t a t e of t h e l i n e . I f t h e
Data Link modules p r o v i d e a d d i t i o n a l s t a t e s ( f o r example, a
m a i n t e n a n c e s t a t e ) , t h e y a r e t r e a t e d a s t h e OFF s t a t e .

STATUS ERROR COUNTERS ( l i n e ;
Returns:

error counters)

e r r o r counter values ( ~ a l ~ e , S t a t ~ S )

T h i s f u n c t i o n r e t u r n s t h e v a l u e s of
c o u n t e r s , and n o t i f i c a t i o n i f e r r o r
exceeded.

SUPPLY RECEIVE BUFFER ( b u f f e r ;
Returns:

t h e Data Link e r r o r
t h r e s h o l d s have been

status)

buffer accepted
buffer rejected

T h i s f u n c t i o n p r o v i d e s a n empty b u f f e r t o t h e D a t a L i n k m o d u l e s
f o r r e c e i p t of t h e n e x t s e q u e n t i a l message.

CHECK RECEIVE BUFFER ( b u f f e r ;
Returns:

status)

no p a c k e t r e c e i v e d
packet received, buffer returned

T h i s f u n c t i o n r e t u r n s t h e above i n f o r m a t i o n a b o u t
buffer.

the

receive

3.3

Network S e r v i c e s Layer I n t e r f a c e

T h i s i n t e r f a c e , between t h e Network S e r v i c e s l a y e r and t h e T r a n s p o r t
l a y e r , c o n s i s t s of commands t o and r e s p o n s e s from t h e T r a n s p o r t l a y e r .
The commands and r e s p o n s e s exchange d a t a and c o n t r o l i n f o r m a t i o n .
Data i s i n f o r m a t i o n t h a t T r a n s p o r t sends or r e c e i v e s .
The d a t a
d e s c r i p t i o n i s a d e s t i n a t i o n address, source address, buffer address
and l e n g t h of d a t a . D e s t i n a t i o n and s o u r c e a d d r e s s e s a r e two-byte
i n t e g e r numbers i n t h e range of 1 t o t h e number of nodes i n t h e
network. T r a n s p o r t u s e s node a d d r e s s e s o n l y , n o t node names, which
a r e r e s o l v e d a t a higher l a y e r .
C o n t r o l information s t a r t s o r s t o p s t r a n s m i s s i o n and r e c e p t i o n of d a t a
and r e g u l a t e s t h e d a t a flow t o a r e a c h a b l e d e s t i n a t i o n .
The f u n c t i o n s of t h e i n t e r f a c e , d e s c r i b e d a s c a l l s , a r e a s f o l l o w s :

TRANSMIT ( s o u r c e , d e s t i n a t i o n , r e t u r n f l a g , c h a n n e l , b u f f e r )
Returns:

b u f f e r i s queued
b u f f e r is n o t
Services

queued

and

returned

Network

T h i s f u n c t i o n sends a p a c k e t .
The r e t u r n f l a g i n d i c a t e s whether o r n o t Network S e r v i c e s wants
t h e packet r e t u r n e d i f t h e d e s t i n a t i o n is unreachable o r
becomes unreachable b e f o r e T r a n s p o r t can d e l i v e r t h e p a c k e t .
I f the f l a g i s s e t t o "true" (Boolean), Transport attempts t o
r e t u r n t h e c o n t e n t s of t h e b u f f e r t o Network S e r v i c e s a s a
"received packet."
I f t h e f l a g is n o t s e t , T r a n s p o r t d i s c a r d s
t h e p a c k e t . T r a n s p o r t may r e t u r n t h e b u f f e r a f t e r Network
S e r v i c e s i s s u e s t h e CHECK TRANSMIT BUFFER c a l l ( d e s c r i b e d
next).
Channel, s e l e c t e d by Network S e r v i c e s , is e i t h e r u n s p e c i f i e d o r
a v a l i d l i n e number.
For l i n e l e v e l loopback t e s t i n g , Network
otherwise, Transport
S e r v i c e s m u s t s p e c i f y a l i n e number;
d e t e r m i n e s t h e channel.

CHECK TRANSMIT B U F F E R ( b u f f e r )

Returns:

b u f f e r queued
b u f f e r r e t u r n e d t o Network S e r v i c e s

T h i s f u n c t i o n checks t h e s t a t u s of a p r e v i o u s l y queued t r a n s m i t
I t r e t u r n s t h e b u f f e r t o Network S e r v i c e s a f t e r any of
buffer.

the following:
The b u f f e r is copied i n t o a T r a n s p o r t b u f f e r .
The p a c k e t is t r a n s m i t t e d .
The p a c k e t i s d i s c a r d e d because t h e d e s t i n a t i o n
unreachable and t h e r e t u r n f l a g i s n o t s e t .

The p a c k e t c o n t e n t s a r e t r a n s f e r r e d t o a r e c e i v e b u f f e r
because t h e d e s t i n a t i o n is unreachable and t h e r e t u r n
f l a g is s e t .
19

SUPPLY RECEIVE BUFFER ( b u f f e r )
Returns:

b u f f e r q u e u e d f o r r e c e i v e by T r a n s p o r t
b u f f e r n o t q u e u e d f o r r e c e i v e by T r a n s p o r t

This function queues a receive buffer t o Transport.

CHECK RECEIVE BUFFER ( s o u r c e , d e s t i n a t i o n , c h a n n e l , b u f f e r )
Returns:

b u f f e r r e m a i n s q u e u e d by T r a n s p o r t
b u f f e r r e t u r n e d t o Network S e r v i c e s w i t h s o u r c e a
d e s t i n a t i o n node a d d r e s s e s ( b u f f e r c o n t a i n s a n o r m a l
packet)
b u f f e r r e t u r n e d t o Network S e r v i c e s ( b u f f e r c o n t a i n s
a
" r e t u r n t o s e n d e r " p a c k e t -- NSP F u n c t i o n a l
Spec i f i c a t i o n )

T h i s f u n c t i o n c h e c k s t h e s t a t u s of a p r e v i o u s l y queued r e c e i v e
buffer.
I t r e t u r n s t h e b u f f e r i f t h e p a c k e t was r e c e i v e d o r i f
The
t h e node is u n r e a c h a b l e and t h e r e t u r n f l a g is s e t .
c h a n n e l v a r i a b l e r e t u r n s a v a l i d l i n e number ( o r a v a l u e f o r a n
i n t e r n a l l i n k ) f o r each received packet.

OPEN ( s o u r c e )
Returns:

none

T h i s f u n c t i o n i d e n t i f i e s a Network S e r v i c e s module a s a n a c t i v e
T r a n s p o r t u s e r a t a node and d e f i n e s i t s node a d d r e s s . An o p e n
m u s t o c c u r b e f o r e Network S e r v i c e s c a n t r a n s m i t o r r e c e i v e .
S o u r c e is a node a d d r e s s .

CLOSE ( s o u r c e )
Returns:

none

T h i s f u n c t i o n r e m o v e s a Network S e r v i c e s module a s a
u s e r a t a n o d e . S o u r c e is a n o d e a d d r e s s .

3.4

Transport

Transport I n i t i a l i z a t i o n Interface

T h i s i n t e r f a c e , b e t w e e n t h e T r a n s p o r t c o n t r o l s u b l a y e r and t h e
Transport i n i t i a l i z a t i o n sublayer, supports the routing events defined
i n S e c t i o n 4.4.2.
The i n t e r f a c e c o n s i s t s o f commands t o and r e s p o n s e s
from t h e T r a n s p o r t i n i t i a l i z a t i o n s u b l a y e r .

TRANSMIT ( l i n e , b u f f e r )
Returns:

none

This function transmits a buffer containing a packet.

CHECK TRANSMIT BUFFER ( b u f f e r ;
Returns:

status)

b u f f e r queued
buffer returned t o user

T h i s f u n c t i o n p o l l s a b u f f e r c o n t a i n i n g a p a c k e t t h a t h a s been
s e n t w i t h t h e TRANSMIT f u n c t i o n .
I f t h e p a c k e t h a s been
If
t r a n s m i t t e d , t h e b u f f e r is r e t u r n e d t o T r a n s p o r t c o n t r o l .
t h e p a c k e t h a s n o t y e t been t r a n s m i t t e d , a message is r e t u r n e d
i n d i c a t i n g t h a t t h e b u f f e r is q u e u e d .

STATUS ( l i n e ;
Returns:

status)
off (line rejected)
initializing
l i n e a c c e p t e d by T r a n s p o r t i n i t i a l i z a t i o n
running;

c u r r e n t value of l i n e c o s t

This function r e t u r n s t h e s t a t u s of t h e l i n e .
The o f f ,
i n i t i a l i z i n g , and r u n n i n g s t a t e s c o r r e s p o n d t o D a t a L i n k l a y e r
l i n e s t a t e s (see Section 3 . 2 ) .

Returns:

none

T h i s f u n c t i o n t u r n s t h e l i n e o f f and i n i t i a l i z e s t h e l i n k i n
manner t h a t p r o h i b i t s r a c e c o n d i t i o n s f r o m o c c u r r i n g .

SUPPLY RECEIVE BUFFER ( b u f f e r ;
Returns:

status)

buffer accepted
buffer rejected

This function provides a
receive
buffer
i n i t i a l i z a t i o n s o t h a t it can r e c e i v e a packet.

CHECK RECEIVE BUFFER ( b u f f e r ;
Returns:

Transport

status)

no p a c k e t r e c e i v e d
packet received, buffer returned

T h i s f u n c t i o n p o l l s t h e s t a t u s of a b u f f e r t h a t T r a n s p o r t
c o n t r o l h a s j u s t s u p p l i e d w i t h t h e SUPPLY R E C E I V E BUFFER
f u n c t i o n . Upon r e c e i v i n g a p a c k e t i n t o t h e b u f f e r , T r a n s p o r t
i n i t i a l i z a t i o n returns the buffer t o Transport control.

SUPPLY L I N E UP COMPLETE (line)

Returns:

none

This function informs Transport initialization
that
the
decision process (Section 4.4) recognizes that a line is up.
(The process has completed its line up event algorithm.)

SUPPLY L I N E DOWN COMPLETE (line)

Returns:

none

This function informs Transport initialization
that
the
decision process recognizes that a line is down. (The process
has completed its line down event algorithm.)

4.0

DETAILED ROUTING SPECIFICATION

A s noted i n Section

2.5.1,
the routing
f o l l o w i n g d a t a b a s e s and p r o c e s s e s :

function

consists

the

Figure

Routing d a t a base
Forwarding d a t a b a s e
Decision process
Update p r o c e s s
Forwarding p r o c e s s
Select process
Receive process
The r e l a t i o n s h i p among t h e s e c o m p o n e n t s is
(Section 2 ) .

illustrated

T h i s s e c t i o n s p e c i f i e s e a c h o f t h e s e components i n d e t a i l .
To
f a c i l i t a t e e x p l a n a t i o n , symbols r e p r e s e n t p a r a m e t e r s a v a i l a b l e t o e a c h
r o u t i n g node. T a b l e 1 d e s c r i b e s t h e s e symbols.
Table 1
R o u t i n g P a r a m e t e r s A v a i l a b l e t o Each R o u t i n g Node
Symbol

Definition

Number o f n o d e s i n n e t w o r k (maximum a d d r e s s )

NLN

Number o f l i n e s s u p p o r t e d by t h i s node (maximum l i n e s )

Maxh

Maximum h o p s

Maxc

Maximum c o s t

Max 1

Maximum c o s t a s s i g n a b l e t o a l i n e

Infh

I n f i n i t e path length

Infc

I n f i n i t e path cost

Background f r e q u e n c y t i m e r ; maximum
t i m e period f o r exchanging r o u t i n g
m e s s a g e s w i t h a d j a c e n t node

R a t e c o n t r o l f r e q u e n c y t i m e r : minimum
time period before another r o u t i n g
message c a n be s e n t .

Designation of undefined l i n e

Appendix C c o n t a i n s r e q u i r e d and s u g g e s t e d s e t t i n g s f o r r o u t i n g
parameters.
The f o l l o w i n g r e l a t i o n s h i p s e x i s t b e t w e e n t h e a b o v e
parameters:
> = a c t u a l maximum n e t w o r k a d d r e s s
Maxh >= a c t u a l maximum n e t w o r k p a t h l e n g t h
Maxc >= ( a c t u a l maximum n e t w o r k p a t h l e n g t h ) X (Maxi)
I n f h > Maxh
I n f c > Maxc
Tl
>>T2

4.1

Routing Data Base

The routing data base contains routing data summarized in Table 2.
The Network Management SET NODE STATE ON function sets the data base
to its initial values.
This is a prerequisite to normal node
operation. Table 2 also shows the initial values of the data.
Table 2
Routing Data Base
Symbol

Description

Initial Value

HOP

Network connectivity matrix

Infh

Minhop

Network minimum connectivity
vector

Infh

Lcv

Line cost vector

Positive
integer
in range 1-Max1

Cost

Traffic assignment matrix

Infc

M incost

Minimum traffic assignment
vector

Infc

Srm

Send routing message flags

Self

Self vector

T id

Transport identification

N ~ Y

Node type vector

N id

Node identification vector

* This value is specified later in this section.
A description of each element of the data base follows.
Network connectivity matrix (Hop). This contains information on the
path length to each destination over each line. An entry consists of
Hop(i,j),
where:
Hop(i,j)

Represents the path length from this Transport
the destination, with the following values:

Value
0
1
2-Maxh
Infh

layer

representing

Meaning
Self
Adjacent node
Other reachable nodes
Unreachable node

Is a decimal integer in
destination address.

the

range

1-NN

Is a decimal integer in the range 0-NLN
line to destination i.

representing

the

Minimum n e t w o r k c o n n e c t i v i t y v e c t o r
(Minhop).
T h i s summarizes t h e
p a t h l e n g t h i n f o r m a t i o n c o n t a i n e d i n t h e Hop t a b l e . An e n t r y c o n s i s t s
of Minhop(i1,
where:
M i n h o p ( i ) R e p r e s e n t s t h e s m a l l e s t p a t h l e n g t h v i a a n y l i n e from t h i s
Transport
layer
t o t h e d e s t i n a t i o n node, with t h e
following values:
Meaning

Value

,
0

1
2-Maxh
Infh

Smallest path length t o Transport users a t
t h i s node
S m a l l e s t p a t h l e n g t h t o a d j a c e n t node
S m a l l e s t p a t h l e n g t h t o o t h e r reachable nodes
Node u n r e a c h a b l e

Is a d e c i m a l i n t e g e r i n
destination address.

the

range

representing

1-NN

L i n e c o s t v e c t o r ( L e v ) . T h i s c o n t a i n s i n f o r m a t i o n on
c o s t o f u s i n g a l i n e . An e n t r y c o n s i s t s o f L c v ( ] ) ,

the

perceived

where:
Lcv(~)

I s a p o s i t i v e i n t e g e r i n t h e r a n g e 1-Max1 r e p r e s e n t i n g t h e
c o s t associated with using l i n e j .

Is a decimal integer i n t h e
1i n e .

range

1-NLN

representing

T r a f f i c a s s i g n m e n t m a t r i x ( C o s t ) . T h i s c o n t a i n s i n f o r m a t i o n on t h e
expected
path c o s t t o each d e s t i n a t i o n over each l i n e .
This
i n f o r m a t i o n d e t e r m i n e s which l i n e t o u s e f o r t r a f f i c t o a d e s t i n a t i o n .
An e n t r y c o n s i s t s o f C o s t ( i , j ) ,
where:
C o s t ( i , j ) R e p r e s e n t s t h e p a t h c o s t from t h i s T r a n s p o r t l a y e r t o
d e s t i n a t i o n , with t h e following values:

the

V a l u e 1 Meaning
E x p e c t e d p a t h c o s t t o t h i s node
Expected p a t h c o s t t o o t h e r reachable nodes
Unreachable nodes
-

Is a d e c i m a l i n t e g e r i n
destination address.

the

range

1-NN

Is a d e c i m a l i n t e g e r i n t h e r a n g e 1-NLN
l i n e t o d e s t i n a t i o n i.

representing
representing

a
the

Minimum t r a f f i c a s s i g n m e n t v e c t o r ( M i n c o s t ) . T h i s s u m m a r i z e s t h e p a t h
c o s t i n f o r m a t i o n c o n t a i n e d i n t h e C o s t t a b l e . An e n t r y c o n s i s t s o f
Mincost ( i) ,
where:
M i n c o s t ( i ) R e p r e s e n t s t h e s m a l l e s t c o s t from t h i s T r a n s p o r t l a y e r t o
t h e d e s t i n a t i o n , with t h e following values:

Value

Meaning

0
1-Maxc
Infc

S m a l l e s t c o s t t o t h i s node
S m a l l e s t c o s t t o o t h e r reachable nodes
U n r e a c h a b l e node

Is a decimal i n t e g e r i n
destination address.

the

range

representing

1-NN

Send r o u t i n g m e s s a g e f l a g s ( S r m ) . The Srm f l a g s e x t e n d p e r m i s s i o n t o
t h e u p d a t e p r o c e s s t o s e n d a r o u t i n g m e s s a g e t o a n a d j a c e n t n o d e . The
update process determines t h e a c t u a l propagation r u l e s .
An e n t r y
c o n s i s t s of S r m ( j ) ,
where:
Srm(j)

I n d i c a t e s w h e t h e r o r n o t a r o u t i n g m e s s a g e s h o u l d be
t o t h e a d j a c e n t node, with t h e following values:

1 V a l u e 1 Meaning

sent

- - - --

Do n o t s e n d r o u t i n g m e s s a g e .
Send r o u t i n g m e s s a g e .

I s a d e c i m a l i n t h e r a n g e 1-NLN r e p r e s e n t i n g t h e
which t o s e n d t h e m e s s a g e t o t h e a d j a c e n t node.

line

S e l f v e c t o r . T h i s c o n t a i n s t h e node a d d r e s s i d e n t i t y o f t h e
T r a n s p o r t a t t h i s node. An e n t r y c o n s i s t s o f S e l f ( i ) ,

user

where:
Self(i)

C o n t a i n s t h e node a d d r e s s i d e n t i t y o f a T r a n s p o r t u s e r .

(i)

Is a decimal i n

t h e r a n g e 1-NN
address of a Transport user.

representing

the

node

Transport Identification (Tid).
This
contains
the
Transport
i n i t i a l i z a t i o n v a l u e from t h e Network Management SET NODE STATE ON
c a l l . The v a l u e is a two-byte i n t e g e r .

T h i s c o n t a i n s t h e node t y p e ( r o u t i n g ,
Node t y p e v e c t o r
(Nty)
nonrouting,
o r P h a s e 11) o f a n a d j a c e n t node. An e n t r y c o n s i s t s o f
Nty(j) ,
where:
Nty ( 1 )

Contains
the
value
received
from
the
Transport
i n i t i a l i z a t i o n message ( S e c t i o n 8 ) most r e c e n t l y r e c e i v e d .
The v a l u e i n d i c a t e s w h e t h e r t h e a d j a c e n t node is r o u t i n g ,
n o n r o u t i n g , o r P h a s e 11.

I s a d e c i m a l i n t e g e r i n t h e r a n g e 1-NLN

l i n e from t h i s node t o t h e a d j a c e n t n o d e .

representing

the

Node identification vector (Nid)
identification of an adjacent node.

. An This
represents
the
node
entry consists of Nid(j),

where:
Nid(j)

Contains the value received from the SRCNODE field of the
Transport initialization message most recently received.

Is a decimal integer from 1-NLN representing the line from
this node to the adjacent node.

Appendix D contains some routing data base examples.

4.2

Forwarding Data Base

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

not

the

representing

the

where:
Reach

Is a reachability value consisting of:

Reachable
Unreachable

Is a decimal in the range
destination node address.

1-NN

Output lines (OL). This identifies the line on which
packet to a destination. An entry consists of OL(i),

forward

where:
OL ( i)

4.3

Represents the line to be used when forwarding a packet to
destination i. OL contains one of the following values:
Value

Meaning

0
1-NLN

Deliver to a Transport user at this node
A line on which to forward a packet

Is a decimal in the range 1-NN representing a
node address.

destination

Data Base Protection

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.4

Transport must periodically propagate routing messages.

Column 0 of the Cost and Hop matrices (in other
values relating to self) cannot be corrupted.

words,

the

Decision Process

The decision process selects paths and maintains the routing and
forwarding data bases. This process consists of a controller and two
algorithms. The following events serve as input to the decision
process:
Line down
Line up
Routing message received
Operator command to change line cost
Operator command to change parameters Maxh or Maxc
Operator command to identify Transport user (owner)
Operator command to remove Transport user
Timer expiration
The decision process produces the following output:
Modifications to the routing data base
Modifications to the forwarding data base

4.4.1 Decision Controller - The
functions:
Performs buffer
messages.
Â

controller

management

performs

necessary

the

following

receive

routing

Supports Transport initialization (Section 7).
Checks for valid routing message.
has:

valid

routing

message

valid checksum

A valid Transport control header (Section 8)

If the routing message is not valid, then a line down event is
generated, and the routing message is discarded and recorded.
A valid routing message is processed through end of message or
end of table.
If the routing 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 existing NN and records the error.
Updates the forwarding data base

4.4.2 Decision Algorithms - This module supports two algorithms: one
for connectivity, the minimum hop algorithm;
and the other for
traffic assignment, the minimum cost algorithm.
The minimum hop
algorithm changes the reachability vector. Reach. The minimum cost
algorithm changes the output line vector. OL, and performs a Boolean
'or" operation on the Reach vector.
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.
In both the subroutines and the list of event actions, the
and j have the following meanings:

symbols

i destination address, a unique integer from 1-NN.
j

line number, a unique integer from 1-NLN.

Subroutine:

Rowmin<M,I,minimum)

Matrix M
Inteser m i n i m u m
Intesier 1
m i n i m u m = "big n u m b e r 8
F o r each c o l u m n J f r o m 0 t o NLN do
BEGIN
I F ( M < I ÃJ) < m i n i m u m ) then
m i n i m u n i = M ( I ÃJ)
OL(1) = J
E N DI F
END

The routine above determines the minimum for row I of
stores line number OL(1).

Subroutine:

Matrix

and

Minimize (I,M,V,Pl,P2)

Intesier I
Matrix M
Vector V
P a r a m e t e r s F l ? F2
Rowmin(MI
~ minimum)
I F ( m i n i m u m > P I ) then m i n i m u m = F2
I F < V ( I ) < > m i n i m u m ) then
V ( I)
= minimum
ENDIF

This routine determines entries for vector V, containing
of each row of matrix M.

the

minimum

S u b r o u t i n e : Routes

INTEGER OLD-HOP? OLD-COST
For each row i from 1 to NN do
Begin
OLD-HOP = MINHOP (i)
OLD-COST = MINCOST (i)
Minimize (row iv HOP? Minhop? Maxhv Infh)
Minimize (row iv Costv Mirioost~ Maxc? Irtfc)
If (Minhop(i) = Infh or Mincost(i) = Info)
Then
Bed i n
Reach(i) = False
Minhop( i) = Infh
Mincost(i) = Infc
End
Else Reach<i) = True
Endiff
If(MINHOP(i) < > OLDHOF or MINCOST(i) < > OLDCOST
Then set each Srm FLAG
End
T h i s r o u t i n e d e t e r m i n e s t h e r e a c h a b i l i t y and o u t p u t l i n e f o r each
d e s t i n a t i o n and s e t s t h e r o u t i n g f l a g s i f a p p r o p r i a t e . The o r d e r of
i n v o c a t i o n s of Minimize i n t h i s s u b r o u t i n e i s very important.
If some
nodes i n a network perform them i n one o r d e r , and o t h e r nodes i n
a n o t h e r o r d e r , then i n c o r r e c t ( c i r c u l a r ) r o u t i n g could r e s u l t .
Subroutine:

Check

BEGIN
For each I from 1 to NN
IF Self (i) = i,
Check that HOP (Self( i ) T O ) =
0
and
Cost
(Self(i)~O)= 0
ELSE
Check that Hop<iY O ) = Infh and Cost( i 9 0 ) = Infc
ENDIF
IF either check fails? then
Terminate Transport
ENDIF
IF both checks are successful ? then
E :.: i t
ENDIF
END
T h i s r o u t i n e d e t e c t s any c o r r u p t i o n of column 0 i n t h e
matrices.
Event
A.

l i n e j down

Hop

1 Action

0 . C a l l Check.

1. S e t each e n t r y i n column "j" of Hop
matrix t o Infh.

2 . S e t each e n t r y i n column "j" of Cost
matrix t o I n f c .
3 . C a l l Routes.

Supply " l i n e down complete" t o
i n i t i a l i z a t i o n sublayer.

( c o n t i n u e d on n e x t page)

and

Cost

Action
l i n e j up

0 . C a l l Check.

1. I F ( N t y ( j ) = " s m a l l " ) , then
" k " is neighbor a t end of l i n e " j "
Hop(k,j) = 1
I F L c v ( j ) i s n o t p o s i t i v e , then
Transport terminates.
Cost(k,j) = Lcv(j)
ENDIF
ENDIF
2 . S e t each Srm f l a g .

3. C a l l Routes.
4.

r o u t i n g message r e c e i v e d
on l i n e j

Supply " l i n e up complete" t o
i n i t i a l i z a t i o n sublayer.

0 . C a l l Check.

1. Copy hop s u b f i e l d of r o u t i n g message
o n t o column " j " of Hop m a t r i x .
2 . Add 1 t o each e n t r y
i n column " j " of
Hop m a t r i x .
3 . Copy c o s t s u b f i e l d of r o u t i n g message

o n t o column " j " of Cost m a t r i x .
4 . I f L c v ( j ) i s n o t p o s i t i v e , then
Transport terminates.
Otherwise, add L c v ( j ) t o each e n t r y
i n column " j " of Cost m a t r i x .
5 . C a l l Routes.

line j cost
change

0 . C a l l Check.
1. C a l c u l a t e t h e d i f f e r e n c e between t h e

new c o s t and t h e o l d c o s t f o r l i n e j.
Note t h a t t h e new c o s t and t h e o l d
c o s t m u s t both be p o s i t i v e , o t h e r w i s e
Transport terminates.
2 . Add t h i s d i f f e r e n c e t o each e n t r y i n
column " j " of Cost m a t r i x .

3 . C a l l Routes.

Maxh o r Maxc
change

0 . C a l l Check.

Event
F.

A c tion

Open(k)
issued
t o identify
Transport
user k

0. C a l l Check.
1. S e l f ( k ) = k
2 . Hop(k.0) = C o s t ( k , O ) = 0

3. C a l l Routes.
G.

Close(k)
issued
t o remove
Transport
user k

0. C a l l Check.
1. S e l f ( k ) = q
2 . Hop(k,O) = I n f h
3. C o s t ( k . 0 ) = I n f h

4 . C a l l Routes.
H.

Timer e x p i r e s

0. C a l l Check.
1. S e t each Srm f l a g .
2 . C a l l Routes.

4.5

Update P r o c e s s

The update p r o c e s s p r o p a g a t e s r o u t i n g messages and d e t e r m i n e s t h e i r
c o n t e n t . I t c o n s i s t s of an a l g o r i t h m and a format module. The update
process accepts t h e following a s input:
The minimum hop v e c t o r , Minhop
The minimum c o s t v e c t o r , Mincost
The update p r o c e s s produces a r o u t i n g message f o r an a d j a c e n t node
output.

4.5.1
Update Algorithm - The f o l l o w i n g a l g o r i t h m s u p p o r t s r o u t i n g
message p r o p a g a t i o n .
The a l g o r i t h m is based on t h e send r o u t i n g
message f l a g s , Srm, and t h e use of two t i m e r s , T l and T2 per l i n e .
For f u r t h e r d i s c u s s i o n on s u g g e s t e d T l and T2 s e t t i n g s , s e e Appendix

A r o u t i n g m e s s a g e is

sent

adjacent

node

when:

is a v a i l a b l e from t h e q u o t a g i v e n t o
t h e routing process f o r update use.

A buffer

and e i t h e r
Tl has elapsed s i n c e t h e l a s t transmission of
a r o u t i n g m e s s a g e on t h i s l i n e .

The Srm f l a g i s s e t f o r t h i s l i n e and a t
least
T2
has
elapsed
since the l a s t
t r a n s m i s s i o n of a r o u t i n g message.

U p d a t e F o r m a t t e r - T h i s module c o n s t r u c t s t h e
from Minhop and M i n c o s t v e c t o r s .

4.5.2

4.6

routing

message

Forwarding Process

The f o r w a r d i n g p r o c e s s s u p p l i e s and manages t h e b u f f e r s n e c e s s a r y
route- through.
Packets a r e discarded i f buffer thresholds
exceeded.

4 -7

for
are

Receive Process

The r e c e i v e p r o c e s s r e c e i v e s p a c k e t s from t h e D a t a L i n k l a y e r .
then passes t h e packet t o t h e appropriate process, a s follows:

4.8

P a c k e t Type

Process

Routing message

Decision process

H e l l o message

Node L i s t e n e r p r o c e s s

Packet f o r Self

Network S e r v i c e s l a y e r

Packet for other
destination

Forwarding p r o c e s s

Select Process

The s e l e c t p r o c e s s e x a m i n e s t h e d e s t i n a t i o n f i e l d i n t h e p a c k e t r o u t e
h e a d e r , r e a d s t h e f o r w a r d i n g d a t a b a s e , and d e t e r m i n e s t h e a p p r o p r i a t e
l i n e on which t o t r a n s m i t t h e p a c k e t .
I f t h e d e s t i n a t i o n is
unreachable o r i f t h e address exceeds t h e range of t h e forwarding d a t a
base, then t h e s e l e c t process e i t h e r r e t u r n s t h e packet t o t h e sender
o r d i s c a r d s t h e p a c k e t , d e p e n d i n g on t h e i n d i c a t e d o p t i o n i n t h e
p a c k e t r o u t e h e a d e r . I f t h e p a c k e t i s t o be r e t u r n e d t o t h e s e n d e r ,
t h e n t h e " r e t u r n t o s e n d e r r e q u e s t " b i t i n t h e p a c k e t r o u t e h e a d e r is
t u r n e d o f f and t h e " r e t u r n t o s e n d e r " b i t i s t u r n e d on.
Also, t h e
s o u r c e and d e s t i n a t i o n f i e l d s a r e e x c h a n g e d .
I f t h e d e s t i n a t i o n is
u n r e a c h a b l e and t h e " r e t u r n t o s e n d e r " b i t is o n , t h e n t h e p a c k e t is
discarded.

5.0

DETAILED CONGESTION CONTROL SPECIFICATION

The t r a n s m i t management s u b r o u t i n e h a n d l e s
congestion
Transmit management c o n s i s t s of t h e f o l l o w i n g Components:

control.

Square r o o t l i m i t e r . Reduces b u f f e r occupancy time per p a c k e t
by using a s q u a r e r o o t l i m i t e r a l g o r i t h m (Appendix F ) . The
s q u a r e r o o t l i m i t e r a l s o queues p a c k e t s f o r an o u t p u t l i n e ,
and p r e v e n t s b u f f e r deadlock by d i s c a r d i n g p a c k e t s when t h e
b u f f e r pool i s e x h a u s t e d . S e c t i o n 5 . 1 s p e c i f i e s t h e s q u a r e
root l i m i t e r process.
Input packet l i m i t e r .
~ i m i t s i n p u t packet t r a f f i c when
n e c e s s a r y t o e n s u r e t h a t t r a n s i t p a c k e t s a r e n o t r e j e c t e d . An
i n p u t p a c k e t ( c a l l e d an a r r i v i n g packet by Network Management)
i s a packet from Network S e r v i c e s a t t h i s node. A t r a n s i t
p a c k e t is a p a c k e t from a n o t h e r node t o be r o u t e d through t o
a n o t h e r d e s t i n a t i o n node.
(Section 5.2)
F l u s h e r . F l u s h e s p a c k e t s queued f o r
down.
(Section 5.3)

line

that

has

gone

Packet s i z e checker. Resolves d i f f e r e n c e s between p a c k e t s i z e
and Data Link r e c e i v e b l o c k s i z e .
( S e c t i o n 5.4)

5.1

Square Root L i m i t e r

The s q u a r e r o o t l i m i t e r d i s c a r d s a t r a n s i t packet or r e j e c t s an i n p u t
packet when t h e o u t p u t l i n e queue exceeds t h e d i s c a r d t h r e s h o l d , Ud.
Ud i s g i v e n a s f o l l o w s :

where:
NB

= Number of T r a n s p o r t b u f f e r s f o r a l l o u t p u t l i n e s .

NLN = Number of a c t i v e o u t p u t l i n e s .

An a l g o r i t h m t o c a l c u l a t e t h e s q u a r e r o o t l i m i t , Ud, a p p e a r s i n
Appendix F . Using t h i s a l g o r i t h m reduces s w i t c h c o n g e s t i o n and a l l o w s
f o r i n c r e a s e d b u f f e r a v a i l a b i l i t y by reducing b u f f e r occupancy per
packet.

5.2

I n p u t Packet L i m i t e r

The i n p u t p a c k e t l i m i t e r f i r s t d i s t i n g u i s h e s between i n p u t p a c k e t s and
I t then
imposes a l i m i t on t h e number of b u f f e r s
t r a n s i t packets.
t h a t i n p u t p a c k e t s can occupy on a per l i n e b a s i s .
I n times of heavy
l o a d , i n p u t p a c k e t s may be r e j e c t e d while t r a n s i t p a c k e t s c o n t i n u e t o
be r o u t e d . T h i s is done because i n p u t p a c k e t s have a r e l a t i v e l y s h o r t
w a i t , whereas t r a n s i t p a c k e t s , i f r e j e c t e d , have a long w a i t -- a
retransmission period.
The i n p u t p a c k e t l i m i t e r a c c e p t s a s i n p u t :
A

packet r e c e i v e d from Network S e r v i c e s

A t r a n s m i t complete from t h e Data Link

S e r v i c e s packet

layer

for

Network

The i n p u t p a c k e t l i m i t e r p r o d u c e s t h e f o l l o w i n g a s o u t p u t :
Packet accepted
Packet rejected
Modifications t o input counter
T h e r e i s a n i n p u t c o u n t e r , N , and a n i n p u t p a c k e t l i m i t , I P L , f o r e a c h
Each IPL is
active output line.
Each N i s i n i t i a l i z e d t o 0 .
i n i t i a l i z e d t o t h e number o f b u f f e r s n e c e s s a r y t o p r e v e n t t h e l i n e
from i d l i n g .

5.3

Flusher

The f l u s h e r a c c e p t s a p a c k e t and c h e c k s t h e l i n e s t a t e .
If the line
t h e f l u s h e r a c c e p t s t h e p a c k e t and p a s s e s it t o t h e
s t a t e is R U N ,
p a r a m e t e r r e s o l v e r component. I f t h e l i n e s t a t e i s n o t R U N , t h e n t h e
f l u s h e r d i s c a r d s a l l p a c k e t s q u e u e d on t h i s l i n e .

5.4

P a c k e t S i z e Checker

The p a c k e t s i z e c h e c k e r c h e c k s t h e s i z e o f e a c h p a c k e t t h a t i t is
a b o u t t o q u e u e on a n o u t p u t l i n e . T h i s i n c l u d e s p a c k e t s from b o t h t h e
Network S e r v i c e s l a y e r a t t h i s node and t h e D a t a Link l a y e r coming
from o t h e r n o d e s . When t h e p a c k e t s i z e e x c e e d s t h e D a t a L i n k r e c e i v e
blocksize (established during Transport i n i t i a l i z a t i o n ) , t h e packet
s i z e c h e c k e r d i s c a r d s t h e p a c k e t and r e c o r d s t h e e v e n t .

6.0

DETAILED PACKET LIFETIME CONTROL SPECIFICATION

The packet lifetime control component consists of the following:
Packet lifetime control data base (Section 6.1)
Node listener process (Section 6.2)
Node talker process (Section 6.3)
Loop detector process (Section 6.4)

6.1

Packet Lifetime Control Data Base

The packet
parameters:

6.2

lifetime

control

data

base

contains

the

following

Maxv

The maximum number of nodes that a packet may visit.

The hello frequency timer.
It supports the periodic
exchange of hello messages.
Hello messages are packet
lifetime activity packets used for dead node recognition.

The listening period timer. If no packets or Transport
control messages are received in this period, the adjacent
node is considered down.

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:
Hello message received
Any message received
Timer pulse received
The node listener process produces the following as output:
Modifications to the line data base
Modifications to the packet lifetime data base

6.2.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
Transport control header and valid data. If the hello message is not
valid, then a line down event is generated, and the hello message is
recorded and discarded.

6.2.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 line is reinitialized.
The
following table describes the algorithm for handling each node
listener event.

~ ci o tn

Event
A.

H e l l o message
or any message
received

B. Timer p u l s e

Reset T4

Check Image d a t a

Decrement T 4

I F (T4 <= O ) , t h e n
Reset T 4
Set l i n e s t a t e t o
"line rejected.
ENDIF

6.3

Node T a l k e r P r o c e s s

The node t a l k e r p r o p a g a t e s h e l l o messages.
t o an a d j a c e n t node when:

I t sends a

hello

message

T3 has e l a p s e d s i n c e t h e l a s t t r a n s m i s s i o n of any message.

A l i n e has come up.

The node t a l k e r can be i n t e r l o c k e d with t h e d e c i s i o n and update
p r o c e s s e s . when e i t h e r d e c i s i o n o r update f a i l s , then t h e node t a l k e r
ceases.

6.4

Loop D e t e c t o r P r o c e s s

The l o o p d e t e c t o r l i m i t s t h e number of nodes t h a t a p a c k e t can v i s i t .
It
increments t h e node v i s i t f i e l d i n t h e p a c k e t r o u t e header by one.
( S e c t i o n 8 d e s c r i b e s t h e packet r o u t e header. The node v i s i t f i e l d is
used f o r counting t h e number of nodes v i s i t e d by t h i s p a c k e t . ) The
l o o p d e t e c t o r d i s c a r d s t h e p a c k e t i f t h i s number exceeds t h e maximum
node v i s i t l i m i t , Maxv. Note t h a t t h e parameter Maxv m u s t always be
g r e a t e r than o r e q u a l t o t h e parameter Maxh.
The f o l l o w i n g t a b l e d e s c r i b e s t h e a l g o r i t h m t h e l o o p d e t e c t o r e x e c u t e s
when i t r e c e i v e s a p a c k e t .
Event
A.

Packet r e c e i v e d

Act i o n
1. Add 1 t o node v i s i t f i e l d
i n p a c k e t r o u t e header.
2 . I F ( ( n o d e v i s i t > Maxv) and
( " r e t u r n t o sender" is
not s e t ) ) , then
Discard packet and record
END I F
I F ((node v i s i t

> 2 * Maxv)
and ( " r e t u r n t o s e n d e r "
is s e t ) ) , then
Discard packet and record
ENDIF

7.0

TRANSPORT INITIALIZATION SUBLAYER

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

The Transport initialization line states (Section 7.1)

The Transport initialization line events (Section 7.2)

The
Transport
initialization
requirements (Section 7.3)

and

message

The Transport initialization state table and diagram

(Section

operation

7.4)

7.1

Transport Initialization Line States

The Transport initialization line states are:
(Symbol) State

Description

(RU) RUN

Transport can use the line
packets between two nodes.

(LR) LINE REJECTED

The line
is
degraded.
To
avoid
excessive packet delay the line will be
declared down.
The routing decision
process has not yet processed a line
down event.

(DS) DATA LINK START

The line is undergoing Data
initialization.

(TI) TRANSPORT INITIALIZE

The line has successfully undergone Data
Link initialization and is waiting to
receive
a
Transport
Initialization
message.

(TV) TRANSPORT VERIFY

A valid Transport Initialization message
has been received for this line and the
line requires verification.

(TC) TRANSPORT COMPLETE

Transport has completed a valid exchange
of Transport Initialization and possibly
Transport Verification messages.

(OF) OFF

Transport cannot use the line.
The
routing decision process has not yet
processed a line down event.

(HA) HALT

Transport cannot use the line.
down event is required.

transmit

Link

layer

line

7.2

Transport Initialization Line Events

The Transport initialization line events are as follows:
(Symbol) Description
Transport received
message.

valid

new

Transport

Initialization

Transport
message.

valid

new

Transport

Verification

received

Transport received a valid NSP Node Initialization message.
Transport timed out.
Transport received a start complete notification (in other
words, a transition from the initializing state to the
running state) from the Data Link layer.
Transport 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.
Operator turned line on.
Operator turned line off.
Transport received an invalid Transport
message or an unexpected message.

Initialization

Transport received a reject complete from the line rejection
component of the line monitor.
Transport initialization received a line down complete event
from the decision process in the Transport control sublayer.
Transport initialization received a line up complete event
from the decision process in the Transport control sublayer.
When the Data Link layer has initialized, a timer starts.
If the
timer expires before the line accepted state is reached, then the line
is reinitialized. If the timer expires after the line accepted state
is reached, then the timer is ignored.

7.3

Transport ~nitializationOperation and Message Requirements

Transport initialization performs the following actions:
1.

Issue reinitialize command to the Data Link layer
timer

Issue stop to the Data Link layer.

Send a valid Transport Initialization message.

Send a valid Transport Verification message.

and

start

valid Transport
characteristics:

Initialization

message

has

valid Transport control header with node address
or equal to this node's NN

7.4

f0ll0~ing
less

than

received Data Link blocksize greater than or equal to
maximum (routing message size, hello message size, 2 4 6 )

the

An acceptable routing version

valid Transport Verification message has a value
the function value.

the

that

agrees

with

Transport Initialization State Table and Diagram

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

Table 3
Transport 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 ( / ) followed by the number of the action. A dash (.- 1 . sianifies
no action. Section 7.3 describes the actions by number.
a

Old State
Event

nti

LR/-

DS/-

D S / ~ D S / ~ OF/-

HA/-

ntv

LR/-

DS/-

DS/1

TC/-

DS/~

OF/-

HA/-

oti

LR/-

DS/-

RU/-

DS/1

OF/-

HA/-

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

Action: 4;
New
received message;

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

Action: 4;
New
received message;

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

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

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

The routing decision process generates line down events in the
LR and OF. It generates a line up event in the state TC.

states

Figure 4, following, shows the Transport state transitions.

lo
Note:

Figure 4

7.5

Legend:

contains symbol representing Transport
initialization state (Table 1)

These state transitions are not guaranteed.

Transport State Transitions

Line Rejection

The line rejection subroutine determines the sustained unusability of
a line. Normal line outages, impulse noise, and so on do not force a
line's rejection.
Instead, this subroutine seeks the continued
unavailability of a line.
The line rejection subroutine monitors a line's effective throughput.
line is rejected when this throughput falls below a threshold. A
line can also be rejected by the initialization process through the
receipt of error threshold reports.

7.5.1 Line Rejection Parameters and Variables - The line rejection
parameters and variables reside in the line data base. The parameters
are as follows:
Tpt

The number of packets that must be transmitted in a given
interval.
If this throughput is not met and the line is
busy then the line is reinitialized.

The interval in which Tpt packets must be sent.

The line rejection variables are as follows:
PC

The packet counter vector, which counts the number of
packets sent during the last period.
An entry, Pc(j),
represents the number of completed transmissions for line
"j" in this last period.

The actual queue size vector. An entry, Qa(j), represents
the actual queue size for line "j" at the time of the last
observation. Each entry can assume any integer value from 0
to Ud, the discard threshold (Section 5.1).

The time interval between successive observations of a
for line load estimations.

7.5.2 Line Rejection Algorithm - The rejection algorithm attempts
maintain a minimum throughput for a line as follows:

line

I f 1i n e aueue i s non-empty
Send T p t p a c k e t s i n T5 seconds
Else r e i n i t i a l i z e the l i n e
Endif

Execute the following algorithm every Op seconds:
Decrement T5
I f (T5 <= 0 ) Then
I f (PC . ;1 0 ) Then
I s s u e r e j e c t complete? re.
E 1s e
R e s e t T5
If(Qa < > 0 ) t h e n
PC = 0
E l PC = T p t
End if
Endif
E l s e (T5 > 0 )
I f PC = 0 and Qa I::. ::> 0 Then
R e s e t T5
PC = T p t
Endif
Endif

Whenever a transmission is complete, execute the following algorithm:
Remove p a c k e t f r o m Queue.
I f (PC :::. 0 ) Then
PC = PC - 1
Endif
I f <Qa = 0 ) Then
PC = 0
Endif

8.0

MESSAGES

T h i s s e c t i o n d e s c r i b e s t h e message f o r m a t s of t h e T r a n s p o r t
T h e r e a r e two t y p e s o f T r a n s p o r t m e s s a g e s :

Packet r o u t e header
T h i s is used f o r
may r e q u i r e f o r w a r d i n g ( S e c t i o n 8 . 2 )

Transport control
These c o n t r o l
i n i t i a l i z a t i o n functions.
They d o
(Section 8.3).

8.1

NSP

protocol.

segments,

which

T r a n s p o r t r o u t i n g and
not r e q u i r e forwarding

Message F o r m a t N o t a t i o n

The f o l l o w i n g n o t a t i o n is u s e d t o d e s c r i b e t h e m e s s a g e s :
FIELD (LENGTH) :

CODING

Description of f i e l d

where:
FIELD

Is t h e name o f t h e f i e l d .

(LENGTH)

Is t h e l e n g t h of t h e f i e l d , one o f :

CODING

A number meaning t h e number o f 8 - b i t

bytes.

A number f o l l o w e d by

The l e t t e r s "EX-n"
meaning e x t e n s i b l e f i e l d , w i t h n
b e i n g a number t h a t s p e c i f i e s t h e maximum l e n g t h o f
8 - b i t b y t e s , where t h e h i g h o r d e r b i t of e a c h b y t e
i n d i c a t e s w h e t h e r t h e n e x t b y t e is p a r t o f t h e same
f i e l d . A o n e (1) means t h e n e x t b y t e is p a r t o f t h e
same f i e l d .
The low o r d e r s e v e n b i t s a r e i n f o r m a t i o n
bits.

The l e t t e r s u I - n " meaning a n image f i e l d , w i t h n b e i n g a
number t h a t s p e c i f i e s t h e maximum l e n g t h o f 8 - b i t b y t e s
i n t h e image. The image is p r e c e d e d by a 1 - b y t e c o u n t
o f t h e l e n g t h o f t h e r e m a i n d e r o f t h e f i e l d . Image
f i e l d s a r e v a r i a b l e l e n g t h and may b e n u l l ( c o u n t = 0).
A l l e i g h t b i t s of each byte a r e information b i t s .

a "B" meaning t h e number o f b i t s .

Represents t h e type of coding used, one o f :
1.

= Binary.

= B i t map.

= Constant.

NULL = I n t e r p r e t a t i o n is d a t a d e p e n d e n t .

Each b i t h a s i n d e p e n d e n t meaning.

F i e l d s i n s e p a r a t e m e s s a g e s w i t h i d e n t i c a l names a r e t h e same f i e l d
and h a v e i d e n t i c a l m e a n i n g s .
A l l numeric v a l u e s are d e c i m a l u n l e s s
o t h e r w i s e n o t e d . A l l h e a d e r f i e l d s and d a t a b y t e s a r e t r a n s m i t t e d low
o r d e r o r l e a s t s i g n i f i c a n t b i t f i r s t on t h e d a t a l i n e u n l e s s o t h e r w i s e
noted.
M u l t i p l e b y t e f i e l d s a r e t r a n s m i t t e d low o r d e r o r l e a s t
significant byte f i r s t .

8.2

P a c k e t Route Header

The p a c k e t r o u t e header h a s t h e f o l l o w i n g format:
RTFLG

SRCNODE

DSTNODE

RTFLG ( E X ) :

FORWARD

I s t h e s e t of f l a g s used by t h e r o u t i n g
The format of t h i s f i e l d i s a s f o l l o w s :

Bit:

Setto:

RTS

RQR

EV ( 1 B )

RTS ( 1 B ) :

RQR ( 1 B )

Is t h e routing evolution f l a g ,
where:

Routing
node
r o u t e header

Phase I1 node
header

the "return
f l a g , where:

Transport
ASCII
to

route
sender"

I n d i c a t e s t h i s packet i s
n o t on a r e t u r n t r i p .
If
is
the
destination
u n r e a c h a b l e , r e f e r t o RQR
flag (next).

I n d i c a t e s t h i s p a c k e t is
being
returned.
I f its
d e s t i n a t i o n is u n r e a c h a b l e ,
then d i s c a r d t h i s p a c k e t .

I s the "return
to
r e q u e s t " f l a g , where:

nodes.

sender

Indicates
discard
the
packet i f t h e d e s t i n a t i o n
is unreachable.

Indicates t r y t o return the
packet t o sender i f t h e
d e s t i n a t i o n is u n r e a c h a b l e .
No
return
g u a r a n t e e is
p o s s i b l e s i n c e no p a t h may
exist.

DSTNODE ( 2 ) :

I s t h e d e s t i n a t i o n zode a d d r e s s , a unique
from 1 t o N N .
B i t 16 is r e s e r v e d .

SRCNODE ( 2 ) :

I s t h e s o u r c e node a d d r e s s , a unique i n t e g e r
1 t o NN.
B i t 16 i s r e s e r v e d .

FORWARD ( E X )

integer
from

I s i n f o r m a t i o n u s e f u l i n t h e forwarding of
the
message. The format of t h i s f i e l d i s a s f o l l o w s :

lit:

S e t to:

7 6 m l
0

VISIT (6B) :

0
BM

VISIT
C o n t a i n s t h e count of
the
number of nodes v i s i t e d by
t h i s packet.

An invalid packet route header is one in which:
SRCNODE or DSTNODE is not in the range 1 to NN.
Reserved bits or extension bits are set.
RQR and RTS are set.
Discard short packets (in other words, packets with less than a packet
route header) and packets with an invalid route header.

8.3 Transport Control Messages
A

control message has the following general format:

CTLFLG

SRCNODE

CTLFLG (EX) :

type-dependent-information
Is the Transport control flag, with the
format:
Bit:

Set to:

TYPE

TYPE ( 3 B ) : B

SRCNODE (2) :

type-dependentinformation

Indicates
Transport
follows :

following

the
type
of
control message, as

Transport
message

Initialization

Transport
message

Verification

Transport
message

Transport Routing message

Hello

and

Test

Is the identification of the
source
node's
Transport, containing the value, Tid (Section
4.1).
SRCNODE is less than or equal to NN
(Section 4.1).
Is as described in Sections 8.3.1

- 4.

8.3.1
Transport
information is:
RTGINFO

Routing

Message - The

Routing

type-dependent

CHECKSUM

RTGINFO

: BM

Is the Transport routing information, which is a
sequence of 16-bit fields in the following format:
Bit:
Set to:
HOPS (5B) :
COST (10B) :

HOPS
B

Is the path
destination.

length

Is the
path
destination.

cost

The length of this field is determined by the
length of the entire message. The word position
determines node reference:
field 1 refers to
destination number 1 , and so on.
CHECKSUM (2) :

Is a check on the routing data base, as well as
the message.
It is a one's complement add,
representing the sum of both COST and HOP, where
COST and HOP are treated as a 16-bit binary value.

Message - The

8.3.2 Transport Hello and Test
type-dependent information is:

TEST DATA (1-128) :

Hello

and

Test

Is a sequence of up to 128 bytes of data used
to test the line. Each byte is 252 octal.
The node listener does the checking.

8.3.3 Transport ~nitializationMessage - The Transport Initialization
type-dependent data has the following format:

1 TIINFO 1 BLKSIZE 1 TIVER 1 RESERVED 1
TIINFO (EX) : BM

Is Transport information on node type and
requests, as follows:

NTYPE (2B) :

Is the Transport node type:
0
1
2
3

VERIF (1B) :

RESERVED (1-64)

service

Reserved
Reserved
Routing node
Nonrouting node

Transport Verification message
required if this bit is set.
reserved field
currently
containing a count of 0.

BLKSIZE ( 2 ) :
TIVER (3) :

I s the maximum Data Link layer receive block Size.

Is the
format:

Transport

version,

with

the

following

Byte 1 -- version number (1)
Byte 2

-- ECO number (3)

Byte 3

-- user ECO number (0)

8.3.4
Transport
Verification
verification information is:

Message

FCNVAL
FCNVAL (1-64) :

Is the function value.

- The

type

dependent

APPENDIX A

ROUTES, ADDRESSES, AND NAMES

T h i s Appendix e x p l a i n s t h e r e l a t i o n s h i p between a d d r e s s e s and names i n
a network.
T r a n s p o r t i d e n t i f i e s nodes i n a network by unique numbers ( a d d r e s s e s ) .
However, i t is o f t e n more c o n v e n i e n t f o r u s e r s t o i d e n t i f y nodes by an
a l p h a b e t i c o r alphanumeric name. I n a d d i t i o n , s e v e r a l u s e r s a t one
node may each wish t o i d e n t i f y network nodes by d i f f e r e n t names.
Moreover, u s e r s may n o t want t o use o n l y names t h a t a r e unique w i t h i n
t h e network.
Thus a problem a r i s e s a s t o how t o bind node names t o
node a d d r e s s e s i n a network.
The s o l u t i o n is t o use names t h a t a r e unique w i t h i n a node ( l o c a l l y
unique) and a d d r e s s e s t h a t a r e unique w i t h i n t h e network ( g l o b a l l y
u n i q u e ) . The following r u l e s apply:
T r a n s p o r t knows nodes o n l y by t h e i r a d d r e s s e s .
A l l a d d r e s s e s a r e known throughout t h e
a r e unique ( a n i n t e g e r from 1 t o N N ) .

network

Names a r e a s s i g n e d i n d i v i d u a l l y on
( l o c a l ) and a r e unique w i t h i n a node.

(global)

node-by-node

and
basis

The l o c a l naming f u n c t i o n (name t o a d d r e s s d i r e c t o r y ) is n o t
n e c e s s a r i l y a one t o one f u n c t i o n . I n o t h e r words, a l i a s node
names may be a s s i g n e d t o a node name a s long a s o v e r a l l l o c a l
uniqueness is p r e s e r v e d .
T h i s s o l u t i o n has t h e f o l l o w i n g advantages:
A l i a s e s a r e not g l o b a l . When networks merge, t h e r e i s no need
t o change l o c a l a l i a s e s .
I t p r e s e r v e s t h e correspondence between names and a d d r e s s e s .
I t a v o i d s t h e complex problem of m a i n t a i n i n g d u p l i c a t e
of a d i s t r i b u t e d d a t a base i n an a u t o m a t i c f u n c t i o n .

copies

I t a v o i d s network maintenance problems
r e l a t e d t o name and
address d i r e c t o r i e s . I n c o r r e c t d i r e c t o r i e s a f f e c t only l o c a l
users.

T h i s s o l u t i o n imposes some r e s p o n s i b i l i t i e s on network managers.
The
l o c a l network manager m u s t e n s u r e t h e l o c a l d i r e c t o r i e s p r e s e r v e
uniqueness of names. The c e n t r a l network manager m u s t e n s u r e t h e
d i r e c t o r i e s p r e s e r v e uniqueness of a d d r e s s e s .

APPENDIX B
ROUTING SUBSETS AND TOPOLOGIES

T h i s Appendix d e f i n e s r o u t i n g and n o n r o u t i n g n o d e s i n terms o f t h e i r
c o m p o s i t i o n , and o u t l i n e s t o p o l o g i c a l c o n s i d e r a t i o n s t h a t m u s t b e made
when p l a n n i n g n e t w o r k c o n f i g u r a t i o n s .

B.1

R o u t i n g and N o n r o u t i n g Nodes

P h a s e I11 n o d e s a r e o f two t y p e s :

B.2

Routing nodes. These c o n t a i n t h e f u l l r o u t i n g s u b s e t o f t h e
d e c i s i o n process, t h e update process, t h e forwarding process,
and t h e s e l e c t and r e c e i v e m o d u l e s .

Nonrouting nodes.
T h e s e c o n t a i n o n l y t h e s e l e c t and r e c e i v e
modules.
A n o n r o u t i n g node s u p p o r t s a s i n g l e l i n e a n d h e n c e
is a n e n d node.

Topological Concepts

Network t o p o l o g y i n v o l v e s two
logical connectivity.

concepts:

physical

connectivity

and

P h y s i c a l c o n n e c t i v i t y d e f i n e s r u l e s f o r c o n n e c t i n g n e t w o r k n o d e s by
A n o d e ' s p o s i t i o n i n t h e n e t w o r k may b e r e s t r i c t e d
physical lines.
Two
d e p e n d i n g on i t s node t y p e ( r o u t i n g , n o n r o u t i n g , o r P h a s e 1 1 ) .
n o d e s a r e p h y s i c a l l y c o n n e c t e d i f t h e y a r e c o n n e c t e d by a s e q u e n c e of
a c t i v e 1i n e s .
Logical connectivity
communicate.
Two
communicate.

d e f i n e s r u l e s f o r two n o d e s b e i n g a b l e t o
nodes
a r e l o g i c a l l y connected i f they can

I n a n e t w o r k o f o n l y P h a s e I11 n o d e s , a n y two n o d e s c a n b e l o g i c a l l y
connected.
I n a network c o n t a i n i n g o n e o r more P h a s e I1 n o d e s , some
r e s t r i c t i o n s a r e imposed. R e f e r t o Appendix G .

B.3

DECnet T o p o l o g i c a l R u l e

I n a n y n e t w o r k o f r o u t i n g and n o n r o u t i n g n o d e s , p h y s i c a l
is i d e n t i c a l t o l o g i c a l c o n n e c t i v i t y .
R o u t i n g n o d e s c a n be p h y s i c a l l y i n t e r c o n n e c t e d i n a n
Any
two p h y s i c a l l y c o n n e c t e d r o u t i n g n o d e s a r e
connected.

connectivity

a r b i t r a r y way.
also logically

n o n r o u t i n q node can o n l y be an
n o n r o u t i n g node, o r a r o u t i n g node.

end

node

adjacent

another

The f i r s t c a s e is a n e t w o r k o f two n o n r o u t i n g n o d e s , which a r e a l s o
l o g i c a l l y connected.
I n t h e s e c o n d c a s e , t h e node is l o g i c a l l y
connected t o any p h y s i c a l l y connected node.

B. 4

L e g a l and I l l e g a l T o p o l o g i e s

A network t o p o l o g y i s l e g a l i f t h e p h y s i c a l c o n n e c t i v i t y s a t i s f i e s t h e

A p a r t from a n i n d e p e n d e n t n e t w o r k o f
condition stated in Section B.3.
P h a s e I1 n o d e s , t h e m o s t g e n e r a l l e g a l n e t w o r k t o p o l o g y is i l l u s t r a t e d
I n i t a l l r o u t i n g and n o n r o u t i n g n o d e s a r e l o g i c a l l y
i n F i g u r e 5.
c o n n e c t e d . A l l P h a s e I1 n o d e s a r e l o g i c a l l y c o n n e c t e d t o a d j a c e n t
nodes only.
Any s u b n e t w o r k
( p o s s i b l y a s i n g l e node) of a l e g a l
n e t w o r k is a l s o a l e g a l n e t w o r k .

Legend:

= routing node

0
0
Figure 5

= non-routing node

= Phase II node

Example o f a L e g a l Network Topology

A n e t w o r k t o p o l o g y may b e c h a n g e d i n t e n t i o n a l l y o r u n i n t e n t i o n a l l y d u e

t o a component f a i l u r e .

P o s s i b l e network changes a r e t h e r e s u l t o f :

Disconnecting a physical l i n e .

S h u t t i n g a node o f f , which d i s c o n n e c t s a l l l o g i c a l l i n k s .

Opening a p h y s i c a l l i n e .

S t a r t i n g a node and o p e n i n g a p h y s i c a l l i n e t o a n o t h e r node.
51

This section discusses conditions for preserving topological
when the network is altered.

legality

Since any subnetwork of a legal network is also a legal network,
disconnecting
a line or shutting a node preserves topological
legality. However, the network may be partitioned into disconnected
subnetworks.
A physical line can legally be established between nodes of
or different routing types, under the following conditions:

B.5

the

same

Routing--Routing

If nodes are not adjacent

Routing--Nonrouting

If the nonrouting node is isolated

Nonrouting--Nonrouting

If both nodes are isolated

Nonrouting--Routing

If the nonrouting node is isolated

Nonrouting Operation

This section describes the routing operation for nonrouting nodes.
Section 4.4 describess the routing algorithm for routing nodes.

B.5.1 Select and Receive Modules - 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.
If the packet is a routing message, the node listener
discards it.
When transmitting to a node other than self, the node listener sends
the packet out over the only line available. Otherwise, the node
listener returns or discards the packet, depending on the packet route
header option.
If a remote NSP sends a packet with "return to sender" requested, and
there is no adjacent routing node, the node listener returns the
packet to NSP. This happens either when the line is down or when it
is up to an adjacent nonrouting node.
B.5.2
Interfaces - The NSP and Data Link interfaces are as described
in Sections 3.2 and 3.3. Nonrouting nodes support the entire Network
Management interface in Section 3.1 except:
READ NODE STATUS
READ NODE HOPS
READ NODE COST
READ NODE LINE
READ LINE COST
SET LINE COST
Since a nonrouting node does not perform the packet aging function,
the interface does not need to support the reading or writing of the
Maxv parameter.
Note that the source address in the OPEN function must be equal to the
Transport identification value, Tid.

APPENDIX C

ROUTING PARAMETER SETTINGS

The follow! ng r o u t i n g p a r a m e t e r s e t t i n g s a r e r e q u i r e d :
1.

I n f h = 31.

I n f c = 1023.

Some s u g g e s t e d r o u t i n g p a r a m e t e r s e t t i n g s a r e a s f o l l o w s :
1.

Maxh = 1 6 .

Maxc = 400.

= 1 m i n u t e when l i n e b a n d w i d t h x < 9600 b i t s / s e c o n d
1 5 s e c o n d s when x >= 9600 b i t s / s e c o n d

Some s u g g e s t e d p a c k e t l i f e t i m e c o n t r o l p a r a m e t e r s a r e a s f o l l o w s :
1.

Maxv = Maxh + k where 1 < k <= Maxh

= 3 seconds

= 30 s e c o n d s

APPENDIX D

ROUTING EXAMPLES

T h i s Appendix p r o v i d e s some examples of r o u t i n g d a t a b a s e s and t h e
e f f e c t of t o p o l o g i c a l changes on t h e r o u t i n g d a t a b a s e s . The examples
a r e s p e c i f i c t o a g i v e n topology and s e l e c t e d nodes i n t h a t topology.
The examples do n o t i l l u s t r a t e a c t u a l r o u t i n g t i m i n g s , a s t h e s e v a r y
with l i n e and node c h a r a c t e r i s t i c s .
Figure 6a shows a r o u t i n g d a t a base i n a s t a t i c topology.
F i g u r e 6b
c o n t i n u e s with a s i m i l a r network c o n f i g u r a t i o n , but shows a l i n e
coming up and t h e e f f e c t s of t h i s e v e n t on t h e r o u t i n g d a t a base.
In
t h i s example a l l l i n e c o s t s a r e assumed t o be 1 ( o n e ) and t h e r e f o r e do
not a f f e c t t h e r o u t i n g message.

A, B, C, D, E = routing nodes
2, 3, 5, 7, 12 = lane costs (same at each end of the line)
DA, DC, DE, AB, AD lines from nodes D and A; line DE is down

Let

mfh = 31.
infc = 1023.
maxh = 4.
m x c = 150.

The following diagram shows the routing data bases at nodes D and A:
Node D
HOP MATRIX

D
E

MINHOP

DUTPUT LINE

1
2
1

DA
DA
DC

Node A
HOP MATRIX

COST MATRIX

F i g u r e 6a

MINCOST DUTPUT LINE

S t a t i c Topology Routing Data Base Example
54

A, B , C, 0, E = routing nodes
OA, OC, DE = lines from node 0
EC, ED = lines from node E
Let

lnfh = 31
Maxh = 4.

The follow~ngdiagram shows the interaction between nodes D and E when link DE comes up.
This diagram shows only the hop matrix and associated minhop vector. This corresponds t o a network where
all l ~ n e
costs are set to 1. I n such a case, minhop is the routing message.
@ L I N K DE COMES UP
Node 0
HOP MATRIX

Node t
MINHOP

MINHOP

OUTPUT LINE

DA
DC

3
2
1

EC
EC
EC
ED

OUTPUT LINE

HOP MATRIX

0 sends the routing message 11, 2, 1,0,2 I
to E.

E sends the routing message 13,2, 1.2,01
to D and C.

@ EFFECT OF EXCHANGE OF MESSAGE
Node D
HOP MATRIX

Node E
MINHOP

OUTPUT LINE

E sends the routing message l2,2. 1, 1.01
to D and C.

Figure 6b

R o u t i n g D a t a B a s e -- L i n e Up Example

F i g u r e 6 c c o n t i n u e s w i t h t h e e x a m p l e f r o m F i g u r e 6b, b u t shows t h e
r o u t i n g m e s s a g e e x c h a n g e s t h a t o c c u r b e t w e e n n o d e s A,B,C, and D and
t h e a d j u s t m e n t s t o t h e r o u t i n g d a t a b a s e s r e s u l t i n g f r o m t h e l i n e up
event.

A, B, C, D, E = routing nodes
AB, AD, BA, BC, CB, CD, CE, OA, DC, DE = lines from nodes A, B, C, and D
The following d~agramshows the interaction between nodes A, B, C, and D when a
routing message exchange occurs, (All lane costs are assumed t o be set t o 1.1

@ Tables A and C prior t o exchange:
Node A

Node C

K\
HOP MATRIX

MINHOP

OUTPUT LINE

MINHOP

HOP MATRIX

OUTPUT LINE

vaa:

1
2
1
3

@ A and C recejve 11, 2, 1, 0, 11 from D as a result of the change in node D's tables as shown in Figure 5b:

Node A

Node C
MIN HOP OUTPUT LINE

HOP MATRIX

MINHOP

OUTPUT LINE

MINHOP

OUTPUT LINE

@ ~ a b l e s B and D prior to exchange:
Node B

Node 0

L O P MATRIX

MINHOP

7
OUTPUT LINE

@Band D recesve LO, 1.2.1. 21 from A:
Node D
- -

Node B
HOP MATRIX

MINHOP

OUTPUT LINE

HOP MATRIX

MINHOP
I

OUTPUT LINE
I

via:
BA

D
E

1
2
2

BC
BA
BC

Figure 6c

Routing Data Base -- Message Exchange Example

F i g u r e 6 d , t h e f i n a l e x a m p l e , shows a node b e i n g i s o l a t e d from t h e
n e t w o r k by a l i n e g o i n g down. O n l y t h e p a r t o f t h e r o u t i n g d a t a b a s e s
r e l a t i n g t o t h e i s o l a t e d node i s shown. The a l g o r i t h m s t h a t c a u s e t h e
changes exemplified a r e described i n S e c t i o n 4.4.2.

A, 8, C, D, E = routing nodes
AB, AD, BA, BC, CB, CD, CE, DA, DC, DE = lines from nodes A, 0, C, and D; line DE is down
Maxh = 4.
lnfh = 31.
The following diagram exemplifies what happens in routing data bases when a node b w m e s iwlated
from the rest of the network. I n this case, line CE goes down, isolating node E. Only that part of the
routing data bases pertaining to node E is shown. An entry of 31 i n the minhop field indicates an
unreachable node. Only the element in the routing message referring to E is shown.

@ Tables A, 0, C, and D prior to link CE gomg down
Node B

Node A

Hop MATRIX

MlNHop

OUTPUT LiNJ

Node C

HOP MATRIX

MINHOP

OUTPUT LINE

Node D

HOP MATRIX

MINHOP

OUTPUT LINE

1 HOPMATRIX

1 MINHOP 1 OUTPUT LINE 1

@ Link CE goes down:
Node 4

Node B

1 HOP MATRIX

1 MINHOP 1 OUTPUT LINE 1

HOP MATRIX

MINMOP

OUTPUT LINE

MINHOP

HOP MATRIX

MINMOP

OUTPUT LINE

Node C
HOP MATRIX

OUTPUT LINE

ia:

F i g u r e 6d

R o u t i n g D a t a B a s e s -- Example o f I s o l a t i o n o f a Node

@ C sends 3 to B and D:
Node B

Node A
HOP MATRIX

MINHOP

OUTPUT LINE

1 HOP MATRIX

1 MINHOP 1 OUTPUT LINE 1

Node D

Node C

HOP MATRIX

MINHOP

OUTPUT LINE

vla:
to:

DA
E

DA
-

@I3

sends 4 to A and C; D sends 4 to A and C

Node A

Node B

Node C

HOP MATRIX

MINHOP

OUTPUT LINE

Node D

kki

HOP MATRIX

via:

MINHDP

OUTPUT LINE

via:

@ A sends AE 5 to B and D; C sends CE 5 to B and D:
Node A

Node B
HOP MATRIX

via:

Node C

Node D

1 HOPMATRIX

Figure 6 D (Cont.)

1 MINHOP 1 OUTPUT LINE 1

HOP MATRIX

R o u t i n g D a t a Bases--

MINHOP

OUTPUT LINE

Example o f I s o l a t i o n o f a Node

APPENDIX E
TRANSPORT COUNTERS AND EVENTS

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

Transport 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
in Table 5.

Table 4
Source Event M a n i f e s t a t i o n s
Event M a n i f e s t a t i o n

Definition

Data Movement

T h i s group of s o u r c e e v e n t s r e f l e c t s t h e
movement of d a t a through T r a n s p o r t .

Congest ion

T h i s group o f s o u r c e e v e n t s r e f l e c t s t h e
discarding
of
d a t a p a c k e t s due t o
Transport congestion.

Data Packet Discarded

T h i s group of s o u r c e e v e n t s r e f l e c t s t h e
d i s c a r d i n g of d a t a p a c k e t s due t o a
fault.

Message Format E r r o r

The format of t h e message is i n e r r o r .

P a r t i a l Routing Update Loss

This source event r e p r e s e n t s the r e c e i p t
of a r o u t i n g message t h a t i s t o o long t o
p r o c e s s s o t h a t some i n f o r m a t i o n from
t h e message is d i s c a r d e d .

Line Down

T h i s group of s o u r c e
the
detection
of
failure.

Initialization Failure

T h i s group of s o u r c e e v e n t s r e p r e s e n t s a
f a i l u r e t o i n i t i a l i z e with an a d j a c e n t
node.

V e r i f i c a t i o n Reject

This source event represents t h e r e c e i p t
of an i n v a l i d v e r i f i c a t i o n message.

Line Up

This
source
event
represents
successful
initialization
with
a d j a c e n t node.

Node R e a c h a b i l i t y Change

T h i s group of s o u r c e e v e n t s r e p r e s e n t s a
change i n node r e a c h a b i l i t y (between
r e a c h a b l e and u n r e a c h a b l e ) .

events represents
a physical link

the
an

Table 5
Source Event Causes
(Symbol) Cause

Explanation

(A) Activity

The normal a c t i v i t y
moving d a t a .

The r e s o u r c e l i m i t c o n d i t i o n , d e t e c t e d
by T r a n s p o r t , t h a t c a u s e s T r a n s p o r t t o
d i s c a r d normal d a t a .

( S ) System F a u l t

F a i l u r e s of e i t h e r hardware o r s o f t w a r e
and u n d e t e c t e d l i n e f a i l u r e s , e x c l u d i n g
line faults.

(0) Operator F a u l t

F a i l u r e of an o p e r a t o r t o s e t p a r a m e t e r s
c o r r e c t l y f o r t h e harmonious o p e r a t i o n
of m u l t i p l e nodes.
Typical operator
f a u l t s i n c l u d e a n o d e ' s maximum a d d r e s s
t h a t i s t o o s m a l l o r an a d j a c e n t n o d e ' s
i d e n t i f i c a t i o n t h a t is t o o l a r g e .

(TI T o p o l o g i c a l Change

M o d i f i c a t i o n s i n topology t h a t r e s u l t i n
a node changing i t s r e a c h a b i l i t y s t a t u s .

(V) Verification Violation

The d e t e c t e d a t t e m p t of a node
initialize
without
providing
expected v e r i f i c a t i o n i n f o r m a t i o n .

(L) Line F a u l t

The d e t e c t e d f a i l u r e of a p h y s i c a l l i n k .
A l i n e f a u l t does not necessarily r e s u l t
i n a t o p o l o g i c a l change.

Transport

to
the

NOTE

Some source
causes:

events

may

have

multiple

Packet loss through aging is caused
topological fault and either:

control
Operator
fault -- Rate
timer, T2, is set too large.
or

SoÂ tware
fault -- Decision
update operates too slowly.

Packet loss through aging is caused by a
software fault when:
0

Visit field is destroyed in some
node
or
by undetected line
error.
Routing
algorithm
has
completed
and
packets
looping.

Packet
loss
unreachability
fault when:

not
are

through
destination
is caused by an operator

Destination
does
not
exist
(detected at source node).

Routing parameters,
Maxh
Maxc, are set too small.

Routing parameter NN (maximum
node address) is less than node
address.

Packet
loss
through
destination
unreachability
is
caused
by
a
topological fault when:
0

Node is really unreachable.

Node will be unreachable when
routing algorithm completes.

Multiple
topological
faults
cause
an increase in actual
network
diameter
and
some
maximum hop parameters are too
small.

Table 6
Source Events

Went
Manifestation
I a t a Movement

Source
Event
Number

Probable
Cause

Definition
A d a t a packet is received

from a l i n e f o r a n o t h e r node
i n t h e network.
A d a t a p a c k e t from a n o t h e r

node i n t h e network is s e n t
over a l i n e .
A d a t a p a c k e t is r e c e i v e d

from a l i n e f o r t h i s n o d e ' s
NSP

A d a t a p a c k e t from t h i s

n o d e ' s NSP i s s e n t o v e r a
line.
Zongest i o n

A t r a n s i t d a t a p a c k e t is

discarded for congestion
reasons.
An o u t p u t p a c k e t is
d i s c a r d e d due t o t h e
i n a b i l i t y of NSP t o p r o c e s s
o u t p u t p a c k e t s f a s t enough.
-

Data P a c k e t
Discarded

D e s t i n a t i o n node is
unreachable.
Packet is too old.
D e s t i n a t i o n node i s
o u t of r a n g e .
Received d a t a p a c k e t is t o o
l a r g e t o forward due t o t h e
b l o c k s i z e of t h e d a t a l i n k
t h a t would be used.
---

Message Format
Error

Message f o r m a t i s i n e r r o r .

P a r t i a l Routing
Update Loss
n o d e ' s NN.

Received l o n g r o u t i n g
message w i t h r e a c h a b l e node
number g r e a t e r t h a n t h i s
n o d e ' s NN.
( c o n t i n u e d on n e x t page)

Table 6 (Cont.
Source Events
Went
lanifestation
Line Down

Source
Event
Number

Probable
Cause

Definition
Data link synchronization
lost.
Data link threshold error
detected.
Line rejection algorithm
rejected line (for reason
other than threshold error).
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.

Initialization
Failure

Verification message not
received in timeout period.
Data link synchronization
lost.
Data link threshold error
detected.
Version skew detected.
Node id in received
initialization message too
large.
Block size in received
initialization message too
large.
Invalid verification seed
value in received
initialization message.
Unexpected message received.

Verification
Reject

Invalid verification
received.

Line Up

Node initialization complete.

Node Reachability

Node reachable.

Change

Node unreachable.

Table 6
Source Events

Went
Manifestation
l a t a Movement

Source
Event
Number

Probable
Cause

Definition
A d a t a packet is received

from a l i n e f o r a n o t h e r node
i n t h e network.
A d a t a packet from a n o t h e r

node i n t h e network i s s e n t
over a l i n e .
A d a t a packet is received

from a l i n e f o r t h i s n o d e ' s
NSP.
A d a t a p a c k e t from t h i s

n o d e ' s NSP i s s e n t over a
line.
Congestion

A t r a n s i t d a t a p a c k e t is

discarded f o r congestion
reasons.
An o u t p u t p a c k e t i s
d i s c a r d e d due t o t h e
i n a b i l i t y of NSP t o p r o c e s s
o u t p u t p a c k e t s f a s t enough.
--

Data Packet
Discarded

D e s t i n a t i o n node i s
unreachable.
Packet i s t o o o l d .
D e s t i n a t i o n node is
o u t of range.
Received d a t a p a c k e t i s t o o
l a r g e t o forward due t o t h e
b l o c k s i z e of t h e d a t a l i n k
t h a t would be used.

Message Format
Error

Message format i s i n e r r o r .

P a r t i a l Routing
Update Loss
node's NN.

Received long r o u t i n g
message with r e a c h a b l e node
number g r e a t e r t h a n t h i s
n o d e ' s NN.
( c o n t i n u e d on n e x t page)

Table 6 (Cont.)
Source Events
-

Event
Manifestation
Line Down

- -

Source
Event
Number

Probable
Cause

definition
3ata link synchronization
lost.
Data link threshold error
detected.
Line rejection algorithm
rejected line (for reason
other than threshold error).
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.

1 Initialization
Failure

Line Up

Node initialization complete.

Node Reachability

Node reachable.

1 Change

Node unreachable.

E.2

Counters

There are two types of counters -- node and line. Transport maintains
one node counter for each of the defined node counters. Transport
maintains one line counter per physical link for each of the defined
line counters.
Node counters count source events attributed to
topological changes, faults, and verification
violation.
Line
counters count source events attributed to activity, congestion, and
faults.
Each counter
Tables 7 and 8 define the node and line counters.
relates to a source event number from Table 6, Section E.I. Refer to
the glossary for definitions of input, output and transit packets.
A
packet is received when it passes from the Data Link layer t o the
Transport layer. A packet is sent when it passes from the Transport
layer to the Data Link layer.
Table 7
Node Counters

Counter
Name

Counter
Width

node unreachable packet loss

16 bits

aged packet loss

8 bits

node out-of-range packet loss

8 bits

oversized packet loss

8 bits

packet format error

8 bits

partial routing update loss

8 bits

verification reject

8 bits

Source
Events
Included

Table 8
Line Counters

Counter
~ame

Counter
Width

t r a n s i t packet received

32 b i t s

t r a n s i t packet s e n t

32 b i t s

output ( a r riving) packet received

32 b i t s

input (departing) packet s e n t

32 b i t s

t r a n s i t congestion loss*

16 b i t s

output ( a r riving) congest ion l o s s

16 b i t s

l i n e down

16 b i t s

initialization failure

16 b i t s

Source
Events
Included

* O n l y r e q u i r e d i n t h e i m p l e m e n t a t i o n s i n which NSP d o e s n o t
guarantee Transport t h a t it w i l l process an output packet (thereby
f r e e i n g t h e b u f f e r h o l d i n g t h e p a c k e t ) i n a bounded p e r i o d o f time.
E.3

Events

Network Management g r o u p s some o f t h e s o u r c e e v e n t s ( S e c t i o n E.1)
t o g e t h e r f o r l o g g i n g . The DNA Network Management F u n c t i o n a l
S p e c i f i c a t i o n s p e c i f i e s t h i s l o g g i n g o p e r a t i o n . When a s o u r c e e v e n t
t o b e l o g g e d o c c u r s , T r a n s p o r t i d e n t i f i e s i t by t y p e , t i m e - s t a m p s i t ,
and p l a c e s i t i n a n i n t e r n a l T r a n s p o r t e v e n t q u e u e . I f t h e e v e n t
q u e u e is f u l l , T r a n s p o r t d i s c a r d s t h e n e w e s t e v e n t i n t h e q u e u e and
r e p l a c e s it with an " e v e n t ( s ) l o s t " event.
T a b l e 9 s p e c i f i e s t h e T r a n s p o r t e v e n t s and t h e s o u r c e e v e n t s t h a t
t r i g g e r them. The s o u r c e e v e n t numbers a r e from T a b l e 6 , S e c t i o n E . I .

Table 9
T r a n s p o r t Events
7

source
Events

Event
Type
Node unreachable p a c k e t l o s s

l i n e , packet
header

Aged p a c k e t l o s s

p a c k e t header

Node out-of-range

l i n e , packet
header

packet l o s s

Oversized p a c k e t l o s s

l i n e , packet
header

Message format e r r o r

l i n e , packet
header

P a r t i a l r o u t i n g update l o s s

l i n e , packet
header, highest
node a d d r e s s

1 Line down - l i n e f a u l t

Logged
Information

1i n e

Line down - s o f t w a r e f a u l t

l i n e , packet
header

Line down - o p e r a t o r f a u l t

l i n e , packet
h e a d e r , expected node id

Initialization failure - line fault

Initialization failure

- software

l i n e , packet
h e a d e r , received version
( 2 3 only)
l i n e , packet
header

fault

Verification reject

1i n e

l i n e , node i d
from message

Line up

l i n e , node id
from message

Node r e a c h a b i l i t y change

node a d d r e s s

NOTE

logged e v e n t of a s i n g l e t y p e t h a t
can r e s u l t from more t h a n one s o u r c e
e v e n t a l s o c o n t a i n s a reason code t o
s p e c i f y the source event.

"Packet header" d e n o t e s t h e f i r s t 6
( 4 8 b i t s ) of a T r a n s p o r t
bytes
message

APPENDIX F
ALGORITHMS AND MODELS

T h i s a p p e n d i x d e s c r i b e s a l g o r i t h m s and models p e r t a i n i n g t o :
L i n e c o s t ( S e c t i o n F.1)
Square r o o t l i m i t e r ( S e c t i o n F . 2 )
0

F.1

B u f f e r management ( S e c t i o n F . 3 )

L i n e Cost Assignment A l g o r i t h m

The a s s i g n m e n t o f c o s t t o l i n e s c a n r e f l e c t b o t h d e l a y and t h r o u g h p u t
data.
Delay d a t a c a n i n c l u d e t r a n s m i s s i o n d e l a y , p r o p a g a t i o n d e l a y ,
p r o c e s s i n g d e l a y , and r e t r a n s m i s s i o n d e l a y .
Delay d a t a d o e s n o t
i n c l u d e q u e u e i n g d e l a y . Throughput d a t a c a n i n c l u d e l i n e b a n d w i d t h ,
c i r c u i t o v e r h e a d , and p r o c e s s o r bandwidth.
Throughput d a t a d o e s n o t
i n c l u d e a c t u a l t r a f f i c o v e r h e a d . B a s i c a l l y , it is d e s i r a b l e t o a v o i d
a l i n e c o s t assignment a l g o r i t h m with high s e n s i t i v i t y t o t r a f f i c
f l u c t u a t i o n s , t h e r e b y p r o d u c i n g a c o n d i t i o n where r o u t e s change t o
accommodate t r a f f i c c h a n g e s and t h e new t r a f f i c f l o w c a u s e s new r o u t e
c h a n g e s , and s o on.
A l i n e c o s t a s s i g n m e n t o c c u r s a s a r e s u l t of a node g e n e r a t i o n

initialization
assignment

module.

operator

can

always

o r an
o v e r r i d e any

One s u c h a s s i g n m e n t is based on l i n e bandwidth and is a s f o l l o w s :
1 where bandwidth x >= 100,000 b i t s / s e c o n d

F ( x ) = [100,000/xl

f o r 4,000 b i t s / s e c o n d

< x < 100,000 b i t s / s e c

2 5 where x <= 4,000 b i t s / s e c o n d

where x is l i n e bandwidth ( b i t s / s e c )

F.2

S q u a r e Root L i m i t A l g o r i t h m

C a l c u l a t e t h e square r o o t t h r e s h o l d a s follows:
Let

n = number o f T r a n s p o r t b u f f e r s i n t h e p o o l
y = number o f o u t p u t l i n e s t h a t a r e a c t i v e

Then x = t h e s q u a r e r o o t l i m i t , which
g r e a t e r t h a n o r e q u a l t o n / SQRT y.

the

smallest

integer

F.3

B u f f e r Management

When no b u f f e r s a r e a v a i l a b l e f o r r e c e i v i n g p a c k e t s from a l i n e , s t o r e
and forward deadlock can o c c u r . Deadlock can be avoided by i n s u r i n g
t h a t a t l e a s t one b u f f e r is a v a i l a b l e p e r l i n e , o r a b u f f e r can be
made a v a i l a b l e w i t h o u t r e q u i r i n g a d d i t i o n a l r e s o u r c e s . Such deadlock
avoidance can r e q u i r e d i s c a r d i n g p a c k e t s .
When r e c e i v e b u f f e r s a r e n o t a v a i l a b l e q u i c k l y enough, a l i n e can go
down u n n e c e s s a r i l y a t t h e Data Link l a y e r . I t i s much b e t t e r f o r
T r a n s p o r t t o d i s c a r d a p a c k e t t h a n f o r a l i n e t o go down.
T r a n s p o r t should n o t i n i t i a l i z e u n l e s s i t can o b t a i n a t l e a s t t h e
minimum number of r e c e i v e b u f f e r s f o r each l i n e . I f an implementation
o b t a i n s t h e s e b u f f e r s from a s h a r e d system b u f f e r p o o l , t h e n t h e
minimum number m u s t be permanently a l l o c a t e d from t h e pool by
T r a n s p o r t when i t i n i t i a l i z e s . They c a n , of c o u r s e , be r e t u r n e d when
Transport h a l t s .
The o n l y time a l i n e may be allowed t o go below i t s minimum number of
b u f f e r s is when t h e system can g u a r a n t e e t h a t a r e c e i v e b u f f e r can be
a l l o c a t e d t o t h e l i n e soon enough i n t h e f u t u r e t o p r e v e n t t h e l i n e
from going down.
T h i s means t h a t i f t h e system has run o u t of f r e e
b u f f e r s and i s down t o t h e minimum number of r e c e i v e b u f f e r s f o r each
l i n e , then:
1.

A r e c e i v e d d a t a p a c k e t t h a t would normally

forwarded

a n o t h e r l i n e must be d i s c a r d e d .
2.

A received

Transport

control

message

can

and

should

processed.
3.

A r e c e i v e d d a t a p a c k e t f o r t h i s node should be g i v e n

t o NSP
o n l y i f NSP i s known t o be a b l e t o r e t u r n t h e b u f f e r i n a
s h o r t , bounded p e r i o d of time.
Otherwise, d i s c a r d t h e
packet.

Compute t h e minimum number of r e c e i v e b u f f e r s r e q u i r e d f o r a g i v e n
l i n e from t h e l i n e speed and an e s t i m a t e of t h e maximum time t h a t
T r a n s p o r t ( o r p o s s i b l y NSP) can t a k e t o p r o c e s s a r e c e i v e d message.

T r a n s p o r t has a common pool
F.3.1 P o s s i b l e B u f f e r Management Model
of b u f f e r s t h a t can t r a n s m i t o r r e c e i v e . I f t h e implementation of NSP
i n a system is known t o be unable t o make t h e g u a r a n t e e of s h o r t ,
bounded p r o c e s s i n g of r e c e i v e d d a t a p a c k e t s , t h e n T r a n s p o r t m u s t l i m i t
t h e number of o u t s t a n d i n g , r e c e i v e d p a c k e t s t h a t NSP can hold o n t o
s i m u l t a n e o u s l y ( p r o v i d e d t h a t NSP and T r a n s p o r t a r e s h a r i n g a common
b u f f e r p o o l ) . T h i s is b e s t done by a f i x e d q u o t a .
S e t t i n g t h i s q u o t a t o t h e s q u a r e r o o t l i m i t used by t h e c o n g e s t i o n
c o n t r o l a l g o r i t h m i s a c c e p t a b l e , but o t h e r v a l u e s may be used a s w e l l .
I f a q u o t a i s used, then any p a c k e t s d i s c a r d e d due t o t h e NSP q u o t a
being f i l l e d m u s t be counted a s d e s c r i b e d i n Appendix E.
The T r a n s p o r t b u f f e r q u o t a provided by t h e system is d i v i d e d i n t o
following buffer quotas:
1.

Decision ( 0 )

Update (1 s u f f i c i e n t ;

Node L i s t e n e r ( 0 )

Node t a l k e r (1)

1 per l i n e recommended)

the

Forwarding ( a t l e a s t 1 p e r l i n e ; 1 2
1 5 per t e r r e s t i a l l i n e
and 3 0 - 35 p e r s a t e l l i t e l i n k recommended)

A s e p a r a t e r e c e i v e q u o t a f o r e a c h l i n e ( d e p e n d s on

l i n e -- a t l e a s t 1 , 2 o r 3 recommended)

speed

I f an i m p l e m e n t a t i o n i s c o n s t r u c t e d u s i n g a s i n g l e b u f f e r
p o o l t h a t T r a n s p o r t s h a r e s w i t h o t h e r s y s t e m p r o c e s s e s , and
i f T r a n s p o r t d o e s n o t do any a c t u a l d a t a moving from one
b u f f e r t o a n o t h e r , t h e n a l l b u f f e r s c o n t a i n i n g d a t a t o be
t r a n s m i t t e d a r e e i t h e r o b t a i n e d from NSP o r a r e r e c e i v e
b u f f e r s t h a t c o n t a i n d a t a p a c k e t s t h a t a r e being forwarded.
The r u l e s above and t h e c o n g e s t i o n c o n t r o l a l g o r i t h m s i n
S e c t i o n 5 a d e q u a t e l y d e f i n e t h e u s e of t h e s e b u f f e r s .
However, n o t e t h e f o l l o w i n g :
F i r s t , t h e s q u a r e r o o t l i m i t i s d e f i n e d t o be t h e number of
b u f f e r s a v a i l a b l e f o r f o r w a r d i n g d i v i d e d by t h e s q u a r e r o o t
of t h e number of l i n e s . The number of b u f f e r s a v a i l a b l e f o r
f o r w a r d i n g s h o u l d n o t i n c l u d e t h e minimum number of r e c e i v e
b u f f e r s , nor s h o u l d i t i n c l u d e NSP's q u o t a , i f such a q u o t a
exists.
Second, i n such a model, a s i n g l e b u f f e r beyond t h e minimum
number of r e c e i v e b u f f e r s and a s i n g l e NSP t r a n s m i t b u f f e r
a r e s u f f i c i e n t t o allow Transport t o run c o r r e c t l y without
starving a l i n e for receive buffers.
In general, for
will
also
be
a d e q u a t e performance a d d i t i o n a l b u f f e r s
required.
F.3.2
D e t a i l s of Charging and C r e d i t i n g A g a i n s t Q u o t a s - A l l b u f f e r s
n o t f r e e w i l l be c h a r g e d a g a i n s t a s p e c i f i c q u o t a . The q u o t a w i l l
never be exceeded e x c e p t p o s s i b l y f o r a b r i e f
i n s t a n t while a
T r a n s p o r t p r o c e s s f r e e s t h e b u f f e r by consuming t h e i n f o r m a t i o n o r by
discarding a packet.
A q u o t a i s c h a r g e d f o r a b u f f e r upon t h e f o l l o w i n g e v e n t s :

A free

b u f f e r is a s s i g n e d t o
r e c e p t i o n on a s p e c i f i c l i n e .

A buffer

A f r e e b u f f e r is s e i z e d by a
c o n t r o l message.

the

ink

Data

layer

for

b u f f e r is moved from one T r a n s p o r t module t o a n o t h e r .
r e c e i v i n g quota is charged.

The

i s s u p p l i e d by NSP t h a t c o n t a i n s i n p u t d a t a .

process

send

Transport

A q u o t a is c r e d i t e d f o r a b u f f e r upon t h e f o l l o w i n g e v e n t s :

T r a n s m i s s i o n of a b u f f e r is completed by t h e Data Link l a y e r .
(The q u o t a i s c r e d i t e d whether o r n o t t h e t r a n s m i s s i o n was
successful.)

A buffer

A p r o c e s s d i s c a r d s a p a c k e t and r e t u r n s t h e b u f f e r .

NSP i s s u e s a s u c c e s s f u l CHECK R E C E I V E command.

is moved from one T r a n s p o r t module t o a n o t h e r .
sending quota is c r e d i t e d .

p r o c e s s consumes t h e c o n t e n t s o f
message and r e t u r n s t h e empty b u f f e r .

Transport

The

control

APPENDIX G
PHASE I1 COMPATIBILITY

T h i s Appendix d e s c r i b e s how P h a s e I1 n o d e s c a n communicate w i t h
111 n o d e s .
P h a s e I1 node c o m p a t i b i l i t y h a s t h e f o l l o w i n g g o a l :

Phase

Any s o l u t i o n m u s t p r o v i d e a smooth t r a n s i t i o n s u c h t h a t
c u s t o m e r s c a n u p g r a d e o n e node a t a time w h i l e n e v e r
d e c r e a s i n g communication c a p a b i l i t i e s .
The s o l u t i o n i s a s f o l l o w s :
A P h a s e I1 node c a n communicate o n l y w i t h a d j a c e n t n o d e s .

P h a s e I1 node d e r i v e s no b e n e f i t s from a r o u t i n g n e t w o r k
u n t i l i t u p g r a d e s t o e i t h e r a r o u t i n g o r n o n r o u t i n g node
subject
to
the topological restrictions described i n
Appendix B.
The s o l u t i o n a s s u m e s t h e f o l l o w i n g P h a s e I1 c h a r a c t e r i s t i c s :
T r a n s p o r t I n i t i a l i z a t i o n o r V e r i f i c a t i o n messages a r e ignored
and d r o p p e d . The l i n e i s n o t r e c y c l e d .
P h a s e I1 n o d e s t r a n s m i t w i t h e i t h e r n o r o u t e h e a d e r o r a n
ASCII r o u t e h e a d e r . An i l l e g a l m e s s a g e ( r o u t i n g m e s s a g e o r
p a c k e t w i t h T r a n s p o r t r o u t e header) is dropped.
Phase
I1
nodes
point-to-point

understand

that

communication

P h a s e I1 n o d e s c a n p r o c e s s NSP acknowledgment m e s s a g e s i n
response
to
NSP C o n n e c t I n i t i a t e and C o n n e c t C o n f i r m
messages.
P h a s e I1 n o d e s c a n d e s t r o y l o g i c a l l i n k s when a p h y s i c a l l i n e
fails.
Communication between P h a s e I1 and P h a s e I11 n o d e s is a s f o l l o w s :
Initialization.
Upon r e c o g n i z i n g a P h a s e I1 Node I n i t i a l i z a t i o n
m e s s a g e , a P h a s e I11 node b u i l d s and s e n d s t h e P h a s e I1 f o r m a t
Node I n i t i a l i z a t i o n m e s s a g e a n d , i f r e q u e s t e d , a v e r i f i c a t i o n
message.
The P h a s e I1 node is f l a g g e d f o r t h i s l i n e . The
r o u t i n g p r o c e s s r e c e i v e s a l i n e up e v e n t and u p d a t e s t h e r o u t i n g
and f o r w a r d i n g d a t a b a s e s .

Receiving messages.
A
p a c k e t from a Phase
I1
node
is
d i s t i n g u i s h a b l e from a p a c k e t w i t h a T r a n s p o r t r o u t e header s i n c e
a Phase I1 node t r a n s m i t s p a c k e t s w i t h e i t h e r no r o u t e header or
an ASCII r o u t e header. When an ASCII r o u t e header is s e n t , t h e
new node removes t h e r o u t e header by s k i p p i n g t h e r o u t e f l a g s and
two image f i e l d s .
The d e s t i n a t i o n a d d r e s s is t h e l o c a l node
address.
The s o u r c e a d d r e s s is t h e a d j a c e n t node a d d r e s s
(established during i n i t i a l i z a t i o n ) .
T r a n s m i t t i n g messages. A p a c k e t from a Phase I11 node t o a Phase
I1 node u s e s t h e l i n e s e l e c t e d by t h e forwarding p r o c e s s .
This
l i n e can be recognized a s having a Phase I1 node a t t h e o t h e r end
because t h i s i n f o r m a t i o n was o b t a i n e d d u r i n g t h e i n i t i a l i z a t i o n
p r o c e s s . A p a c k e t t o a Phase I1 node does n o t r e c e i v e a
T r a n s p o r t r o u t e header.

GLOSSARY

aged packet
A

packet that has exceeded the maximum number of visits.

congestion
The condition that arises when there are too many packets
queued.

datagram
unit of data passed between Transport and the Network Services
layer. When a route header is added, it becomes a packet.

end node
topological description of a nonrouting node.
Since
a
nonrouting node cannot perform route-through and supports only a
single line, it must be an end node.
However, it is also
possible for a routing node with a single line to be an end node.

error
The manifestation of a fault.
event
Occurrences that are logged for recording by Network
Events result from occurrences of source events.

Management.

fault
The cause of a problem in the operation of the Transport modules.
hello
The term for the packet lifetime activity used for
recognition. The node talker sends hello messages.

dead

node

hop
The logical distance between two adjacent nodes in a network.
initialization
With regard to
adjacent nodes.

Transport,

start-up

procedure

input (departing) packet
A

packet from this node's Network Services layer.

between

two

line cost
The positive integer value associated with using a line.
logical connectivity
The result of nodes being able to communicate
Used in describing network topologies.

with

each

other.

max imum address
This
The largest possible node address in a DECnet network.
equal to or less than the number of nodes in the network.

maximum cost
An operator-controllable Transport parameter that defines the
point where the routing decision algorithm in a node declares
another node unreachable because the cost of the least costly
path to the other node is excessive. For correct operation, this
parameter must not be less than the maximum path cost of the
network.
maximum hops
An operator-controllable Transport parameter that defines the
point where the routing decision algorithm in a node declares
another node unreachable because the shortest path between the
two nodes is too long. For correct operation this parameter must
not be less than the network diameter.
maximum path cost
The routing cost between the two nodes of a network having the
greatest routinq cost, where routinq cost is the cost of the
least costly path between a given pair of nodes. In ~ i g u r e3 the
maximum path cost is 9.
maximum path length
The routing distance between the two nodes of a network having
the greatest routing distance, where routing distance is the
length of the least costly path between a given pair of nodes.
In Figure 3 the maximum path length is 4.
maximum visits
An operator-controllable Transport parameter that defines the
point where the packet lifetime control algorithm discards a
packet which has traversed too many nodes.
For
correct
operation, this parameter must not be less than the maximum path
length of the network.
network diameter
The reachability distance between the two nodes of a network
having the greatest reachability distance, where reachability
distance is the length of the shortest path between a given pair
of nodes. In Figure 3 the network diameter is 3.
node
An implementation of Session Control. The interface between
network and a DIGITAL computer system.

the

n o n r o u t i n g node
Phase I11 DECnet node t h a t c o n t a i n s a s u b s e t o f r o u t i n g modules
( s e l e c t p r o c e s s and r e c e i v e p r o c e s s ) and can d e l i v e r and r e c e i v e
I t i s c o n n e c t e d t o t h e network by a s i n g l e l i n e .
packets.

output ( a r r i v i n g ) packet
A

p a c k e t whose d e s t i n a t i o n i s t h i s node.

packet
u n i t of d a t a t o be r o u t e d from a s o u r c e node t o a d e s t i n a t i o n
i t s r o u t e h e a d e r and p a s s e d t o t h e
node.
When s t r i p p e d of
Network S e r v i c e s l a y e r , i t becomes a datagram.
A

packet looping
C o n d i t i o n where a p a c k e t r e v i s i t s a node.
path
The r o u t e a p a c k e t t a k e s from s o u r c e node t o d e s t i n a t i o n node.
T h i s can be a s e q u e n c e of c o n n e c t e d nodes between two nodes.
path cost
The sum of t h e l i n e c o s t s a l o n g a p a t h between two nodes.
path length
The number of hops a l o n g a p a t h between two nodes.
physical connectivity
The r e s u l t of nodes b e i n g a t t a c h e d t o e a c h o t h e r by a c t i v e
used i n d e s c r i b i n g network t o p o l o g i e s .

lines

r e a c h a b l e node
A

node t o which a r o u t i n g node b e l i e v e s i t can d i r e c t a p a c k e t .

received packet
p a c k e t r e c e i v e d by t h i s n o d e ' s T r a n s p o r t l a y e r
Link l a y e r .

from

the

Data

route-through
P a c k e t s w i t c h i n g . The d i r e c t i n g of p a c k e t s from s o u r c e n o d e s
d e s t i n a t i o n nodes. Routing nodes p e r m i t r o u t e - t h r o u g h .

routing
D i r e c t i n g d a t a message p a c k e t s from s o u r c e nodes
nodes.

destination

r o u t i n g node
A Phase I11

Transport
packets.

DECnet
modules,

node t h a t c o n t a i n s t h e c o m p l e t e s e t o f
and c a n d e l i v e r , r e c e i v e and r o u t e t h r o u g h

sent packet
A packet passed from this node's Transport layer to the Data Link
layer.

source event
A specified occurrence in this node's Transport layer that
cause a counter to be incremented or an event to be logged.

may

topology
The physical arrangement and relationships of interconnected
nodes and lines in a network. A legal topology satisfies the
requirements of this specification.
transit packet
A packet arriving at this node from a source
for another node.

node

and

destined

unreachable node
A node to which a routing node has determined
exceed the maximum hops of the network.

that

the

path

count

visit field
The field in the packet route header that contains the
the number of nodes visited by this packet.

DECnet DIGITAL
Network Architecture
(Phase 111)
AA-K180A-TK
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 find this manual understandable, usable, and well-organized?
Please make suggestions for improvement.

Did you find errors in this manual?
page number.

If so, specify the error and the

Please indicate the type of reader 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)

Name

Date

Organization
Street
City

State

Zip Code
or
Country

Necessary

-Y

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

- 1
- 1

- 1

SOFTWARE DOCUMENTATION
146 MAIN STREET ML 5-5lE39
MAYNARD, MASSACHUSETTS 01754

- 1
- 1

-;
-1

- - - Do Not Tear - Fold Here and Tape - - - - - - - - - - - - - - - - - --II