summaryrefslogtreecommitdiff
path: root/doc/rfc/rfc823.txt
diff options
context:
space:
mode:
Diffstat (limited to 'doc/rfc/rfc823.txt')
-rw-r--r--doc/rfc/rfc823.txt2610
1 files changed, 2610 insertions, 0 deletions
diff --git a/doc/rfc/rfc823.txt b/doc/rfc/rfc823.txt
new file mode 100644
index 0000000..4b87f03
--- /dev/null
+++ b/doc/rfc/rfc823.txt
@@ -0,0 +1,2610 @@
+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.
+
+
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+ -1-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+ -2-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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
+
+
+
+ -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 Internet
+
+ research community. This document represents a snapshot of the
+
+ current implementation, rather than a specification.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ -4-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+
+
+
+
+
+ -5-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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:
+
+
+
+
+
+
+
+
+ -6-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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
+
+
+
+
+ -7-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+
+
+
+ -8-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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
+
+
+
+ -9-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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
+
+
+
+ -10-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ -11-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+ -12-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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
+
+
+
+
+
+
+
+ -13-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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
+
+
+
+
+ -14-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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
+
+
+
+
+ -15-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+
+
+
+
+
+
+ -16-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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
+
+
+
+
+ -17-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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
+
+
+
+ -18-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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
+
+
+
+
+ -19-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+
+ -20-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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
+
+
+
+ -21-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+ -22-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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
+
+
+
+ -23-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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
+
+
+
+ -24-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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].
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ -25-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+
+ -26-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+ -27-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+ -28-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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
+
+
+
+
+ -29-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+
+
+
+
+ -30-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ RFC 823
+
+
+
+ 5.2.3 HMP Process
+
+
+ The HMP process handles timer-based gateway statistics
+
+ collection and the periodic transmission of traps.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ -31-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+ -32-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ -33-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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
+
+
+
+ -34-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ -35-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ -36-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ -37-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ -38-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+
+ -39-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ -40-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+ -41-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ -42-
+
+
+
+
+
+ DARPA Internet Gateway September 1982
+ 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.
+
+
+
+
+
+
+
+
+
+
+ -43-
+
+
+