Digital PDFs

AA-X435A-TK

December 1983

140 pages

Original

27MB

view download

OCR Version

8.3MB

view download

Document:	DECnet Digital Network Architecture Phase IV Routing Layer Functional Description
Order Number:	AA-X435A-TK
Revision:	0
Pages:	140
Original Filename:

OCR Text

dlilgliltlall

|440I(S;

DECnet Drgltal Network Architecture
Phase IV

Routing Layer Functlonal Speclflcatlon
Order No. AA-X435A-TK

December 1983
This document specifies the functions, interfaces, and protocols for implementing that part of the Digital Network Architecture that models the

software controlling the routing of messages within DECnet communications networks.

SUPERSESSION/UPDATE INFORMATION:

This is a new manual.

VERSION:

2.0.0

)

| To order addltlonal copiles of this document contact your Iocal
Digital Equipment Corporation Sales Office.

digital equipment corporotion - maynard, massachusetts

First Printing, December 1983

The information in this document is subject to change without notice and should not be construed as a
commitment by Digital Equipment Corporation. Digital Equipment Corporation assumes no respons1b111ty
for any errors that may appear in this document.

The software described in this document is furnished under a license and may only be used or copied in
accordance with the terms of such license.

No respons1b111ty is assumed for the use or rehablhty of software on equlpment thatis not supphed by
DIGITAL or its affiliated compames

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

The following are trademarks of Digital Equipment Corporation:

DIGITAL

DECsystem-10

MASSBUS

DEC

DECtape

PDP

DIBOL

OMNIBUS
0S/8

DECUS

EDUSYSTEM

PHA

FLIP CHIP

RSTS

COMPUTER LABS

FOCAL

RSX

COMTEX

INDAC

TYPESET-8

DDT

LAB-8

TYPESET-11

DECCOMM

DECSYSTEM-20

TMS-11

ASSIST-11

RTS-8

ITPS-10

UNIBUS

VAX

VMS

SBI

DECnet

IAS

PDT

DATATRIEVE

TRAX

Distributed Systems Publications typeset this manual using DIGITAL’s
TMS-11 Text Management System.

MGTPEALL

Table

Contents

] bo

]

o °

[

L | )

]

[

&
e

Design Scope
.
o
Relationship To DIGITAL Network Archltecture
Routing Layer Environment Requirements . . .
Routing Layer Characteristics
. . .
« .
Routlng Layer Control Functional Organlzatlon

.
.

[]

R J

Process

e
e

o
o
o o
oo

o
o
o

.
.

o o
o o
o o
¢« ¢«
. .

¢«
.

.
.

o«
.

o
o
o
.
.

Update Process .
.
Forwarding ProCesSsS
Receive ProCessS
«

¢« o
« «
o« o

Congestion Control
. . .
Packet Lifetime Control

«
¢
o« «
o« o
..
. .

o
«
o

Loop

Detector

¢«

Node

Listener

¢«

o«

o« &

Node

Talker

o o

Network Management Layer

Interface

Data Link Layer Interface
. . .
End Communications Layer Interface
Routing Layer Initialization Interface

o
o

Routing Parameters . .
.
.
« e
Routing Data Base (in Level 1 And Level 2
Routers)
« e e .
. .
.
Area Routlng Data Base In Level 2 Routers
.
Forwarding Data Base In Level 1 And Level 2
.

N
w

®
®

Area Forwardlng Data Base (level 2 Routers Only)
Data Base Protectlon s
s
s
s
ve e
s e
DeCcislon ProCessS . v ¢ v o
o o o o o o
Decision Controller . . . . . . .
Decision Algorithms
e
'
Decision Process Events And ACthflS

Update

ProCessS

.«

Update Algorithm

Forwarding ProCess
Recelive ProCess
.

BOWUNHHFHOFOERERWNDHFOHMFUOUOOOO
NN
JdJO0OWO,

—

Loop

Detector

DETAILED

Square

Root

e
s

e
e

e
4

e
«
o

«.

. «
¢ v

«
o

¢
o

o
o

CONTROL

Limiter

ee
o o

Process

CONGESTION

e
o

|
SPECIFICATION

o
«

Originating Packet Limiter c e e e e e e e e e
Flusher
.
.
Packet Size Checker

ROUTING

LAYER

X. 25

Node Listener ProCess .« « « « o o o o oo o
Node Listener Controller . . . . .. . . .
Node Listener Algorithm . . . . . . . . .
Node Talker ProcCess
. « « « o« o o o
.
Routing Layer Initialization Circuit States‘
Routing Layer Initialization Circuit Events

(NS
I

INITIALIZATION

R
. .
e
e
e e e e
e

Version Skew

[]
[
[
[]

DETAILED ROUTING SPECIFICATION e

[]

>
O1 0T
OO
NN
NN
NNNN

| .

Decision

Routers

) | .

DESCRIPTION

Rout lng

Lahu:;>ofioLabfino1mcno1mcno1mcno1pcun:wc3c>
:»Laun»;aLu~+4F4H
W
H
=
e Wt
W N+

INTRODUCTION )
FUNCTIONAL

' INTERFACES e

RWWWWWRNNRONDNNDNODNDNDNDNDNDNDNDNDDN
-

CONTENTS

INITIALIZATION

SUBLAYER

DDCMP

Page

.
.
.
e

68
.
711
.«
11
.
.11
11
o
11
.«

Table of Contents

Routing Layer Initialization State Table And.’

(@)

Routing Layer Initialization Operation And
Message Requirements . . « «¢ o « &
« . e
Closing Down

;

]

Fragmentation,

Closing Down .

Assembly And Blocking

ETHERNET
Routers
. .
c
4 s e
Ethernet Router Hello Messages

@
o
e
o
e
e

OO
W N

INITIALIZATION SUBLAYER‘

Designated Router . . .
e
When To Transmit Router Hellos
Closing DOWN .« « o ¢
Database Of Endnodes

c
s
«

> W

O
WN

4 = WO W

=
OO
)
NN

10.5
10.6
10.7
10.8
10.9

10.10
10.11

10.12

SN OO
W N

[]
L]
|]

[]

.«

¢«

o«

e
s
e

e
e
&

e e
8 e o
eo

ee
e e e

oo
. .

o
.

s
.

o
.

Ethernet

Endnode Hello Messages

Message

F1111ng

.
«

¢
.

Designated Router's Ethernet Router Hello
*

"next Hop

o«
e
¢
.

«
o
¢

o
e
«

.
.

Level 1 Routing Message

Initialization Message .
Verification Message
‘Hello And Test Message
.

Level 2 Routing Message
. .
Ethernet Router Hello Message
Ethernet Endnode Hello Message

NODE TYPES . . .

TOPOLOGICAL CONCEPTS

e
¢

e e e

- DECNET TOPOLOGICAL PRINCIPLES
ENDNODE RESTRICTIONS . . . .
ETHERNET ROUTER RESTRICTIONS
LARGER NETWORKS
. .
. . . .

HIERARCHICAL NETWORKS

[}

In Packet Headers .

MESSAGES + « v « + & o o o
Message Format Notatlon
Reserved Fields
. . « «
Optional Padding . . .
Short Data Packet Format
Long Data Packet Format

ROUTING SUBSETS AND TOPOLOGIES

¢
.

'ROUTES, ADDRESSES, AND NAMES

APPENDIX A

DWwowoww

e e e
e e

Multiple Areas On An Ethernet
.
Endnodes

10.4

APPENDIX

ADDITIONAL INITIALIZATION SUBLAYER FOR X.25
Incoming Call Control
. . . . . . . .
Error Control
. . .
I

MNNHHRFEFRHRHFHEO®WN
O

WO W W W W

W W W W W O M

o ‘o

Dlagram e

.
.
.

o &
e e
o «

e
o«

e
o

..
. .
. .
.«
'« «
. «
. .
. .
« o
. o

14
14
14
715
15
15
16
16
17
17

17
o«
17
o
17
.
18
.
. 19
19
.
. 80
81
.
82
.
83
.
85
.
86
..
87
. .
89
. .
91
.
93
. .

«
e
.
.
.
.
.
.
.
.

Page

Table of Contents

Receive Module
.

Interfaces

. .

EVENTS

ALGORITHMS

COST

W N

BUFFER
DETAILS

SIZES

POSSIBLE BUFFER

APPENDIX

GLOSSARY

APPENDIX
I

REVISION

ALGORITHM

- ,

MANAGEMENT

CHARGING

AND

MODEL

CREDITING

AGAINST

QUOTAS

HISTORY

I
I

Ethernet Support
Hierarchical Routing
Segmented Routing Messages
Terminology Changes
Clean-ups
Phase 1II Support Removed
X 25 [ ] .‘ [ ] [ ] ® L J ., L )
Miscellaneous

CHANGES FROM PHASE III

L]
®
e
®

s T
e
O
Y

e
|]
[]

[

OO
WN

BUFFER

ASSIGNMENT

MANAGEMENT

APPENDIX

o B o O e B o T o O o

MODELS

[]

CIRCUIT

AND

3 -

COUNTERS

AND EVENTS

w N

e Me

SOURCE EVENTS

F
] *j o

LAYER COUNTERS

tl:ltillltl:l

ROUTING

COMPATIBILITY

"11'11"71"11

- APPENDIX

III

i
W N

PHASE

I
-

I
WNNDNNDND-

APPENDIX

OPERATION

e N

C.0.1
C.0.2

=
e
e

NONROUTING

)

APPENDIX

Introduction

1.0

Page

INTRODUCTION

This document
describes
the
structure,
functions, 1interfaces,
protocols, and
algorithms
for implementing the Routing Layer.
The
Routing Layer is the part of the
DIGITAL
Network
Architecture
that
models the software (or hardware) controlling the routing of messages,
called packets, within DECnet communications networks.
A DECnet network 1s
hardware components
resource
sharing,

a family of software
modules,
data
bases,
and
typically used to tie DIGITAL systems together for
distributed
computation,
= or
remote
system

communication.
DECnet
network
Network Architecture (DNA) model.

1implementations

the DIGITAL
|

DNA is a layered structure.
Modules in each
1layer
perform distinct
functions.
Equivalent modules within the same layer in both the same
and different
nodes
communicate
using
protocols.
A
node
1s
an
implementation
of
the
DNA- Session Control Layer.
Usually a single
computer is associated with one
node.
Protocols
are
the
messages
exchanged
by
modules and the rules governing the message exchanges,
Modules in functionally different layers of DNA interface using either
subroutine
calls
or a
system-dependent
method.
This
document
describes these interfaces in the format of calls to subroutines.
The routing described in this document
is Phase IV DECnet routing.
is
the
major
function
of
the Routing Layer.
DIGITAL's routing
intended for users with networks consisting
of
any combination
point-to-point links,
X.25 links, multipoint links, and Ethernets.

It
is
of

Phase IV DECnet routing 1s hierarchical, in
order
to
support
large
networks.
A large network is partitioned by the network manager into
"areas".
Each node resides
in exactly one area.
Routing
within
an
area
1s
referred
to as "level 1 routing".
Routing between areas 1is
referred to as "level 2 routing".
Level 2 routers keep track
of
the

paths

destination

areas.

Level

routers keep track only of

the

routing within their own area, and keep track of the nearest
level
2
router within their area.
When a level 1 router receives
a packet for
forwarding to a foreign area, 1t sends the packet to the nearest level
2
router.
Then
the
packet
travels
via
1level
2
routing to the
destination area, where it again travels via level 1
routing
to
the
~destination node.
Phase

IV DECnet

upwards

compatible with Phase

Thus there are the following types of nodes
1.

III

DECnet.

in Phase IV:

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

Routing Layer.

Introduction
2.

|
level

from
-

routers

other

nodes,

These

nodes deliver

and route packets

through to other destination nodes.

nodes
within
their
own
area,
router when the destination node

and

Page
7

receilve packets

from other

source nodes

They route

directly

and route towards a level
is in a different area.

to
2

IV level
2 routers -- These nodes act as IV level 1
routers
in
addition to acting as a node in the subnet consisting of
level 2 routers.
A node in the level 2 subnet routes towards
‘a destination area.

III routers -— These nodes deliver
and receive
packets
from
other
nodes
within their
own area, and route packets from
other source nodes through
to other destination nodes
1in
their own area.
These nodes do not include an Initialization
~Sublayer for
the
Ethernet,
and
thus
cannot
support
the
Ethernet.

III endnodes -- These nodes deliver packets

and receive
packets
from
packets
through.
These

Initialization

support

the

Sublayer

for

the

do not route
include
an

Ethernet, and thus cannot

and/or that consist
of more
than
nodes can be interconnected.

In Phase IV a node's.address:is a 16 bit number, the top

which define the
within an area.

area,

and

Ethernet.

Networks that include endnodes,
area, are restricted in how the

to other nodes

other
nodes, but
nodes
do
not

the

bottom 10
|
f

bits

which
,

A glossary at the end of this

document

defines

many

terms.

one
-

6 bits of

give an
o

address
|
|

Routing

Layer

This
document
is
intended
for readers
familiar
with
computer
communications
and with DECnet.
The primary audience
is those who are
implementing DECnet systems.
However, 1t may also be of
1interest
to

those
other

who

want

to know the details of

current DNA

functional

DNA Data Access Protocol
5.6.0,

DNA

Order

No.

Digital ‘Data

Functional

(DAP)

Functional

~ Order No. --AA-Y298A-TK

- 1.0.0,

DNA

Node

Order

Maintenance

3.0.0,

Order

No.

Product

Message |

Version

‘

4.1.0,

;

Protocol

Order No.

Version
|

Specification,

(DDCMP)

AA-K175A-TK

Version
-

1.0.0,

Architecture ~Spe¢ification,

Version

Functional

Version

AA-X440A-TK

Operations

No.

Specification,
|

Communications

Specification,

The

are:

AA-K177A-TK

DNA Ethernet Data Link Functional

.~ DNA Ethernet

the Rout ing Layer de51gn.

spec1f1catlons

AA-X436A-TK

SpeCification,

Introduction

)

DNA Network Management Functional
Order No.

Order

No.

Functional

AA-X439A-TK

Specification,

AA—K182A—TK

Version

DNA Session Control Functional Specification,
NO.

Version 4.0.0,

AA-X437A-TK

DNA Network Services Protocol
4.0.0,

Specification,

Page 8

Version 1.0.0,

Order

The Ethernet - A Local Area Network - Data L1nk Layer and Phy51cal
Layer
Specifications,
Version 2.0,
(Digital,
1Intel,
and
Xerox), Order No.

AA-K759B- TK

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

2.0

FUNCTIONAL DESCRIPTION~

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

1.
.

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

non-broadcast

links,

DDCMP mu1t1p01nt

broadcast

‘The

Routing

topological
layers.

links,

which

and X 25,

whlch

include DDCMP p01nt to- p01nt
and

1nclude‘the Ethernet.

Control Sublayer masks
characteristics

consists of

Routing

Congestion control

Packet

lifetime

the

network

physical

following components:

from

and

higher

control

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

Initialization

Functional Description

Page 9

Physical circuit monitor

The Routing Initialization Sublayer controls
Layer

and

Data

Link

Layer

the

dependent.

Data

Link

The Routing Layer components provide the following functions.
Routing.

The

routing

sequence

connected

node.

function determines
nodes

When the Routing Layer

refers

data

base

that

between

packet

paths.

source

node

receives a packet,

the

A path is

and

the

destination

routing component

perlodlcally updated

by Routing Layer
modules in adjacent nodes.
The routing component uses information
in
this data base to determine if a path to a destination exists, and, if
so, what the next hop in the path
1is.
The routing
component
then
forwards
the packet to its destination.
If more than one path exists
to a destination, the routing component ascertains
the best path.

The combined knowledge of all the Routing Layer
modules
of
all
the
nodes
1n
a network 1s used to ascertain the existence of a path, and
route the packet to its
destination.
The
routing
component
at
a
‘routing node has the following specific functions:
R

It extracts and interprets the route header in a packet.

It performs packet forwarding based on the destination.

It manages the characteristics
of the path.

link

fails

a path,

o It interfaces with the
|

receive

the

subsequent

Initialization

circuit
a

circuit

node

Sublayer

that has

falled

node.

network

node

Packet lifetime control.
packet

Initialization.

functions:

can visit,

(that

s,
at
I

each

node

that

each

permits

Packet lifetime control bounds the number of
|

The'Initialization-component supplies

1dent1f1es

Layer.

Congestion control manages the buffers

packet
switching
route-through).

recovery

route,

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

Congestion control,

an alternate

Routing

reports concerning

length in the

nodes

finds

the adjacent

node

and

the

adjacent

the

following
|

node s Routing

Functional Description

Page 10

It performs node verification, 1f required.

‘Physical circuit monitor. This component monitors errors detected

2.1

the Data Link Layer.

‘Design Scope

The Routing
1.

Layer

supports
the following design

requirements:

Deliverability.
It accepts and delivers packets addressed
reachable destinations
and
rejects
packets addressed
unreachable destinations.
|

to
to

Adaptability.
It adapts to topological changes, but
not
to
traffic
changes.
(Topological
<changes
are changes in the
configuration of active circuits
and nodes
1in
a network.
Traffic
changes
are
<changes
1n
the load on circuits 1in a
network.)
o
|
Promptness.
The period of adaptation to topological
in the network
1s
a
reasonable
function of the

changes
network

diameter (that
network nodes)

between

Efficiency.
efficient.
overhead.

1is,
the
maximum
and circuit speeds.

logical

distance

The Routing Layer is both processing and
It does

not

create

excessive

Robustness.
The Routing Layer recovers
such
as
1lost or temporarily 1incorrect

tolerates 1mpreC1se parameter settings.

routing

membry

traffic

from transient errors
routing messages.
It

Stablllty
The Routing Layer stabilizes
in
finite
time
"good - routes," provided no continuous topologlcal changes
continuous data base corruptions occur.

Operator control,.

operator

«can

control

many

functions
via
parameter
changes,
and
1inspect
counters,
and routes.
Routing, however, will not
operator input for correct behavior.

Simplicity. The Routing"LaYer 18

permit performance

tuning

sufficiehtly

and failure isolation.

to
or

routing

parameters,
depend
on

simple

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

Functional Description

10.

12,

Heterogeneity.
network
node
In particular,
multiaccess.

The Routing Layer operates over a mixture
of
types, communication circuits, and topologies.

Support

support

routing

algorithm
network.

15,

17.

point-to-point,

subsets.
The
Routing
Layer
subset of the routing functions.

The

Routing

leaving

Layer

earlier

algorithm without

Deadlock

Prevention.

prevents

deadlock,

The
the

nodes

‘

accommodates
as

shutting
\

congestion'

and

increased

a subset.

down

control

from

entire

component

condition

which

the Routlng

control

does

not

depend on

packet

lifetime

Layer

fails to deliver data.

Independence.
for effectlve

Congestlon

Large

networks.

are

not

The

With hierarchical
of

within

Traffic adaptation.
traffic

several

the

routing,

the

service

Phase

‘Source-destination
determine

routes

Routing

Layer

<classes of

routing.

The

as well

Layer:

not

»Theerouting~-Layer

different

source

user

IV Routing

The Routing'\Layer ‘does

classes.

distinguish
among
determination.

the

thousand nodes.

scope

control

risk of
\
|

flow automatically.

Traffic

routing

operation.

,Dupllcate message reduction.

following

allows

The Routing Layer allows orderly transition

supports networks

The

Layer

routing
|

multipoint,

functions

algorithm
significantly
reduces
receiving duplicate messages.

18.

Routing

prevents
1ncompat1ble‘
in the network.

supports

functions,

Evoiution.

14.

16.

The

of compatibility.

Extensibility.

13.

Page

Verification

Initialization
Sublayer
algorithms from coexisting

11.

react

does

traffic

1in

Routing' Layer does

as destination.

not

route

not

Gross operator failure.
The Routing Layer does
not
attempt
to
protect
the
network from
operator
actions,
such
as
removing a. circuit
or .a
node, that
may
disconnect
the
|
network.

Guaranteed delivery.

delivery of

all

ThedRouting Layer

offered packets.

does

not

guarantee

Functional Description
2.2

- Page 12

Relationship To DIGITAL Network Architecture

The DIGITAL Network Architecture (DNA) is
a model
that
defines
the
functional requirements of all DECnet implementations.
The model 1is a
layered one. The Routing Layer lies between
the
End Commun1cat1ons
Layer
and the Data Link Layer, as shown in Flgure 1.
o

m——————

= Pt

Network

