RFC relevance of sequence

As per Relevance of the word sequence, we have this rfc below:

Request for Comments: 823
Obsoletes IEN-30 and IEN-109

THE DARPA INTERNET

RFC 823

Robert
Alan

Bolt Beranek and Newman Inc
10 Moulton St
Cambridge, Massachusetts 02238

September 1982

Prepared

Defense Advanced Research Projects
Information Processing Techniques
1400 Wilson
Arlington, Virginia 22209

This RFC is a status report on the Internet Gateway developed by BBN.
describes the Internet Gateway as of September 1982. This memo
detailed descriptions of message formats and gateway procedures,
this is not an implementation specification, and such details are
subject to change

DARPA Internet Gateway September 1982
RFC 823

Table of

1 INTRODUCTION.......................................... 1
2 BACKGROUND............................................ 2
3 FORWARDING INTERNET DATAGRAMS......................... 5
3.1 Input............................................... 5
3.2 IP Header Checks.................................... 6
3.3 Routing............................................. 7
3.4 Redirects........................................... 9
3.5 Fragmentation....................................... 9
3.6 Header Rebuild..................................... 10
3.7 Output............................................. 10
4 PROTOCOLS SUPPORTED BY THE GATEWAY................... 12
4.1 Cross-Net Debugging Protocol....................... 12
4.2 Host Monitoring Protocol........................... 12
4.3 ICMP............................................... 14
4.4 Gateway-to-Gateway Protocol........................ 14
4.4.1 Determining Connectivity to Networks............. 14
4.4.2 Determining Connectivity to Neighbors............ 16
4.4.3 Exchanging Routing Information................... 17
4.4.4 Computing Routes................................. 19
4.4.5 Non-Routing Gateways............................. 22
4.4.6 Adding New Neighbors and Networks................ 23
4.5 Exterior Gateway Protocol.......................... 24
5 GATEWAY SOFTWARE..................................... 26
5.1 Software Structure................................. 26
5.1.1 Device Drivers................................... 27
5.1.2 Network Software................................. 27
5.1.3 Shared Gateway Software.......................... 29
5.2 Gateway Processes.................................. 29
5.2.1 Network Processes................................ 29
5.2.2 GGP Process...................................... 30
5.2.3 HMP Process...................................... 31
APPENDIX A. GGP Message Formats.......................... 32
APPENDIX B. Information Maintained by Gateways........... 39
APPENDIX C. GGP Events and Responses..................... 41
REFERENCES............................................... 43

-i

DARPA Internet Gateway September 1982
RFC 823

1

This document explains the design of the Internet

