DARPA Internet gateway
A status report on the router that ran the early Internet, and the protocols it used.
Hinden, R.M. and A. Sheltzer, "DARPA Internet gateway", RFC 823, DOI 10.17487/RFC0823, September 1982, <https://www.rfc-editor.org/info/rfc823>.
@misc{rfc823,
series = {Request for Comments},
number = 823,
howpublished = {RFC 823},
publisher = {RFC Editor},
doi = {10.17487/RFC0823},
url = {https://www.rfc-editor.org/info/rfc823},
author = {R.M. Hinden and A. Sheltzer},
title = {{DARPA Internet gateway}},
pagetotal = 45,
year = 1982,
month = sep,
} RFC text
Request for Comments: 823
Obsoletes IEN-30 and IEN-109
THE DARPA INTERNET GATEWAY
RFC 823
Robert Hinden
Alan Sheltzer
Bolt Beranek and Newman Inc.
10 Moulton St.
Cambridge, Massachusetts 02238
September 1982
Prepared for
Defense Advanced Research Projects Agency
Information Processing Techniques Office
1400 Wilson Boulevard
Arlington, Virginia 22209
This RFC is a status report on the Internet Gateway developed by BBN. It
describes the Internet Gateway as of September 1982. This memo presents
detailed descriptions of message formats and gateway procedures, however
this is not an implementation specification, and such details are
subject to change.
RFC 823
Table of Contents
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-
RFC 823
1 INTRODUCTION
This document explains the design of the Internet gateway
used in the Defense Advanced Research Project Agency (DARPA)
Internet program. The gateway design was originally documented
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 internet
protocols and in the gateway design since these documents were
released. It supersedes both IEN-30 and IEN-109.
The Internet gateway described in this document is based on
the work of many people; in particular, special credit is given
to V. Strazisar, M. Brescia, E. Rosen, and J. Haverty.
The gateway's primary purpose is to route internet datagrams
to their destination networks. These datagrams are generated and
processed as described in RFC 791, "Internet Protocol - DARPA
Internet Program Protocol Specification" [1]. This document
describes how the gateway forwards datagrams, the routing
algorithm and protocol used to route them, and the software
structure of the current gateway. The current gateway
implementation is written in macro-11 assembly language and runs
in the DEC PDP-11 or LSI-11 16-bit processor.
RFC 823
2 BACKGROUND
The gateway system has undergone a series of changes since
its inception, and it is continuing to evolve as research
proceeds in the Internet community. This document describes the
implementation as of mid-1982.
Early versions of gateway software were implemented using
the BCPL language and the ELF operating system. This
implementation evolved into one which used the MOS operating
system for increased performance. In late 1981, we began an
effort to produce a totally new gateway implementation. The
primary motivation for this was the need for a system oriented
towards the requirements of an operational communications
facility, rather than the research testbed environment which was
associated with the BCPL implementation. In addition, it was
generally recognized that the complexity and buffering
requirements of future gateway configurations were beyond the
capabilities of the PDP-11/LSI-11 and BCPL architecture. The new
gateway implementation therefore had a second goal of producing a
highly space-efficient implementation in order to provide space
for buffers and for the extra mechanisms, such as monitoring,
which are needed for an operational environment.
RFC 823
This document describes the implementation of this new
gateway which incorporates several mechanisms for operations
activities, is coded in assembly language for maximum space-
efficiency, but otherwise is fundamentally the same architecture
as the older, research-oriented, implementations.
One of the results of recent research is the thesis that
gateways should be viewed as elements of a gateway system, where
the gateways act as a loosely-coupled packet-switching
communications system. For reasons of maintainability and
operability, it is easiest to build such a system in an
homogeneous fashion where all gateways are under a single
authority and control, as is the practice in other network
implementations.
In order to create a system architecture that permitted
multiple sets of gateways with each set under single control but
acting together to implement a composite single Internet System,
new protocols needed to be developed. These protocols, such as
the "Exterior Gateway Protocol," will be introduced in the later
releases of the gateway implementation.
We also anticipate further changes to the gateway
architecture and implementation to introduce support for new
RFC 823
capabilities, such as large numbers of networks, access control,
and other requirements which have been proposed by the Internet
research community. This document represents a snapshot of the
current implementation, rather than a specification.
RFC 823
3 FORWARDING INTERNET DATAGRAMS
This section describes how the gateway forwards datagrams
between networks. A host computer that wants an IP datagram to
reach a host on another network must send the datagram to a
gateway to be forwarded. Before it is sent into the network, the
host attaches to the datagram a local network header containing
the address of the gateway.
3.1 Input
When a gateway receives a message, the gateway checks the
message's local network header for possible errors and performs
any actions required by the host-to-network protocol. This
processing involves functions such as verifying the local network
header checksum or generating a local network acknowledgment
message. If the header indicates that the message contains an
Internet datagram, the datagram is passed to the Internet header
check routine. All other messages received that do not pass
these tests are discarded.
RFC 823
3.2 IP Header Checks
The Internet header check routine performs a number of
validity tests on the IP header. Datagrams that fail these tests
are discarded causing an HMP trap to be sent to the Internet
Network Operations Center (INOC) [7]. The following checks are
currently performed:
o Proper IP Version Number
o Valid IP Header Length ( >= 20 bytes)
o Valid IP Message Length
o Valid IP Header Checksum
o Non-Zero Time to Live field
After a datagram passes these checks, its Internet destination
address is examined to determine if the datagram is addressed to
the gateway. Each of the gateway's internet addresses (one for
each network interface) is checked against the destination
address in the datagram. If a match is not found, the datagram
is passed to the forwarding routine.
If the datagram is addressed to the gateway itself, the IP
options in the IP header are processed. Currently, the gateway
supports the following IP options:
RFC 823
o NOP
o End of Option List
o Loose Source and Record Route
o Strict Source and Record Route
The datagram is next processed according to the protocol in the
IP header. If the protocol is not supported by the gateway, it
replies with an ICMP error message and discards the datagram.
The gateway does not support IP reassembly, so fragmented
datagrams which are addressed to the gateway are discarded.
3.3 Routing
The gateway must make a routing decision for all datagrams
that are to be to forwarded. The routing algorithm provides two
pieces of information for the gateway: 1) the network interface
that should be used to send this datagram and 2) the destination
address that should be put in the local network header of the
datagram.
The gateway maintains a dynamic Routing Table which contains
an entry for each reachable network. The entry consists of a
network number and the address of the neighbor gateway on the
shortest route to the network, or else an indication that the
RFC 823
gateway is directly connected to the network. A neighbor gateway
is one which shares a common network with this gateway. The
distance metric that is used to determine which neighbor is
closest is defined as the "number of hops," where a gateway is
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 the
Routing Table (see Section 4.4 describing the Gateway-to-Gateway
Protocol).
The gateway tries to match the destination network address
in the IP header of the datagram to be forwarded, with a network
in its Routing Table. If no match is found, the gateway drops
the datagram and sends an ICMP Destination Unreachable message to
the IP source. If the gateway does find an entry for the network
in its table, it will use the network address of the neighbor
gateway entry as the local network destination address of the
datagram. However, if the final destination network is one that
the gateway is directly connected to, the destination address in
the local network header is created from the destination address
in the IP header of the datagram.
RFC 823
3.4 Redirects
If the routing procedure decides that an IP datagram is to
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 final
destination. Nevertheless, the datagram will still be forwarded
to the next address chosen by the routing procedure. If the
datagram is not using the IP Source Route Option, and the IP
source network of the datagram is the same as the network of the
next gateway chosen by the routing procedure, an ICMP Redirect
message will be sent to the IP source host indicating that
another gateway should be used to send traffic to the final IP
destination.
3.5 Fragmentation
The datagram is passed to the fragmentation routine after
the routing decision has been made. If the next network through
which the datagram must pass has a maximum message size that is
smaller than the size of the datagram, the datagram must be
fragmented. Fragmentation is performed according to the
algorithm described in the Internet Protocol Specification [1].
Certain IP options must be copied into the IP header of all
RFC 823
fragments, and others appear only in the first fragment according
to the IP specification. If a datagram must be fragmented, but
the Don't fragment bit is set, the datagram is discarded and an
ICMP error message is sent to the IP source of the datagram.
3.6 Header Rebuild
The datagram (or the fragments of the original datagram if
fragmentation was needed) is next passed to a routine that
rebuilds the Internet header. The Time to Live field is
decremented by one and the IP checksum is recomputed.
The local network header is now built. Using the
information obtained from its routing procedure, the gateway
chooses the network interface it considers proper to send the
datagram and to build the destination address in the local
network header.
3.7 Output
The datagram is now enqueued on an output queue for delivery
towards its destination. A limit is enforced on the size of the
output queue for each network interface so that a slow network
RFC 823
does not unfairly use up all of the gateway's buffers. If a
datagram cannot be enqueued due to the limit on the output queue
length, it is dropped and an HMP trap is sent to the INOC. These
traps, and others of a similar nature, are used by operational
personnel to monitor the operations of the gateways.
RFC 823
4 PROTOCOLS SUPPORTED BY THE GATEWAY
A number of protocols are supported by the gateway to
provide dynamic routing, monitoring, debugging, and error
reporting. These protocols are described below.
4.1 Cross-Net Debugging Protocol
The Cross-Net Debugging Protocol (XNET) [8] is used to load
the gateway and to examine and deposit data. The gateway
supports the following XNET op-codes:
o NOP
o Debug
o End Debug
o Deposit
o Examine
o Create Process
4.2 Host Monitoring Protocol
The Host Monitoring Protocol (HMP) [6] is used to collect
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 networks
which it can reach are reported in the HMP status message.
RFC 823
Two types of gateway statistics, the Host Traffic Matrix and
the gateway throughput, are currently defined by the HMP. The
Host Traffic Matrix records the number of datagrams that pass
through the gateway with a given IP source, destination, and
protocol number. The gateway throughput message collects a
number of important counters that are kept by the gateway. The
current gateway reports the following values:
o Datagrams dropped because destination net unreachable
o Datagrams dropped because destination host unreachable
o Per Interface:
Datagrams received with IP errors
Datagrams received for this gateway
Datagrams received to be forwarded
Datagrams looped
Bytes received
Datagrams sent, originating at this gateway
Datagrams sent to destination hosts
Datagrams dropped due to flow control limitations
Datagrams dropped due to full queue
Bytes sent
o Per Neighbor:
Routing updates sent to
Routing updates received from
Datagrams sent, originating here
Datagrams forwarded to
Datagrams dropped due to flow control limitations
Datagrams dropped due to full queue
Bytes sent
RFC 823
4.3 ICMP
The gateway will generate the following ICMP messages under
appropriate circumstances as defined by the ICMP specification
[4]:
o Echo Reply
o Destination Unreachable
o Source Quench
o Redirect
o Time Exceeded
o Parameter Problem
o Information Reply
4.4 Gateway-to-Gateway Protocol
The gateway uses the Gateway-to-Gateway Protocol (GGP) to
determine connectivity to networks and neighbor gateways; it is
also used in the implementation of a dynamic, shortest-path
routing algorithm. The current GGP message formats (for release
1003 of the gateway software) are presented in Appendix A.
4.4.1 Determining Connectivity to Networks
When a gateway starts running it assumes that all its
neighbor gateways are "down," that it is disconnected from
RFC 823
networks to which it is attached, and that the distance reported
in routing updates from each neighbor to each network is
"infinity."
The gateway first determines the state of its connectivity
to networks to which it is physically attached. The gateway's
connection to a network is declared up if it can send and receive
internet datagrams on its interface to that network. Note that
the method that the gateway uses to determine its connectivity to
a network is network-dependent. In some networks, the host-to-
network protocol determines whether or not datagrams can be sent
and received on the host interface. In these networks, the
gateway simply checks-status information provided by the protocol
in order to determine if it can communicate with the network. In
other networks, where the host-to-network protocols are less
sophisticated, it may be necessary for the gateway to send
datagrams to itself to determine if it can communicate with the
network. In these networks, the gateways periodically poll the
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 to
networks: 1) if the gateway can send and receive traffic on its
RFC 823
network interface, its distance to the network is zero; 2) if it
cannot send and receive traffic on the interface, its distance to
the network is "infinity." Note that if a gateway's network
interface is not working, it may still be able to send traffic to
the network on an alternate route via one of its neighbor
gateways.
4.4.2 Determining Connectivity to Neighbors
The gateway determines connectivity to neighbors using a "K
out of N" algorithm. Every 15 seconds, the gateway sends GGP
Echo messages [Appendix A] to each of its neighbors. The
neighbors respond by sending GGP echo replies. If there is no
reply to K out of N (current values are K=3 and N=4) echo
messages sent to a neighbor, the neighbor is declared down. If a
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 operational
parameters which can be adjusted as required.
RFC 823
4.4.3 Exchanging Routing Information
The gateway sends routing information in GGP Routing Update
messages. The gateway receives and transmits routing information
reliably using sequence-numbered messages and a retransmission
and acknowledgment scheme as explained below. For each neighbor,
the gateway remembers the Receive Sequence Number, R, that it
received in the most recent routing update from that neighbor.
This value is initialized with the sequence number in the first
Routing Update received from a neighbor after that neighbor's
status is set to "up." On receipt of a routing update from a
neighbor, the gateway subtracts the Receive Sequence Number, R,
from the sequence number in the routing update, S. If this value
(S-R) is greater than or equal to zero, then the gateway accepts
the routing update, sends an acknowledgment (see Appendix A) to
the neighbor containing the sequence number S, and replaces the
Receive Sequence Number, R, with S. If this value (S-R) is less
than zero, the gateway rejects the routing update and sends a
negative acknowledgment [Appendix A] to the neighbor with
sequence number R.
The gateway has a Send Sequence Number, N, for sending
routing updates to all of its neighbors. This sequence number
RFC 823
can be initialized to any value. The Send Sequence Number is
incremented each time a new routing update is created. On
receiving an acknowledgment for a routing update, the gateway
subtracts the sequence number acknowledged, A, from the Send
Sequence Number, N. If the value (N-A) is non-zero, then an old
routing update is being acknowledged. The gateway continues to
retransmit the most recent routing update to the neighbor that
sent the acknowledgment. If (N-A) is zero, the routing update
has been acknowledged. Note that only the most recent routing
update must be acknowledged; if a second routing update is
generated before the first routing update is acknowledged, only
the second routing update must be acknowledged.
If a negative acknowledgment is received, the gateway
subtracts the sequence number negatively acknowledged, A, from
its Send Sequence Number, N. If this value (N-A) is less than
zero, then the gateway replaces its Send Sequence Number, N, with
the sequence number negatively acknowledged plus one, A+1, and
retransmits the routing update to all of its neighbors. If (N-A)
is greater than or equal to zero, then the gateway continues to
retransmit the routing update using sequence number N. In order
to maintain the correct sequence numbers at all gateways, routing
updates must be retransmitted to all neighbors if the Send
RFC 823
Sequence Number changes, even if the routing information does not
change.
The gateway retransmits routing updates periodically until
they are acknowledged and whenever its Send Sequence Number
changes. The gateway sends routing updates only to neighbors
that are in the "up" state.
4.4.4 Computing Routes
A routing update contains a list of networks that are
reachable through this gateway, and the distance in "number of
hops" to each network mentioned. The routing update only
contains information about a network if the gateway believes that
it is as close or closer to that network then the neighbor which
is to receive the routing update. The network address may be an
internet class A, B, or C address.
The information inside a routing update is processed as
follows. The gateway contains an N x K distance matrix, where N
is the number of networks and K is the number of neighbor
gateways. An entry in this matrix, represented as dm(I,J), is
the distance to network I from neighbor J as reported in the most
RFC 823
recent routing update from neighbor J. The gateway also contains
a vector indicating the connectivity between itself and its
neighbor gateways. The values in this vector are computed as
discussed above (see Section 4.4.2, Determining Connectivity to
Neighbors). The value of the Jth entry of this vector, which is
the connectivity between the gateway and the Jth neighbor, is
represented as d(J).
The gateway copies the routing update received from the Jth
neighbor into the appropriate row of the distance matrix, then
updates its routes as follows. The gateway calculates a minimum
distance vector which contains the minimum distance to each
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 Jth
neighbor, and dm(I,J) is the distance from the Jth neighbor to
the Ith network. If the Ith network is attached to the gateway
and the gateway can send and receive traffic on its network
interface (see Section 4.4.2), then the gateway sets the Ith
entry of the minimum distance vector to zero.
RFC 823
Using the minimum distance vector, the gateway computes a
list of neighbor gateways through which to send traffic to each
network. The entry for a given network contains one of the
neighbors that is the minimum distance away from that network.
After updating its routes to the networks, the gateway
computes the new routing updates to be sent to its neighbors.
The gateway reports a network to a neighbor only if it is as
close to or closer to that network than its neighbor. For each
network I, the routing update contains the address of the network
and the minimum distance to that network which is MinD(I).
Finally, the gateway must determine whether it should send
routing updates to its neighbors. The gateway sends new updates
to its neighbors if every one of the following three conditions
occurs: 1) one of the gateway's interfaces changes state, 2)
one of the gateway's neighbor gateways changes state, and 3) the
gateway receives a routing update from a neighbor that is
different from the update that it had previously received from
that neighbor. The gateway sends routing updates only to
neighbors that are currently in the "up" state.
The gateway requests a routing update from neighbors that
are in the "up" state, but from which it has yet received a
RFC 823
routing update. Routing updates are requested by setting the
appropriate bit in the routing update being sent [Appendix A].
Similarly, if a gateway receives from a neighbor a routing update
in which the bit requesting a routing update is set, the gateway
sends the neighbor the most recent routing update.
4.4.5 Non-Routing Gateways
A Non-routing Gateway is a gateway that forwards internet
traffic, but does not implement the GGP routing algorithm.
Networks that are behind a Non-routing Gateway are known a-priori
to Routing Gateways. There can be one or more of these networks
which are considered to be directly connected to the Non-routing
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 send
Redirects for Non-routing Gateways. A Routing Gateway will
always use another Routing Gateway as a path instead of a Non-
routing Gateways if both exist and are the same number of hops
away from the destination network. The Non-routing Gateways path
will be used only when the Routing Gateway path is down; when the
Routing Gateway path comes back up, it will be used again.
RFC 823
4.4.6 Adding New Neighbors and Networks
Gateways dynamically add routing information about new
neighbors and new networks to their tables. The gateway
maintains a list of neighbor gateway addresses. When a routing
update is received, the gateway searches this list of addresses
for the Internet source address of the routing update message.
If the Internet source address of the routing update is not
contained in the list of neighbor addresses, the gateway adds
this address to the list of neighbor addresses and sets the
neighbor's connectivity status to "down." Routing updates are
not accepted from neighbors until the GGP polling mechanism has
determined that the neighbor is up.
This strategy of adding new neighbors requires that one
gateway in each pair of neighbor gateways must have the
neighbor's address configured in its tables. The newest gateway
can be given a complete list of neighbors, thus avoiding the need
to re-configure older gateways when new gateways are installed.
Gateways obtain routing information about new networks in
several steps. The gateway has a list of all the networks for
which it currently maintains routing information. When a routing
update is received, if the routing update contains information
RFC 823
about a new network, the gateway adds this network to the list of
networks for which it maintains routing information. Next, the
gateway adds the new network to its distance matrix. The
distance matrix comprises the is the matrix of distances (number
of hops) to networks as reported in routing updates from the
neighbor gateways. The gateway sets the distance to all new
networks to "infinity," and then computes new routes and new
routing updates as outlined above.
4.5 Exterior Gateway Protocol
The Exterior Gateway Protocol (EGP) is used to permit other
gateways and gateway systems to pass routing information to the
DARPA Internet gateways. The use of the EGP permits the user to
perceive all of the networks and gateways as part of one total
Internet system, even though the "exterior" gateways are disjoint
and may use a routing algorithm that is different and not
compatible with that used in the "interior" gateways. The
important elements of the EGP are:
o Neighbor Acquisition
The procedure by which a gateway requests that it become a
neighbor of another gateway. This is used when a gateway
wants to become a neighbor of another in order to pass
RFC 823
routing information. This includes the capability to accept
or refuse the request.
o Neighbor Up/Down
The procedure by which a gateway decides if another gateway
is up or down.
o Network Reachability Information
The facility used to pass routing and neighbor information
between gateways.
o Gateway Going Down
The ability of a gateway to inform other gateways that it is
going down and no longer has any routes to any other
networks. This permits a gateway to go down in an orderly
way without disrupting the rest of the Internet system.
A complete description of the EGP can be found in IEN-209, the
"Exterior Gateway Protocol" [10].
RFC 823
5 GATEWAY SOFTWARE
The DARPA Internet Gateway runs under the MOS operating
system [9] which provides facilities for:
o Multiple processes
o Interprocess communication
o Buffer management
o Asynchronous input/output
o Shareable real-time clock
There is a MOS process for each network that the gateway is
directly connected to. A data structure called a NETBLOCK
contains variables of interest for each network and pointers to
local network routines. Network processes run common gateway
code while network-specific functions are dispatched to the
routines pointed to in the NETBLOCK. There are also processes
for gateway functions which require their own timing, such as GGP
and HMP.
5.1 Software Structure
The gateway software can be divided conceptually into three
parts: MOS Device Drivers, Network software, and Shared Gateway
software.
RFC 823
5.1.1 Device Drivers
The gateway has a set of routines to handle sending and
receiving data for each type of hardware interface. There are
routines for initialization, initiation, and interruption for
both the transmit and receive sides of a device. The gateway
supports the following types of devices:
a) ACC LSI-11 1822
b) DEC IMP11a 1822
c) ACC LHDH 1822
d) ACC VDH11E
e) ACC VDH11C
f) Proteon Ring Network
g) RSRE HDLC
h) Interlan Ethernet
i) BBN Fibernet
j) ACC XQ/CP X.25 **
k) ACC XQ/CP HDH **
5.1.2 Network Software
For each connected network, the gateway has a set of eight
routines which handle local network functions. The network
routines and their functions are described briefly below.
_______________
** Planned, not yet supported.
RFC 823
Up.net Perform local network initialization such as
flapping the 1822 ready line.
Sg.net Handle specific local network timing functions
such as timing out 1822 Destination Deads.
Rc.net A message has been received from the network
interface. Check for any input errors.
Wc.net A message has been transmitted to the network
interface. Check for any output errors.
Rs.net Set up a buffer (or buffers) to receive messages
on the network interface.
Ws.net Transmit a message to the network interface.
Hc.net Check the local network header of the received
message. Perform any local network protocol
tasks.
Hb.net Rebuild the local network header.
There are network routines for the following types of
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 used
_______________
** Planned, not yet supported.
RFC 823
for each type of network as described in the previous section.
5.1.3 Shared Gateway Software
The internet processing of a datagram is performed by a body
of code which is shared by the network processes. This code
includes routines to check the IP header, perform IP
fragmentation, calculate the IP checksum, forward a datagram, and
implement the routing, monitoring, and error reporting protocols.
5.2 Gateway Processes
5.2.1 Network Processes
When the gateway starts up, each network process calls its
local network initialization routine and read start routine. The
read start routine sets up two maximum network size buffers for
receiving datagrams. The network process then waits for an input
complete signal from the network device driver.
When a message has been received, the MOS Operating System
signals the appropriate network process with an input complete
signal. The network process wakes up and executes the net read
RFC 823
complete routine. After the message has been processed, the
network process waits for more input.
The net read complete routine is the major message
processing loop in the gateway. The following actions are
performed when a message has been received:
o Call Local Network Read Complete Routine
o Start more reads
o Check local Network Header
o Check Internet header
o Check if datagram is for the gateway
o Forward the datagram if necessary
o Send ICMP error message if necessary.
5.2.2 GGP Process
The GGP process periodically sends GGP echos to each of the
gateway's neighbors to determine neighbor connectivity, and sends
interface status messages addressed to itself to determine
network connectivity. The GGP process also sends out routing
updates when necessary. The details of the algorithms currently
implemented by the GGP process are given in Section 4.4,
Gateway-to-Gateway Protocol, and in Appendix C.
RFC 823
5.2.3 HMP Process
The HMP process handles timer-based gateway statistics
collection and the periodic transmission of traps.
RFC 823
APPENDIX A. GGP Message Formats
Note that the GGP protocol is currently undergoing extensive
changes to introduce the Exterior Gateway Protocol facility; this
is the vehicle needed to permit gateways in other systems to
exchange routing information with the gateways described in this
document.
Each GGP message consists of an Internet header followed by
one of the messages explained below. The values (in decimal) in
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 in
octets.
ID, Flags,
Fragment Offset 0.
Time to Live Time to live in seconds. This field is
decremented at least once by each
machine that processes the datagram.
Protocol Gateway Protocol = 3.
Header Checksum The 16 bit one's complement of the one's
complement sum of all 16-bit words in
the header. For computing the checksum,
the checksum field should be zero.
RFC 823
Source Address The address of the gateway's interface
from which the message is sent.
Destination Address The address of the gateway to which the
message is sent.
RFC 823
ROUTING UPDATE
0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!Gateway Type ! unused (0) ! ; 2 bytes
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! Sequence Number ! ; 2 bytes
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! need-update ! n-distances ! ; 2 bytes
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! distance 1 ! n1-dist ! ; 2 bytes
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! net11 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; 1, 2 or 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ; bytes
! net12 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; 1, 2 or 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ; bytes
.
.
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! net1n1 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; n1 nets at
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ; dist 1
. ...
. ; ndist groups
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ; of nets
! distance n ! nn-dist ! ; 2 bytes
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! netn1 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; 1, 2 or 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ; bytes
! netn2 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; 1, 2 or 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ; bytes
.
.
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! netnnn !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; nn nets at
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ; dist n
Gateway Type 12 (decimal)
Sequence Number The 16-bit sequence number used to
identify routing updates.
need-update An 8-bit field. This byte is set to 1
RFC 823
if the source gateway requests a routing
update from the destination gateway, and
set to 0 if not.
n-distances An 8-bit field. The number of
distance-groups reported in this update.
Each distance-group consists of a
distance value and a number of nets,
followed by the actual net numbers which
are reachable at that distance. Not all
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 in
this distance-group.
net11 1, 2, or 3 bytes for the first net at
distance "distance 1".
net12 second net
...
net1n1 etc.
RFC 823
ACKNOWLEDGMENT or NEGATIVE ACKNOWLEDGMENT
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. Negative
acknowledgments are type 10.
Sequence Number The 16-bit sequence number that the
gateway is acknowledging or negatively
acknowledging.
RFC 823
GGP ECHO and ECHO REPLY
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 address
of the gateway on the same network as
the neighbor to which it is sending the
echo message. In an echo reply message,
the source and destination addresses are
simply reversed, and the remainder is
returned unchanged.
RFC 823
NETWORK INTERFACE STATUS
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 Address
Destination Address The address of the gateway's network
interface. The gateway can send Net
Interface Status messages to itself to
determine if it is able to send and
receive traffic on its network
interface.
RFC 823
APPENDIX B. Information Maintained by Gateways
In order to implement the shortest-path routing algorithm,
gateways must maintain information about their connectivity to
networks and other gateways. This section explains the
information maintained by each gateway; this information can be
organized into the following tables and variables.
o Number of Networks
The number of networks for which the gateway maintains
routing information and to which it can forward traffic.
o Number of Neighbors
The number of neighbor gateways with which the gateway
exchanges routing information.
o Gateway Addresses
The addresses of the gateway's network interfaces.
o Neighbor Gateway Addresses
The address of each neighbor gateway's network interface
that is on the same network as this gateway.
o Neighbor Connectivity Vector
A vector of the connectivity between this gateway and each
of its neighbors.
o Distance Matrix
A matrix of the routing updates received from the neighbor
gateways.
RFC 823
o Minimum Distance Vector
A vector containing the minimum distance to each network.
o Routing Updates from Non-Routing Gateways
The routing updates that would have been received from each
non-routing neighbor gateway which does not participate in
this routing strategy.
o Routing Table
A table containing, for each network, a list of the neighbor
gateways on a minimum-distance route to the network.
o Send Sequence Number
The sequence number that will be used to send the next
routing update.
o Receive Sequence Numbers
The sequence numbers that the gateway received in the last
routing update from each of its neighbors.
o Received Acknowledgment Vector
A vector indicating whether or not each neighbor has
acknowledged the sequence number in the most recent routing
update sent.
RFC 823
APPENDIX C. GGP Events and Responses
The following list shows the GGP events that occur at a
gateway and the gateway's responses. The variables and tables
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 routing
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 routing
updates to the neighbors.
o A Routing Update message is received.
a. Compare the Internet source address of the Routing Update
message to the Neighbor Addresses. If the address is not
on the list, add it to the list of Neighbor Addresses,
increment the Number of Neighbors, and set the Receive
Sequence Number for this neighbor to the sequence number
in the Routing Update message.
b. Compare the Receive Sequence Number for this neighbor to
the sequence number in the Routing Update message to
determine whether or not to accept this message. If the
message is rejected, send a Negative Acknowledgment
message. If the message is accepted, send an
Acknowledgment message and proceed with the following
steps.
RFC 823
c. Compare the networks reported in the Routing Update
message to the Number of Networks. If new networks are
reported, enter them in the network vectors, increase the
number of networks, and expand the Distance Matrix to
account for the new networks.
d. Copy the routing update received into the appropriate row
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 routing
updates to the neighbors.
o An Acknowledgment message is received.
Compare the sequence number in the message to the Send
Sequence Number. If the Send Sequence Number is
acknowledged, update the entry in the Received
Acknowledgment Vector for the neighbor that sent the
acknowledgment.
o A Negative Acknowledgment message is received.
Compare the sequence number in the message to the Send
Sequence Number. If necessary, replace the Send Sequence
Number, and retransmit the routing updates.
RFC 823
REFERENCES
[1] Postel, J. (ed.), "Internet Protocol - DARPA Internet
Program Protocol Specification," RFC 791, USC/Information
Sciences Institute, September 1981.
[2] Strazisar, V., "Gateway Routing: An Implementation
Specification," IEN-30, Bolt Beranek and Newman Inc., August
1979.
[3] Strazisar, V., "How to Build a Gateway," IEN-109, Bolt
Beranek and Newman Inc., August 1979.
[4] Postel, J., "Internet Control Message Protocol - DARPA
Internet Program Protocol Specification," RFC 792,
USC/Information Sciences Institute, September 1981.
[5] Postel, J., "Assigned Numbers," RFC 790, USC/Information
Sciences Institute, September 1981.
[6] Littauer, B., Huang, A., Hinden, R., "A Host Monitoring
Protocol," IEN-197, Bolt Beranek and Newman Inc., September
1981.
[7] Santos, P., Chalstrom, H., Linn, J., Herman, J.,
"Architecture of a Network Monitoring, Control and
Management System," Proc. of the 5th Int. Conference on
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, Bolt
Beranek and Newman Inc., August 1982.
ISO Plain Language
On this page
§1What This Document Is
The memo is a status report on the Internet gateway developed by BBN, describing it as of September 1982. It presents detailed descriptions of message formats and gateway procedures, but it is not an implementation specification, and such details are subject to change.
The gateway design was originally documented in IEN-30, Gateway Routing: An Implementation Specification, and later updated in IEN-109, How to Build a Gateway. The memo reflects changes made both in the Internet protocols and in the gateway design since those documents were released, and it supersedes both.
The gateway's primary purpose is to route Internet datagrams to their destination networks. The datagrams are generated and processed as described in RFC 791. The memo describes how the gateway forwards datagrams, the routing algorithm and protocol used to route them, and the software structure of the current gateway. The implementation is written in macro-11 assembly language and runs in the DEC PDP-11 or LSI-11 16-bit processor.
This is a report on one particular machine, written so that others can see how it worked. The gateway's job was to take datagrams from one network and pass them to another, and the memo describes that job in detail: what the machine checked, how it decided where to send things, and what the software looked like.
§2How the Gateway Evolved
Early versions of gateway software were implemented using the BCPL language and the ELF operating system. That implementation evolved into one that used the MOS operating system for increased performance. In late 1981 an effort began to produce a totally new gateway implementation. The primary motivation was the need for a system oriented towards the requirements of an operational communications facility, rather than the research testbed environment associated with the BCPL implementation. It was also generally recognised that the complexity and buffering requirements of future gateway configurations were beyond the capabilities of the PDP-11/LSI-11 and BCPL architecture, so the new implementation had a second goal of producing a highly space-efficient implementation in order to provide space for buffers and for the extra mechanisms, such as monitoring, needed for an operational environment.
One result of recent research was the thesis that gateways should be viewed as elements of a gateway system, where the gateways act as a loosely-coupled packet-switching communications system. For reasons of maintainability and operability, it is easiest to build such a system in a homogeneous fashion where all gateways are under a single authority and control, as is the practice in other network implementations. In order to create a system architecture that permitted multiple sets of gateways, each set under single control but acting together to implement a composite single Internet system, new protocols needed to be developed, such as the Exterior Gateway Protocol.
The memo also anticipates further changes to introduce support for new capabilities, such as large numbers of networks, access control and other requirements proposed by the Internet research community. It represents a snapshot of the current implementation rather than a specification.
The first gateways were research machines written in a language of the era. The memo explains why a new one was built: the Internet was becoming an operational service, with monitoring and many networks attached, and the old machines were too small to hold the buffers and the code that required. The design idea that came out of this was that a set of gateways under one authority should act together as one system.
§3Forwarding an Internet Datagram
A host that wants an IP datagram to reach a host on another network sends the datagram to a gateway, attaching to it a local network header containing the address of the gateway. On receipt, the gateway checks the local network header for errors and performs any action required by the host-to-network protocol, such as verifying the local network header checksum or generating a local network acknowledgment. If the header indicates that the message contains an Internet datagram, the datagram is passed to the Internet header check routine, and all other messages that do not pass these tests are discarded.
The Internet header check routine performs a number of validity tests: the proper IP version number, a valid IP header length of at least 20 bytes, a valid IP message length, a valid IP header checksum, and a non-zero time to live field. Datagrams that fail these tests are discarded, causing an HMP trap to be sent to the Internet Network Operations Center. The Internet destination address is then examined to see whether the datagram is addressed to the gateway itself, by comparing each of the gateway's Internet addresses, one for each network interface, against the destination address. If no match is found, the datagram is passed to the forwarding routine. If it is addressed to the gateway, the IP options are processed; the gateway supports NOP, End of Option List, Loose Source and Record Route and Strict Source and Record Route. The datagram is then processed according to the protocol in the IP header, and if the protocol is not supported the gateway replies with an ICMP error message and discards the datagram. The gateway does not support IP reassembly, so fragmented datagrams addressed to it are discarded.
The gateway must make a routing decision for every datagram to be forwarded, and the routing algorithm provides two things: the network interface to use and the destination address to put in the local network header. The gateway maintains a dynamic routing table with an entry for each reachable network, holding a network number and the address of the neighbour gateway on the shortest route, or an indication that the gateway is directly connected. A neighbour gateway is one that shares a common network with this gateway. The distance metric is the number of hops, a gateway being zero hops from its directly connected networks and one hop from a network reachable via one other gateway. The Gateway-to-Gateway Protocol is used to update the table.
The destination network address in the IP header is matched against the routing table. If no match is found, the gateway drops the datagram and sends an ICMP Destination Unreachable message to the IP source. If an entry is found, the neighbour gateway's network address becomes the local network destination address, except when the final destination network is one the gateway is directly connected to, in which case the destination address comes from the IP header. If the routing procedure decides the datagram is to be sent back out the same interface it was read in, this gateway is not on the shortest path, but the datagram is still forwarded to the next address chosen; and if the datagram is not using the IP Source Route Option and the IP source network is the same as the network of the next gateway, an ICMP Redirect is sent to the source host saying another gateway should be used.
After the routing decision the datagram goes to the fragmentation routine. If the next network has a maximum message size smaller than the datagram, the datagram is fragmented according to the algorithm in the Internet Protocol specification, with certain IP options copied into the header of all fragments and others appearing only in the first. If fragmentation is needed but the don't fragment bit is set, the datagram is discarded and an ICMP error message is sent to the source. The datagram or its fragments then go to a routine that rebuilds the Internet header, decrementing the time to live by one and recomputing the IP checksum, and the local network header is built, choosing the interface and the destination address. Finally the datagram is enqueued on an output queue for delivery towards its destination. A limit is enforced on the size of the output queue for each interface so that a slow network does not unfairly use up all of the gateway's buffers; if a datagram cannot be enqueued because of that limit, it is dropped and an HMP trap is sent to the operations centre.
Forwarding a datagram is a fixed sequence of steps. Check the local header, then check the IP header for a bad version, a short header, a bad length, a bad checksum or an expired time to live. Work out which interface and which neighbour to use. Split the datagram if the next network cannot carry it whole. Lower the time to live, fix the checksum, write the local header, and queue it. Along the way, the gateway answers back to the sender when something is wrong, using ICMP messages for unreachable destinations, redirects, and packets it could not forward.
- InputCheck the local network header and do whatever the host-to-network protocol requires.
- IP header checksVersion, header length, message length, header checksum and time to live.
- RoutingMatch the destination network against the routing table to pick an interface and a neighbour.
- RedirectsTell the source host if another gateway would have been a shorter way.
- FragmentationSplit the datagram if the next network cannot carry it whole.
- Header rebuildDecrement the time to live, recompute the checksum and build the local header.
- OutputQueue the datagram, and drop it with a trap if the queue is full.
§4.4The Gateway-to-Gateway Protocol
The Gateway-to-Gateway Protocol, GGP, is used to determine connectivity to networks and neighbour gateways and to implement a dynamic, shortest-path routing algorithm. When a gateway starts running it assumes that all its neighbour gateways are down, that it is disconnected from the networks to which it is attached, and that the distance reported in routing updates from each neighbour to each network is infinity. The connection to a network is declared up if the gateway can send and receive Internet datagrams on its interface to it; the method is network-dependent, and on some networks the gateway polls with GGP network interface status messages to find out whether an interface is operational. Two rules apply to distances: if the gateway can send and receive traffic on an interface its distance to that network is zero, and if it cannot its distance is infinity.
Connectivity to neighbours uses a K out of N algorithm. Every 15 seconds the gateway sends GGP Echo messages to each of its neighbours, and the neighbours respond with GGP echo replies. If there is no reply to K out of N echo messages, currently K=3 and N=4, the neighbour is declared down; if a neighbour is down and J out of M echo replies are received, currently J=2 and M=4, the neighbour is declared up. The values of J, K, M, N and the interval are operational parameters.
Routing information is exchanged in routing update messages, reliably, using sequence numbers and a retransmission and acknowledgment scheme. For each neighbour the gateway remembers the receive sequence number R from the most recent routing update. On receipt, it subtracts R from the update's sequence number S. If the difference is zero or more the update is accepted, an acknowledgment carrying S is sent and R is replaced with S; if the difference is negative the update is rejected and a negative acknowledgment carrying R is sent. The gateway also has a send sequence number N for updates to all neighbours, incremented each time a new update is created. When an acknowledgment arrives, the acknowledged number A is subtracted from N; if the result is non-zero an old update is being acknowledged and the most recent update is retransmitted to that neighbour, and if it is zero the update has been acknowledged. A negative acknowledgment that makes the difference negative causes the send sequence number to be reset to A+1 and the update to be retransmitted to all neighbours, because the sequence numbers at all gateways must stay correct. Updates are retransmitted periodically until acknowledged and whenever the send sequence number changes, and are sent only to neighbours that are up.
A routing update contains a list of networks reachable through this gateway and the distance in hops to each. It contains a network only if the gateway believes it is as close or closer to that network than the neighbour that is to receive the update. The gateway keeps an N by K distance matrix, where N is the number of networks and K the number of neighbour gateways, with an entry dm(I,J) giving the distance to network I as reported by neighbour J, plus a vector of the connectivity to each neighbour. The minimum distance to network I is the minimum over all neighbours of the distance to that neighbour plus the distance the neighbour reports to network I; if the network is attached to the gateway and the gateway can send and receive traffic on its interface, that entry is set to zero. Using that minimum distance vector the gateway computes which neighbour to send traffic to for each network, and then works out the updates to send: it reports a network to a neighbour only if it is as close or closer than that neighbour, and the update carries the address of the network and the minimum distance to it. New updates are sent if one of the gateway's interfaces changes state, if one of its neighbours changes state, or if it receives an update from a neighbour different from the one it had received before.
A non-routing gateway forwards Internet traffic but does not implement the GGP routing algorithm. The networks behind it are known in advance to routing gateways and are considered directly connected to it. A routing gateway will forward a datagram to a non-routing gateway if it is addressed to a network behind it, but will always prefer another routing gateway at the same number of hops, using the non-routing path only when the routing gateway path is down.
The gateway learns the shape of the network from its neighbours. Every fifteen seconds it pings each of them; a neighbour that misses three of four pings is taken to be down, and one that answers two of four is taken to be up. Each neighbour reports the networks it can reach and how many hops away they are, and the gateway adds its own distance to that neighbour to work out the shortest route. The updates carry sequence numbers, so a neighbour can say which one it has, and updates are resent until they are acknowledged.
- 12Routing Update — The networks reachable through this gateway and the distance to each.
- 2Acknowledgment — Confirms a routing update, carrying its sequence number.
- 10Negative Acknowledgment — Rejects a routing update and names the sequence number it expected.
- 8GGP Echo — Polling a neighbour to find out whether it is up.
- 0GGP Echo Reply — The neighbour's answer to an echo.
- 9Network Interface Status — Reports the state of one of the gateway's own interfaces.
- GGP ECHOSent every 15 seconds to check whether the neighbour is up.
- GGP ECHO REPLYThe neighbour's answer.
- ROUTING UPDATENetworks reachable through A and the distance to each. Resent until acknowledged.
- ACKNOWLEDGMENTCarries the sequence number of the update B received.
§4.2Monitoring, Debugging and Error Reporting
Several protocols give the gateway its operational abilities. The Cross-Net Debugging Protocol is used to load the gateway and to examine and deposit data, with op-codes for NOP, Debug, End Debug, Deposit, Examine and Create Process. The Host Monitoring Protocol collects measurements and status information from the gateways; exceptional conditions are reported in HMP traps, and the status of a gateway's interfaces, neighbours and the networks it can reach is reported in the HMP status message.
Two types of gateway statistics are defined by HMP. The Host Traffic Matrix records the number of datagrams that pass through the gateway with a given IP source, destination and protocol number. The gateway throughput message collects counters that the gateway keeps: datagrams dropped because the destination network or host was unreachable; per interface, datagrams received with IP errors, datagrams received for the gateway itself, datagrams received to be forwarded, datagrams looped, bytes received, datagrams sent originating at the gateway, datagrams sent to destination hosts, datagrams dropped because of flow control limitations, datagrams dropped because of a full queue, and bytes sent; and per neighbour, routing updates sent to and received from, datagrams sent originating at the gateway, datagrams forwarded to, datagrams dropped because of flow control limitations, datagrams dropped because of a full queue, and bytes sent.
The gateway generates ICMP messages under the appropriate circumstances: Echo Reply, Destination Unreachable, Source Quench, Redirect, Time Exceeded, Parameter Problem and Information Reply.
The Exterior Gateway Protocol permits other gateways and gateway systems to pass routing information to the DARPA Internet gateways, so that a user can perceive all of the networks and gateways as part of one total Internet system even though the exterior gateways are disjoint and may use a different routing algorithm. Its important elements are neighbour acquisition, the procedure by which a gateway asks to become a neighbour of another and that other accepts or refuses; neighbour up and down, the procedure by which a gateway decides whether another is up; network reachability information, the facility used to pass routing and neighbour information between gateways; and gateway going down, the ability of a gateway to inform others that it is going down and has no routes left, so that it can go down in an orderly way without disrupting the rest of the system. A complete description is in IEN-209.
Besides forwarding, the machine reported on itself. A debugging protocol let an operator load it and look inside. The monitoring protocol sent periodic statistics about each interface and each neighbour, and raised traps when something went wrong, such as a queue filling up. ICMP messages told the sending host about unreachable destinations and about better gateways to use. And the exterior gateway protocol was the door to the rest of the Internet, letting gateways outside exchange routing information with these ones.
§5The Gateway Software
The gateway runs under the MOS operating system, which provides multiple processes, interprocess communication, buffer management, asynchronous input and output, and a shareable real-time clock. There is a MOS process for each network the gateway is directly connected to. A data structure called a NETBLOCK holds the variables of interest for each network and pointers to local network routines; the network processes run common gateway code while network-specific functions are dispatched to the routines pointed to in the NETBLOCK. There are also processes for gateway functions that require their own timing, such as GGP and HMP.
The software divides into three parts: MOS device drivers, network software and shared gateway software. The device drivers handle sending and receiving data for each type of hardware interface, with routines for initialisation, initiation and interruption on both the transmit and receive sides. The supported devices are the ACC LSI-11 1822, the DEC IMP11a 1822, the ACC LHDH 1822, the ACC VDH11E, the ACC VDH11C, the Proteon Ring Network, the RSRE HDLC, Interlan Ethernet, BBN Fibernet, and two ACC XQ/CP devices, the X.25 and the HDH, which were planned but not yet supported.
For each connected network the gateway has a set of eight routines handling local network functions: Up.net performs local network initialisation such as flapping the 1822 ready line; Sg.net handles specific local network timing functions such as timing out 1822 destination deads; Rc.net is called when a message has been received and checks for input errors; Wc.net is called when a message has been transmitted and checks for output errors; Rs.net sets up a buffer or buffers to receive messages on the network interface; Ws.net transmits a message to the network interface; Hc.net checks the local network header of a received message and performs any local network protocol tasks; and Hb.net rebuilds the local network header. There are network routines for Arpanet, Satnet, the Proteon Ring Network, the Packet Radio Network, the Rsre HDLC Null Network, Ethernet, Fibernet and Telenet X.25, which was planned but not yet supported.
The shared gateway software performs the Internet processing of a datagram, including routines to check the IP header, perform IP fragmentation, calculate the IP checksum, forward a datagram, and implement the routing, monitoring and error reporting protocols. When the gateway starts, each network process calls its local network initialisation routine and read start routine, which sets up two maximum network size buffers for receiving datagrams, and then waits for an input complete signal from the network device driver. When a message arrives the operating system signals the appropriate network process, which wakes up and runs the net read complete routine. That routine is the major message processing loop, and it calls the local network read complete routine, starts more reads, checks the local network header, checks the Internet header, checks whether the datagram is for the gateway, forwards the datagram if necessary, and sends an ICMP error message if necessary.
The GGP process periodically sends GGP echoes to each of the gateway's neighbours to determine neighbour connectivity, sends interface status messages addressed to itself to determine network connectivity, and sends out routing updates when necessary. The HMP process handles timer-based gateway statistics collection and the periodic transmission of traps.
The machine ran one process per connected network, so a slow network could not hold up the others, and the common code that did the actual Internet work was shared between them. Each network type supplied eight small routines for its own quirks, such as reading its headers and waking it up, while everything to do with IP sat in the shared part. A separate process handled the routing protocol and another the monitoring.