{

!
!
!
s———=>
{

¢
|

e e e e

e e e

Management

e e e e e

= = — i — " ——— — —— — —

Modules

e,
—— e ——— '

——_——
=

g '

:-——->
!

———

!
!
!

Network Application Modules

!
\'
T

!
\'
e
e
e
Session Control Modules

—_—_———— e

— e

e
|

—— ——

——

T T T TT T T T
T
T
Rout1ng Layer Modules

T LJ
!

—————-——---—---—-——-——---—.——' :

!
!
. !
.

!
!
!
!

{

!
!

{

\%
T
|

————— e ———————
— — '

——— ——— o ——— ——

1
{

!
\'

!
\
e.
! End Communications Modules !

!
t——————— >

B e
b e .

f———————————- >
b

!
!

Data Link Modules

e e

vt o

n o

= =

o —t

!
\Y

. !

it >

« - - - - --"""""-"=-"-"""=""="=—-"—"—"""="-"=-"="-"7"—""—"== |

Phy51cal Llnk Modules

Figure

Routing Layer Relation to DNA

—

!
J

Functional

A brief

Description

description

User Layer.
services

each DNA layer

The highest

Network Management

Layer.

Page

follows:

layer

and programs.

‘

the User Layer supports

Modules
in

the

Network

user

Management

Layer
provide wuser
control over and access
to
network
parameters and counters.
These modules also furnish
wup-line
dumping,
down-line
loading,
and
testing
functions.
This
layer is the only layer that has direct access to each
lower
layer

for control

Network

Application

= Layer.

Modules

the

Application
Layer support network functions,
file access and file transfer, used by the two

Session Control'Layer.

- system-dependent
allows

End

Communications

Routing
between

logical

Layer.

link

between

The End

system-independent
»

communication,

Communications

aspects
|

Layer.
Modules
in the Routing
source and destination nodes.

Data Link Layer.
The Data Link Layer
concerning data integrity and physical

which

network nodes.

Layer

logical

route

Layer

1link

messages

defines
the
protocol
channel management.

Physical Link Layer.
The Physical Link Layer
encompasses
a
part of the device driver for each communications device plus
the communications hardware 1itself.
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.

Network
Management provides a control interface to all
below 1t.
User and Network Appllcatlon Layer
modules
directly with Session Control

2.3

Network

such as remote
higher layers.

The Session Control Layer defines the

aspects of

controlled data movement

defines
the
communication.

purposes.

Routing

addition,

the DNA layers
can
1interface
|

Layer Environment Requirements

The Routing Layer requires guarantees from the operating
End Communications Layer,

and the Data Link Layer.

The required operating system guarantees are:

system,

the

Functional Description

Page 14

Priority scheduling such that

minimum process1ng
2.

End

Routing

Layer'

receives

A quota of buffers to the Routlng Layer suff1c1ent to perform
routing

and packet

Access

to
a

lifetime

timer

expiration

The

the

guarantees

control

functions

notification
of

Communications Layer must guarantee the

specific

return

timer

buffer

within
a short, bounded amount of time.
Otherwise,
the Routing
may discard packets received for ECL if ECL exceeds a quota.

Layer

The

are:

required Data

Link

Layer

quarantees

Provision that both source
start-up

before message

-Detectlon of
Provision
complete

and

destination

exchange

can

links

nodes

complete

occur

remote start- up

that

Masking of

for point-to-point

no old messages

transient

be received

errors in order

after

start-up

to prevent packet

data

corruption

‘Provision for not duplicating or corrupting packets

Packet sequentiality ensuring that,

The
)

all

Reporting

failures

and degraded c1rcu1t

Link

Layer

for

required Data
N

sent

packets

guarantees

have

packet

been

has

received

Dbeen

cond1t1ons

Ethernets

are:

Provision for not corrupting packets
Packet sequentiality ensuring that,
received,
received

2.4

prev1ously

if a

received,

Routing

Layer

previously

sent

packet

‘packet

will

'has

been

subsequently

Characteristics

The Routlng Layer possesses the follow1ng characteristics:
Ne)

Variable delay ' There is a variable delay time.

defined as the time between
source node
and
delivery
destination node.
o

Delay

receipt of a packet from ECL at
of
that
packet
to
ECL at
|
S
|
|

a
a

Functional Description
‘0

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

source node

2.5

Page
15

Packet

1ntegrity.'

The

Routing
|

a packet.
misdeliver

Layer
,

will

not

modify

Routing'Layer Control Functional Organization

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

2.5.1
The

Routing

processes

and data

bases

e Decisioanroeess )

Update Process

Forwarding Process

Receive ProceSs

Routing data base

Forwarding data base

2.5.1.1

.Decision

destination

Process

are:

- This

process

selects

routes

each

the network.
It consists of a connectivity algorithm

that maintains path lengths and a traffic assignment
algorithm
that
maintains
path costs.
Path length is the number of hops along a path
between two nodes.
Circuit cost 1s
a nonzero, pOsitive‘integer
value
associated
with wusing
a
circuit,
and path cost 1s the sum of the
circuit costs along a path between two nodes.
|
.

Functional Description

Page 16

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

The system manager must set several of the parameters in
the
Routing
data base
that
the Decision Process
uses.
These include maximum
address, maximum number of areas (in level
2
nodes),
maximum
cost,
maximum hops, maximum circuits, circuit costs, maximum total broadcast
end-node adjacencies, maximum total broadcast router adjacencies,
and
maximum
broadcast router adjacencies
for each broadcast circuit.
The
values of the cost parameters are arbitrary. Appendix F
suggests
an
algorithm
for
determining
<circuit
costs.
The values of the other
parameters depend on the specific topology of the network.
'If
these
values
are
not
set correctly, the decision algorithms will not work
correctly.

The figure below shows a sample network, consisting of a single
areas,
and depicts
some
of
the
Routing
terms.
The
glossary contains
definitions of these and other Routing Layer terms.

Functional Description

Page

|-===——- |

hop

|
\

-—-

—.

D |-—-—==—=—=mm
-|

|--——==———————- |

= node
= circuit

|--]

it ettt

= hop

possible paths.

—.
_.
lal-|B|l

-0
|BI-|Ccl

.—. 0—
|Cl-|DI

l
|

Path Cost

—. .—
|al-|Bl

—.
|BI-|D|

|
|

— —

There are three

Path

x |

Node A wants to send a packet to node D.

st et

s, @

[

= circuit cost

7 is
node

Figure

the lowest path cost;
D via this path.

Routing Terms

node A

therefore

routes

the packet

Page 18

Functional Description

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

are met.

Level 1 Routing Messages

are

sent

adjacent

routing

Level 2 Routing Messages are

sent

adjacent

level

n all
Level 1 Routing Messages contain informatioon

2.5.1.3

nodes within the node's home area

routing

within

nodes

the

home

nodes

area

Level 2 Routing Messages contain

information

areas

about

all

Routing Message transmission is event-driven with periodic

The routing update algorithm maintains an upper

backup

routing

limit

traffic overhead

Forwarding Process- This process supplies ‘and

manages’ the

buffers necessary
to support packet route-through to all destinations.
It performs a table lookup to determine the output

adjacency

use

for forwarding to a given destination, reformats packets between short
when
fields
area
the
strips off
necessary,
format if
and long
when
fields
area
the
1in
fills
node,
III
a Phase
to
forwarding
receiving from a Phase III node,

2.5.1.4

and marks

Receive Process - The Receive

intra-Ethernet packets.

Process

inspeCts

a packet's

route header and dispatches the packet
to an appropriate Routing Layer

Control component or to the End Communications Layer (ECL).

Functional Description

~ Page 19

2.5.2
Congestion Control - The Congestion Control
component
manages
buffers by 1limiting the maximum number of packets
on the transmit

queue for a

«circuit.

packets
. received

Congestion

directly

<Control

from

ECL

regulates

Congestion Control
also checks the packet size
sent.

2.5.3
Packet Lifetime Control
requires three processes:
1.

Loop

Detector

Node

Listener

Node

Talker

2.5.3.1

Loop

Detector - This

ratio

packets.

for each packet

The packet

process

the

route-through

lifetime

prevents

control

excessive

looping.
It
counts
the
number
of
nodes a packet
removes a packet when 1t exceeds the visit 11m1t

component

packet

has v151ted
.
|

and

2.5.3.2
Node Listener
- This process determines that a minimum amount
of
activity
has occurred between this node and an adjacent node.
It
also determines if the identity of
the
adjacent
node
has
changed.
Violations
of
the
minimum
act1v1ty audit result in the declaration
that the adjacency between the nodes 1is down.

On non-broadcast circuilts, Hello Messages need to be sent only in
the
absence
of other traffic, to ensure that a minimum amount of activity
occurs. On broadcast circuits, Hello Messages need
to be
sent
periodically regardless of other forms of traffic.
|
:

Functional Description

Page 20

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

3.0

v‘

INTERFACES

This section descrlbes the three external Routlng Layer 1interfaces:

l.» Network Management Layer interface

Data Link Layer interface

End Communications Layer

In addition,
interface,

interface

this sectlon describes the s1ng1e 1nternal Routlng

Layer

Initialization Sublayer,

The interfaces take the format of calls to subroutines,as follows:
" FUNCTION (input

;

output)

Each call represents a spec1f1c functlon.

An ”implementation

requ1red to code the 1nterface as calls to subroutlnes._

1S not

The follow1ng symbols are used throughout the document:_,,‘
not

less than or equal to

>=
>>

equal

|
.

SQRT(x)

greater than or equal to
much greater

than

the square root of

CEILING(x) the least 1integer greater-than or equal_to X

3.1

Network Management Layer

Interface

This interface allows Network Management to control

and

observe

the

Routing Layer
1interactively.
Network Management can exert indirect
following
control over the Routing Layer via parameter changes. The
Network Management
functions
form a set of primitive functions that

Interfaces

- Page 21

can be used to construct more complex

READ SELF PARAMETERS
This

(;parameters)

function

Parameters

functions.

gives

the

|
wvalues

o0of

the

requiring problem correction and

operating,

Net-Management-State —-- ON or OFF.
"ON"

from

"OFF"

Setting this

forces Routing

which

NN --

highest

Tid,

(in level

parameter

initialize
|

ID, top 6 bits of which is

terminated,

initialization

data bases.

parameters.
|

Routing-State -- Routing Layer

node's

are:

node within

HOMEAREA,

bottom

area

all

1its

bits

1in

the

node number within the area

routers only),

highest area

number

network

NC --

number of

NBRA --

NBEA -- number

Maxh -- Maximum'hops possible in

Maxc -- Maximum cost possible in

AMaxh --

(in level 2

routers only),

AMaxc --

(in level

routers only),

Maxv

T1 -- Background timer

BCT1l -- Background timer

Routing TYpe -- Phase IV

number

circuits supported by this node

Broadcast

Router

Adjacencies

(BRAs)

of Broadcast

Endnode

Adjacencies

(BEAs)

supported by this

node

supported
by this node

destination within

a path

area

reachable

a reachable

-- Maximum visits

circuits

allowable

)

for

circuits

Phase

IV nonrouting

path to

reachable

path

reachable

maximum

hops

possible

maximum

cost

possible

area

‘

for a packet

routing updates on non-broadcast

for routing updates

area

router,

Phase

broadcast

router,

Interfaces

)

Routing Version

BS -- Buffer size -- Six greater than 'the

the

\>
B

size

used by ECL.

)

SS must

equal
sizes

and

buffer

less

than or equal

for

less
are

than
being

forwarding

Subaddresses -- (in nodes with X.25 Data Link Mappihg only)

-—on

the range of local
an X.25 circuit for

function

sets

the

supported

PARAMETERS

DTE subaddresses
an incoming call

returned

success

unknown parameter

illega

are

status

that

status)

parameter

call.

The

READ SELF COUNTER

those

are

PARAMETER

enumerated

above

acceptable

VALUE.
|

the

The
READ

is:

value

(;

counters)

This
function
gives the
wvalues
maintained by the
Routing Layer.
~ counters in detail.
1

Counters are:

ECO,

maximum

to BS.
It may be
in
the
network

NB -- maximum number of buffers

parameters

SELF

version,

SS -- Segment size'—— Six greater than the maximum segment

SET SELF PARAMETER (PARAMETER, VALUE:
This

routing

size for use by Routing, excluding Routing Layer Header and
excluding Data Link Layer header.
(Note
-the
added
6
bytes are for historical compatibility with Phase III, when
the Buffer size parameter included
Routing
Layer
header,
which was 6 bytes at the time.)

BS.
It will usually be
BS
while
the buffer
increased or decreased.

current

Page 22

user ECO

nhode unreachable packet

aged packet

loss

. node out-of-range packet loss

of
the
node's
counters,
Appendix E describes these
|
|

Interfaces

oversized packet

packet

partial routing update loss

verification

format

error

reject

counters)

This function returns the same values as
It zeroes all counters upon-completion

READ CIRCUIT PARAMETERS

Page
23

loss

READ AND CLEAR.SELF COUNTERS (;
|

(CIRCUIT;

status,

READ
|

SELF

COUNTERS.

parameters)

This function gives the values
o0of
the
CIRCUIT's
parameters.
- These parameters are described
more fully
in Section 4.2,
The

returned

status

Success

unknown circuit

one

of:

Parameters aré:
. Type (Ethernet, X.25; DDCMP)
.

Net-Management-State (ON or OFF)

State (as determined by Initialiiation>Sublayer)

Cost

Hello Timer

Recall Timer

,' Originating Packet Limiter (OPL)

. vape Specific Information
o

For Ethernet,

the type specific

information

is:

NR -- Number
of BRAs allowed on this Ethernet

Priority -Router

the

router's priority to be

Designated

Interfaces

Page

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

For

X.25,

the

type

Port

State

Blocking -this node

speC1f1c
supplled

indicates

1nformat10n
by

the

X.25

blocking
:

is:
Data

can

Negotiated Blocking -- indicates 1f
requested

done

also

maximum
number
of
the
Data Link Start
-

call
state

Recall Count -- the number of call
have
been
made
circuit.
This 1is
circuit on.

Layer

neighbor

blocking

Maximum Recalls
-- the
trials
permitted
from
before halting

Llnk

to try
reset by

to
the
-

attempts

that

1initialize a virtual
operator turning the
|

VC Type —-- type of virtual circuit:
PVC

The

circuit

outgoing

switched virtual

circuit

For

(CIRCUIT,
sets

VALUE

returned

circuit)

SW1tched v1rtual

name.

function

v1rtual

incoming

address.

SET CIRCUIT PARAMETER
This

(permanent

the

status

SVC,

PVC,

PARAMETER,

parameter

network

PVC

name

name.

VALUE:

PARAMETER

Success

unknown circuit
~unknown

parameter

illegal

value

DTE

status)
in

circuit
|

1is:

and

CIRCUIT
|

Interfaces

- Page 25

READ CIRCUIT COUNTERS (CIRCUIT;
status, counters)
|
This function gives the values of the
counters
maintained
by
the
Routing Layer
for
the
specified circuit.
Counters are
described more
The

fully

returned status

success

unknown circuit

Counters

in Appendix E.

1s one of:

are:

Transit ("Route-Through") Packets Received

Transit

Terminating Packets Received (packets received

‘Originating Packets Sent (packets from this node

Transit Congestion Loss

Terminating Congestion Loss

Circuit

Initialization Failure

Packets Sent

nodes addressed to this node)
to other nodes)

In addition,

from

other

addressed

Down

for X.25 circuits,

there

1is

the

type

specific

counter:

Corruption Loss -- a count of the data errors detected
this

for

circuit

READ AND CLEAR CIRCUIT COUNTERS (CIRCUIT;

status,

counters)

This function returns the same values as READ CIRCUIT COUNTERS.
It zeroes the counters upon completion,

READ NODE PARAMETERS (NODE;

parameters)

This function gives the
Routing

values

for the speC1f1ed node.

parameters
~

maintained

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

Interfaces
2

router"

are

Parameters

Page 26

given.

are:

Reachability Flag

Output Circuit

Hops of minimum cost path to NODE

Cost of minimum cost path to NODE

[and NextHop,

READ AREA PARAMETERS (AREA;

for Ethernets only]

to NODE

parameters)

This function gives the values of the parameters maintained
by
Routing
for
the specified area. This function is implemented
in level 2 routers only.
Parameters are:
*

Reachability Flag

Output Circuit [and NextHop,

Hops of minimum cost path to AREA

Cost of minimum cost path to AREA

READ ADJACENCY PARAMETERS
This

function

"Routing

for

<circuit, node
~adjacency # in

(ADJACENCY;

gives

the

specified

ID>
pair.
the Routing

Parameters are:
.

In Use

Node

Node Type,

values

Flag

one
1

of:

Level

router

Level 2 router

Phase

endnode

Phase

III

router

for Ethernets only]

parameters)
of

to AREA

the parameters maintained

adjacency.

The
argument
Data Base.

adjacency

"adjacency"

1is

Interfaces

Page 27

‘Phase IITI endnode

Clrcuit

Listen Timer

neighbor's blocksize

READ EVENT

Return:

event)

the oldest event
queue

in the Routing Layer's

internal
|

The Routing Layer maintains an internal event queue into
it
places
events. = Events are described in Appendix E.
function

reads

the oldest

event

in the queue.

which
This

CLEAR EVENTS
Returns:

none

This function
internal

event

3.2 Data Link Layer

clears

queue.

all

events

from

the

Routing

Layer's

Interface
|

This interface, between the Routing
Layer's. Initialization
Sublayer
and the
Data
Link Layer, consists of commands to and responses from
the Data Link Layer.
The interface supports
the
exchange of
data,
control,
and error
1information.
Data 1s information to be sent or
received by the Data Link Layer
protocol.
Its
description
wusually
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
circult
conditions.
The functions of the interface, described as
<calls,
are
as

follows:

Interfaces

)

TRANSMIT (circuit, buffer,

-« Page 28

[NextHop],
[more data to follow])

Returns:' none
This function gives a

message

the

Data

Link

Layer

for

transmission.

broadcast

The

parameter

"More data

follow"

non-broadcast

circuits.

circuit,

supplied.

circuit.

the

parameter

"NextHop"

flag

1is

"NextHop"

not

specified

only

must

supplied

Dbe

X.25

'CHECK TRANSMIT BUFFER (buffer)
Returns:

This

buffer

still queued

buffer

returned to the Routing Layer

function returns information about

the

transmit buffer.

INITIALIZE CIRCUIT (circuit)
Returns:

This

none

function causes the Data Link protocol

circuit.

1initialize

the

In the case of the Ethernet, Data Link padding must be enabled.
Also,
Routing
must
tell
the
Data
Link Layer to enable the

protocol type PROT-TYPE, and the multicast ID
ALL-ROUTERS (if
the
local
node is a router), or the multicast
ID ALL-ENDNODES
(if the local node is an endnode).
In the case of X.25,

virtual

circuit

1is

this tells the Data Link Layer that

1in

the

UNSYNC

state,

send

1f the

'"reset

confirmation”, and if the wvirtual circuit
1is
1in the
RUNNING
state, send a "reset" packet.
If the virtual circuit
1s 1in the
cleared state, a call must be initiated.

STOP circuit

(circuit)

Returns:

none

ThlS function halts the Data Link operatlon

circuit.

the

specified

Interfaces

- - Page 29

For X.25 circuits,

STATUS

Switched
Permanent

Virtual
Virtual

(circuit;

status)

Returns:

this

means

Circuit,
Circuit.

send

and

send

"clear"
a

packet

"reset"

packet

a
a

off

running
initializing
the Data Link modules provide additional states
maintenance state), they are treated as the OFF

READ ERROR COUNTERS
Returns:

SUPPLY

(circuit;

error

a
\

error counters)

counter

values (value,status)

This function

returns

counters,
exceeded.

notification

and

<circuit.

(for example,
state.

the

wvalues
1f

error

the

Data

Link

thresholds
|

‘error

have

been
|

RECEIVE BUFFER (buffer; status)
Returns:

buffer

accepted

‘buffer rejected

This function provides an empty buffer to the Data Link modules
for

receipt

CHECK RECEIVE BUFFER
follow], status)
Returns:

the

sequential message.