used in the Defense Advanced Research Project Agency (DARPA

Internet program. The gateway design was originally

in IEN-30, "Gateway Routing: An Implementation Specification

[2], and was later updated in IEN-109, "How to Build a Gateway

[3]. This document reflects changes made both in the

protocols and in the gateway design since these documents

released. It supersedes both IEN-30 and IEN-109.

The Internet gateway described in this document is based

the work of many people; in particular, special credit is

to V. Strazisar, M. Brescia, E. Rosen, and J. Haverty

The gateway's primary purpose is to route internet

to their destination networks. These datagrams are generated

processed as described in RFC 791, "Internet Protocol -

Internet Program Protocol Specification" [1]. This

describes how the gateway forwards datagrams, the

algorithm and protocol used to route them, and the

structure of the current gateway. The current

implementation is written in macro-11 assembly language and

in the DEC PDP-11 or LSI-11 16-bit processor

-1-

DARPA Internet Gateway September 1982
RFC 823

2

The gateway system has undergone a series of changes

its inception, and it is continuing to evolve as

proceeds in the Internet community. This document describes

implementation as of mid-1982.

Early versions of gateway software were implemented

the BCPL language and the ELF operating system.

implementation evolved into one which used the MOS

system for increased performance. In late 1981, we began

effort to produce a totally new gateway implementation.

primary motivation for this was the need for a system

towards the requirements of an operational

facility, rather than the research testbed environment which

associated with the BCPL implementation. In addition, it

generally recognized that the complexity and

requirements of future gateway configurations were beyond

capabilities of the PDP-11/LSI-11 and BCPL architecture. The

gateway implementation therefore had a second goal of producing

highly space-efficient implementation in order to provide

for buffers and for the extra mechanisms, such as monitoring

which are needed for an operational environment

-2-

DARPA Internet Gateway September 1982
RFC 823

This document describes the implementation of this

gateway which incorporates several mechanisms for

activities, is coded in assembly language for maximum space

efficiency, but otherwise is fundamentally the same

as the older, research-oriented, implementations

One of the results of recent research is the thesis

gateways should be viewed as elements of a gateway system,

the gateways act as a loosely-coupled packet-

communications system. For reasons of maintainability

operability, it is easiest to build such a system in

homogeneous fashion where all gateways are under a

authority and control, as is the practice in other

implementations

In order to create a system architecture that

multiple sets of gateways with each set under single control

acting together to implement a composite single Internet System

new protocols needed to be developed. These protocols, such

the "Exterior Gateway Protocol," will be introduced in the

releases of the gateway implementation

We also anticipate further changes to the

architecture and implementation to introduce support for

-3-

DARPA Internet Gateway September 1982
RFC 823

capabilities, such as large numbers of networks, access control

and other requirements which have been proposed by the

research community. This document represents a snapshot of

current implementation, rather than a specification

-4-

DARPA Internet Gateway September 1982
RFC 823

3 FORWARDING INTERNET

This section describes how the gateway forwards

between networks. A host computer that wants an IP datagram

reach a host on another network must send the datagram to

gateway to be forwarded. Before it is sent into the network,

host attaches to the datagram a local network header

the address of the gateway

3.1

When a gateway receives a message, the gateway checks

message's local network header for possible errors and

any actions required by the host-to-network protocol.

processing involves functions such as verifying the local

header checksum or generating a local network

message. If the header indicates that the message contains

Internet datagram, the datagram is passed to the Internet

check routine. All other messages received that do not

these tests are discarded

-5-

DARPA Internet Gateway September 1982
RFC 823

3.2 IP Header

The Internet header check routine performs a number

validity tests on the IP header. Datagrams that fail these

are discarded causing an HMP trap to be sent to the

Network Operations Center (INOC) [7]. The following checks

currently performed

o Proper IP Version
o Valid IP Header Length ( >= 20 bytes
o Valid IP Message
o Valid IP Header
o Non-Zero Time to Live

After a datagram passes these checks, its Internet

address is examined to determine if the datagram is addressed

the gateway. Each of the gateway's internet addresses (one

each network interface) is checked against the

address in the datagram. If a match is not found, the

is passed to the forwarding routine

If the datagram is addressed to the gateway itself, the

options in the IP header are processed. Currently, the

supports the following IP options

-6-

DARPA Internet Gateway September 1982
RFC 823

o
o End of Option
o Loose Source and Record
o Strict Source and Record

The datagram is next processed according to the protocol in

IP header. If the protocol is not supported by the gateway,

replies with an ICMP error message and discards the datagram

The gateway does not support IP reassembly, so

datagrams which are addressed to the gateway are discarded

3.3

The gateway must make a routing decision for all

that are to be to forwarded. The routing algorithm provides

pieces of information for the gateway: 1) the network

that should be used to send this datagram and 2) the

address that should be put in the local network header of

datagram

The gateway maintains a dynamic Routing Table which

an entry for each reachable network. The entry consists of

network number and the address of the neighbor gateway on

shortest route to the network, or else an indication that

-7-

DARPA Internet Gateway September 1982
RFC 823

gateway is directly connected to the network. A neighbor

is one which shares a common network with this gateway.

distance metric that is used to determine which neighbor

closest is defined as the "number of hops," where a gateway

considered to be zero hops from its directly connected networks

one hop from a network that is reachable via one other gateway

etc. The Gateway-to-Gateway Protocol (GGP) is used to update

Routing Table (see Section 4.4 describing the Gateway-to-

Protocol).

The gateway tries to match the destination network

in the IP header of the datagram to be forwarded, with a

in its Routing Table. If no match is found, the gateway

the datagram and sends an ICMP Destination Unreachable message

the IP source. If the gateway does find an entry for the

in its table, it will use the network address of the

gateway entry as the local network destination address of

datagram. However, if the final destination network is one

the gateway is directly connected to, the destination address

the local network header is created from the destination

in the IP header of the datagram

-8-

DARPA Internet Gateway September 1982
RFC 823

3.4

If the routing procedure decides that an IP datagram is

be sent back out the same network interface that it was read in

then this gateway is not on the shortest path to the IP

destination. Nevertheless, the datagram will still be

