path: root/doc/rfc/rfc823.txt

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.




^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L


     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-


^L