(buffer;

no packet

packet
This function
buffer.

circuit,

[PrevHopl],

[more

data

received

received,

returns

the

buffer returned
above

information

about
~
|

the
|

receive
-

The PrevHop value is returned when a packet is received
broadcast
packet 1is

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

returned when

a
a

This function returns the Data Link State of the

Interfaces

‘The "more data
circuits.

3.3

End Communications

follow"

Layer

flag

1is

returned

only

Page

X.25

Interface

This interface, between the End Communications Layer and
the
Routing
Layer,
consists of commands to and responses from the Routing Layer.
The commands and responses exchange data and control information.

Data is information that the Routing Layer

sends

receives.,

The

data
description 1s
a
destination
address, source address, buffer
address and length of data.
Destination
and
source
addresses
are
two-byte
1integer
numbers
with the most significant 6 bits being the
area number, and the least significant
10
Dbits
being
the
address
within the area.
The Routing Layer uses node addresses only, not node
names, which are resolved at a higher layer.

Control information starts or stops transmission and reception of
and regulates the data flow to a reachable destination.
The

functions

TRANSMIT
buffer)

the

interface,

(destination,
'

Returns:

This

described

return

flag,
|

buffer

queued

buffer

not

function

sends

calls,

are

follows:

[circuit,[NextHop]],

queued and

returned

data

Tryhard,

to ECL

a packet.

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

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

Interfaces

“TryHard,

entries
are

if set,

1n endnodes

Returns:

the Routing Layer

for the destination.

CHECK TRANSMIT BUFFER

tells

- Page 31
to

flush

any

cache

Currently the only cache entries

attached to broadcast

circuits.

(buffer)

buffer still queued |

”)

buffer returned to ECL

f\Thfs functionchecks the,status-of a previously.queuedtfansmit
‘buffer.
It returns
folIOW1ng

the

buffer

ECL after

any

of the

of The buffer is copled into aRoutlng Layer buffer
rc

The packet 1S transmltted

Theupacket is

The packet contents are transferred to a
because
the
destination is unreachable
flag 1s set.
,

unreachable

SUPPLY RECEIVE BUFFER

Returns:

and

discarded

the return

because
flag

the

is not

destination

set.

receive buffer
and the return

(buffer)

buffer queued for receive by the Routing Layer
buffer

not queued

This function queues
a

for

receive

receive buffer

the

Routing

the Routing

Layer

Layer.

CHECK RECEIVE BUFFER (source, circuit, [PrevHopl, buffer)
Returns-

buffer remalns-queued,by the Routing Layer

‘buffer returned to
source node

address

End

Communications

(buffer

Layer

‘buffer returned to End Communications -Layer
contains
Functlonal

a
"return
to
Spec1f1cat10n)

with

contains a normal packet)

sender"

packet

(buffer
--

ECL

This functlon checks the status of a prev1ously queued receive
buffer.
It returns the buffer if the packet was received or if
the node is unreachable
and the return
flag 1is set.
The

circuit variable returns a valid circuit number (or
a value for
an internal
1link)
for
each
received
packet.
For
packets

Interfaces

received

over

broadcast

Page

circuit,

PrevHop

set

the

number of the node which forwarded the packet to this node.
READ BLOCKSTZE

(;blocksize)

Returns:

blocksize

node

This function informs ECL of the maximum blocksize the
Routing
Layer can handle, not including routing header.
ECL should not
transmit any packets larger than this size.

3.4

This value is equal to 6 less than the Segment Size
parameter

Routing

set

Layer

This interface,
Routing
Layer

(SS)

network management.

Initialization

Interface

between the Routing Layer
Initialization
Sublayer,

Control
Sublayer
and
the
supports
the routing events

defined in Section 4.7.3.

The interface consists of commands

responses

Layer

TRANSMIT

from

the

Routing

(adjacency,

Returns:

This

SELF

Initialization

and

Sublayer.

buffer)

none

function transmits

a buffer

CHECK TRANSMIT BUFFER

(buffers

Returns:

buffer

still

buffer

returned

containing

a packet.

status)
queued
to

user

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

message

1is

Interfaces

STATUS (circuit:

Returns:

Page 33

status)

off

initializing
circuit accepted by Routing

running;

Layer

Initialization

current value of circuit cost -

"This functibn.returnsAthe status of

the

«circuit. The

.
off,

initializing,
and running states correspond to Data Link Layer
states.
For Ethernets, the only valid
states
are
"off"
and
"running."
=

STATUS

(adjacency;

Returns:

status)

unused entry
in
use;
node
~circuilt
for that

~This

function

returns

ID,
node
adjacency

the status of

type,

the

and

corresponding

adjacency.

REINITIALIZE (circuit)
Returns:

none

This function turns the circuit off and initializes the circuit
in

such

circuit will

manner

that

messages

be discarded.

SUPPLY RECEIVE BUFFER (buffer;
Returns:

previously received

status)

buffer

accepted

buffer

rejected

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

CHECK RECEIVE BUFFER (buffer;
Returns:

status, adjacency)

no packet received
packet

in the

received,

buffer

returned

Routing

Layer

Interfaces

;

Page

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

SUPPLY

CIRCUIT
UP COMPLETE
Returns:

(circuit)

none

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

SUPPLY CIRCUIT

DOWN COMPLETE (circuit)

Returns:

none

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

SUPPLY

BROADCAST ADJACENCY UP COMPLETE
Returns:

(adjacency)

none

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

SUPPLY

BROADCAST

ADJACENCY

Returns:

none

DOWN COMPLETE

(adjacency)

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

Detailed Routing Specification

Page 35

4,0

DETAILED ROUTING SPECIFICATION

The

routing

function

consists

the

following

data

bases

and

processes:
O

Routing

data base

Forwarding data base
Decision
Update

Process

Forwarding
Receive

4.1

Process

Routing Parameters

The following parameters are settable via Network Management:

NN -- Maximum node number within the'area
NA -- Maximum area number (For level 2 routers only)
NC -- Number of

circuits

supported by this node

NBRA -- Number of broadcast router adjacencies

supported by

NBEA -- Number of broadcast
this node

supported
|

this

node

NR -- Number of broadcast

endnode

router

adjacencies

allowed

given
Ethernet (settable separately for each Ethernet).
The
sum of all the NR for <circuits
1n
Net-Management-State ON
cannot exceed NBRA.
|

Maxh -- Maximum hops possible iln a path to a

reachable

node

Maxc -- Maximum cost possible in a path to a

reachable

node

within the area, suggested value
path length 1in hops.

within

the

area,

twice

the worst-case
|

suggested value Maxh*Maxl.

longest

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

in a
the

Detailed Routing Specification
10.

11.

Maxv -- Maximum visits for a packet
1l

packet

< k

Page 36

looping,

before

suggested value

Routing

in a

assumes

is Maxh + k,

where

<=Maxh

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

13.

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

12.

minutes.

" BCT1 -- Background frequency timer

for

broadcast

circuits;

[
=

[1)

maximum time
period between broadcasted Routing Messages on
the Ethernet. The purpose of this timer is to
recover
from
lost packets on the Ethernet.
Suggested value is 10 seconds.

T3 -- Hello timer.

Settable separately for each circuit.

The following are implementation parameters that are not settable
|

Network Management:
1.

T2 -- Rate control frequency
before
1s

timer:

another Routing Message can be

minimum

sent.

time

via
»

period

Suggested value

1 second.

CACHETIMEOUT -- amount of
time
Ethernet
endnodes
leave
a
cache
entry
in
the On-Ethernet Cache without traffic which
confirms the entry's correctness
before erasing the
cache

entry

(See

value

'Ethernet

1 minute.

Initialization
|

Sublayer).

Suggested

The following parameters are architectural constants:
1.

Infh

31,

Infc

1023.

‘Maxl -- Maximum cost assignable to a circuit, 25.
T3MULT -- The multiple of the'neighbor's Hello

Timer

(on

BCT3MULT -- The multiple of the neighbor's Hello Timer (on

non-broadcast
circuit)
at which your Listen Timer should be
set (i.e., T4 <-- neighbor's T3*T3MULT).

T3MULT

broadcast- circuit)

at which your Listen Timer should be set

(i.e., T4 <-- neighbor's T3*BCT3MULT).

BCT3MULT = 3.

Detailed Routing Speéification
6.

Page 37

HIORD -- The 32 bit quantity to be

prefixed

the

16-bit

Therefore, 1f the node address is Al-A2, with Al

the

least

node address to form the 48 bit Ethernet physical address.

HIORD

AA-00-04-00.

significant

byte,

then

the formed 48 bit Ethernet physical

address will be AA-00-04-00-Al-A2.

ALL-ROUTERS -- the multicast ID "All Routers".
ALL-ROUTERS

= AB-00-00-03-00-00.

ALL-ENDNODES -— the multicast ID "All Endnodes”.

ALL-ENDNODES = AB-00-00-04-00-00.
PROT-TYPE -Ethernet.

the

protocol

type

wused

Routing
|

the

PROT-TYPE = 60-03.
10.

DRDELAY -- the number of seconds
before declaring
DRDELAY

Ethernet

itself Designated Router

router

waits

The following relationships exist between the above parameters:
1.

NN >= actual maximum address within area
NN

1024

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

Maxh >= actual maximum path length in an area
Maxh

<= 30

Maxc >=
Maxc

(actual maximum network path length) X (Maxl)

1022

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

>
AMaxh
AMaxh <

actual maximum path length to any area

AMaxc >= actual maximum path cost to any area
AMaxc

1022

Detailed Routing Specification

T3 <= 8191 (to ensure that it fits into a

16-bit

multiplied by BCT3MULT or T3MULT)

Routing Data Base

The Network Management

action of

setting

parameter to ON from
OFF
1initializes
prerequisite to normal node operatlon.
of

summarized

1in

Table

the
data
base.
This
1is
a
Table 1 also shows the initial

1 Routing
Data Base

Description

Table

Level

Adj
Circuits
Hop
Cost
|
Minhop

when

the Net-Management-State SELF

the data.

Symbol

word

(in Level 1 And Level 2 Routers)

The routing data base contains routing data

values

Page 38

Tl >> T2

4.2

Adjacency Data Base
|
|
Circuits Data Base
- Network connectivity matrix
Cost matrix
Network minimum connectivity

Initial value
empty
empty
%
*
Infh

vector

Mincost

Minimum traffic
.

Srm
Tid
HomeArea
*

a551gnment

Infc

vector

Send Routing Message flags
Routing Layer 1dent1f1cat10n
Home Area

0
* %
k%

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

A description of each element of the data base follows.
Adjacency Vector.
This contains information about
entry consists of Ad](l)
where:

'Adj(i)

contains

the

information:

each adjacency.

Specification

state

(unused

initialization,

entry,

type -- neighbor node type -- Types are:

4.,

Level 1 router

LeVel 2lrouter

Phase

IV endnode

Phase

IIT

router

Phase

III

endnode

No neighbor
circuits

circuilt

Circuits

circuit

Adjacency

1is

one o
|

corresponding

this

neighbor

neighbor's Hello Timer

(T3,

time of last Hellb heérd fromfieighbor

priority -priority on

undergoing‘

the

Dbroadcast
|

adjacency

vector.

Dblocksize requested by

~Note:

is an integer
an adjacency.

Page

nodelD - neighbbf ID

currently

up)

neighbor

(BRAs only), neighbor
that Ethernet

the

range

counts

all

broadcast

Phase

broadcast

III)

router's
|

1-<NC+NBRA+NBEA>

circuits

plus

representing
|
neighbors

‘non-broadcast circuits, NBRA counts
all router adjacencies
on Ethernet, and NBEA counts
all
endnode
neighbors
on
Ethernet.
,
|
|

Adjacencies 1 through NC are in one-to-one
correspondence
with
the
<circuits.
Adjacencies [NC+1] through [NC+NBRA]
are reserved for Broadcast Router Adjacencies.
(So
that
columns
1in
the
Hop
and
Cost
matrices
can correspond
exactly with the first NC+NBRA adjacencies.)
|
B

Circuits Vector.

entry consists of

where:
.

This contains information about

Circuit(1i),

each

circuit.

Detailed Routing

Detailed Routing Specification

Circuit(i)

Contains

the

Page 40

information:

type of circuit

state

(e.q.

determined by

(Ethernet,

off,

X.25,

running,

DDCMP)

initializing,

etc.)

Initialization Sublayer .

cost

s datallnk

_enveIOpe)

Note
must
SELF
the

block51ze

(up

and

1including

Routing

that on Ethernet circuits, the datalink blocksize
be greater than or equal to BS-6 (the buffer size
parameter set by network management minus 6) plus
overhead
in
the
routing
envelope 1n long data

packet

format.

On DDCMP circuits,

the

greater than or equal
routing

envelope

datalink

Dblocksize

must

to BS-6 plus the overhead

in short data packet

in the

format.

" Hello Timer (T3)
‘last

time Hello

issued on this circuit

Recall Timer -- Amount
of

time

Routing

before reinitializing the Data Link Layer

should

wait

OPL -- Originating Packet Limit
counters

type speCific information

. .For Ethernét, the tYpe specific information is:'
1.

NR -- Number of BRAs allowed on this Ethernet

Priority

Designated Router --

the

Designated Router

currently

chosen

router's

the

priority
ID

the

Dbe

router

be Designated Router on

this Ethernet

For X.25,
1.

the type specific

information

Port State -- supplled by the X. 25

1is:
Data

Link

Layer

2. Blocking
-- indicates
requested by this

node

if ‘blocking

will

Detailed‘Routing Specification

Negotiated Blocking -- indicates

also

requested blocking

Page 41

‘neighbor

Maximum Recalls -- the maximum number of
attempts
permitted
from
the Data Link
state before halting

call
start

Recall

Count -- the number
of
«call
attempts
that
have
been
made
to try to initialize a
virtual
«circuit.
This '1is
reset
by
the

~operator turning
VC

Type

circuit:

incoming SWitched virtual circuit

outgoing switched virtual circuit
For an SVC, a netWork name and a DTE

integer

For
a PVC,

PVC

name.

in the range 1-NC representing a circuit.

Network connectivity matrix (Hop).

This contains information

to
each destination over
of Hop(i,j),

length

consists

virtual

on.

PVC (permanent Virtnal circuit)

address.

path

circuit

VC name.

is an

type

the

each

circuit

BRA.

on
An

the
entry

where:
‘Hop(1i,j)

represents

the

destination,
Value

0
1

2-Maxh
Infh

path

with

length

the

from

Meaning

Routlng

Layer

the

Self
Adjacent node
Other reachable nodes
Unreachable node

1s an integer in the range 0-NN
‘Destination
0
1is
address.
"nearest level
2 router".
s an integer
a circuit, or

this

follow1ng values:

in
an

representing a destination
the
special
destination

the range 0-<NC+NBRA> representing
Ethernet router adjacency.

self,

Detailed Routing

Specification

Value

Page

Meaning

Self

1-NC
[NC+1]- [NC+NBRA]

Circuit in Circuit(j)
Broadcast Router Adjacency

in Adj(j)

Traffic assignment matrix (Cost).
This contains
information on
the
path
cost
to each destination over each adjacency. This information
determines which

adjacency to use

for

traffic

destination.

entry consists of Cost(i,j),

where:

Cost(i,j)

represents
the path cost
destination,

Value

Meaning

0
1-Maxc
Infc

Path

from this Routing

Layer

the

following values:

Self
cost

Unreachable

is an 1nteger
address.

with the

other

reachable

nodes

the range

0-NN

representlng

a destlnatlon

is an integer in the range 0-<NC+NBRA> representing
a
circuit,
matrix.

a Broadcast
,

Router Adjacency
as

in
|

self,
the Hop
|

Minimum network connectivity vector
(Minhop).
This
summarizes
the
path length information contained in the Hop table. An entry consists
of Minhop(1i),

where:
Mlnhop(l)

represents
least
node,

the path

length via

the

cost path from this Routing
with the following values:
Value

Meaning

0
1

Self
Path

2-Maxh
~Infh

is an integer
~address.

length

the

range

the

the destination

|
adjacent

Path length to other
Node unreachable
in

adjacency yielding
Layer

0-NN

node
reachable

representlng

nodes

a destination

Detailed Routing Specification

Minimum traffic assignment vector (Mincost).
cost

1information

contained

Mincost (i),

Page 43

This summarizes the path

1in the Cost table.

An entry consists of

where:

Mincost(i) Represents the smallest cost from this Routing
|

the destination,

with the

Value

Meaning

0
1-Maxc
Infc

Self
Smallest cost to
Unreachable node

~1s an 1nteger

in the

Layer

following values:

range

other

reachable

nodes

0-NN representlng a destination

address.

Send Routing Message flags (Srm).

The Srm flags extend permission

the Update Process to send a Routing Message about a given destination
on
a
given
circult.
The
Update Process
determines
the
actual
propagation rules. An entry consists
of Srm(i,j),
where:

Srm(i,j)

indicates whether or not a Routing Message
about destlnatlon 1 to circuit ]

]

1s an

1integer

1in the

range

the value

0-NN representlng

set

sent

a destlnatlon

is an integer in the range 1-NC representlng

on which to

send the message

Routing Layer Identification (Tid).
of

should

the

circuit

This contains the bottom ten bits

by Network Management

the

ID parameter of the

SELF

parameters.

Home Area (HomeArea).

This contains the top 6 bits of the

by Network Management
in

4.3

Area Routing

the ID parameter of

Data Base

Level

wvalue

the SELF parameters.

set

Routers

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

Detailed RoUting Specification

)
”

- Symbol

* All

Table 2
Area Routing Data Base

AHop
AMinhop
|
ACost
AMincost
ASrm
AttachedFlg

entries

Descrlptlon

Initial value

Area Hop Informatlon.
Area Minimum Hops
Area Cost Information
Area Minimum Cost
Area Send Routing Msg Flags
Other Areas Reachable Flag

Infh,

Page 44

*
Infh
*
Infc
0
‘False

)
|
-

in AHop are set

and all

entries

each element

the area database

in ACost

are set to Infc upon initialization, except that AHop (HomeArea,0)
and ACost(HomeArea 0) are 1n1t1allzed to 0.

A description of

follows.

Area Hop Information (AHop). This contains information on the
number
of
hops
to
each destination
area
via
each
adjacency.
An entry
consists of AHop(i,j), where:
|
-

)

-AHop(i,j) represents
the number of.hops‘tO‘destination.-area

adjacency j

is an

1nteger

in the

range

1-NA representlng a destination
|

area

via

is an integer in the range 0-<NC+NBRA> representing the
attached area (0), a circuit (1-NC), or a broadcast router

adjacency

([NC+1]-[NC+NBRA])

,> Area Minimum Hops (AMinhop). This summarizes the information in AHop.
An entry consists of AMinhop(%),

AMinhop(i)

represents the path length
in

along
the
path
destination area

~is an
|

1nteger

each

least

<cost

hops

wvia

from

the

this

adjacency

node

the

in the

range

1-NA representlng a dest1nat1on

area.

Area Cost Information (ACost).
to

where:

destination

ACost(i,j), ,where:

area

This contains information on the

via each adjacency.

ACost(i,j) represents the path cost
circult

or broadcast

router

‘

destination

adjacency

cost

An entry consists of

area

via

Detailed Routing Specification
1

integer

the

range

1NA

representlng

Page 45

a destination

area

1S an 1nteger 1n the range

attached area

(0),

a circuit

0 <NC+NBRA>
(1-NC),

adjacency ([INC+1]-[NC+NBRA])
Area Minimum Cost (AMincost).
ACost.

This

summarizes

An entry consists of AMincost(i),

where

representing

the

information

AM1ncost(1) represents the smallest cost via any adjacency
node to the destlnatlon area

the

or a broadcast router

from this

is an 1nteger in the range 1-~NA representlng a destlnatlon
area.

Area Send Routing
Message
flags
(ASrm).
The
ASrm
flags
extend
permission
to the
Update
Process to send a Level 2 Routing Message
about a given destination area on a given circuit.
The Update Process
determines
the actual propagation
rules.
An
entry consists of
ASrm(i,j), where:
|

ASrm(i,j) —-- Indicates whether or not
|

should
be sent

]

Level

about destination area

Routing Message

to circuit
j.

'is an integer 1in the range l—NA representing'an area

is an integer in the range 1-NC representlng

on which to

send

the-message

Other Areas Reachable Flag (AttachedFlg)
reachable

true.

Indicates other

4.4

Forwarding Data Base In Level 1 And Level 2 Routers

The

information

this

data

base

the

indicates

circuit
.

areas

whether

not

are

destination
is
reachable and, if reachable, what adjacency to use to
get there.
This data base consists of two vectors, as follows:

Reachability vector

destination

(Reach).

is reachable.

This

1indicates

whether

An entry consists of Reach(i),

not

the

Reach(i)

is either True (reachable)

is
an
integer
1n
the
range
O0-NN
representing
the
destination
node
address. Destination #0 is the special
destination

"nearest

level

or False

where:

(unreachable)

router".

Detailed Routing Specification

)

Output adjacencies
forward a packet

OA(1i)
-

(OA).

This

to destination
-

Value

used

when

)

is an

integer
address.

forwarding

the

following
.

a Routing Layer user at this node
An adjacency on which to
forward
e

in the range

level

0-NN representing a destination

Destination
2

Area Forwarding Data Base

The

1information

this

1is

the

special

destination

router”.

4.5

1in

where:

Meaning

node

"nearest

which

a packet

OA contains
one of

0
- Deliver to
1-<NC+NBRA+NBEA>

Page 46

An entry consists of OA(i),

represents the'adjacencY to

values'

identifies the adjacency

to a destination.

~packet

(level 2 Routers Only)

data

base

1indicates

whether

not