to the next address chosen by the routing procedure. If

datagram is not using the IP Source Route Option, and the

source network of the datagram is the same as the network of

next gateway chosen by the routing procedure, an ICMP

message will be sent to the IP source host indicating

another gateway should be used to send traffic to the final

destination

3.5

The datagram is passed to the fragmentation routine

the routing decision has been made. If the next network

which the datagram must pass has a maximum message size that

smaller than the size of the datagram, the datagram must

fragmented. Fragmentation is performed according to

algorithm described in the Internet Protocol Specification [1].

Certain IP options must be copied into the IP header of

-9-

DARPA Internet Gateway September 1982
RFC 823

fragments, and others appear only in the first fragment

to the IP specification. If a datagram must be fragmented,

the Don't fragment bit is set, the datagram is discarded and

ICMP error message is sent to the IP source of the datagram

3.6 Header

The datagram (or the fragments of the original datagram

fragmentation was needed) is next passed to a routine

rebuilds the Internet header. The Time to Live field

decremented by one and the IP checksum is recomputed

The local network header is now built. Using

information obtained from its routing procedure, the

chooses the network interface it considers proper to send

datagram and to build the destination address in the

network header

3.7

The datagram is now enqueued on an output queue for

towards its destination. A limit is enforced on the size of

output queue for each network interface so that a slow

-10-

DARPA Internet Gateway September 1982
RFC 823

does not unfairly use up all of the gateway's buffers. If

datagram cannot be enqueued due to the limit on the output

length, it is dropped and an HMP trap is sent to the INOC.

traps, and others of a similar nature, are used by

personnel to monitor the operations of the gateways

-11-

DARPA Internet Gateway September 1982
RFC 823

4 PROTOCOLS SUPPORTED BY THE

A number of protocols are supported by the gateway

provide dynamic routing, monitoring, debugging, and

reporting. These protocols are described below

4.1 Cross-Net Debugging

The Cross-Net Debugging Protocol (XNET) [8] is used to

the gateway and to examine and deposit data. The

supports the following XNET op-codes

o
o
o End
o
o
o Create

4.2 Host Monitoring

The Host Monitoring Protocol (HMP) [6] is used to

measurements and status information from the gateways

Exceptional conditions in the gateways are reported in HMP traps

The status of a gateway's interfaces, neighbors, and the

which it can reach are reported in the HMP status message

-12-

DARPA Internet Gateway September 1982
RFC 823

Two types of gateway statistics, the Host Traffic Matrix

the gateway throughput, are currently defined by the HMP.

Host Traffic Matrix records the number of datagrams that

through the gateway with a given IP source, destination,

protocol number. The gateway throughput message collects

number of important counters that are kept by the gateway.

current gateway reports the following values

o Datagrams dropped because destination net

o Datagrams dropped because destination host

o Per Interface
Datagrams received with IP
Datagrams received for this
Datagrams received to be
Datagrams
Bytes
Datagrams sent, originating at this
Datagrams sent to destination
Datagrams dropped due to flow control
Datagrams dropped due to full
Bytes

o Per Neighbor
Routing updates sent
Routing updates received
Datagrams sent, originating
Datagrams forwarded
Datagrams dropped due to flow control
Datagrams dropped due to full
Bytes

-13-

DARPA Internet Gateway September 1982
RFC 823

4.3

The gateway will generate the following ICMP messages

appropriate circumstances as defined by the ICMP

[4]:

o Echo
o Destination
o Source
o
o Time
o Parameter
o Information

4.4 Gateway-to-Gateway

The gateway uses the Gateway-to-Gateway Protocol (GGP)

determine connectivity to networks and neighbor gateways; it

also used in the implementation of a dynamic, shortest-

routing algorithm. The current GGP message formats (for

1003 of the gateway software) are presented in Appendix A

4.4.1 Determining Connectivity to

When a gateway starts running it assumes that all

neighbor gateways are "down," that it is disconnected

-14-

DARPA Internet Gateway September 1982
RFC 823

networks to which it is attached, and that the distance

in routing updates from each neighbor to each network

"infinity."

The gateway first determines the state of its

to networks to which it is physically attached. The gateway'

connection to a network is declared up if it can send and

internet datagrams on its interface to that network. Note

the method that the gateway uses to determine its connectivity

a network is network-dependent. In some networks, the host-to

network protocol determines whether or not datagrams can be

and received on the host interface. In these networks,

