doc: Add RFC documents

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-
+
+
+