destination area 1is reachable,
and if reachable, what adjacency to use
to get there.
This data base consists of two vectors, as follows:

Area Reachability Vector
destination‘area

AReach(i)
i
|

(AReach).

reachable.

This indicates whether or not

An entry consists

is either True.(reachable)

1-NA

integer

the

range

False

AReach(i),

the

where:

(unreachable)

representing

a destlnatlon

area

"Area Output Adjacencies (AOA).
This
1ndentifies
the
adjacency
which to forward a packet to a destlnatlon ‘area.
An entry consists
AOA(1), where

AOA(i)

represents the adjacency to
packet

to destination

Value

a packet
|

area.

1nteger

wused

when

forwarding

Meaning

0
Home Area--Use
1-<NC+NBRA+NBEA>
An

area 1i.

on
of

the

range

level 1 Forwarding Information
adjacency on which to
forward
)
,
-

1NA

representlng

a destlnatlon

Detailed Routing'Specification
4.6

Page 47

Data Base Protection

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

The

Routing

Messages.

Layer must
|

propagate
|

Column 0 of the Cost and Hop matrices (in

values

relating

self)

routers, column 0 of
cannot be corrupted.

4.7

periodically

cannot be

the AHop
|

and

other

words,

corrupted.

ACost

Rout ing

For

matrices

the

level

similarly

Decision Process

The Decision Process selects .paths and maintains the-.fouting and
foryayding

Decision

data

bases.

The

following

events

serve

input to

the

Process:

O Operatdrcomménd to sét'Net4Management—State to.ON fromYOFF,
o Adjacency down
‘

The

Adjacency up

Circuit down

Circuit'up

Routing'Message received

Operator

command

change

Operator

command

change parameters Maxh or Maxc

Timer

cost

expiration

Decision Process produces

circuit

the

following output:

Modifications to the routing data base

)

Detailed Routing Specification

Modifications to the

4.7.1
Decidion Controller
~functions:

Page

forwarding data base

- The

controller
|

Performs

buffer management

Messages.

performs
|
|

necessary
|

the

receilve

Supports Routing Layer initialization (Section 7).

Checks

for valid Routing Message.

has:

following

valid

Rout1ing

Routing

Message

A valid

checksum

A valid Routing Layer control header

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

4.7.2

event.

Updates

the

forwarding data base

Decision Algorithms

The Decision Process contains an algorithm for computing
the
minimum
cost
path,.
It then computes the path length of that path, and sets
the reachability vector, Reach, according to whether the cost and hops
of
the path found are w1th1n the set limits.
It also sets the output
adjacency vector, OA, to the adjacency which is the next
hop
of
the
minimum cost path.for each destination.
‘

The following subroutines represent the decision algorithms.
followed by a descrlptlon of
for each event received.

the action that

They are

the decision module takes
.

Detailed Routing'Specification
Subroutine:
.

’
)

’

Rowmin(M,

minimum,

the

VECT)

This routine determines the minimum for row I

Matrix M and stores

column number

in VECT(I).

Matrix M
|
Integer I,minimum
Vector

VECT

minimum =
FOR j = 0

"big number"
to NC+NBRA DO

BEGIN

(M(I,j) < minimum ),
OR ((M(I j) = m1n1mum)

AND

(ADJ(J) nodeID > ADJ(VECT(I)). nodeID))

THEN
minimum

VECT(I)

M(I,J)
]

ENDIF
END

“wo

Subroutine:

Minimize(I,M,V,P1l,P2,VECT)

" This routine determines entries.for vector V,
containing the minimum of each row of matrix M,
and passes to Rowmin the vector VECT in which to store
»resultlng output adjacency number.
Integer

Matrix M
Vector

Parameters
Vector

Pl,

VECT

Rowmin(M, I,minimum,VECT)
IF (minimum > Pl1) THEN minimum = P2
V(I) = minimum
ENDIF

the'

' Page 49

Detailed Routing Specification

Wme

Subroutine:

Routes(FirstDest,

.Page 50

LastDest)

This routine determines the reachability and output adjacency
for each destination in the range FirstDest to LastDest
within the area,

with destination #0

INTEGER OLD HOP,

OLD COST

FOR 1 =

the nearest

level

router.

FlrstDest "~ to LastDest

OLD HOP = MINHOP (i)
OLD COST = MINCOST (i)
e
Minimize (row i, Cost, Mincost, Maxc, Infc, OA)
Col = OA(1i)
|
|
Minhop(i) = Hop(i,Col)
|
|
IF Minhop(i) > Maxh THEN Set Mlnhop(l) = Infh

snow set OA to

adjacency

rather

than column

IF Col <= NC AND C1rcu1t(Col) Type=Ethernet THEN
sto

Search for BEA with node ID i
set OA(i) to that BEA

IF (Minhop(i)

Infh OR Mincost(i)

THEN

Infc)
-

BEGIN

Reach(i) = False
Minhop(i)
= Infh
Mincost(i) = Infc
END

ELSE Reach(i)
= True
ENDIF

IF(MINHOP(i)
THEN

< > OLDHOP OR MINCOST(i)

for

each k

Set Srm(i, k)
ENDIF

ENDDO

from

-need

convert to ‘BEA

< > OLDCOST

Detailed Routing Specification
SubroUtine-ARoutes(FirstArea,
;
;

;

LastArea)

This routine determines the reachability and output
for each area in the range FirstArea to lastArea
Integer

FOR

OLD

HOP

OLD

= FirstArea

Page 51

adjacency

COST

LastArea

OLD HOP = AMinhop (i)
OLD COST = AMincost
(i)
|
Minimize (row i, ACost, AMincost,
Col = AOA(1)
|
AMinhop(i)
= AHop(i,Col)
IF AMinhop(i) > AMaxh THEN
Set AMinhop(i) = Infh
;note

in this

case Col

the

|
AMaxc,

THEN

AOA)

Adjacency,

sbe a path to a different area
IF (AMinhop(i) = Infh OR AMincost

Infc,

since

(i)
=

Infc)

BEGIN

AReach(i) = False
AMinhop(i) = Infh
AMincost(i) = Infc
END

ELSE AReach(i)
o
ENDIF

= True

IF (AMinhop(i) <> OLD_HOP OR AMincost(i) <> OLD COST
THEN

FOR

1 to

IF Adj(j).Type=level 2 router
OR Circuit(j).Type=Ethernet
THEN Set ASrm(i,j)
ENDIPF

ENDDO

sset value of AttachedFlg

and Hop(0,0)

and Cost(0,0)

AttachedFlg=False

Hop(0,0)=Infh
Cost(0,0)=Infc
FOR i1 = 1 to NA
IF AReach(i)=True AND
Hop(0,0)=0
Cost(O 0)=0

> HomeArea THEN

AttachedFlg=True
ENDIF
ENDFOR

CALL Routes(0,0)

;to calculate
rlevel

for nearest

router

BEA cannot

attached

Detailed Routing Specification
Subroutine:

TMo

Page 52

Check

This routine detects any corruptlon of
Hop, Cost, AHop and ACost matrices.

column 0

in the

BEGIN

;first

check

column

Check that Hop (Tid,0)

Hop

and Cost

(Tid,0)

= 0

IF a

level

router AND AttachedFlg = True

IF a

level

router AND AttachedFlg

Check that Hop(0,0)

and Cost

Check that Hop(0, O)

FOR

UNLESS

(0,0)

Infh and Cost

= 0

False

(0,0)

Infc

(i = Tid
OR (i = 0 AND node is level 2 router))

Check that Hop (i,0) = Infh
AND Cost (i,0) = Infc

| snow check column 0 of AHop and ACost
IF

level 2 router
I = 1 to NA
IF HomeArea =

FOR

Check that AHop

ELSE

Check that AHop(i,0)

ENDIF

)

(i,0)

= 0 and ACost
=

(i,0)
B

Infh and ACost(i,0)

=0
=

Infc

IF any check fails, then
|
Terminate the Routing Layer
ENDIF
o
R

\>
)

IF both
|

checks

are

successful

then

EXIT

ENDIF

END

4.7.3

Decision Process Events And Actions -

A. Operator command to set Net—Management—Staté to ON from OFF.
1. Tell Ethernet Data Link the physical

address

consisting

of
B1-B2-B3-B4-B5-B6,
where
Bl-B2-B3-B4
are
the four
bytes of HIORD, with Bl the most
significant
byte; and
B5-B6 1s ID, w1th B5 the least 51gn1f1cant byte. of ID.

In1t1allze Routing databases,

Set Hop(Tid,0)=0
and Cost (Tid,0)=0

IF
a
level
2
=0
ea)
(HomeAr
ACost

Call Routes

(0,NN)

router,
|

set

AHop(HomeArea)=0,
’

Detailed Routing Specification

IF a

level
2 router,

Page

call ARoutes(1l,NA)

Broadcast adjacency ] down (note that

if j

;adjacency j

is a circuit down event)

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

d.
2,

then

the

(NC+1l)

(NC+NBRA),

<= NC,

AHop matrix

event
|

a BRA
Infh.
"j"
of

Infh.

Set each entry'in column "3" of Cost matrix to Infc.

IF a level 2
ACost matrix

router, set
to Infc.

IF local node type is

adjacency j

level

each entry
|

level

and

column

node

call ARoutes(1,NA)

"j"

type

cCall Routes(0,NN)

IF NC+NBRA < j, THEN ;adjacency J 1s a BEA
NODEID <-- Adj(j).NodelD
k <-- circuit pointed to in Adj(])

'Set Hop(NODEID, k) .= Infh

Set Cost(NODEID, k) = Infc
- Call Routes(NODEID,NODEID)

3.
C.

Supply

Sublayer

Broadcast

"adjacency

adjacency ]

down

(NC+1l) <= j <= (NC+NBRA) ;j is BRA
CIRC <= Adj(j).Circuit
FOR 1 = 0 to NN, Set Srm(i,CIRC)

FOR i

IF NC+NBRA
<

Initialization
R

IF
local
node
Adj(j).Type=level

complete"

2
to NA,

THEN

a
»

level

Set ASrm(i, CIRC)
is

router,

AND

BEA

'NODEID <-- Adj(j).NodelID
k <--— Adj(j).Circuit
Set Hop(NODEID,k) = 1

Set Cost(NODEID,k) = cost of Circuit(k)
Call Routes(NODEID,NODEID)

3.~ Supply "adjacency
up complete” to Initialization Sublayer

Detailed Routing Specification

Page

j down
Circuit
l.

Call

Check.

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

Infh.

Set each entry in column "j" of Cost matrix to Infc.
IF a

level

ACost matrix

Infh.
"j" of AHop

router,

set

each

entry

1in

column

Infc.

"j"

FOR each adjacency kpointing to circuit j
Declare broadcast

local

node

type

Call ARoutes(l NA).

adjacency k down

level

router

Call Routes(O,NN).

Supply

"circuit

down

Complete" . to Initialization

Sublayer.

Circuit
j up

Case 1l:
Circuit j is a
number as determined
by

non-broadcast circuit
Initialization Sublayer

Call

IF Adj(j).Type=endnode, THEN
a.

with

k=node

Check.

Hop(k,j)=1

1IF Circuit(j).Cost

is not

0 THEN the Routlng

Layer

terminates.

c.
d.

3.
4,
5.
Case

'Cost(k,J)=C1rcuit(j).Cost
Call Routes(k,k)

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

local

node

Adj(j) .Type=level

type

level

set ASrm(i,j)

FOR

router, ~ AND
to NA

Supply "circuit up complete" to Initialization Sublayer.
2:

Circuit

Call Check

is a broadcast circuit

Detailed Routing Specification
2‘

IF Circuit(j).Cost is not>

terminates.

FOR

to NN,

set

Srm

o Page 55
THEN

the

Routing

Layer

(i,j)

IF local node type 1is level 2 router, set ASrm(i,j) FOR i
=

)

Supply "circuit up complete" to Initialization Sublayer.

Level
/1 Routing Message received on adjacency j,

- (NC+NBRA).

The

Routing Message

contains destinations

Call

Check.

Copy
onto

hop subfield of Routing Message for
row 1, column "3" of Hop matrlx.

1IF Cost of Circuit pointed to by’adjacency j is not >
THEN

the

Routing

cost to Cost
FOR each

column

(i,j)

"j"

for each

Otherwise,

add

set
0,

that

in set S.

Call Routes(i,i).

Routing Message

adjacency

contains

(level

areas

1.'

Call

Copy hop subfield of Routing Message, for each i

set

Check.

onto

Add

row

to AHop

column

(i,j)

"j"

for

each

AHop matrix.

in set

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

IF Cost of Circuit pointed
greater

than

Otherwise,
s.

Cost matrix.

Level 2 Routing Message received
The

Layer terminates.

i in set S,

routers only).

set

‘

set

Copy cost subfield of Routing Message for each i
row

for each

onto

(i,j)

Add 1

to Hop

each

in set

then

add that cost
:

the

adjacency

Routing

to Cost

Layer

(i,j)

FOR eachi in set S, Call ARoutes(i,1i).

for
-

is not

terminates.

each

in
|

set

Detailed Routing Specification
H.

Circuit

cost

Page 56

change

Call

Check.

Calculate
the difference between the new cost and the old
cost
for
circuit j.
Note that the new cost and the old
cost must both be greater than 0, otherwise
the
Routing
Layer

terminates.

Add this difference to each entry in column "j"

Cost

matrix.

IF circuit type is broadcast, add this difference to each
~entry
in
each column k of the Cost matrix, where k 1s a
broadcast router adjacency with circuit=j
Call Routes(0,NN).

IF loCal node is level
2 router, add this

each entry

in column "j"

difference

the ACost matrix.

IF local node is level 2 router and the circuit
type
1is
broadcast, add this difference to each entry of the ACost
matrix for each column k, where k 1s a
broadcast router
adjacency with circuit=j
|

IF local node

" Maxh,

Maxc,

is level 2

AMaxh,

or AMaxc

Call

Call Routes(0,NN)

IF local node type

router,

call ARoutes(1,NA).

change

Check.

Timer

expilres

Call

Check.

level 2

router,

Call ARoutes(1l,NA)

FOR

a.
|

IF Circuit(j).Type=nonbroadcast, AND
Adj(j).Type=router (level 1, level 2,
THEN

FOR i

to NN,

Set Srm(i,j)

IF local node is level 2 router AND
Adj(j) .Type=level 2, AND
Adj(j).Circuit.Type=nonbroadcast THEN

FOR i

1 to NA,

Set ASrm(i,j)

Phase
,

1III)

Detailed Routing

3.
4,

Specification

Page

Call Routes(0,NN).

| IF’local node 1s level 2, Call ARoutes(l,NA)

BCT1 Timer expires
1.

Call Check.

FOR

IF Circuit(j).Type=broadcast, THEN

FOR

0 to NN,

Set

Srm(i,j)

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

Update Process

The Update Process propagates Routing Messages
and determines
The
It consists of an algorithm and a format module.
content.
Process

accepts

the

following

input:

The

minimum hoplvector, Minhop

The

minimum cost vector, Mihcost

The

area minimum hop vector,

The

aréa.minimum cost vector, AMincost

The

Send Routing Message

The

Area

AMinhop

flags,

Send Routing Message

Srm

flags,

The Update Process produces a Routing Message
output.

their

Update

ASrm

for

an adjacent node

4.8

Detailed Routing Specification

Page 58

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

Any algorithm that sends,

as a minimum,

all

information flagged by the

Srm and ASrm flags can be used.
(An algorithm may send more data
this to simplify the algorlthm or reduce the
data
storage
for
flags.)
‘
|

When the circuit
the multicast ID
Care must
example,

be
an

destination
circuit

is of type Ethernet,
"all routers”.

the Routing Message
f
|

taken that no nodes, areas,
algorithm
that
does
not

(nodes or

areas)

before

or destination.

sent

or circuits are starved.
scan through all circuits

For
and

restarting,

might

1is

than
Srm

never

reach some

Care must also be taken that systematic ordering
of
the
transmitted
segments
does
not
cause
the
same segments to always be lost.
For
example, on an Ethernet, 1f all segments are sent, one after another,
in
rapid
succession,
the
last
segments
might
be
1lost with high
probability.
Thus,
on
Ethernets,
each
time
a
periodic
complete
Routing
Message
1s
sent,
the segments should be cycled through SO
that each segment gets a chance to be the first segment |
The T2 timer 1s intended to
be
destinations
with
Srm
or ASrm
transmitted on that circuit.

restarted
on
a
flags set during

circuit
one pass

after
through

On a point—to—point_cichit, a Routing Message may be as long

neighbor's
blocksize.
On an Ethernet circuit, a Routing Message
be as long as the minimum block51ze of all BRAs on that circuit.

4.9

Forwarding

exceeded.

the

may

Process

The Forwardlng Process supplies and manages the buffers necessary
route—-through.

all
are

Packets

are

discarded

buffer

thresholds

for
are

Detailed Routing Specification
Packet formats,

and ‘names of f1elds,

Page 59

are described in Section 10.

Data packets can be in one of three formats: .
1. vlong format_’
|
2.

short

format

3. Phase III format
Packets in long format have bit 2 of the
FLAGS
byte=l.
Packets
1n
short
format
or
Phase
III format
have bit 2 of the FLAGS byte=0.
Phase IV nodes are required to be able
to
receive
short
format
on
point-to-point
circuits, and long format on Ethernet circuits.
They
should transmit
short format on point-to- point
circults,
and
1long
format on Ethernet circuits.
They must receive and transmit Phase III
format

to Phase

III

adjacenciles,

Packets in all three formats have bit 6 ("Future version")=0.
but do not log packets received with bit6 = 1.

Discard

Discard and log (as "message format error") short packets
(in
other
words,
packets with less than a packet route header) and packets with
an invalid route header (including packets in short format received on
an

Ethernet

circuit,

1if

this

node

cannot

handle such packets,

packets received 1n long format on a p01nt to-point circuit,
node cannot handle such packets).

this

If the 1ncom1ng adjacency is a Phase III endnode or router,
1if the top
6
bits
of
Destination ID=0, fill in "HomeArea" in the top 6 bits of
Destination ID.
If the top 6
bits of Source
ID
are
0,
fill
1in
"HomeArea"

in the

Source

field.

If the source and destination are attached Ethernet endnodes,

same Ethernet,

set

the

intra-Ethernet bit,.

the

If the‘destination is in a foreign area, and the local node type is a
level

router,

AttachedFlg=False,

the

1local

node

type

then forward based on OA(0).

1s a

level

router and

If the destination is in a foreign area, and the local node type 1s

level 2

area).

router and AttachedFlg=True,

then forward based on AOA(foreign

If the adjacency the packet is to be forwarded on has node type
Phase
III
router
or
Phase
III
endnode,
<clear
the area
field
1in the
Destination ID.
If the area in Source ID is "HomeArea", clear that as

well.

1If the area

in Source

ID is not

"HomeArea",

and the Destination

is the next node, and
the
Destination's
node
type
1s
"Phase 1III
router"
or
"Phase
III endnode", do not forward the packet.
Instead
drop the packet or return
it
to
sender, as
with
an
unreachable
destination.
|
o
’

Detailed Routing Specification

)

- Page 60

If the destination
is unreachable, and "return
to sender requested" is
set,
set
"return
to
sender",
<clear
"return to sender requested",
switch the destination and source ID fields, and
forward the packet

towards
the

the

new

destination

packet.

(the previous

source).

Otherwise,

drop

If the circuit the packet is to be forwarded on is
an
Ethernet,
and
the
packet
1s
1n
short
format,
then reformat the packet to long
format.
If the "intra-Ethernet bit"
is set, clear the bit unless
the
packet
1s
to
be forwarded
onto the same circuit from which it was
received.
,
|

When

originating a

intra-Ethernet

packet

bit.

Ethernet,
|

always

set

the
|

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

4,10

ReCeive Process

The Receive Process receives packets from the
then passes

the

packet

Packet Type |

the appropr1ate

Node

Packet for Self

The
It

Detector

Listener Process

End Communications Layer

Packet for other

Loop

Layer.

DeciSion Process

Hello Message

4.11

Link

as follows:

Process

'Routlng Message

destination

Data

process,

iForwardihg Process

Process

loop detector limits the number of
1increments the node visit field in

The loop detector discards the

packet

nodes that
the packet

1if

‘this

a packet can
visit.
route header by one.

number

exceeds

the

maximum
node
visit limit,
Maxv.
Note that the parameter Maxv must
always be greater than or equal to the parameter Maxh.

Detailed Routing

Specification

Page 61

‘The algorithm the loop detector executes when it recelves a packet
the
Add

following:
1 to node visit

((node visit
If

field

> Maxv)

in packet route

and

header.

(*return to sender"

"return to sender requested” is set,
-~ set "return to sender”
|
clear "return
to sender requested”
reverse source and destination
forward the packet towards the (new)

Else

drop

the

packet

not

set))