gateway simply checks-status information provided by the

in order to determine if it can communicate with the network.

other networks, where the host-to-network protocols are

sophisticated, it may be necessary for the gateway to

datagrams to itself to determine if it can communicate with

network. In these networks, the gateways periodically poll

network using GGP network interface status messages [Appendix A

to determine if the network interface is operational

The gateway has two rules relevant to computing distances

networks: 1) if the gateway can send and receive traffic on

-15-

DARPA Internet Gateway September 1982
RFC 823

network interface, its distance to the network is zero; 2) if

cannot send and receive traffic on the interface, its distance

the network is "infinity." Note that if a gateway's

interface is not working, it may still be able to send traffic

the network on an alternate route via one of its

gateways

4.4.2 Determining Connectivity to

The gateway determines connectivity to neighbors using a "

out of N" algorithm. Every 15 seconds, the gateway sends

Echo messages [Appendix A] to each of its neighbors.

neighbors respond by sending GGP echo replies. If there is

reply to K out of N (current values are K=3 and N=4)

messages sent to a neighbor, the neighbor is declared down. If

neighbor is down and J out of M (current values are J=2 and M=4)

echo replies are received, the neighbor is declared to be up

The values of J,K,M,N and the time interval are

parameters which can be adjusted as required

-16-

DARPA Internet Gateway September 1982
RFC 823

4.4.3 Exchanging Routing

The gateway sends routing information in GGP Routing

messages. The gateway receives and transmits routing

reliably using sequence-numbered messages and a

and acknowledgment scheme as explained below. For each neighbor

the gateway remembers the Receive Sequence Number, R, that

received in the most recent routing update from that neighbor

This value is initialized with the sequence number in the

Routing Update received from a neighbor after that neighbor'

status is set to "up." On receipt of a routing update from

neighbor, the gateway subtracts the Receive Sequence Number, R

from the sequence number in the routing update, S. If this

(S-R) is greater than or equal to zero, then the gateway

the routing update, sends an acknowledgment (see Appendix A)

the neighbor containing the sequence number S, and replaces

Receive Sequence Number, R, with S. If this value (S-R) is

than zero, the gateway rejects the routing update and sends

negative acknowledgment [Appendix A] to the neighbor

sequence number R

The gateway has a Send Sequence Number, N, for

routing updates to all of its neighbors. This sequence

-17-

DARPA Internet Gateway September 1982
RFC 823

can be initialized to any value. The Send Sequence Number

incremented each time a new routing update is created.

receiving an acknowledgment for a routing update, the

subtracts the sequence number acknowledged, A, from the

Sequence Number, N. If the value (N-A) is non-zero, then an

routing update is being acknowledged. The gateway continues

retransmit the most recent routing update to the neighbor

sent the acknowledgment. If (N-A) is zero, the routing

has been acknowledged. Note that only the most recent

update must be acknowledged; if a second routing update

generated before the first routing update is acknowledged,

the second routing update must be acknowledged

If a negative acknowledgment is received, the

subtracts the sequence number negatively acknowledged, A,

its Send Sequence Number, N. If this value (N-A) is less

zero, then the gateway replaces its Send Sequence Number, N,

the sequence number negatively acknowledged plus one, A+1,