destination.

and- record

ENDIF

.IF ((node visit > 2 * Maxv) and ("return to sender" is set))
Discard packet

and

record

ENDIF

5.0

DETAILED CONGESTION CONTROL

SPECIFICATION

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

control.

‘0
Square root limiter.
Reduces buffer occupancy time per packet
by
wusing
a
square root limiter algorithm (Appendix F).
The
square root limiter also queues packets for an output circuit,
and prevents
buffer
deadlock by discarding packets when the

buffer pool

is exhausted.

Root

Process.

Limiter

Section 5.1

specifies

the

Originating packet limiter.
VLimits
when
necessary
to
ensure
that
rejected.
An originating packet is

originating packet traffic
transit
packets
are
not
a packet from the
ECL
at

this
node. A transit packet
is a packet from another
be routed through to another destination node.

Flusher.
gone

Square

Flushes packets queued for

adjacency

node
-

that

has

between packet

size

down.

Packet size checker.
and Data Link receive

Resolves differences
blocksize.

Detailed Congestion Control Specification
5.1

Square Root

.Page 62

Limiter

The square.root,limiter

discards a

transit

packet

rejects

originating
packet
when the output circuit queue exceeds the discard
threshold, Ud.
Ud is given as follows:

Ud = CEILING

(NB/ SQRT(NC))

where:

‘NB = Number of Routing Layer buffers for all output circuits.
NC = Number of

5.2

active

output

circuits.

Originating‘Packet Limiter

The originating packet limiter first distinguishes between originating
packets and transit packets.
It then imposes a limit on the number of

buffers that originating packets can occupy on a

per

circuit

basis.

In
times
of
heavy 1load,
originating packets may be rejected while
transit
packets
continue
to be
routed.
This
1i1s
done
because
originating
packets
have
a
relatively
short wait, whereas transit
packets,
1f rejected, have a long wait -a retransmission period.

The Originating packet limiter acéepts as input:
,o. A packet received from End Communications Layer
0 A transmit complete from the
~Communications

Data Link Layer

Layer packet

for an

End

The originating packet limiter produtes the following as output:

o Packet accepted ‘
o

Packet rejeCted

o Modifications to originating packet counter
There

active

a counter,

output

initialized

from i1dling.

and an originating packet

circuit.

the number

Each

buffers

1is

limit,

OPL,

1initialized
to 0.

necessary

to prevent

for

each

Each OPL is

the

circuit

Detailed Congestion Control Specification

5.3

Page 63

Flusher

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

5.4

state
-

Packet
Size Checker

The packet size checker checks the size of
each
packet
that
1t
1is
about
to
queue
on
an output adjacency.
This 1includes packets from
both the End Communications Layer at this node
and
transit
packets.
When
the
packet
size
exceeds
the
Data
Link
receive
blocksize

(established during Routing Layer

checker
discards
broadcast circuit

6.0

ROUTING

LAYER

initialization),

the

the
packet
and records the event.
are not required to have
a packet size

INITIALIZATION

packet

Endnodes
checker.

size

on a

SUBLAYER

The In1t1a11zat10n Sublayer masks the characterlstlcs of the dlfferent
kinds
of
Data
Link
Layers from the Control Sublayer.
The only two
types
of
<circuits
the Control
Sublayer
sees
1s
broadcast
or
non-broadcast.
|
|

In Phase IV, the only type of supported
broadcast circuit
1s
Ethernet.
The
only
types of
supported non- broadcast c1rcu1ts
DDCMP point-to-point, DDCMP multipoint, and X.25.

6.1

the
are

Version Skew

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

Routing Layer Initialization Sublayer

Page 64

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

7.0

INITIALIZATION SUBLAYER:

DDCMP OR X.25

The Routing Layer initialization 1s a start-up procedure

between

two

adjacent
nodes.
The
procedure
involves
exchanging
Routing Layer
Initialization Messages and possibly
Routing
Layer
Verification
Messages.
This
exchange
1identifies
the
nodes
to
each other and
provides additional node information.
This section describes:

7.1

The Routing Layer

The Routing Layer Initialization circuit events

The

The Routing Layer Initialization state table and'diagram

Routing

Layer

requirements

Node

Initialization circuit states

Initialization

operation

the

controller

following as

and an algorithm module.

1input:

The process consists

The Node Listener accepts
|

Hello Message

Any message received
‘on a non-broadcast circuit

Timer pulse

received

The Node Listener Process produces the following as output:

message

Listener Process

The Node Listener Process detects node failures.
of

and

Modifications
to the adjacency data base

Initialization

Sublayer:

DDCMP

or X.25

Page

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

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

Hello Message
l.

Reset

Set

any message

Set
Endif

If Adj(j).Type=Phase

adjacency

by:

TEMP

Set

received on

TEMP

IV router or

neighbor's

endnode

Hello Timer
|

TEMP*T3MULT

If received message is Hello; check that TEST DATA is all

octal

252

Timer pulse
l.

Decrement

(T4

<= 0), then

Reset

Set

circuit

ENDIF

7.2

Node

Talker

state

to CR

("C1rcu1t

Process

The Node Talker propagates Hello Messages.
to

rejected ")

adjacent node when:

It sends a
|

Hello

Message
|

Page 66

Initialization Sublayer: DDCMP or X.25
o

T3 has elapsed since the last transmission of any message.

A circuit has come up.

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

7.3

Routing Layer Initialization Circuilt States

The Routing Layer Initialization circult states are:

(Symbol) State

Description

(RU) RUN

The Routing Layer can use the circuit to

(CR) CIRCUIT REJECTED

The

transmit packets between two nodes.,

avoid

degraded.

1is

circuit

excessive

packet delay the circuit will

be declared down.
The Routing
Decision
Process
has not yet processed a circuit
down event.
|
|
|

(DS) DATA LINK START

The

Layer

initialization.

successfully

(RI) ROUTING LAYER INITIALIZE The circuit has
|

Data
to

Data

wundergoing

circuit

Link

undergone

Link initialization and is waiting
receive
a
Routing
Layer

Initialization Message.

(RV) ROUTING LAYER VERIFY
|

(RC) ROUTING LAYER COMPLETE

(OF)

OFF

valid

~ Message

Routing
has

circuilt
and
verification.

Dbeen
the

Initialization

Layer

received
circuit

for

this

requires

The Routing Layer has completed a

valid

exchange of Routing Layer Initialization
and possibly Routing Layer
Verification
Messages.
|
|

The Routing
Layer
cannot
use
the
circuit.
The
Routing Decision Process

has

not

yet

processed

circuit

down

the

«cir-

event.

(HA) HALT

The Routing Layer cannot
cuit.

use

A circuit down event

1is

required.

Initialization Sublayer:

7.4

DDCMP or X.25

Page 67

Routing Layer Initialization Circuit Events

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

Description

(nri)

The

Routing

Layer

received

valid

new

Routing

Layer

The

‘Routing

Layer

received

valid

new

Routing

Layer

(nrv)

(rt)
(sc)

Initialization Message.

Verification Message.

The Routing Layer timed out.
'

(ste)

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

The Routing Layer

received a start

words,
a
transition
from
threshold error notification

state

notification

(in

the

other

any state to the stop state)
from the Data Link Layer.

In the case of X.25, a start notification is
given
by
the
Data
Link
Layer
wupon
receipt of a "Clear Indication" or
"Reset" packet, or when a data error 1s observed.

(opo)

Operator turned circuit on.

(opf)

Operator turned circuit off.

(im)

The

(rc)

The Routing

(cdc)

The Routing Layer

circuit

complete

Layer

(cuc)

Routing

Layer

received

Initialization Message

Layer

rejection

event

Control

The Routing

invalid

received

component

reject

of the

Initialization

from

the

Routing

Layer

an unexpected message.

complete

circuit monitor.

received

Decision

Process

from

Layer

circuit down

the

Routing

Sublayer.

Initialization

complete event
from
the
Layer Control Sublayer.

the

Decision

received

Process

circuit
the

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

Routing

If
the
then the
«circuit

Initialization Sublayer:

7.5

Routing Layer

DDCMP or X.25

Page

Initialization Operation And Message Requirements

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

'\\
/

)

Issue reinitialize
Recall Timer.

Issue stop to the Data Link Layer.

Send a valid Routing Layer

Send a valid Routing Layer Verification Message.

valid

Routing

Layer

characteristics:

command to

the Data Llnk Layer

and

the

start

Initialization Message.

Initialization

Message
.

has

the

following

A valid Routlng Layer control header with node

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

o
|

than or

to this node's NN

If this node 1is a leyel 2 router, then

area

level

equal

must
2

match

router or Phase

III

the

less

neighbor's» home

unless the neighbor node type

1is

A received Data Link blocksize greater than or equal
to
the
(Routing
Message size of Routing Message containing
if nelghbor 1s Phase III router Hello Message size,

max imum
NN nodes
246)

HomeArea

address

An acceptable routing version

(see section on Version Skew)

)
/A
valid Routing Layer Verification Message has
with

the

function value.

value

that

agrees

7.6 Routing Layer Initialization State Table And Diagram
e

The following table shows all the possible state transitions from
the
Routing Layer's viewpoint at a single node.
It also shows the events
that cause the
state changes
and
the
actions
the
Routing
Layer
Initialization
takes,
1if
any, upon the occurrence of an event.
The

/) numbers in the "actions" column correspond to those
actions

above.

in the

1list

Initialization Sublayer: DDCMP or X.25
Routing Layer

This table
occurrence

slash
no

(/)

Initialization State Table

shows each possible
of
each
event in

new state and action
relating
to
each state.
The actions are shown

followed by the number of

action.

The

actions

numbers

nri

CR/-

DS/-

nrv

CR/-

RU/-

CR/-

the action.

are defined

Old
RU

Page 69

A dash

(-)

the
by a

signifies

above.

State

DS/1

DS/l

OF/-

HA/-

DS/~

DS/i

RC/-

DS/1

OF/-

HA/-

DS/l

RC/-

OF/-

HA/-

CR/-

CR/- RI/3

DS/1

OF/-

HA/-

ste

CR/-

DS/1

OF/-

HA/-

opo

RU/-

CR/-

DS/ -

Ri/—

RV/-

RC/-

CR/-

DS/1

opf

OF/2

OF/-

HA/2

OF/-

HA/-

CR/-

DS/-

DS/1

DS/l

OF/-

HA/-

CR/-

DS/-

RI/-

RV/-

DS/l

OF/-

HA/-

cdc

RU/-

DS/l

DS/-

RI/-

RV/-

RC/-

HA/-

cuc

RU/-

CR/-

DS/-

RI/-

RV/~

RU/-

OF/-

HA/-

Event

There are
follows:

four possible

NOTE

new state/action

sets for

this

transition,

Action:
4&;
New
received message;

state:
RV;
verification

Verification
requested
required by this node.

1in

Action:
4;
New
received message;

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

1in

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

1in

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

1in

Initialization'SUblayer: DDCMP or X.25

Page 70

The Routing Decision Process generates
circuit
down
events
1n
the
states CR and OF.
It generates a circuit up event 1n the state RC.

Once

the

Recall

Timer

reinitialize command

The following

is 'set,

must

expire

is given to the Data Link Layer.

figure shows the Routing Layer

Dbefore
|

another

state transitions.

e>
>
RU
|
S> |
|
I
|
|

|
|
I
I

I
I
|
I

|
|

Y e

I
I

|
|
== '

|>
e> |
>

I
I
!
|

v
Vv
v
-,
—————————— .
|
|
| |
OF
| -— - > |
HA
|
|
I
|
I
I

# ——

Note:

contains

state

symbol

A
I
|
|

state

| <—=—==-=="

I
o
|
|
|
v
|
== .

|
|
|
|
|
I

representing Routing

transitions

are

not

|
|
|
|

|
v
|
]
S ————— .
|
|
I
I
|
<-———-- | -—-1
RI
I===1—
I
|

These

|
| <—-.
|
|

|
|
I
|

I
~
A
||
|
I
|
| |
I
I
|
| |
I
I
|
||
I
I
emTmm
e ——— .
| |
e
e
I
| -—————- S
———————————————————————— |

guaranteed.

Initialization

Initialization Sublayer: DDCMP or X.25
7.7
If

Closing
at

Down

all possible,

before

router

1is

reinitialize
the
Data Link Layer, causing
the circuit without unnecessary delay.
In

Routing
case

Layer

Clear
should

Page 71

an X.25

brought

its
the

down,

should

neighbor to bring
case
of
DDCMP,

should command DDCMP to put out a DDCMP Start.

SVC,

the

Routing

of
the circuit.
1In
command X.25 to do a

Layer

the case
Reset of

should

command

of an X.25 PVC,
the circuit.

8.0

ADDITIONAL INITIALIZATION SUBLAYER FOR X.25

8.1

1Incoming Call

X.25

the

Routing

down
the

In the
do

a
Layer

Control

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

8.2

Error

Control

introduced

detect

possible

corruption

data

within
the
public
data
net.
A 16 bit cyclic redundancy check word
based on the CRC-16 polynomial
1is
prefixed
to
each
Routlng
Layer
datagram.
The check character is generated on the message as a string
of bits beginning with the LSB of the message ending with the
MSB
of
the message.

(Note- A Routing Layer datagram may traverSe the X.25 net as a
of
for

X.25
data

packets
errors.

number

as described below.) Received datagrams are checked
1If an error
1is
found,
it
1is
accounted for,
by

incrementing
the
error counter in the Circuit database, the datagram
is discarded, and the event is
treated
as
an. "ste"
event
by
the
Initialization
Layer.
This will
cause
the
circult
to
Dbe
reinitialized.
-

8.3

Fragmentation,

Assembly And

Blocking

Fragmentation of RoUting Layer datagrams may be required if the Public
Data

poses

network

requires

smaller

packet

size

than

that

DECnet.

This

twofold problem.

The
-

Routing

Layer

packets before

datagram must

transmission

and

fragmented

reassembled

into

multlple

receipt.

2.
|

Page 72

Additional Initialization Sublayer for X.25

multiple packets
on the
depending

Transmitting the Routing Layer datagram in
may require additional buffer capacity

of
characteristics
increase

packet

level

lower

the

implementation.

This

in the buffer requirement is due to the 5 byte X.25
-

header.

The buffer problem above is not solved here as it 1is implementation
A particular implementation may solve this, for example,
‘dependent.
by dedicating a fixed number of fragmentation/assembly buffers per
virtual circuit or via hardware capable of supplying packet headers
from separate buffers.

The maximum packet size supported on a particular virtual circuit will
The actual packet size will be
be set wvia Network Management.
negotiated when the circuit is established and will be stored 1n the
circuit

data base.

Fragments of datagrams will be transmitted across

the data link interface sequentially.

packet

All but the last

will

specify "more data to follow" in the TRANSMIT call. Similarly,
receive packets will be checked for "more data to follow" and
assembled into Routing Layer datagrams before being forwarded to Error

Control.

In some instances, blocking of multiple Routing datagrams within a
single X.25 packet may be motivated by vendor facilities and tariffs.
when X.25 vendors support large packet sizes, improvements in cost and
(Blocking 1s also
responsiveness may be obtained by blocking.
somewhat motivated by the presence of ECL control messages.)
Blocking is enabled or disabled via the Network Management interface.
It may be desirable to disable blocking when operating at small packet
sizes. Negotiation i$ performed at Routing Layer initialization to

\\_/’J

determine whether blocking will be used on a given virtual circuit.
has been enabled by network management, the "blocking
When blocking
"TIINFO" field of the Routing Layer
the
in
bit
requested”
Initialization Message

1s set.

'is used if both sides have requested 1t.
Blocking

when blocking is in use, Routing Layer datagrams are viewed as a
serial stream of data (fragmentation procedures discussed above are
not used). A header is prefixed to the datagram (including the CRC
generated by the error control function) and it 1s placed in an X.25
packet assembly buffer. Datagrams are loaded into packet assembly

buffers until full. 1In general filling assembly buffers will require
fragmenting datagrams. The figure below shows the mapping of the
Routing Layer data stream onto the X.25 data stream.

Routing Layer datagrams

data stream
-

1
2
3
4
5
6
7
—-=-X----X
—-X-———--]==[-=—=X~==
—————— X-——==]-——=—X=====X=====]-==—————
1
2
3
4
5
X.25

X
I

Frames Routing Layer datagram
Frames X.25 packets

Additional

Initialization

The header

that

count of

Sublayer

prefixed

the number

the

of bytes

The message formats for datagrams
cases of blocking not enabled and

BC [CRC

Blocklng multlple
BC
DG
In both

bit

byte

for X.25

datagram 1s
used

frame

two
the

Page

byte

[CRC

1nto X.25

Routing

- Routing Layer datagram
cases fragmentation may occur

Layer

field

which

datagram.

are 1llustrated below
blocking enabled.

datagrams

count

for

the

|CRC

two

packets

datagram and CRC
|

any point

1in

the message.

Efficient implementation of a
blocking
facility requires
a
buffer
management
policy
sensitive
to
the blocking operation.
A specific
policy 1s not required by the
architecture
as
it
will
not
impact
correct
operation.
Under
1light load conditions, a decision must be
made as to whether to pass a partially filled packet across
the
X.25
packet
1level
1interface or to wait in anticipation of additional data
to fill the packet.
Policies may require
a
timer
to
perform
this
function.
However,
the
policy recommended here is independent of a
timer.
The policy 1s basically to
buffer
as
few
X.25
packets
as

possible

in X.25

1level

(one or

two).

The Routing Layer supplies

packets to level 3 only as the short queue permits, thereby retaining
the
data
as
long
as possible without sacrificing efficiency.
This
policy will have the property of being cost efficient
under
moderate
to heavy loading and always being responsive.
|

8.4

Closing

Down

It is costly to keep attempting to bring an X.25 circuit
not
usable.
Thus
a
retry
counter is maintained for

up if
it
1is
Routing Layer

time-outs
(rt Initialization circuit event) and X.25 Data
Link
Layer
Start Notifications (ste Initialization circuit event).
When in state
DS, 1f actions
rt
or
ste
occur
transition is made to the OF state,
bring the circuit back up.

MAXIMUM
RECALLS
in
a
row,
the
requiring operator intervention to

)

Initialization Sublayer: Ethernet
INITIALIZATION SUBLAYER:

9.0

Page 74

ETHERNET

Routers

9.1
9.1.1

Ethernet Router Hello Messages -

Routers broadcast Ethernet Router Hello Messages to the multicast 1ID
These contain the transmitting router's ID, T3, and
"all routers".
other

PRIORITY, plus a list containing information about the

routers

the transmitting router has heard from "recently enough" (described
below), and provided that the number of routers does not exceed NR.
Each entry in the list contains a router's ID, that router's PRIORITY,

and a bit indicating whether that

the

1includes

router

router in its Ethernet Router Hello Messages.

When a new router NEWROUTER is heard from, and NR

and

transmitting

NBRA

are

not

included 1in future Ethernet Router Hello
NEWROUTER 1is
exceeded,
is set aside for NEWROUTER,
cy
slot
An adjacen
Messages by this node.
on an adjacency numbered between [NC+1] and [NC+NBRA]. The state of
the
the adjacency is set to "initializing", until it 'is known that
" communication between this node and NEWROUTER 1s two-way.
its Ethernet Router Hello
When NEWROUTER reports this node's ID in
the adjacency's state is changed to "up", and an adjacency
Messages,
up event

1s generated.

A separate Listen Timer is kept for each Ethernet neighbor.

The value

of the Listen Timer 1is BCT3MULT * neighbor's T3 as reported in its
If a neighbor is not heard from in
Hello Messages in the TIMER field.
that

time,

it is purged from the database and an adjacency down event

generated.

If a Hello is received from neighbor OLDROUTER, and this node's ID 1is
the adjacency's state 1is
in OLDROUTER's Hello Message,
no longer
changed to "initializing", and an adjacency down event is generated.
and a
If a router already has heard from NR routers on an Ethernet,
with
router
the
Message,
Hello
Router
Ethernet
issues an
‘new router
1is
router
new
the
(or
database
the
from
lowest priority is purged
the
has
router
one
than
more
If
lowest).
is
if its priority
ignored,

(An
ID 1s purged.
lowest priority, the router with the lowest
48
unsigned
an
as
comparisons
numerical
in
Ethernet address is treated

bit integer, with the first byte transmitted, and the leftmost byte as
written, treated as the least significant byte.) If an old router must

be purged, an adjacency down event
occupied by the old router.

generated

for
-

After the Control Sublayer issues an "adjacency down
an

the adjacency
|

cdmplete“,

then

adjacency up event is generated for that adjacency number with the

new neighbor.

Initialization

9.1.2

Sublayer:

Ethernet

Page

Designated Router
-

The Designated Router is the highest priority router, with numerically
highest
ID
breaking
ties.
The set of all routers to be considered
includes all routers in the area
on that
«circuit
in the "up"
or
"initializing" states.
(See Section 9.1.1 for definition of numerical
comparison of Ethernet addresses.)
|
A

new

router must

DRDELAY*T2

has

not

The Designated Router
Hello

Message

9.1.3
-

declare

itself

periodically

additionally

the

Ethernet

Router

turned

BCT3

Hello Message

Router

until

1its
"all

Ethernet

Router

endnodes".

sent

immediately

when

the

circuit

on.

has

transpired
since
on this circuit by

the

last
node

this

expired

the contents of the next

Hello Message to

would
differ from the contents of
transmltted by this node, or

De51gnated

broadcasts

It 1s also sent when
at
1least
T2
has
transmission
of
a
Router Hello Message
and either:
|
1.

the

multicast

When To Transmit Router Hellos

has been

transpired.

this node

has decided

the

transmitted
Hello Message

to become Designated Router

Sending of a Hello Message should restart

and

T3.

For

maximum

performance in the case of a clock with fine granularity, these should
be restarted only after successful transmlss1on of the
Hello
Message
by the Data Link Layer.

9.1.4

Closing Down -

at all

possible,

before

empty

Ethernet

Router

Hello Message,

receiving
departing

this
message
router, without

router

bring

brought

down

down,

which

their

unnecessary delay.

w1ll

should

cause

all

adjacencies

issue

routers

the

Initialization Sublayer: Ethernet
9.1.5

Page 76

Database Of Endnodes -

An endnode

is entered

into the adjacency

database,

event

an adjacency

between [NC+NBRA+1]
and [NC+NBRA+NBEA] when a hello is received from
‘the endnode, provided there is room (not more than NBEA endnodes
have
been

heard

from).

adjacency

generated

on that

adjacency.

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

When the adjacency is cleared, the Control Sublayer is informed of
"adjacency
down"
event,
"adjacency down complete"

and
the
adjacency
can be reused after
1s received from the Control Sublayer.

an
an

9.1.6 ‘Multiple Areas On An Ethernet If there are multiple areas on an Ethernet,
control traffic from other areas.

routers

must filter
|

out
,

When a level 1 router receives
an
endnode
or
router
hello
on
an
Ethernet,
it checks that the area field i1n the ID equals "HomeArea".
If not, the packet is dropped without being logged.
Thus
a
level 1
router will not keep any adjacencies from other areas.

A level 2 router must keep
adjacencies
to
other 1level
2
routers,
besides
the
adjacencies
1in
1ts
own area.
A level 2 router drops
without logging any Ethernet Endnode Hello Messages it
receives
from
other
areas,
and
any
Ethernet
Router Hello Messages from level 1
routers (node type in IINFO field indicates level 1 router)
in
other
areas.

When a level 2 router R receives an Ethernet Router Hello Message from
a
level
2
router A in another area, it does not drop the packet.
R
does include A in its adjacency database.
R also includes
A in E-LIST

in
in

1its Ethernet Router Hello Messages.

R's

calculation of

Designated Router

However,

for

the

R does not

Ethernet.

include A

Initialization Sublayer:

Page

Endnodes broadcast Ethernet Endnode Hello Messages to the multicast

9.2

Ethernet

Endnodes

9.2.1

"all

Ethernet

routers"

Endnode Hello Messages

when

they first

come up,

with period T3.

and periodically thereafter,
|

9.2.2
Designated Router's Ethernet
Router
Hello
Message - When
an
Ethernet Router Hello Message is received by an endnode, ID is checked
to ensure that it is in the endnode's area.
If the area field
1in
1ID

does not equal "HomeArea", the packet is dropped without being logged.
Otherwise, ID is copied into the endnode's ROUTERID
variable,
T4
1is
set
to
BCT3MULT
times
the
wvalue in HELLOTIME, and an adjacency up
event 1s generated.

If ROUTERID had a value different
from ID, an adjacency down event
1s
generated,
followed
by an adjacency up event.
If T4 expires wilthout
receipt of
ROUTERID is

9.2.3

a
Designated
Router's
Ethernet
erased and an adjacency down event

On-Ethernet

Cache

Router
Hello
1s generated.

Message,

The endnode maintains a cache of destinations
with
which
1t
1s 1n
contact
and
which
are on the Ethernet.
An entry for
A is made 1f a
packet
is received with the "intra-Ethernet bit" set, from source A.
‘An

entry

for A

erased if:

the Routing Layer user gives the Routing Layer
destination A and the dlrectlve "Tryhard"”

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

A 1s the least recently used cache entry, and the room in the

9.2.4

cache

Filling

needed

for

In "next Hop"

a new entry

1if
A is

the

with

for
that
the

In Packet Headers -

On transmission of
a packet for destination A,
the Ethernet header according to the rules:
l.

a packet

cache,

send

to A

fill

in the

hop in
.

Initialization Sublayer:

10.0

else

else send to A

Ethernet

ROUTERID

filled

in,

send

Page

to ROUTERID

MESSAGES

This section describes
There

protocol.
O

are

two

Packet route
may
require
data packet

the

message

types

formats

Routing

the

Routing

Layer messages:

Layér

header -- This is used for ECL
segments,
which
forwarding.
There are two possible formats for
route

headers:

short format (identical to Phase
III format)

long format

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

Initialization Message

Verification Message

Hello

4.,

Level 1 Routing Message

Level
2 Routing Message

and Test

Message

On broadcast circuits the
messages

}types' of

are:

Ethernet

Router

Hello

Message

Ethernet

Endnode

Level

1 Routing Message

Level

Hello

Routing Message

Message

Routing Layer
;

control

Messages
10.1

The

Page 79

Message Format Notation

following notation

FIELD (LENGTH)':

is used to describe the messages:

CODING

Description of field

where:
FIELD

the name of

(LENGTH)

is the length of the field, one of:

A number meaning the number
of 8-bit bytes.

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

The letters "I-n" meaning an image field, with n being a
number
that specifies the maximum length of 8-bit bytes
in

the

image.

field.

The

image

1s preceded by
a

1l-byte

count

of
the
1length
of
the
remainder of the field.
Image
fields are variable length and may be null (count =
0).
All eight bits of each byte are information bits.

CODING

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

= Binary.

= Bit map.

=-Constant.

NULL

Each bit has independent meaning.

Interpretation

is data dependent.

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

10.2

are

transmitted
|

1low

order

least

Reserved Fields

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

dropped along with the

field to be dropped.

Messages
10.3

Page 80

Optional Padding

All Routing
Padding

Layer

can

messages

except Initialization can

be used when communicating with Phase

IV nodes,

not be used when communicating with adjacent Phase III nodes.

'If the top bit of the flrst byte is set,

the remainder

padded.

but must

of the

first

byte
1is a count of the number of pad bytes, including the first byte.
The total length of a message, including the padding, must not
exceed

the

neighbor's blocksize.

If the neighbor's blocksize is unknown (as

in the case of Ethernet endnodes)

length

Thus the

then the maximum total pad sequence

format of

the optional padding

is as

follows:

p———————— t———— +

PLENGTH

PAD

———— +————- +

PLENGTH

(1)

the total
-

Bit:

the pad sequence

5141

3121|110

———+
==t ———F———F —t
+———F———t———Ft——

Set to:
PAD

length of

ettt ———F———t———t———F———+

TOTAL-PAD-SEQUENCE-LENGTH

t———t———F———t————— +————- +———+———+

((TOTAL-PAD-SEQUENCE-LENGTH)

No Meaning

Messages
10.4

Page 81

Short Data Packet Format

The packet route header in short format is as follows:
—————— ————————Tt

FLAGS

| DSTNODE

————— o —————— +

SRCNODE

FORWARD

- ———————— t———————— e —————— +

FLAGS (1) :

the set of flags used
The

format
of this

the

field
is as

routing

follows:

nodes.

-ttt ————— +————— +———t———t———+

Bit:

———

Set to:

61514
| 3 [ 21110

et ———F————— +————— t———t———t———+

RTS

RQR

SFDP

-t ———t———— -t

Bit

Definition

0-2

SFPD

RQR

(Return to Sender Request)

1
0
4

meaning

Return

DSTNODE

(2)

the destination node

SRCNODE

(2)

the source node address

FORWARD

(1)

information useful in
the
forwarding
message.
The format of this field 1is
|

Set to:

VISIT

(6B)

format

Sender

1 => packet 1s on return trip
Reserved
Version, set to O
PF
pad field = 0 indicating
no padding follows

Bit:

short

indicates try to return
indicates discard

RTS

6
7

———t—-——+

address

the count of

of
the
as follows:

the number of

nodes visited by

this

packet

10.5

Page 82

Messages
Long Data Packet Format

- - ———— f—m——_——————— e t——————— e ———— - +

- - —————— e ————— - - ————— o

———— - +

+————- t———————— f———————— +————+

| NL2

| VISIT-CT |

S-CLASS

+————e ——————— - ———— +————+

FLAGS

(1)

the set of

The

flags used by the routing nodes.

format of

this

field

1is as

follows:

t————t———F——— == - +————— t———t———t—-——+

Bit:

[

p————t———t————— +————— +————— +———+———+———+

Set to:

I-E

LFDP

RQR |

RTS

t————t———F————— +————— +————= +———t———+—-——+

Bit

Definition

0-2

D-SUBAREA

(1)

indicates

indicates discard

S-AREA

(1)

Reserved

VISIT-CT

S-CLASS

(1)

PT (1) :

to Sender

1is on return trip

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

Source ID (first 4 bytes must be
set

to HIORD)

Next level 2 router, reserved
:

return

Reserved

B
(1)

Return

Reserved

NL2 (1) :

try

Intra-Ethernet packet
Version, set to 0
discarded if 1
PF
pad field = 0 indicating
no padding follows
|

: B

S-SUBAREA
(1) :

S-I1D (6)

RTS

1 => packet

Reserved

format

D- ID (6) : B

long

meaning

5
6

(1)

RQR (Return to Sender Request)

D-AREA

LFDP =

Visit Count

(0)

Servicte Class,

reserved

Protocol Type, reserved

Messages
10.6

Page 83

Initialization Message

o —————— Fmm——————— o ————— m————_———— F——m————— o ————— e +

e
e ——— Frm——————— tm———————— - —————— t——————————

FLAGS

(1)¢+

the

Routing

following

Layer

control

flag,

with

format:

the

t————F———t———
e
—pm
e
——— ¢

Bit:

|7
|

Set

|61l

43121110

to:

RES

el etk

(2)

(1)

Routing
and

|
~

Set

0
1-3
4-6
7

1 1ndicates Control Packet
Type = 0
Reserved
PF
pad field = 0 indicating

Layer

service

the

follows

source node's Routing

the value ID as set
SELF parameters.

information on node

requests,

to:

[

61
T

51
e

by Network

type

follows:

(2B)

BLO

BM
|

NTYPE

Layer

node

type:

Reserved

level 2
level 1
endnode

router
router

Routing

Layer Verification

Message

required

Blocking Requested
1s set.
|

(1B)
|

VERIF

the Routing

w N

‘

BLO

———p————— $-————— t—————— +

VERIF (1B)

$mm————— +-———+-———+

- O

NTYPE

+———t——— et

(2)

t———t———t———t———————
= R +-——t—-—=+

Bit:

BLKSIZE

Definition

the identification of

Bit

Layer, containing
Management in the

TIINFO

TYPE

TP
E
+———+

no padding

SRCNODE

-ttt
—— bt —— = ———+———+

the maximum Data Link Layer
this node will accept.

(includes Routing header,

this

bit

set.

this bit
|

receive block

size

excludes Data Link header)

Page

Messages

TIVER (3)

the Routing Layer version, with
format:

the

following

Byte1 -- version number

(00000010 binary))

Byte 2 -- ECO number (0 (00000000 binary))

Byte 3 -- user ECO’number'(O (00000000 binary))
TIMER

(2)

RESERVED

(I-64)

Hello Timer, 1n Seconds
A reserved

field containing

a count

Messages
10.7

Page 85

Verification Message

o —————— Fm———————— Fmm—————— +

FLAGS| SRCNODE

Fm—————— o ——————— Fm—m

FLAGS

(1)

FCNVAL

e ——— +

the Routing Layer control
following format:
o

Bit:

to:

with the

m e
—— —

|17

Set

flag,

RES

Bit

31211110

|
e

it et

TYPE

indicates Control Packet

Type = 1
Reserved
PF
pad field

no padding

0 indicating
follows

the identification of the source node's Routing
Layer, containing
Management in the

FCNVAL (I-64)

Definition

1-3
4-6
7

SRCNODE (2)

et +———t

the value ID as
SELF parameters.

the function value.

set

by Network

Page

Messages

10.8

Hello

And Test

Message

- Fmm——————— fmm

FLAGS

e ———— +

SRCNODE
| TEST DATA

+—————— tm———————— e ————————— +

FLAGS

(1)

the

Routing

following

Layer

control

flag,

with

the

format:
-ttt

Bit:

———F———t———F+———+

14113121110

-ttt ——————p———F———+———+

Set

to:

RES

TYPE

-t

Bit

SRCNODE

)

(2)

Definition

1ndicates Control
=

Packet

1-3

Type

4-6
7

Reserved
PF
pad field = 0 indicating
no padding follows

the identification of the source node's Routing

Layer, containing
Management
in the

TEST DATA (I-128)

+-———+

the value ID as set by Network
SELF parameters.

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

Each byte

is 252 octal.

Messages

Page 87

A Level
1 Routing Message contalns
one or more segments, each

ségment

10.9

Level

referring

Routing Message

to COUNT destinations

starting with STARTID.

Destination #0 1s uhderstood to mean "nearest level 2 router".
+—————— - +————- - ————— ———————— +————— ————————— +

FLAGS

SRCNODE

RES

SEGMENT

CHECKSUM

t——————— e ——————— - t————————— - +————- +————————— +

FLAGS

(1)

the Routing Layer
following format:

control

flag, with the

t————t———t———F———t———
= ———+———+

Bit:

16151413121
1]0|

t-————t———t———t———t———F———F———F—-——+

Set

to:

RES

Bit

the

RES (1)

: B

SEGMENT

1s of

indicates Control Packet
|

PF
pad field = 0 indicating
no padding follows

+—-——+

Type = 3
‘Reserved

(2)

TYPE

Definition

1-3
4-6

SRCNODE

identification of

Layer, containing
Management in the

the

source node's Routing

the value ID as set
SELF parameters.

by Network

A reserved field of 1 byte
the

FORM:

Fm—m————— e ——————— $mm———————— +

| COUNT | STARTID | RTGINFO |
fm—————— o ——————— fm———————— +

COUNT

(2)
: B

STARTID (2)
RTGINFO

the number of

: B

Bit:

top 6 bits

“the hops

in the RTGINFO segment

the first ID reported in the Routing Message,

with the

BM
——

IDs

and cost

(the

area bits)

to a destination,

set to

format:

the

e —————— $—————— +

e
——
$m—————— +

HOPS

cosT

e ———— e ————— +

CHECKSUM
ensure

(2)

Phase

Messages,

B a check on the

IV Routing Messages
well

check

routing data base,

and

not be mistaken

Phase

the

message.

for
1s

one's

check
III

Routing

complement

Messages

- Page 88

add starting with the first SEGMENT and continuing until the CHECKSUM.
To ensure that a Phase IV Routing Message will be distingquished from a
Phase
III Routing Message, the sum on the Phase
IV Routing Message 1s

initialized
to

Messages
10.10

Level

Page 89

2 Routing Message

A Level 2»Routing'Message contains one Oor more segments, each
referring

to COUNT

areas

segment

starting with STARTAREA.

—————— Fm——————— +———— Fmm—————— $—m——— +———— e —————— +

fm—————— e —————— e

FLAGS (1) :

—

fmm—————— o ———— o

————— +

the Routing Layer control flag,'with the
following

format:

Bit:

ek i

et 2

16151 413121110 |

t————t———t———F———t———t———F———F———+

Set to:

RES

TYPE

e st
T
S

Bit

Definition

1-3
4-6

RES

(1)

Packet

PF
pad field = 0 indicating
no padding follows

the identification of the source node’'s Routing

Layer, containing
Management 1n the

A reserved

SEGMENT
is of

indicates Control

Type = 4
Reserved

SRCNODE (2)

+-———+

the

field of

the value ID as set
SELF parameters.

by Network

1 byte

FORM:

t—————— mm————————— o —_———— +

COUNT

| STARTAREA

RTGINFO

—m————— t——————————— tm————————— +

COUNT

(2)

STARTAREA (2)
v

RTGINFO : BM

the number of areas

in the RTGINFO segment

The first area reported in the Routing Message,

with the top 10 bits 0

(area

is a 6 bit quantity)

Hops‘and cost to a destination area,

in the format:

t————t————————— +————- —-——+

Bit:

| 0

9 -

t—————— +

HOPS

cosT

e ——— tm—————— +

CHECKSUM (2) :
B a check on the routing data base,
and
a
check
to
ensure Phase IV Routing Messages not be mistaken for Phase III Routing
Messages, as well as a check of the message.
It i1s a one's complement
add starting with the first SEGMENT and continuing until the CHECKSUM.

Messages

To ensure that a Phase

Phase

Page 90

IV Routing Message will be distinguished from a

III Routing Message,

initialized

the sum on the Phase IV Routing Message

Messages

10.11

Ethernet Router Hello Message

t——————— e e

Page 91

FLAGS

s o

TIVER

e
e — — b —————— e ——————— +

IINFO

+t——————— tm—————— L

BLKSIZE| PRIORITY
s

o ———————— +

t————— tm—————— +————— +——————— +

AREA

TIMER

MPD

E-LIST

+————— Fm—————— +————— e ————— +

FLAGS
|

(1)
»

the Routing Layer control
following format:

flag,

t————dm——fm
Bit:

with

the

e
51

—p——— 4

312111

+-———+-——t———t———tm——t———t
———f———+

Set

to:

RES

TYPE

+-————t———F e ————————— +—-——+

Bit

Definition

(6)

IINFO

the

(1)

0,1

3
4
5

6
7

system

the

transmitter

Definition
|

Packet

flags

Bit

BLKSIZE (2)

Control

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

(3)

Reserved

TIVER

indicates

PF
pad field = 0 indicating
no padding follows

oY W

Type

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

Blocking Requested Flag

Reserved

Ethernet)

maximum Data Link Layer receive

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

Messages
\>

PRIORITY (1)
AREA (1)

TIMER (2)
MPD (1)

B
|

E-LIST (I-244)

Page 92

reserved

router's priority

Hello Timer in seconds
.

reserved

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

NAME (7)

: B

logical Ethernet name, reserved

" R/S-LIST (I1-236)

)

ROUTER (6) :

PRISTATE
- Bit

(1)
7:

list of router/state pairs.
format

Bits 0-6:
Note:

)

E-LIST will

NAME = 0

R/S-LIST

list

each

list

item

The

is:

~ router ID

BM
priority and state
State:
1
means
known
otherwise

Priority:

always contain a single

router/state

This router's priority

entry of

pairs

2-way,

the

format:

Messages

10.12

Ethernet

Page

Endnode Hello Message

+—————— $——————— -t ————— +————————— +—————- +

FLAGS

TIVER

IINFO

| BLKSIZE

t——————— tm—————— e
e

AREA

$—————— +

b —————— R o ———— b

[DATA]

SEED

NEIGHBOR

t—————— e

FLAGS (1) :
|

TIMER

| MPD

———— +m—————— +———— - +

the Routing Layer control flag, with the
following

format:

t————t———t———t-———t———t———t———+———+

Bit:

514131211110

t————t——————F———F———F———F———F———
¢

Set

to:

RES

TYPE

+---—+-—-——+————"t—-————t———_————————— +-——+

Bit

Definition

Type

4-6

Reserved

TIVER (3) :

indicates Control

1-3

Packet

6
.

PF
pad field = 0 indicating
no padding follows

the

version,

following

format:

with

the

'Byte‘l -- version number (2)
Byte
Byte

ID (6) :
|

2
3

-- ECO number (0)
-- user ECO number

ID of the transmitting node.

bytes must

The

bottom

address
IINFO

(1)

(0)

set

2 bytes

(ID)

to HIORD.

are

the

assigned to

The first

Phase

the node.

flags
Bit

Definition

0,1

the node type

3
4
5

6
7

(value

endnode)
Verification Required
on the Ethernet)

for

flag

(0
|

Reject Flag, Reserved
Verification Failed, Reserved
No Multicast Traffic Accepted
O=accepts multicast

Blocking Requested Flag
|

Reserved

(0 on

Ethernet)

Page

Messages

BLKSIZE (2)

maximum Data

block size
header,

Layer

excludes

Data

reserved

SEED

(8)

the verification seed

"MPD

(2)

(1)

DATA (I-128)

Link

header)

(0)

neighbor's system ID, ID of
Designated Router on Ethernets

(6)

fee

TIMER

receive

(Includes Routing

(1)

Link

AREA

NEIGHBOR

if no Designated Router)

Hello Timer,§in seconds
reserved

A sequence of 0 to 128 bytes of
data used
Each byte

to
is

test the circuit.
252 octal.

APPENDIX

ROUTES,

ADDRESSES,

AND

NAMES

This appendix explains the relationship between addresses
and names 1in
a

network.

The Routing

Layer

(addresses).

identifies

However,

nodes

often

network

unique

convenient

numbers

for users to

identify nodes by an alphabetic or alphanumeric
name.
In
addition,
several
users
at one node may each wish to identify network nodes by
different names.
Moreover, users may not want to use only names
that
are
unique
within
the
network.
Thus a problem arises as to how to
bind node names to node addresses in a network.

The solution is to use names that are unique within
a
node
unique)
and
addresses
that
are unique within the network
unique).
The following rules apply:

The Routing Layer knows nodes only by their addresses.

Names

\b/

(local)
o

The

are

assigned

1individually

local

naming

solution
has the

function

following

Aliases are not global.
to

change

preserves

o
o

node-by-node

and are unique within
a node.

necessarily a one-to-one
names may be assigned to
uniqueness 1is preserved.
This

(locally
(globally

local

the

(name to address directory)

1is

advantages:

aliases.

When networks merge, there 1s no need

correspondence

a distributed data base

between

names and addresses.

in an automatic

It avoids network maintenance problems

address

directories.

not

function.
In other words, alias node
a node name as long as overall
1local

It avoids the complex problem of méintaining duplicate

basis

Incorrect

function.

directories

affect

copies

‘name

only

and

local

ROUTES, ADDRESSES, AND NAMES

Page A-2

users.

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

APPENDIX B
ROUTING

SUBSETS

AND

TOPOLOGIES

This appendix defines routing and nonrouting nodes in terms
composition, and outlines topological
when planning network configurations.

B.1

NODE

considerations

that must

their
be made

TYPES

In_Phase‘IV'there are the following types of nodes:v
.

Level 2 routers

Level

routers

. Phase III routers

B.2

Phase IV endnodes

Phase III endnodes

TOPOLOGICAL CONCEPTS

Network topology involves two

physical

connectivity

and

Physical connectivity defines rules for connecting

network nodes

logical

connectivity.

concepts:

'ROUTING SUBSETS AND TOPOLOGIES

Page B-2

‘physical circuits.
A node's position

in the network may be

restricted.

Two nodes are physically connected if they are connected by a sequence
of

active circuits.

Two nodes are logically connected

' B.3

if they can communicate.

DECNET TOPOLOGICAL PRINCIPLES

'The following are goals:

B.4

Logical connectivity should equal physical connectivity.

Any subset of a legal topology should be a legal topology.

ENDNODE

RESTRICTIONS

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

For
|

Ethernet

______________ +——.___........._.--_—_._...._._.____._..___.._.._

Ethernet

------------- T

e ET
R

Rl1-———+

Ethernet

————————————— e e

Suppose
R2

can

Ethernet
#4

in this network the number of BEAs Rl can handle
handle R2.NBEA,

and R3

can

handle

R3.NBEA.

RI1.NBEA,

ROUTING SUBSETS AND TOPOLOGIES

page B-3

. Suppose there are El endnodés on Ethernet,#l,fEZ endnodes;ofi£{Etherfiet~w.'

\> #2, E3 endnodes on Ethernet #3, and E4 endnodes
on Ethernet #4.

Then

B.5

El1+E2+E3 must be less than or equal to R1.NBEA.

E3+E4 must be less than or equal
to R2.NBEA

must

less

equal

R3.NBEA

ETHERNET ROUTER RESTRICTIONS

> The sum of the number of
~/

than

routers on Ethernets

attached

router

cannot
exceed
R's
parameter
NBRA.
The
number
of
routers on an
Ethernet to which router R is connected cannot exceed R's parameter NR
for that Ethernet.
|
|

There 1s a large amount of control traffic
routers

Ethernets.

Each

router

Messages,

This

the

well

due

two

Ethernet
Ethernet

overhead

causes:

associated
|

frequently - 1ssues

Router

with

Routing

Hello Messages.

2. The control traffic associated with the temporary 1looping

property of the routing algorithm,
as nodes count to realize
‘the unreachability
of unreachable nodes, is
proportional
to
the square of the number of routers on the Ethernet.
|

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

can

B.6

LARGER NETWORKS

In Phase III, a legal network was restricted
in size
nodes that fit in a Routing Message.
With segmented

to the number .of
Routing Messages,

this node limit is no longer necessary.
However,
depending
on
the
application,
performance
will
no longer
be
acceptable above some
network size.
Also, memory restrictions also impose a maximum network
size.

Phase
number

III
of

nodes

cannot

nodes

of nodes that fit
~blocksize of that

_Phase

III

node

deal with segmented Routing Messages.

Phase

III

node

can

in a Routing Message
node's circuits.
In

cannot

communicate

with

handle
is

Thus

the

limited
by the number

of the size
supported
by the
a mixed Phase III/IV network, a
nor be included on a path to
a

/)node with node number higher than the Phase III node can handle.

ROUTING SUBSETS AND TOPOLOGIES
If

the rule that

node

B.7

hold,

"any subset of

.
a

legal topology

any network contalnlng Phase

numbers higher

than any router's

1s a

legal

Page B-4
topology"

III nodes must not contaln

capacity.

HIERARCHICAL NETWORKS

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

rules

for

a hierarchical

network

are:

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

Only level
other

routers are allowed to have

neighbor

nodes

1in

Each area must be physically intact, i.e. there must exist a

path

totally

in the

areas.

area.

internal.
to the area between each pair of
|

The subnet con51st1ng of

level

routers must

intact.

be
|

nodes

physically
:

A Phase III routing node cannot communicate with nodes 1in other areas,
nor can it be on a path between two Phase IV nodes in different areas.
Thus, for each area, the subnet consisting of the Phase
IV
nodes
1n
that area must be physically intact.
It is strongly recommended for performance reasons that
routers and endnodes on an EtHernet be in the same area.

all

level

APPENDIX C
NONROUTING OPERATION

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

nodes

of
routing
nodes, and the
C1rcu1ts,
are covered
1n

C.0.1 Receive Module

The Node Listener processes a packet upon receipt.
The Node
Listener
then passes
the
packet or discards it, depending on whether it 1is 'a
packet for self or any other message.
If
the
packet
1s
a
Routing
Message, the Node Listener discards it.
|

When transmitting to a node other than self,

the node sends the packet

out
over
the
only circuit available, unless the adjacent node 1s an
endnode, not the destination.
Otherwise, the node returns or discards
the packet, denendlng on the packet route header optlon.

C.0.2

Interfaces

The ECL and
Data
Nonrouting
nodes
except:

Link
interfaces
are
as
described
for
support
the
entire
Network
Management
|
|

READ NODE PARAMETERS
READ AREA PARAMETERS
READ ADJACENCY PARAMETERS

Inapplicable

SELF parameters

are:

routers.
interface
|

NONROUTING OPERATION

Page

. NN
.

NBRA

NBEA

Maxh

Maxc

Maxv

BCT1

Inapplicable

SELF

counters are:

noderunreachable'packet loss

aged packet

node

partial routing update

Inappllcable

loss

out-of-range

packet

CIRCUIT counters

transit packet

recelved

tran51t packet

sent

transit

congestion

loss

are:

loss

C-2

APPENDIX

PHASE III COMPATIBILITY
Thus there is no
Phase III nodes cannot appear on broadcast circuits.
Phase III compatlblllty problem with broadcast adjacencies.

On non-broadcast c1rcu1ts,,1f an Initialization

with

TIVER 1.3.0,

the

adjacency

Message

receilved

marked as Phase III router or

endnode, and an In1t1allzatlon Message with TIVER 1.3.0, and in Phase
III neighbor. Slnce Phase III
1is sent to - the Phase
format,
IIT
the Data Link
routers cannot recelive segmented ‘Routing Messages,
in the received Initialization Message must be large enough
blocksize
Otherwise,
to accommodate an entire Phase III Routling Message.
1is logged, and the circuit 1is not brought up.
failure
initialization
a Phase III
since
to T3,
The Hello Timer in the adjacency is set
report the value of its Hello Timer in control
neighbor does not
messages.

they
neighbor,
When Routing Messages are received from the Phase III
When Routing Messages are sent to a
treated as Phase III format.
are
for
The field
Phase III neighbor, they are sent in Phase III format.
2 router" is not sent, and the Routing Message cannot
level
"nearest
To ensure that nodes do not confuse Phase III and Phase
be segmented

IV Routing Messages,

the checksum 1is computed differently.

that
Phase III and Phase IV data packet formats are the same, except
III nodes will not know how to ‘interpret the area field in the
Phase
source and destination addresses. Thus a Phase IV node must strip off
the destination area field (which will of course be equal to the home
area if a packet is routed through a Phase III node) before forwarding

In addition, for "return to
to the Phase III neighbor.
the packet
sender" to work with a Phase III neighbor, the source area field 1is
as well, provided that the source area 1s equal to home
stripped off
area.

When a data packet is received from a Phase ITI nelghbor home area is
written into the destination area field, and home area is written 1into
the source area field, provided that it 1is 0.

Note
III
drop
ITI

that the Phase III functional specification specifies that Phase
nodes must check the SRCNODE field in the data packet header and
the packet if SRCNODE is out of range. This would cause a Phase
Thus
to drop a packet that arrived from a different area.
node

PHASE III COMPATIBILITY
any Phase
from
the

Page D-2

III nodes that perform that check must be patched or removed
network
before
a
multiple
area Phase IV network can be

implemented.
If

Phase

- connects
area,

the

III

router,

two

disrupting

same

1low

chain

dlfferent
operation

order

occur

node

areas,

nodes

IDs.

connected

Phase

III

these areas become merged
in

the

different

To prevent

areas

this problem,

routers

into one

which

have

which mlght

due to inadvertent connection of two nodes, node verification is
used.
For example, if each node is assigned a password which is area
specific, this area leakage can be prevented.

enforce

password

usage,

Phase

routers

not

area

must

require

verification
from
Phase
III
routers.
Specifically,
matching
of
non-null passwords is required before
bringing
up
such
a
circuit.
Individual
passwords
on
each
circuit,
or
the
ability
to enable
verification on a per circuit or per node basis 1s required for
level
2
routers,
so
that passwords can be assigned according to the above
recommendation.
|
4

)

APPENDIX

ROUTING

LAYER COUNTERS AND EVENTS

This appendix specilfies the Routing Layer 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 Routing Layer activities, congestion, faults, topological

changes,

and verification

(security)

violations.

related to packet modification, misdelivery,
can detect, are not specified here.

Counters and

or duplication,

events

which ECL

In the following discussion, the term fault refers to the cause
problem.

The

term

error refers

a manifestation

Routing Layer counters and events capture

sufficient

fault.

information

are detected,
B

but
|

E.1

SOURCE

EVENTS

;

\\\\-—//

detect
and
1solate single faults.
Multiple faults
only isolated when 1t is cost effective to do so.

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
generic event for logging.

Source events are classified

source events may produce
-

in two ways:

a
\

single

by event manifestation

and

by
cause,
The
primary
classification is
by event manifestation.
Within each event manifestation category
are subcategories of specific
source
events.
Each of these specific source events has a particular
cause.
The
following
three
tables
describe
source
event
manifestations, causes, and source events.
Table
4 defines each event
manifestation category.
Table 5
defines
each
source
event
cause.
Table
6
defines each source event along with its event manifestation
category and probable cause.
The abbreviations in Table 6 are defined

ROUTING LAYER COUNTERS AND EVENTS
in

Page E-2

Table 5.
Table 4
Source Event Manifestations

Event Manifestation

- This group of
the
movement
Routing Layer.

Movement

This group of

Congestion

source
events
reflects
of data
through
the

source

events

reflects

the discarding
of data packets due
Routing Layer congestion.

Data Packet Discarded

This group of

the discarding

source

Fprmat

Error

reflects

of data packets due

fault.

Message

events

The format of the message is in error.

Partial Routing UpdatéflLoss This

source

eVent" represents

the

receipt
of
a
Routing Message that is
too long to
process
so
that
some
information
from
the
message
1s
~discarded.

Circuit

Down

'Adjacency Down

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

group of source

events

represents

‘This group of source events

represents

loss

connection

to an adjacent

node.

Initialization Failure

failure

initialize

with

~adjacent node.

Verification Reject

~This

source

receipt

event

represents

1invalid

the

Verification

Message.

Circuit Up

This
source
event
represents
= the
successful initialization of a circuit.

Adjacency Up

This
source
event
represents
successful
initialization
with
adjacent node.
|

Node Reachability Change

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

Adjacency Reject

| ‘\\\_.u—'//

Data

Definition

and

unreachable.

This group of source events
this
node
adjacency.

the
an

represents

being forced.
to reject
R
|

Page E-3

"ROUTING LAYER COUNTERS AND EVENTS

Table
Source

(Symbol)

Event

5
Causes

Explanation

Cause

(A)

Activity

The normal activity of
Layer in moving data.

(C)

Congestion

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

(s)

System Fault:

Failures

failures,

excluding

(0)

Operator

Initiated

software

and

the

either

Routing

hardware

undetected
circuit

circuilt

faults.

Events directly caused by the action of an operator, including failure of
an
operator
= to . set
'parameters

correctly

for

" the

harmonious

operation
of
multiple
nodes.
Typical operator
faults
1include
a
node's maximum address that
1s
too
small
or an adjacent node's ID that
1s

too

large.

(T)

Topological Change

topology
Modifications
1n
changing
result
1in
a
node
reachability status.

(v)

Verification Violation

The detected attempt
of
a
node
initialize
without
providing

expected verification

(L)

Circuit Fault

that

1its

to
the
information.

. The detected failure of

circuit.

A circuit fault does not necessarily
result in a topological change.

ROUTING

LAYER

COUNTERS

AND

EVENTS

Table

e ey

!
!

Event
Manifestation

e e

o S

Source

!
!

Event
Number

!
!

e e

!
!
!

Data Movement !
B
!
!

!
!

!
!
!

!
3
!

!
!
!

Events

e e

!
!
!

Probable
Cause
e =