retransmits the routing update to all of its neighbors. If (N-A

is greater than or equal to zero, then the gateway continues

retransmit the routing update using sequence number N. In

to maintain the correct sequence numbers at all gateways,

updates must be retransmitted to all neighbors if the

-18-

DARPA Internet Gateway September 1982
RFC 823

Sequence Number changes, even if the routing information does

change

The gateway retransmits routing updates periodically

they are acknowledged and whenever its Send Sequence

changes. The gateway sends routing updates only to

that are in the "up" state

4.4.4 Computing

A routing update contains a list of networks that

reachable through this gateway, and the distance in "number

hops" to each network mentioned. The routing update

contains information about a network if the gateway believes

it is as close or closer to that network then the neighbor

is to receive the routing update. The network address may be

internet class A, B, or C address

The information inside a routing update is processed

follows. The gateway contains an N x K distance matrix, where

is the number of networks and K is the number of

gateways. An entry in this matrix, represented as dm(I,J),

the distance to network I from neighbor J as reported in the

-19-

DARPA Internet Gateway September 1982
RFC 823

recent routing update from neighbor J. The gateway also

a vector indicating the connectivity between itself and

neighbor gateways. The values in this vector are computed

discussed above (see Section 4.4.2, Determining Connectivity

Neighbors). The value of the Jth entry of this vector, which

the connectivity between the gateway and the Jth neighbor,

represented as d(J).

The gateway copies the routing update received from the

neighbor into the appropriate row of the distance matrix,

updates its routes as follows. The gateway calculates a

distance vector which contains the minimum distance to

network from the gateway. The Ith entry of this vector

represented as MinD(I) is

MinD(I) = minimum over all neighbors of d(J) + dm(I,J

where d(J) is the distance between the gateway and the

neighbor, and dm(I,J) is the distance from the Jth neighbor

the Ith network. If the Ith network is attached to the

and the gateway can send and receive traffic on its

interface (see Section 4.4.2), then the gateway sets the

entry of the minimum distance vector to zero

-20-

DARPA Internet Gateway September 1982
RFC 823

Using the minimum distance vector, the gateway computes

list of neighbor gateways through which to send traffic to

network. The entry for a given network contains one of

neighbors that is the minimum distance away from that network

After updating its routes to the networks, the

computes the new routing updates to be sent to its neighbors

The gateway reports a network to a neighbor only if it is

close to or closer to that network than its neighbor. For

network I, the routing update contains the address of the

and the minimum distance to that network which is MinD(I).

Finally, the gateway must determine whether it should

routing updates to its neighbors. The gateway sends new

to its neighbors if every one of the following three

occurs: 1) one of the gateway's interfaces changes state, 2)

one of the gateway's neighbor gateways changes state, and 3)

gateway receives a routing update from a neighbor that

different from the update that it had previously received

that neighbor. The gateway sends routing updates only

neighbors that are currently in the "up" state

The gateway requests a routing update from neighbors

are in the "up" state, but from which it has yet received

-21-

DARPA Internet Gateway September 1982
RFC 823

routing update. Routing updates are requested by setting

appropriate bit in the routing update being sent [Appendix A].

Similarly, if a gateway receives from a neighbor a routing

in which the bit requesting a routing update is set, the

sends the neighbor the most recent routing update

4.4.5 Non-Routing

A Non-routing Gateway is a gateway that forwards

traffic, but does not implement the GGP routing algorithm

Networks that are behind a Non-routing Gateway are known a-

to Routing Gateways. There can be one or more of these

which are considered to be directly connected to the Non-

Gateway. A Routing Gateway will forward a datagram to a Non

routing Gateway if it is addressed to a network behind the Non

routing Gateway. Routing Gateways currently do not

Redirects for Non-routing Gateways. A Routing Gateway

always use another Routing Gateway as a path instead of a Non

routing Gateways if both exist and are the same number of

away from the destination network. The Non-routing Gateways

will be used only when the Routing Gateway path is down; when

Routing Gateway path comes back up, it will be used again

-22-

DARPA Internet Gateway September 1982
RFC 823

4.4.6 Adding New Neighbors and

Gateways dynamically add routing information about

neighbors and new networks to their tables. The

maintains a list of neighbor gateway addresses. When a

update is received, the gateway searches this list of

for the Internet source address of the routing update message

If the Internet source address of the routing update is

contained in the list of neighbor addresses, the gateway

this address to the list of neighbor addresses and sets

neighbor's connectivity status to "down." Routing updates

not accepted from neighbors until the GGP polling mechanism

determined that the neighbor is up

This strategy of adding new neighbors requires that

gateway in each pair of neighbor gateways must have

neighbor's address configured in its tables. The newest

can be given a complete list of neighbors, thus avoiding the

to re-configure older gateways when new gateways are installed

Gateways obtain routing information about new networks

several steps. The gateway has a list of all the networks

which it currently maintains routing information. When a

update is received, if the routing update contains

-23-

DARPA Internet Gateway September 1982
RFC 823

about a new network, the gateway adds this network to the list

networks for which it maintains routing information. Next,

gateway adds the new network to its distance matrix.

distance matrix comprises the is the matrix of distances (

of hops) to networks as reported in routing updates from

neighbor gateways. The gateway sets the distance to all

networks to "infinity," and then computes new routes and

routing updates as outlined above

4.5 Exterior Gateway

The Exterior Gateway Protocol (EGP) is used to permit

gateways and gateway systems to pass routing information to

DARPA Internet gateways. The use of the EGP permits the user

perceive all of the networks and gateways as part of one

Internet system, even though the "exterior" gateways are

and may use a routing algorithm that is different and

compatible with that used in the "interior" gateways.

important elements of the EGP are

o Neighbor

The procedure by which a gateway requests that it become
neighbor of another gateway. This is used when a
wants to become a neighbor of another in order to

-24-

DARPA Internet Gateway September 1982
RFC 823

routing information. This includes the capability to
or refuse the request

o Neighbor Up/

The procedure by which a gateway decides if another
is up or down

o Network Reachability

The facility used to pass routing and neighbor
between gateways

o Gateway Going

The ability of a gateway to inform other gateways that it
going down and no longer has any routes to any
networks. This permits a gateway to go down in an
way without disrupting the rest of the Internet system

A complete description of the EGP can be found in IEN-209,

"Exterior Gateway Protocol" [10].

-25-

DARPA Internet Gateway September 1982
RFC 823

5 GATEWAY

The DARPA Internet Gateway runs under the MOS

system [9] which provides facilities for

o Multiple
o Interprocess
o Buffer
o Asynchronous input/
o Shareable real-time

There is a MOS process for each network that the gateway

directly connected to. A data structure called a

contains variables of interest for each network and pointers

local network routines. Network processes run common

code while network-specific functions are dispatched to

routines pointed to in the NETBLOCK. There are also

for gateway functions which require their own timing, such as

and HMP

5.1 Software

The gateway software can be divided conceptually into

parts: MOS Device Drivers, Network software, and Shared

software

-26-

DARPA Internet Gateway September 1982
RFC 823

5.1.1 Device

The gateway has a set of routines to handle sending

receiving data for each type of hardware interface. There

routines for initialization, initiation, and interruption

both the transmit and receive sides of a device. The

supports the following types of devices

a) ACC LSI-11 1822
b) DEC IMP11a 1822
c) ACC LHDH 1822
d) ACC VDH11
e) ACC VDH11
f) Proteon Ring
g) RSRE
h) Interlan
i) BBN
j) ACC XQ/CP X.25 **
k) ACC XQ/CP HDH **