{

E-4

e o o

!
!

Definition

—— — — — ——— —— o — —

——

o
—— —— ’___;___!

! A data packet 1s received
!
! from an adjacency for another!
! node in the network.
!
:

A data

!
!

node
over

packet

in
an

from

another

the network
adjacency.

sent

!
P
!

!
!
:

Page

Source

|
|

!
!
!

A data packet 1s received
from an adjacency for this
node's ECL.

!
!
!

!
!
!
'
!
!

A data packet
node's ECL 1is
adjacency.

from this
sent over
|

!
!
!

| _._._.___._._.___.___._.___.__.___..._..___._._.._._.___._..._.._.....____._.._..___._. ____________________ !

Congestion
~

!
!
!

!
!
!
!

!
!
!
v

6
|

!
!
|

A transit data packet 1is
discarded for congestion
reasons.
|

!
Ry
!
!

!
!
!
!

A terminating packet is
discarded due to the
1nability of ECL to process
packets fast enough.

Data Packet
Discarded

!
!

‘

7
-

—————————————————

!
I

! Destination node
! unreachable.

Packet

{

’

Destination node

out

{

too old.
,

!
10

{

!
!
!
!
!

!
!
|

'
!

1is

!
!
!

of
'

!
i

range.

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

(continued on next page)

!
|
!
!

‘\\\\——//’

!
!
!

ROUTING LAYER COUNTERS AND EVENTS

Event

Manifestation

Message

Format

Error

Table 6

(Cont.)

Source

Events

E-5

Event

Cause

Received long Routing
Message with reachable node
number greater than thlS
node's NN,

‘Partial Rout!
ing Update
!
Loss
!
{

Circuit

Page

- Data

Down

11nk synchronlzatlon

lost
14

14.1

Data link threshold error
detected.
‘

Data Corruption detected in “
X.25

net.

Circuit rejection algorithm

Node

Listener

timeout.

received

checksum error.

Node

',“
O=Ek
Pan

the

Hu=h

not

GmEE

from Routing or

Hello Message
expected one.

Hello received indicating
connectivity became l-way

Gral

Quul

OQOewn

GvEN

$~Un

O=En

Hup

with

Soan

'Routing Message

G=ap

(¢ an

$mem

Sain

S-En

received.

@ oEn

[X ]

ization or Verification)

message

8 =an

Unexpected control (Initial-

O-m

P
$oED
$ER

O~GR
GmEs
G

—

‘Node Listener received
invalid data.

@ wu

15,2

O =g

Adjacency Down!.

@ el

rejected circuit (for reason
other than threshold error).

(continued on next page)

ROUTING LAYER COUNTERS AND EVENTS
Table

Page

Source

E-6

(Cont.)
Events

Source
Event

Event

Probable

Manifestation

Number

Cause

Initialization!

Verification Message not

Failure

received

timeout

period.

Data link synchronization
lost.
|
22.

Data link threshold errorv

detected.

Version skew detected.

Node 1d in received Initialization Message too large.

Block size in received Initialization Message too small.

Invalid verification seed

value in received
Initialization Message.

26.1

Password required
from Phase
III

node

Unexpected message
27.1

Reject

received.

Area mismatch.
Invalid verification
received.

Initialization with neighbor
complete

(continued on next page)

ROUTING LAYER COUNTERS AND EVENTS

Page E-7

Table 6 (Cont.)
Source Events

!
!
!

! Node Reach! ability
! Change
| o e e e e e ee

!
!
!

Adjacency
Reject

| —
! Area Reach-

!
!
!
!

!
!
!

Event
Manifestation

Source
Event
Number

!
!
!

Probable
Cause

e e,

!
!
!

Definition
e

!
!
!

—————————————
—— |

!
30
!
T
! Node reachable.
‘
| - =,
!
31
!
T
! Node unreachable.

!
'
!

!
!

32
|

!
!

e e . — — — — — — — — — — — — — —————_— — — ——— —_—

!
!

Too many BRAs
(NBRA or
NR on an Ethernet exceeded).

!
!

Too many BEAs

e —————— !

e !
T
! Became reachable
!

o 34
!
ability
| -—————- e
—
- !
Change
!
35
!
T
! Became unreachable
|
!
(or nearest
j--———_———————_—_——_e—_e—,—,——_——_,——e—e—ee e
e!
level 2 router, for level 1 nodes)
!

E.2

COUNTERS

There are two types
of counters -node
and
circuit.
The
Routing
Layer
maintains
one
node
counter
for
each
of
the
defined node
counters.
The Routing Layer maintains one circuit counter per circuit
for

each of

the defined circuit

counters.

Node counters count

source

events attributed to topological
changes,
faults,
and
verification
violation.
Circuit
counters
count
source
events
attributed
to
activity,

congestion,

The node and circuit

and

faults.

counters are defined below.

Each counter

relates

to
a
source
event number.
Refer to the glossary for definitions of
terminating, originating, and transit packets.
A packet
1s
received
when
it
passes
from
the
Data
Link Layer to the Routing Layer.
A
packet is sent when it passes from the Routing Layer to the Data
Link
Layer.

ROUTING LAYER COUNTERS AND EVENTS

",'

Node Counters

Page E-8

T U source
oT

Counter

I 16 bits

: node oUthf+range packet loss

i' 8 bits

: packet format, ervor

: 8 bits

i node unreachable paCket loss

: aged packet loss

% oversized packet loss

% partial routing update loss
! verification reject

’

E 8 bits

Events

’

% 8 bits %

- %

:
!

12
28

:
:

’

:
!

8 bits
8 bits

)

ROUTING LAYER COUNTERS AND EVENTS
"Circuit

E
!

Counter

Name

transit packet received

Page E-9

Counters

Counter

Width

32 bits

! Source

T
:

Events

Included

: transit packet sent

: 32 bits

: 2

: originating packet Sent

: 32 bits

! 4

: 6

: terminating packet received
% transit congestion loss

: terminating cbngestiofi loss*

! circuit down'

Einitialization failure

: corruption loss (X.25 only)

: 32 bits

: 3

;

5 16 bits

; 5

: 8 bits

: 13 - 15

: 16bits

: 8 bits
:

8-bits

;

: 20 - 27.1 %
% 14.1

* Only required in the implementations
in which ECL does not guarantee

Routing that it will process a terminating packet (thereby freeing the
buffer holding the packet)
in a short, bounded period of time.

E.3

EVENTS

Network Management groups some of
the
source
together
for
logging.
The
DNA Network

events
(Section E.1)
Management = Functional

Specification specifies this logging operation.
When a source
event
to
be
logged occurs,
the
Routing ©Layer
identifies 1t
by type,
time-stamps it, and places it in an internal Routing event queue.
If

the
event
queue
1is
full,
Routing discards the newest event
queue and replaces it with an "event(s) lost" event.

in the

ROUTING LAYER COUNTERS AND EVENTS

oUYER

WEEG

Source

Events

GMUME | GNSR

RGN

MDD

GAER

URGES

AOTW

SEnAD

SME

Gnmy

SMUND

AEmmS

WANGY WENGE

SIS

CUIEEN

GENND

WENST

GIMEE

TINES

WEEDT

GHUS

Gmmin

SEe

SEm

GEmE

Logged
Information
I

Node unreachable»packet loss

S
S
P
SIS

dEnel

)

SRS

GETEN

Gmm

header

out-of-range packet

adj,

loss

packet

header

Oversized packet loss

adj, packet header

Message

format

adj,

packet

Partial

routing

adj,

packet header

error

header

update

loss

circuit

fault

13-15

Circuit down -

O an 0-.. Oman
HSmEp
SuEh
CuEE
SoEs
SoEh
Goal

adjacency

15.1-17 |

adj; packet header

Adjacency down

15.1-17

adj,

packet

header

Circuit dowa - operator initiated
Adjacency down - cperator initiated

adj, packet header

~adj, packet header

Initialization

20-22

circuilt

failure

circuit

fault

Initialization failure éjoperator
initiated

PuEh

:phighest node address!

Circuit down

Gmum

OG=ab

HeEbh

PeER

Poal

feEbh

SER

HBD

packet header

Aged packet loss
Node

adj, packet

Dvis

GrER

Peuid

S=AN

Layer

Events

o qv

— =
" <

Routing

23-26.1 : adjacency,
pkt hdr,
recelived version

Initialization

failure

software

adj,

packet

header

Verification

reject

circuit,

SED
S
SmEh
SoER
OwaS
Suan
PuS
CGmtn S-an
f Oeuh Qutn

node

from message

S~ES

SvB

GoEw

HeER

CGUAD

(23 only)

Circuit up'

29.1

adjacency

Adjacehcy up

29.2

adjacency

Node reachability change"

30,31

Area reachability change

34-35

area (level 2)

Adjacency

32.1-331

adj,

reject

! node address, state

exceeded param.

ROUTING

LAYER

COUNTERS

AND

EVENTS

A logged event of a single type that
than
one source event
the source event.

also

contains
|

can
a

"Packet header" denotes the first 6
bytes
Routing Layer message in short format, and
for packets in long format.
"Adjacency"

logged

as <circuit,

node

result

reason code

Page

from
to

E-11

specify

(48
bits)
the first 21

of a
bytes

ID>

"Adjacency up" 1s logged as
"Circuit
Up",
and
"Adjacency
Down" (1s logged as "Circuit Down" on point-to-point circuits.

APPENDIX

ALGORITHMS

AND MODELS

) This appendix describes algorithms and models pertaining to:
Circuit

cost

Buffer management

N "‘“-—v/

F.1

CIRCUIT COST ASSIGNMENT ALGORITHM

The assignment
of
cost
to
«circuits
can
reflect
both
delay
and
throughput
data.
Delay
data
<can
include
transmission
delay,
propagation delay, processing delay, and retransmission delay.
Delay
data
does
not
1include queuing delay.
Throughput data can include
circuit
bandwidth,
circuit overhead,
and
processor
bandwidth.
Throughput
data does not include actual traffic overhead.
Basically,
it is desirable
to avoid a circuit cost assignment algorithm with high

sensitivity
to
traffic
fluctuations,
thereby producing
a condition
where routes change to accommodate traffic changes and the new traffic
flow causes new route changes,

and so on.

A circuit cost assignment occurs as a result of a node
generation
or
an
Initialization module.
An
operator
can
always
override
any
assignment.

One such assignment is based on circuit bandwidth and is as follows:
1 where bandwidth x >= 100,000 bits/second

- F(x) = [100,00/x]-for 4,000 bits/second < x < 100,000 bits/sec
25

where

4,000

bits/second

ALGORITHMS AND MODELS

Page F-2

where x is circuit bandwidth (bits/seC)

F.2

BUFFER MANAGEMENT

When no buffers are available for receiving packets
store

and

insuring

forward

that

deadlock

can

least one buffer

occur.

from

circuit,

Deadlock
can be avoided by

is available

per

circuit,

buffer
can be made available without requiring additional
Such deadlock avoidance can require discarding packets.

resources.

When receive buffers are not available quickly enough,
a circuit can
'go
down
unnecessarily at the Data Link Layer.
It 1s much better for
the Routing Layer to discard a packet than for a circuit to go down.
The Routlng Layer should not initialize unless it can obtain at least
the
minimum
number
of
receive
buffers
for
each
circuit.
If an
implementation obtains these buffers from a shared system buffer pool,
then the minimum number must be permanently allocated from the pool by
the Routing Layer when
it
initializes.
They
<can,
of
course,
be
returned when Routing

halts.
=

The only time a circuit may be allowed to go below its minimum
number
of
buffers is when the system can guarantee that a receive buffer can
be allocated to the circuit soon enough in the future to
prevent
the
circuit from going down. This means that if the system has run out of
free buffers and is down to the minimum number of receive buffers
for

be forwarded

A received data packet that would normally

another circuit must be discarded.

{

then:

each circuit,

. A

received

processed.

Routing

control
|

message

can

and should
Dbe

A received data packet for this node should be given
to
only
if
ECL
is known to be able to return the buffer

short,
packet.

bounded period

time.

Compute the minimum number of receive buffers

Otherwise,
|
|

required

ECL
in a
discard
the
|

for

a given

circuit for the circuit speed and an estimate of the maximum t1me that

Routing

(or p0551bly ECL) can take to process a received message.

Page F-3

S MODELS
AND
ALGORITHM
POSSIBLE BUFFER MANAGEMENT MODEL

F.3

If
Routing has a common pool of buffers that can transmit or receive.
make
to
unable
be
to
known
is
implementation of ECL in a system
the
the guarantee of short, bounded processing of received data packets,
1limit the number of outstanding, received packets
‘then Routing must
that ECL can hold onto simultaneously (provided that ECL and Routing
This is best done by a fixed
are sharing a common buffer pool).
guota.

the

congestion

then any packets discarded due to

the

ECL

Setting this quota to the square root limit

wused

control algorithm is acceptable, but other values may be used as well.
is used,
If a quota

being filled must be counted.

by the system is divided
The Routing Layer buffer quota provided
1.

Decision

1into

(0)

2. ~Update (1 sufficient;
-

following buffer quotas:

the

quota

Node Listener

.4.

Node Talker (1)

1 per circuit recommended)

(0)

5. »Forwarding (at least 1 per circuit;

12-15

terrestrial

per

“circuit and 30 - 35 per satellite circuit recommended).

6. A separate receive quota for each circuit (depehds
of circuit -- at least 1,

2, or 3 recommended).

speed

buffer
single
a
using
If an implementation is constructed
system
shares with other
Layer
Routing
the
that
pool
actual
any
do
processes, and if the Routing Layer does not
to another, then all buffers
buffer
from one
data moving
from
either obtained
containing data to be transmitted are
ECL or are receive buffers that contain data packets that are
being

The

forwarded.

rules

adequately
the

above

define

following:

First,

control

the

congestion

limit

is defined to be the

and

wuse of these buffers.

the

algorithms

However,

note

the square root

number

for forwarding divided by the square root
available
buffers
of the number of circuits.
The number of
buffers
available
for forwarding
receive buffers,

quota exists.

should
not 1include
the
minimum number of
nor should it include ECL's quota, 1f such a
v

the minimum
Second, in such a model, a single buffer beyond
number
of
receive
buffers and a single ECL transmit buffer
are sufficient to allow the Routing Layer to
run
correctly
without
starving a circuit for receive buffers. 1In general,

for adequate performance

additional

buffers

will also

quota.

The

required.

DETAILS OF CHARGING‘AND CREDITING AGAINST QUOTAS

All buffers not free will be charged against a

specific

quota will never be exceeded except possibly for a brief instant while
a Routing process frees the buffer by consuming the information or by
discarding

a packet.

A quota is charged for a buffer upon the following events:
buffer

assigned

1is

the

Data

Layer

Link

A free

A buffer is moved from one Routing module

A buffer is supplied by ECL that contains input data.

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

reception on a specific circult.

receiving quota

for

another.

The

1s charged.

Layer

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

Transmission of a buffer is completed by the Data Link Layer.

(The

quota

successful.)

2.
3.

1is.

credited whether or not the transmission was

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

is credited.

a
A process consumes the contents of

message and returns

Routing

another.

Layer

control

the empty buffer.

A process discards a packet and returns the buffer.

a successful CHECK RECEIVE command.
ECL issues

fu2

F.4

Page F-4

S MODELS
AND
ALGORITHM

APPENDIX
G
BUFFER

SIZES

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

Buffer

Size

(BS)

ECL Segment Size

(SS)

The buffer size 1is 6 greater than the size of buffers Routing uses for
forwarding,

not

including

routing

header

datalink header.

The ECL segment size 1s reported by Routing to ECL.
It
equals
SS-6.
SS-6
is
the
maximum
size
segment
the ECL
1is allowed to pass to
Routing.
NSP requires SS-6 to be at least of some minimal size.
(The
size
of
the
maximum
length CI Message, with maximum length connect

data

required by the Session Layer.)

Usually, BS=SS.

changed,

However,

BS may be

greater

when

the

than SS.

network

can

buffer

never

size

less

than

being

SS.

Thus to expand the buffer sizes in the network, each node's BS must be
increased,
one
at
a
time.
When
all
nodes'
BS
parameters
are
increased, then each node's SS
can
be
1increased, one
at
a
time.
Similarly,
to
shrink the buffer sizes 1n the network, each node's SS
must be decreased, one at a time.
When all nodes' SS
parameters
are

decreased,

then each node's BS can be decreased,

Note that BS and SS do not include route
however,
1include
an
extra 6 bytes for
There
are two formats of route header in
short
format.
The
overhead
1in
1long
overhead in short format.

one at

a time,

header overhead.
They
do,
compatibility with Phase III.
Phase IV -- long
format
and
format
1is
greater than the

For each circuit, there is a datalink blocksize, which includes
route
header
overhead.
Thus for Ethernet circuits, the datalink blocksize
must be greater than or equal to BS minus 6
plus
the
route
header
overhead in long data packet format.
For DDCMP circuits, the datalink
blocksize must be greater than or equal to BS minus 6 plus
the
route

header overHead

in short

format.

BUFFER SIZES

Page G-2

For each adjacency, there is a negotiated datalink bldcksize, which is
the

smaller

non-X.25

blocksize

circuits,

the

routers

cannot

requested

by either end.

negotiated blocksize must

For adjacencies on
greater

than

equal
to
BS
minus
6
plus
the
route
overhead
(long
format for
Ethernets, short format for point-to-point circuits).
Also,
1f
the
node
type
of
the
adjacency
1is
Phase 1III
router, the negotiated
blocksize must be large enough to fit an entire Routing Message, since
Phase

III

segmented Routing Message.

Since the X.25
1Initialization
Sublayer
performs
fragmentation
and
reassembly,
the
datalink blocksize on X.25 circuits
does not need to
meet the above constraints.

APPENDIX

GLOSSARY

adjacency -- a
attached nodes

[circuit, nodelID] pair.
An
Ethernet
with
n
represents n-1 adjacencies|
to a router on that

Ethernet.

has

A router attached to
adjacencies to the second

aged packet
of visits.

BEA

(broadcast

packet

(broadcast

same

this

has
|

router

Ethernet

node.

exceeded

node.

the

term also

The

circuits

maximum
|

an endnode

The

via

associates with

adjacency)

this

router

router.

endnode adjacency)

the same Ethernet
state information

BRA

that

another

the

router

number

connected

applies

adjacency.

connected to

term also

the

applies

the

state information
a router associates with the adjacency.
1If
the
same router is attached to more than one common Ethernet
as this node, that router appears as a
BRA
on
each
common
Ethernet.
=
|
|
broadcast circuit -- a circuit on which
multiple
nodes
are
connected,
and
there
exists
a
method
for transmitting a
~packet which will be received by multiple receivers.

circuit -- one of the folloWing:
.

a DDCMP

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

Ethernet

1link

an X.25 circuit -~router
via an X.25
n circuits for that

if there are n nodes
network,
router.

that

X.25

reachable

network represents

GLOSSARY

there

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

Page

H-2

are

too

Layer
Routing
datagram -- A unit of data passed between the
is
header
route
a
When
Layer.
ns
Communicatio
End
the
and
added,

becomes a packet.

to
'Designated Router -- the router on the Ethernet chosen
on
endnodes
the
informing
as
such
duties,
additional
perform
Ethernet
the
the Ethernet of the existence and identity of
The router chosen is the one with highest priority,
routers.
with highest

ID breaking ties.

10,

end node -- A nonrouting node.

11.

error —-- The manifestation of a fault.

13.
14.

event —-- Occurrences that are logged for recording by Network

16.

from occurrences of source events.

Layer modules.

the

1in

problem

fault -- The cause of a

Routing

_operation' of the

vhop’—— The logical distance between two adjacent nodes
network.

15.

Events result

Management.

adjacent

two

initialization -- A start-up procedure between

nodes.

to communicate.
of nodes
logical connectivity -- The ability

17.

multiaccess channel -- A special tYpe of broadcast circuit on

18.

nonbroadcast circuit -- Any circuit other than a

which the channel is shared on a contention basis.

than one

19.

20,

broadcast

example, '‘a multipoint DDCMP circuit 1s not a
For
circuilt.
broadcast circuit because a packet cannot be received by more
node.

originating packet

Communications Layer.

packet

from

this

node's

End

packet -- A unit of data to be routed from a source node to a

1its route header and
When stripped of
destination node.
passed
to
the
End Communications
Layer,
it
becomes
a
datagram.

21,

a node.
packet looping -- A condition where a packet revisits

22.

-path

The

route

packet

takes

from

of the

circuit

costs

source

node

path

destination node.

23,

path cost -- The sum
between

two

nodes.

along

\\\‘-'/,,}

12.

Page

GLOSSARY

24
.

path length -- the number of hops along a

path

nodes.

25,

26,

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

29,

31.

attached

from the Data Link Layer

node's

Routing

route-through -- packet switching.

routing -- Directing data message packets from
‘

sent packet -- a packet passed
~to the Data Link Layer.

that may cause

a counter

source

nodes

from thlS node's Routlng Layer

source event -- a specified occurrence

Layer
to

32,

being

£wWo

to destination nodes.
30.

a packet.

received packet -- a packet received by this

Layer
28.

between

reachable node -- a node to Wthh a routing node believes
can direct

27.

H-3

to be

in this node's Routing

incremented or

event

destination

1is

this

logged.

terminating packet -- A

node.

packet

whose

33.

topology -- The physical
arrangement and
relationships
of
interconnected
nodes
and
circuits
1in
a network.
A legal
topology satisfies the requirements of this specification.

34,

transit packeét -- a packet
arriving
at this
source node and destined for another node.

35.

unreachable node -- a
determined
that
the
network.

node
path

node

from

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

APPENDIX

REVISION HISTORY

I.1

CHANGES

I.1l.1

FROM

Ethernet

1.
2.

3.
|

I.1.2

PHASE III

Support

The concept of lines became
circuits.

An NI

two

concepts--adjacencies

and

Initialization Sublayer was added.

Extra routing timers and Hello Timer

parameters

due to the different_characteristics of

the NI.

were

added

Hierarchical Routing'

1.
2.

I.1.3

Code and parameters for level 2 routers was added.
Code and parameters in level 1 routers was added for

with

interarea packets and

"nearest

level

router”.

dealing

Segmented Routing Messages

Srm flags made into
a matrix.

Code added for dealingdwith segmented Routing Messages.

REVISION HISTORY

I.1.4

Page

I-2

Terminology Changes
1.

Transport => Routing (state names
word Transport changed also)

Phase

NSP => ECL

I.1.5

Phase

=> Phase

and state

actlons

involving

(End Communications

Layer)

Clean-ups

Self

Select

MinHops algorithm changed to reflect hops of chosen path

vector

removed,

Process

Open

and

calls

removed

Hello Timer communication,

and

setting

Listen

function of

neighbor's Hello Timer

Buffer size

bug

Line Rejection algorithm removed

Useless

Extensible fields changed to single byte fields

Formats of packets
as before)

10.

Lots

I.1.6

Phase

I.1.7

X.25

fixed,

or Wrong

diagrams

Data

Verification

as done

X.25

number

to be migrated

than

kept

two

version

(rather

in machinable

Removed

Link mapping

sizes

removed

complete

editing
to get

Support

enabling buffer

Timer

spec merged
removed

removed

shape.

places

REVISION HISTORY

I.1.8

Page I-3

Miscellaneous

Appendix on buffers

added

Parameter ECL segment

size

Redefined arithmetic

comparison of

leftmost byte be

least

Changed word "top"

added

significant

"first"

when

bytes

addresses

discussing

0 and also check

and

address

alignment

for

Process.

S-ID

done

COST(0,0)

in CHECK

Resérved field of a byte added to Routing Messages
Check

have

Fixed bug--level 2 routers initialize HOP(0,0)
to

only

when

necessary

for

1in

‘

word

Forwarding

Priority of BRA neighbor added 1into Adjacenéy database,

All mention of NI was changed £o Ethernet

}

Optional padding added to all Routing MessagésA
Speed up and clarify Ethernet;initialiZation
Graceful going down messages for Ethernet, X.25, and DDCMP

Hello Timer-2 bytes

‘

of T3;

Maxc, Maxh,

BCT3MULT changed§to 3 from 8
‘Upper limits placed on
AMaxh,

16.

Maxv,

NN,

values

AMaxc,

Packet formats
renamed
Process
rewritten
for

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

format
17,

Circuit parameter

18.

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

19.

OPL (Originating

database.

Text

network management

"Recall Timer"

packet
of

added

limiter),

section

5.2

put

states

1into

that

the
it

<circuits

is set by

REVISION HISTORY
20.

Link Dependent
set

call

Sublayer

1incoming

X.25

switched virtual

specify that
circuit,

1if

number

Page I-4
VC

name

must

match

rejected

21,

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

22.

Forwarding Size renamed Buffer Size, and increased by 6 to be

compatible
with
Phase III.
ECL Segment Size decreased by 6
when being reported to ECL, so that its value can
equal BS,
yet be a sensible value for ECL.
23.

Circuit down, corruption lOss,' and
counters

changed

from

initialization

bits,

network management.

Adjacency down counter

24,

Numerical

25,

Packet formats reorganlzed
lst byte named FLAGS
sometimes FLAGS, RTFLG, or CTLFLG.

26. Limit

comparison

Algorithm

size

Ethernet

Routing

addresses

Message

failure

compatible

clarified

instead

specified in

with

removed.

of
|

Update

27. Enabling of multiple areas on Ethernets
28.

Adjacency up/down for Designated Router by endnodes

29,

Look

only

byte

of ver51on

number when

comparlng

version

numbers

30.

31.

Note

that

adjacency

point-to-point

links

Routing

added

Type

events

SELF

Management

32,

ECL

from

removed

routlng

34,

Rules for

bit

always

keep

intra-Ethernet
set, and routers

36.

Network

destination

determlnlstlc

by u51ng

node

changed

to be originating
nodes
on when forwarding onto same

Endnodes

on Ethernets

checker

(no adjacency database necessarily)

not

required

have

Ver1f1cat10n requ1red of Phasé III routers
leakage

37.

from TRANSMIT,

circuit

set

events

Rowmin changed to make
for breaking ties

circuit

RECEIVE

33.

35.

parameters

interface--source

removed

1logged

No* checking

packet

prevent
|

reserved bits

size

afea

REVISION HISTORY

38.

Inter-area packet not

Page

forwarded to destination Phase

I-5

III node

DECnet Digital Network Architecture: Phase |V

Routing Layer Functional Specification
AA-X435A-TK

READER’S COMMENTS

| NOTE: This form is for dochment comments only. DIGITAL will use comments submitted on this forin 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? If so, specify the error and the page number.

Please indicate the type of user/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

— — — —

==I)o Not Tear - Fold Here and Tape

—

dlilgliltlall

No Postage
Necessary

if Mailed in the

United States

" BUSINESS REPLY MAIL
FIRST CLASS PERMIT NO.33 MAYNARD MASS.

— — — — — — —

— — — — — —

Cut Along Dotted Line

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

SOFTWARE DOCUMENTATION
1925 ANDOVER STREET TW/EQ7
TEWKSBURY, MASSACHUSETTS 01876

POSTAGE WILL BE PAID BY ADDRESSEE