5.1.2 Network

For each connected network, the gateway has a set of

routines which handle local network functions. The

routines and their functions are described briefly below

_______________
** Planned, not yet supported

-27-

DARPA Internet Gateway September 1982
RFC 823

Up.net Perform local network initialization such
flapping the 1822 ready line

Sg.net Handle specific local network timing
such as timing out 1822 Destination Deads

Rc.net A message has been received from the
interface. Check for any input errors

Wc.net A message has been transmitted to the
interface. Check for any output errors

Rs.net Set up a buffer (or buffers) to receive
on the network interface

Ws.net Transmit a message to the network interface

Hc.net Check the local network header of the
message. Perform any local network
tasks

Hb.net Rebuild the local network header

There are network routines for the following types

networks

o Arpanet (a,b,c,k
o Satnet (d,e,k
o Proteon Ring Network (f
o Packet Radio Network (a,b,c
o Rsre HDLC Null Network (g
o Ethernet (h
o Fibernet (i
o Telenet X.25 (j) **

Note: The letters in parentheses refer to the device drivers

_______________
** Planned, not yet supported

-28-

DARPA Internet Gateway September 1982
RFC 823

for each type of network as described in the previous section

5.1.3 Shared Gateway

The internet processing of a datagram is performed by a

of code which is shared by the network processes. This

includes routines to check the IP header, perform

fragmentation, calculate the IP checksum, forward a datagram,

implement the routing, monitoring, and error reporting protocols

5.2 Gateway

5.2.1 Network

When the gateway starts up, each network process calls

local network initialization routine and read start routine.

read start routine sets up two maximum network size buffers

receiving datagrams. The network process then waits for an

complete signal from the network device driver

When a message has been received, the MOS Operating

signals the appropriate network process with an input

signal. The network process wakes up and executes the net

-29-

DARPA Internet Gateway September 1982
RFC 823

complete routine. After the message has been processed,

network process waits for more input

The net read complete routine is the major

processing loop in the gateway. The following actions

performed when a message has been received

o Call Local Network Read Complete
o Start more
o Check local Network
o Check Internet
o Check if datagram is for the
o Forward the datagram if
o Send ICMP error message if necessary

5.2.2 GGP

The GGP process periodically sends GGP echos to each of

gateway's neighbors to determine neighbor connectivity, and

interface status messages addressed to itself to

network connectivity. The GGP process also sends out

updates when necessary. The details of the algorithms

implemented by the GGP process are given in Section 4.4,

Gateway-to-Gateway Protocol, and in Appendix C

-30-

DARPA Internet Gateway September 1982
RFC 823

5.2.3 HMP

The HMP process handles timer-based gateway

collection and the periodic transmission of traps

-31-

DARPA Internet Gateway September 1982
RFC 823

APPENDIX A. GGP Message

Note that the GGP protocol is currently undergoing

changes to introduce the Exterior Gateway Protocol facility;

is the vehicle needed to permit gateways in other systems

exchange routing information with the gateways described in

document

Each GGP message consists of an Internet header followed

one of the messages explained below. The values (in decimal)

the Internet header used in a GGP message are as follows

Version 4.

IHL Internet header length in 32-bit words

Type of Service 0.

Total Length Length of Internet header and data
octets

ID, Flags
Fragment Offset 0.

Time to Live Time to live in seconds. This field
decremented at least once by
machine that processes the datagram

Protocol Gateway Protocol = 3.

Header Checksum The 16 bit one's complement of the one'
complement sum of all 16-bit words
the header. For computing the checksum
the checksum field should be zero

-32-

DARPA Internet Gateway September 1982
RFC 823

Source Address The address of the gateway's
from which the message is sent

Destination Address The address of the gateway to which
message is sent

-33-

DARPA Internet Gateway September 1982
RFC 823

ROUTING

0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!Gateway Type ! unused (0) ! ; 2
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! Sequence Number ! ; 2
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! need-update ! n-distances ! ; 2
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! distance 1 ! n1-dist ! ; 2
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! net11 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; 1, 2 or 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ;
! net12 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; 1, 2 or 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ;
.
.
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! net1n1 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; n1 nets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ; dist 1
. ...
. ; ndist
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ; of
! distance n ! nn-dist ! ; 2
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! netn1 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; 1, 2 or 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ;
! netn2 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; 1, 2 or 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ;
.
.
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! netnnn !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; nn nets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ; dist

Gateway Type 12 (decimal

Sequence Number The 16-bit sequence number used
identify routing updates

need-update An 8-bit field. This byte is set to 1

-34-

DARPA Internet Gateway September 1982
RFC 823

if the source gateway requests a
update from the destination gateway,
set to 0 if not

n-distances An 8-bit field. The number
distance-groups reported in this update
Each distance-group consists of
distance value and a number of nets
followed by the actual net numbers
are reachable at that distance. Not
distances need be reported

distance 1 hop count (or other distance measure
which applies to this distance-group

n1-dist number of nets which are reported
this distance-group

net11 1, 2, or 3 bytes for the first net
distance "distance 1".

net12 second

...

net1n1 etc

-35-

DARPA Internet Gateway September 1982
RFC 823

ACKNOWLEDGMENT or NEGATIVE

0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Gateway Type | Unused | Sequence number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Gateway Type Acknowledgments are type 2.
acknowledgments are type 10.

Sequence Number The 16-bit sequence number that
gateway is acknowledging or
acknowledging

-36-

DARPA Internet Gateway September 1982
RFC 823

GGP ECHO and ECHO

0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Gateway Type | Unused |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Gateway Type 8 for echo message; 0 for echo reply

Source Address In an echo message, this is the
of the gateway on the same network
the neighbor to which it is sending
echo message. In an echo reply message
the source and destination addresses
simply reversed, and the remainder
returned unchanged

-37-

DARPA Internet Gateway September 1982
RFC 823

NETWORK INTERFACE

0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! Gateway Type ! unused !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Gateway Type 9

Source
Destination Address The address of the gateway's
interface. The gateway can send
Interface Status messages to itself
determine if it is able to send
receive traffic on its
interface

-38-

DARPA Internet Gateway September 1982
RFC 823

APPENDIX B. Information Maintained by

In order to implement the shortest-path routing algorithm

gateways must maintain information about their connectivity

networks and other gateways. This section explains

information maintained by each gateway; this information can

organized into the following tables and variables

o Number of

The number of networks for which the gateway
routing information and to which it can forward traffic

o Number of

The number of neighbor gateways with which the
exchanges routing information

o Gateway

The addresses of the gateway's network interfaces

o Neighbor Gateway

The address of each neighbor gateway's network
that is on the same network as this gateway

o Neighbor Connectivity

A vector of the connectivity between this gateway and
of its neighbors

o Distance

A matrix of the routing updates received from the
gateways

-39-

DARPA Internet Gateway September 1982
RFC 823

o Minimum Distance

A vector containing the minimum distance to each network

o Routing Updates from Non-Routing

The routing updates that would have been received from
non-routing neighbor gateway which does not participate
this routing strategy

o Routing

A table containing, for each network, a list of the
gateways on a minimum-distance route to the network

o Send Sequence

The sequence number that will be used to send the
routing update

o Receive Sequence

The sequence numbers that the gateway received in the
routing update from each of its neighbors

o Received Acknowledgment

A vector indicating whether or not each neighbor
acknowledged the sequence number in the most recent
update sent

-40-

DARPA Internet Gateway September 1982
RFC 823

APPENDIX C. GGP Events and

The following list shows the GGP events that occur at

gateway and the gateway's responses. The variables and

referred to are listed above

o Connectivity to an attached network changes

a. Update the Minimum Distance Vector
b. Recompute the Routing Updates
c. Recompute the Routing Table
d. If any routing update has changed, send the new
updates to the neighbors

o Connectivity to a neighbor gateway changes

a. Update the Neighbor Connectivity Vector
b. Recompute the Minimum Distance Vector
c. Recompute the Routing Updates
d. Recompute the Routing Table
e. If any routing update has changed, send the new
updates to the neighbors

o A Routing Update message is received

a. Compare the Internet source address of the Routing
message to the Neighbor Addresses. If the address is
on the list, add it to the list of Neighbor Addresses
increment the Number of Neighbors, and set the
Sequence Number for this neighbor to the sequence
in the Routing Update message

b. Compare the Receive Sequence Number for this neighbor
the sequence number in the Routing Update message
determine whether or not to accept this message. If
message is rejected, send a Negative
message. If the message is accepted, send
Acknowledgment message and proceed with the
steps

-41-

DARPA Internet Gateway September 1982
RFC 823

c. Compare the networks reported in the Routing
message to the Number of Networks. If new networks
reported, enter them in the network vectors, increase
number of networks, and expand the Distance Matrix
account for the new networks

d. Copy the routing update received into the appropriate
of the Distance Matrix

e. Recompute the Minimum Distance Vector

f. Recompute the Routing Updates

g. Recompute the Routing Table

h. If any routing update has changed, send the new
updates to the neighbors

o An Acknowledgment message is received

Compare the sequence number in the message to the
Sequence Number. If the Send Sequence Number
acknowledged, update the entry in the
Acknowledgment Vector for the neighbor that sent
acknowledgment

o A Negative Acknowledgment message is received

Compare the sequence number in the message to the
Sequence Number. If necessary, replace the Send
Number, and retransmit the routing updates

-42-

DARPA Internet Gateway September 1982
RFC 823

[1] Postel, J. (ed.), "Internet Protocol - DARPA
Program Protocol Specification," RFC 791, USC/
Sciences Institute, September 1981.

[2] Strazisar, V., "Gateway Routing: An
Specification," IEN-30, Bolt Beranek and Newman Inc.,
1979.

[3] Strazisar, V., "How to Build a Gateway," IEN-109,
Beranek and Newman Inc., August 1979.

[4] Postel, J., "Internet Control Message Protocol -
Internet Program Protocol Specification," RFC 792,
USC/Information Sciences Institute, September 1981.

[5] Postel, J., "Assigned Numbers," RFC 790, USC/
Sciences Institute, September 1981.

[6] Littauer, B., Huang, A., Hinden, R., "A Host
Protocol," IEN-197, Bolt Beranek and Newman Inc.,
1981.

[7] Santos, P., Chalstrom, H., Linn, J., Herman, J.,
"Architecture of a Network Monitoring, Control
Management System," Proc. of the 5th Int. Conference
Computer Communication, October 1980.

[8] Haverty, J., "XNET Formats for Internet Protocol Version 4,"
IEN-158, Bolt Beranek and Newman Inc., October 1980.

[9] Mathis, J., Klemba, K., Poggio, "TIU Notebook- Volume 2,
Software Documentation," SRI, May 1979.

[10] Rosen, E., "Exterior Gateway Protocol," IEN-209,
Beranek and Newman Inc., August 1982.

-43-

if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.

RFC documents can be found at I.E.T.F.

Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX