home *** CD-ROM | disk | FTP | other *** search
/ Unix System Administration Handbook 1997 October / usah_oct97.iso / rfc / 800s / rfc823.txt < prev    next >
Text File  |  1991-10-16  |  60KB  |  2,611 lines
  1. Request for Comments:  823
  2. Obsoletes IEN-30 and IEN-109
  3.  
  4.  
  5.  
  6.  
  7.                         THE DARPA INTERNET GATEWAY
  8.  
  9.  
  10.  
  11.                                   RFC 823
  12.  
  13.  
  14.  
  15.  
  16.  
  17.  
  18.                                Robert Hinden
  19.                                Alan Sheltzer
  20.  
  21.  
  22.  
  23.  
  24.  
  25.                        Bolt Beranek and Newman Inc.
  26.                               10 Moulton St.
  27.                       Cambridge, Massachusetts 02238
  28.  
  29.  
  30.  
  31.  
  32.  
  33.                               September 1982
  34.  
  35.  
  36.  
  37.  
  38.                                Prepared for
  39.  
  40.                  Defense Advanced Research Projects Agency
  41.                  Information Processing Techniques Office
  42.                            1400 Wilson Boulevard
  43.                          Arlington, Virginia 22209
  44.  
  45.  
  46.  
  47.  
  48.  
  49. This RFC is a status report on the Internet Gateway developed by BBN. It
  50. describes the Internet Gateway as of September 1982.  This memo presents
  51. detailed descriptions of message formats and gateway procedures, however
  52. this is not an implementation specification, and such details are 
  53. subject to change.
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.      DARPA Internet Gateway                             September 1982
  62.      RFC 823
  63.  
  64.  
  65.  
  66.                              Table of Contents
  67.  
  68.  
  69.  
  70.  
  71.      1   INTRODUCTION.......................................... 1
  72.      2   BACKGROUND............................................ 2
  73.      3   FORWARDING INTERNET DATAGRAMS......................... 5
  74.      3.1   Input............................................... 5
  75.      3.2   IP Header Checks.................................... 6
  76.      3.3   Routing............................................. 7
  77.      3.4   Redirects........................................... 9
  78.      3.5   Fragmentation....................................... 9
  79.      3.6   Header Rebuild..................................... 10
  80.      3.7   Output............................................. 10
  81.      4   PROTOCOLS SUPPORTED BY THE GATEWAY................... 12
  82.      4.1   Cross-Net Debugging Protocol....................... 12
  83.      4.2   Host Monitoring Protocol........................... 12
  84.      4.3   ICMP............................................... 14
  85.      4.4   Gateway-to-Gateway Protocol........................ 14
  86.      4.4.1   Determining Connectivity to Networks............. 14
  87.      4.4.2   Determining Connectivity to Neighbors............ 16
  88.      4.4.3   Exchanging Routing Information................... 17
  89.      4.4.4   Computing Routes................................. 19
  90.      4.4.5   Non-Routing Gateways............................. 22
  91.      4.4.6   Adding New Neighbors and Networks................ 23
  92.      4.5   Exterior Gateway Protocol.......................... 24
  93.      5   GATEWAY SOFTWARE..................................... 26
  94.      5.1   Software Structure................................. 26
  95.      5.1.1   Device Drivers................................... 27
  96.      5.1.2   Network Software................................. 27
  97.      5.1.3   Shared Gateway Software.......................... 29
  98.      5.2   Gateway Processes.................................. 29
  99.      5.2.1   Network Processes................................ 29
  100.      5.2.2   GGP Process...................................... 30
  101.      5.2.3   HMP Process...................................... 31
  102.      APPENDIX A. GGP Message Formats.......................... 32
  103.      APPENDIX B. Information Maintained by Gateways........... 39
  104.      APPENDIX C. GGP Events and Responses..................... 41
  105.      REFERENCES............................................... 43
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.                                     -i-
  114.  
  115.  
  116.  
  117.  
  118.  
  119.      DARPA Internet Gateway                             September 1982
  120.      RFC 823
  121.  
  122.  
  123.  
  124.      1  INTRODUCTION
  125.  
  126.  
  127.           This document explains the design of  the  Internet  gateway
  128.  
  129.      used  in  the  Defense  Advanced  Research Project Agency (DARPA)
  130.  
  131.      Internet program.  The gateway design was  originally  documented
  132.  
  133.      in  IEN-30,  "Gateway  Routing:  An Implementation Specification"
  134.  
  135.      [2], and was later updated in IEN-109, "How to Build  a  Gateway"
  136.  
  137.      [3].   This  document  reflects changes made both in the internet
  138.  
  139.      protocols and in the gateway design since  these  documents  were
  140.  
  141.      released.  It supersedes both IEN-30 and IEN-109.
  142.  
  143.  
  144.           The Internet gateway described in this document is based  on
  145.  
  146.      the  work  of many people; in particular, special credit is given
  147.  
  148.      to V. Strazisar, M. Brescia, E. Rosen, and J. Haverty.
  149.  
  150.  
  151.           The gateway's primary purpose is to route internet datagrams
  152.  
  153.      to their destination networks.  These datagrams are generated and
  154.  
  155.      processed as described in RFC 791,  "Internet  Protocol  -  DARPA
  156.  
  157.      Internet  Program  Protocol  Specification"  [1].   This document
  158.  
  159.      describes  how  the  gateway  forwards  datagrams,  the   routing
  160.  
  161.      algorithm  and  protocol  used  to  route  them, and the software
  162.  
  163.      structure  of  the  current   gateway.    The   current   gateway
  164.  
  165.      implementation  is written in macro-11 assembly language and runs
  166.  
  167.      in the DEC PDP-11 or LSI-11 16-bit processor.
  168.  
  169.  
  170.  
  171.                                     -1-
  172.  
  173.  
  174.  
  175.  
  176.  
  177.      DARPA Internet Gateway                             September 1982
  178.      RFC 823
  179.  
  180.  
  181.  
  182.      2  BACKGROUND
  183.  
  184.  
  185.           The gateway system has undergone a series of  changes  since
  186.  
  187.      its  inception,  and  it  is  continuing  to  evolve  as research
  188.  
  189.      proceeds in the Internet community.  This document describes  the
  190.  
  191.      implementation as of mid-1982.
  192.  
  193.  
  194.           Early versions of gateway software  were  implemented  using
  195.  
  196.      the   BCPL   language   and   the  ELF  operating  system.   This
  197.  
  198.      implementation evolved into one  which  used  the  MOS  operating
  199.  
  200.      system  for  increased  performance.   In  late 1981, we began an
  201.  
  202.      effort to produce a  totally  new  gateway  implementation.   The
  203.  
  204.      primary  motivation  for  this was the need for a system oriented
  205.  
  206.      towards  the  requirements  of  an   operational   communications
  207.  
  208.      facility,  rather than the research testbed environment which was
  209.  
  210.      associated with the BCPL implementation.   In  addition,  it  was
  211.  
  212.      generally   recognized   that   the   complexity   and  buffering
  213.  
  214.      requirements of future gateway  configurations  were  beyond  the
  215.  
  216.      capabilities of the PDP-11/LSI-11 and BCPL architecture.  The new
  217.  
  218.      gateway implementation therefore had a second goal of producing a
  219.  
  220.      highly  space-efficient  implementation in order to provide space
  221.  
  222.      for buffers and for the extra  mechanisms,  such  as  monitoring,
  223.  
  224.      which are needed for an operational environment.
  225.  
  226.  
  227.  
  228.  
  229.                                     -2-
  230.  
  231.  
  232.  
  233.  
  234.  
  235.      DARPA Internet Gateway                             September 1982
  236.      RFC 823
  237.  
  238.  
  239.  
  240.           This document  describes  the  implementation  of  this  new
  241.  
  242.      gateway  which  incorporates  several  mechanisms  for operations
  243.  
  244.      activities,  is coded in assembly  language  for  maximum  space-
  245.  
  246.      efficiency,  but otherwise is fundamentally the same architecture
  247.  
  248.      as the older, research-oriented, implementations.
  249.  
  250.  
  251.           One of the results of recent research  is  the  thesis  that
  252.  
  253.      gateways  should be viewed as elements of a gateway system, where
  254.  
  255.      the  gateways   act   as   a   loosely-coupled   packet-switching
  256.  
  257.      communications   system.   For  reasons  of  maintainability  and
  258.  
  259.      operability,  it  is  easiest  to  build  such  a  system  in  an
  260.  
  261.      homogeneous  fashion  where  all  gateways  are  under  a  single
  262.  
  263.      authority and control,  as  is  the  practice  in  other  network
  264.  
  265.      implementations.
  266.  
  267.  
  268.           In order to create  a  system  architecture  that  permitted
  269.  
  270.      multiple  sets of gateways with each set under single control but
  271.  
  272.      acting together to implement a composite single Internet  System,
  273.  
  274.      new  protocols  needed to be developed.  These protocols, such as
  275.  
  276.      the "Exterior Gateway Protocol," will be introduced in the  later
  277.  
  278.      releases of the gateway implementation.
  279.  
  280.  
  281.           We  also  anticipate  further   changes   to   the   gateway
  282.  
  283.      architecture  and  implementation  to  introduce  support for new
  284.  
  285.  
  286.  
  287.                                     -3-
  288.  
  289.  
  290.  
  291.  
  292.  
  293.      DARPA Internet Gateway                             September 1982
  294.      RFC 823
  295.  
  296.  
  297.  
  298.      capabilities, such as large numbers of networks, access  control,
  299.  
  300.      and  other  requirements which have been proposed by the Internet
  301.  
  302.      research community.  This document represents a snapshot  of  the
  303.  
  304.      current implementation, rather than a specification.
  305.  
  306.  
  307.  
  308.  
  309.  
  310.  
  311.  
  312.  
  313.  
  314.  
  315.  
  316.  
  317.  
  318.  
  319.  
  320.  
  321.  
  322.  
  323.  
  324.  
  325.  
  326.  
  327.  
  328.  
  329.  
  330.  
  331.  
  332.  
  333.  
  334.  
  335.  
  336.  
  337.  
  338.  
  339.  
  340.  
  341.  
  342.  
  343.  
  344.  
  345.                                     -4-
  346.  
  347.  
  348.  
  349.  
  350.  
  351.      DARPA Internet Gateway                             September 1982
  352.      RFC 823
  353.  
  354.  
  355.  
  356.      3  FORWARDING INTERNET DATAGRAMS
  357.  
  358.  
  359.           This section describes how the  gateway  forwards  datagrams
  360.  
  361.      between  networks.   A host computer that wants an IP datagram to
  362.  
  363.      reach a host on another network  must  send  the  datagram  to  a
  364.  
  365.      gateway to be forwarded.  Before it is sent into the network, the
  366.  
  367.      host attaches to the datagram a local network  header  containing
  368.  
  369.      the address of the gateway.
  370.  
  371.  
  372.  
  373.  
  374.      3.1  Input
  375.  
  376.  
  377.           When a gateway receives a message, the  gateway  checks  the
  378.  
  379.      message's  local  network header for possible errors and performs
  380.  
  381.      any actions  required  by  the  host-to-network  protocol.   This
  382.  
  383.      processing involves functions such as verifying the local network
  384.  
  385.      header checksum or  generating  a  local  network  acknowledgment
  386.  
  387.      message.   If  the  header indicates that the message contains an
  388.  
  389.      Internet datagram, the datagram is passed to the Internet  header
  390.  
  391.      check  routine.   All  other  messages  received that do not pass
  392.  
  393.      these tests are discarded.
  394.  
  395.  
  396.  
  397.  
  398.  
  399.  
  400.  
  401.  
  402.  
  403.                                     -5-
  404.  
  405.  
  406.  
  407.  
  408.  
  409.      DARPA Internet Gateway                             September 1982
  410.      RFC 823
  411.  
  412.  
  413.  
  414.      3.2  IP Header Checks
  415.  
  416.  
  417.           The Internet header  check  routine  performs  a  number  of
  418.  
  419.      validity tests on the IP header.  Datagrams that fail these tests
  420.  
  421.      are discarded causing an HMP trap to  be  sent  to  the  Internet
  422.  
  423.      Network  Operations  Center (INOC) [7].  The following checks are
  424.  
  425.      currently performed:
  426.  
  427.  
  428.           o  Proper IP Version Number
  429.           o  Valid IP Header Length ( >= 20 bytes)
  430.           o  Valid IP Message Length
  431.           o  Valid IP Header Checksum
  432.           o  Non-Zero Time to Live field
  433.  
  434.  
  435.      After a datagram passes these checks,  its  Internet  destination
  436.  
  437.      address  is examined to determine if the datagram is addressed to
  438.  
  439.      the gateway.  Each of the gateway's internet addresses  (one  for
  440.  
  441.      each  network  interface)  is  checked  against  the  destination
  442.  
  443.      address in the datagram.  If a match is not found,  the  datagram
  444.  
  445.      is passed to the forwarding routine.
  446.  
  447.  
  448.           If the datagram is addressed to the gateway itself,  the  IP
  449.  
  450.      options  in  the IP header are processed.  Currently, the gateway
  451.  
  452.      supports the following IP options:
  453.  
  454.  
  455.  
  456.  
  457.  
  458.  
  459.  
  460.  
  461.                                     -6-
  462.  
  463.  
  464.  
  465.  
  466.  
  467.      DARPA Internet Gateway                             September 1982
  468.      RFC 823
  469.  
  470.  
  471.  
  472.  
  473.           o  NOP
  474.           o  End of Option List
  475.           o  Loose Source and Record Route
  476.           o  Strict Source and Record Route
  477.  
  478.  
  479.      The datagram is next processed according to the protocol  in  the
  480.  
  481.      IP  header.  If  the protocol is not supported by the gateway, it
  482.  
  483.      replies with an ICMP error message  and  discards  the  datagram.
  484.  
  485.      The  gateway  does  not  support  IP  reassembly,  so  fragmented
  486.  
  487.      datagrams which are addressed to the gateway are discarded.
  488.  
  489.  
  490.  
  491.  
  492.      3.3  Routing
  493.  
  494.  
  495.           The gateway must make a routing decision for  all  datagrams
  496.  
  497.      that  are to be to forwarded.  The routing algorithm provides two
  498.  
  499.      pieces of information for the gateway:  1) the network  interface
  500.  
  501.      that  should be used to send this datagram and 2) the destination
  502.  
  503.      address that should be put in the local  network  header  of  the
  504.  
  505.      datagram.
  506.  
  507.  
  508.           The gateway maintains a dynamic Routing Table which contains
  509.  
  510.      an  entry  for  each  reachable network.  The entry consists of a
  511.  
  512.      network number and the address of the  neighbor  gateway  on  the
  513.  
  514.      shortest  route  to  the  network, or else an indication that the
  515.  
  516.  
  517.  
  518.  
  519.                                     -7-
  520.  
  521.  
  522.  
  523.  
  524.  
  525.      DARPA Internet Gateway                             September 1982
  526.      RFC 823
  527.  
  528.  
  529.  
  530.      gateway is directly connected to the network.  A neighbor gateway
  531.  
  532.      is  one  which  shares  a  common network with this gateway.  The
  533.  
  534.      distance metric that is  used  to  determine  which  neighbor  is
  535.  
  536.      closest  is  defined  as the "number of hops," where a gateway is
  537.  
  538.      considered to be zero hops from its directly connected  networks,
  539.  
  540.      one  hop  from a network that is reachable via one other gateway,
  541.  
  542.      etc.  The Gateway-to-Gateway Protocol (GGP) is used to update the
  543.  
  544.      Routing  Table (see Section 4.4 describing the Gateway-to-Gateway
  545.  
  546.      Protocol).
  547.  
  548.  
  549.           The gateway tries to match the destination  network  address
  550.  
  551.      in  the IP header of the datagram to be forwarded, with a network
  552.  
  553.      in its Routing Table.  If no match is found,  the  gateway  drops
  554.  
  555.      the datagram and sends an ICMP Destination Unreachable message to
  556.  
  557.      the IP source.  If the gateway does find an entry for the network
  558.  
  559.      in  its  table,  it  will use the network address of the neighbor
  560.  
  561.      gateway entry as the local network  destination  address  of  the
  562.  
  563.      datagram.   However, if the final destination network is one that
  564.  
  565.      the gateway is directly connected to, the destination address  in
  566.  
  567.      the  local network header is created from the destination address
  568.  
  569.      in the IP header of the datagram.
  570.  
  571.  
  572.  
  573.  
  574.  
  575.  
  576.  
  577.                                     -8-
  578.  
  579.  
  580.  
  581.  
  582.  
  583.      DARPA Internet Gateway                             September 1982
  584.      RFC 823
  585.  
  586.  
  587.  
  588.      3.4  Redirects
  589.  
  590.  
  591.           If the routing procedure decides that an IP datagram  is  to
  592.  
  593.      be  sent back out the same network interface that it was read in,
  594.  
  595.      then this gateway is not on the shortest path  to  the  IP  final
  596.  
  597.      destination.   Nevertheless, the datagram will still be forwarded
  598.  
  599.      to the next address chosen by  the  routing  procedure.   If  the
  600.  
  601.      datagram  is  not  using  the  IP Source Route Option, and the IP
  602.  
  603.      source network of the datagram is the same as the network of  the
  604.  
  605.      next  gateway  chosen  by the routing procedure, an ICMP Redirect
  606.  
  607.      message will be sent  to  the  IP  source  host  indicating  that
  608.  
  609.      another  gateway  should  be used to send traffic to the final IP
  610.  
  611.      destination.
  612.  
  613.  
  614.  
  615.  
  616.      3.5  Fragmentation
  617.  
  618.  
  619.           The datagram is passed to the  fragmentation  routine  after
  620.  
  621.      the  routing decision has been made.  If the next network through
  622.  
  623.      which the datagram must pass has a maximum message size  that  is
  624.  
  625.      smaller  than  the  size  of  the  datagram, the datagram must be
  626.  
  627.      fragmented.   Fragmentation  is  performed   according   to   the
  628.  
  629.      algorithm  described  in the Internet Protocol Specification [1].
  630.  
  631.      Certain IP options must be copied  into  the  IP  header  of  all
  632.  
  633.  
  634.  
  635.                                     -9-
  636.  
  637.  
  638.  
  639.  
  640.  
  641.      DARPA Internet Gateway                             September 1982
  642.      RFC 823
  643.  
  644.  
  645.  
  646.      fragments, and others appear only in the first fragment according
  647.  
  648.      to the IP specification.  If a datagram must be  fragmented,  but
  649.  
  650.      the  Don't  fragment bit is set, the datagram is discarded and an
  651.  
  652.      ICMP error message is sent to the IP source of the datagram.
  653.  
  654.  
  655.  
  656.  
  657.      3.6  Header Rebuild
  658.  
  659.  
  660.           The datagram (or the fragments of the original  datagram  if
  661.  
  662.      fragmentation  was  needed)  is  next  passed  to  a routine that
  663.  
  664.      rebuilds  the  Internet  header.  The  Time  to  Live  field   is
  665.  
  666.      decremented by one and the IP checksum is recomputed.
  667.  
  668.  
  669.           The  local  network  header  is  now   built.    Using   the
  670.  
  671.      information  obtained  from  its  routing  procedure, the gateway
  672.  
  673.      chooses the network interface it considers  proper  to  send  the
  674.  
  675.      datagram  and  to  build  the  destination  address  in the local
  676.  
  677.      network header.
  678.  
  679.  
  680.  
  681.  
  682.      3.7  Output
  683.  
  684.  
  685.           The datagram is now enqueued on an output queue for delivery
  686.  
  687.      towards  its destination.  A limit is enforced on the size of the
  688.  
  689.      output queue for each network interface so that  a  slow  network
  690.  
  691.  
  692.  
  693.                                    -10-
  694.  
  695.  
  696.  
  697.  
  698.  
  699.      DARPA Internet Gateway                             September 1982
  700.      RFC 823
  701.  
  702.  
  703.  
  704.      does  not  unfairly  use  up  all of the gateway's buffers.  If a
  705.  
  706.      datagram cannot be enqueued due to the limit on the output  queue
  707.  
  708.      length, it is dropped and an HMP trap is sent to the INOC.  These
  709.  
  710.      traps, and others of a similar nature, are  used  by  operational
  711.  
  712.      personnel to monitor the operations of the gateways.
  713.  
  714.  
  715.  
  716.  
  717.  
  718.  
  719.  
  720.  
  721.  
  722.  
  723.  
  724.  
  725.  
  726.  
  727.  
  728.  
  729.  
  730.  
  731.  
  732.  
  733.  
  734.  
  735.  
  736.  
  737.  
  738.  
  739.  
  740.  
  741.  
  742.  
  743.  
  744.  
  745.  
  746.  
  747.  
  748.  
  749.  
  750.  
  751.                                    -11-
  752.  
  753.  
  754.  
  755.  
  756.  
  757.      DARPA Internet Gateway                             September 1982
  758.      RFC 823
  759.  
  760.  
  761.  
  762.      4  PROTOCOLS SUPPORTED BY THE GATEWAY
  763.  
  764.  
  765.           A number of  protocols  are  supported  by  the  gateway  to
  766.  
  767.      provide   dynamic   routing,  monitoring,  debugging,  and  error
  768.  
  769.      reporting.  These protocols are described below.
  770.  
  771.  
  772.  
  773.  
  774.      4.1  Cross-Net Debugging Protocol
  775.  
  776.  
  777.           The Cross-Net Debugging Protocol (XNET) [8] is used to  load
  778.  
  779.      the  gateway  and  to  examine  and  deposit  data.   The gateway
  780.  
  781.      supports the following XNET op-codes:
  782.  
  783.  
  784.           o  NOP
  785.           o  Debug
  786.           o  End Debug
  787.           o  Deposit
  788.           o  Examine
  789.           o  Create Process
  790.  
  791.  
  792.  
  793.  
  794.      4.2  Host Monitoring Protocol
  795.  
  796.  
  797.           The Host Monitoring Protocol (HMP) [6] is  used  to  collect
  798.  
  799.      measurements   and   status   information   from   the  gateways.
  800.  
  801.      Exceptional conditions in the gateways are reported in HMP traps.
  802.  
  803.      The status of a gateway's interfaces, neighbors, and the networks
  804.  
  805.      which it can reach are reported in the HMP status message.
  806.  
  807.  
  808.  
  809.                                    -12-
  810.  
  811.  
  812.  
  813.  
  814.  
  815.      DARPA Internet Gateway                             September 1982
  816.      RFC 823
  817.  
  818.  
  819.  
  820.           Two types of gateway statistics, the Host Traffic Matrix and
  821.  
  822.      the  gateway  throughput,  are currently defined by the HMP.  The
  823.  
  824.      Host Traffic Matrix records the number  of  datagrams  that  pass
  825.  
  826.      through  the  gateway  with  a  given IP source, destination, and
  827.  
  828.      protocol number.   The  gateway  throughput  message  collects  a
  829.  
  830.      number  of  important counters that are kept by the gateway.  The
  831.  
  832.      current gateway reports the following values:
  833.  
  834.  
  835.           o  Datagrams dropped because destination net unreachable
  836.  
  837.           o  Datagrams dropped because destination host unreachable
  838.  
  839.  
  840.           o  Per Interface:
  841.                   Datagrams received with IP errors
  842.                   Datagrams received for this gateway
  843.                   Datagrams received to be forwarded
  844.                   Datagrams looped
  845.                   Bytes received
  846.                   Datagrams sent, originating at this gateway
  847.                   Datagrams sent to destination hosts
  848.                   Datagrams dropped due to flow control limitations
  849.                   Datagrams dropped due to full queue
  850.                   Bytes sent
  851.  
  852.           o  Per Neighbor:
  853.                   Routing updates sent to
  854.                   Routing updates received from
  855.                   Datagrams sent, originating here
  856.                   Datagrams forwarded to
  857.                   Datagrams dropped due to flow control limitations
  858.                   Datagrams dropped due to full queue
  859.                   Bytes sent
  860.  
  861.  
  862.  
  863.  
  864.  
  865.  
  866.  
  867.                                    -13-
  868.  
  869.  
  870.  
  871.  
  872.  
  873.      DARPA Internet Gateway                             September 1982
  874.      RFC 823
  875.  
  876.  
  877.  
  878.      4.3  ICMP
  879.  
  880.  
  881.           The gateway will generate the following ICMP messages  under
  882.  
  883.      appropriate  circumstances  as  defined by the ICMP specification
  884.  
  885.      [4]:
  886.  
  887.  
  888.           o  Echo Reply
  889.           o  Destination Unreachable
  890.           o  Source Quench
  891.           o  Redirect
  892.           o  Time Exceeded
  893.           o  Parameter Problem
  894.           o  Information Reply
  895.  
  896.  
  897.  
  898.  
  899.      4.4  Gateway-to-Gateway Protocol
  900.  
  901.  
  902.           The gateway uses the Gateway-to-Gateway  Protocol  (GGP)  to
  903.  
  904.      determine  connectivity  to networks and neighbor gateways; it is
  905.  
  906.      also used in  the  implementation  of  a  dynamic,  shortest-path
  907.  
  908.      routing  algorithm.  The current GGP message formats (for release
  909.  
  910.      1003 of the gateway software) are presented in Appendix A.
  911.  
  912.  
  913.  
  914.  
  915.      4.4.1  Determining Connectivity to Networks
  916.  
  917.  
  918.           When a gateway  starts  running  it  assumes  that  all  its
  919.  
  920.      neighbor  gateways  are  "down,"  that  it  is  disconnected from
  921.  
  922.  
  923.  
  924.  
  925.                                    -14-
  926.  
  927.  
  928.  
  929.  
  930.  
  931.      DARPA Internet Gateway                             September 1982
  932.      RFC 823
  933.  
  934.  
  935.  
  936.      networks to which it is attached, and that the distance  reported
  937.  
  938.      in  routing  updates  from  each  neighbor  to  each  network  is
  939.  
  940.      "infinity."
  941.  
  942.  
  943.           The gateway first determines the state of  its  connectivity
  944.  
  945.      to  networks  to  which it is physically attached.  The gateway's
  946.  
  947.      connection to a network is declared up if it can send and receive
  948.  
  949.      internet  datagrams  on its interface to that network.  Note that
  950.  
  951.      the method that the gateway uses to determine its connectivity to
  952.  
  953.      a  network  is network-dependent.  In some networks, the host-to-
  954.  
  955.      network protocol determines whether or not datagrams can be  sent
  956.  
  957.      and  received  on  the  host  interface.   In these networks, the
  958.  
  959.      gateway simply checks-status information provided by the protocol
  960.  
  961.      in order to determine if it can communicate with the network.  In
  962.  
  963.      other networks, where  the  host-to-network  protocols  are  less
  964.  
  965.      sophisticated,  it  may  be  necessary  for  the  gateway to send
  966.  
  967.      datagrams to itself to determine if it can communicate  with  the
  968.  
  969.      network.   In  these networks, the gateways periodically poll the
  970.  
  971.      network using GGP network interface status messages [Appendix  A]
  972.  
  973.      to determine if the network interface is operational.
  974.  
  975.  
  976.           The gateway has two rules relevant to computing distances to
  977.  
  978.      networks:   1) if the gateway can send and receive traffic on its
  979.  
  980.  
  981.  
  982.  
  983.                                    -15-
  984.  
  985.  
  986.  
  987.  
  988.  
  989.      DARPA Internet Gateway                             September 1982
  990.      RFC 823
  991.  
  992.  
  993.  
  994.      network interface, its distance to the network is zero;  2) if it
  995.  
  996.      cannot send and receive traffic on the interface, its distance to
  997.  
  998.      the network is "infinity."  Note  that  if  a  gateway's  network
  999.  
  1000.      interface is not working, it may still be able to send traffic to
  1001.  
  1002.      the network on  an  alternate  route  via  one  of  its  neighbor
  1003.  
  1004.      gateways.
  1005.  
  1006.  
  1007.  
  1008.  
  1009.      4.4.2  Determining Connectivity to Neighbors
  1010.  
  1011.  
  1012.           The gateway determines connectivity to neighbors using a  "K
  1013.  
  1014.      out  of  N"  algorithm.   Every 15 seconds, the gateway sends GGP
  1015.  
  1016.      Echo messages  [Appendix  A]  to  each  of  its  neighbors.   The
  1017.  
  1018.      neighbors  respond  by  sending GGP echo replies.  If there is no
  1019.  
  1020.      reply to K out of  N  (current  values  are  K=3  and  N=4)  echo
  1021.  
  1022.      messages sent to a neighbor, the neighbor is declared down.  If a
  1023.  
  1024.      neighbor is down and J out of M (current values are J=2 and  M=4)
  1025.  
  1026.      echo  replies  are  received,  the neighbor is declared to be up.
  1027.  
  1028.      The values of J,K,M,N  and  the  time  interval  are  operational
  1029.  
  1030.      parameters which can be adjusted as required.
  1031.  
  1032.  
  1033.  
  1034.  
  1035.  
  1036.  
  1037.  
  1038.  
  1039.  
  1040.  
  1041.                                    -16-
  1042.  
  1043.  
  1044.  
  1045.  
  1046.  
  1047.      DARPA Internet Gateway                             September 1982
  1048.      RFC 823
  1049.  
  1050.  
  1051.  
  1052.      4.4.3  Exchanging Routing Information
  1053.  
  1054.  
  1055.           The gateway sends routing information in GGP Routing  Update
  1056.  
  1057.      messages.  The gateway receives and transmits routing information
  1058.  
  1059.      reliably using sequence-numbered messages  and  a  retransmission
  1060.  
  1061.      and acknowledgment scheme as explained below.  For each neighbor,
  1062.  
  1063.      the gateway remembers the Receive Sequence  Number,  R,  that  it
  1064.  
  1065.      received  in  the  most recent routing update from that neighbor.
  1066.  
  1067.      This value is initialized with the sequence number in  the  first
  1068.  
  1069.      Routing  Update  received  from  a neighbor after that neighbor's
  1070.  
  1071.      status is set to "up."  On receipt of a  routing  update  from  a
  1072.  
  1073.      neighbor,  the  gateway subtracts the Receive Sequence Number, R,
  1074.  
  1075.      from the sequence number in the routing update, S. If this  value
  1076.  
  1077.      (S-R)  is greater than or equal to zero, then the gateway accepts
  1078.  
  1079.      the routing update, sends an acknowledgment (see Appendix  A)  to
  1080.  
  1081.      the  neighbor  containing the sequence number S, and replaces the
  1082.  
  1083.      Receive Sequence Number, R, with S. If this value (S-R)  is  less
  1084.  
  1085.      than  zero,  the  gateway  rejects the routing update and sends a
  1086.  
  1087.      negative  acknowledgment  [Appendix  A]  to  the  neighbor   with
  1088.  
  1089.      sequence number R.
  1090.  
  1091.  
  1092.           The gateway has a  Send  Sequence  Number,  N,  for  sending
  1093.  
  1094.      routing  updates  to  all of its neighbors.  This sequence number
  1095.  
  1096.  
  1097.  
  1098.  
  1099.                                    -17-
  1100.  
  1101.  
  1102.  
  1103.  
  1104.  
  1105.      DARPA Internet Gateway                             September 1982
  1106.      RFC 823
  1107.  
  1108.  
  1109.  
  1110.      can be initialized to any value.  The  Send  Sequence  Number  is
  1111.  
  1112.      incremented  each  time  a  new  routing  update  is created.  On
  1113.  
  1114.      receiving an acknowledgment for a  routing  update,  the  gateway
  1115.  
  1116.      subtracts  the  sequence  number  acknowledged,  A, from the Send
  1117.  
  1118.      Sequence Number, N.  If the value (N-A) is non-zero, then an  old
  1119.  
  1120.      routing  update  is being acknowledged.  The gateway continues to
  1121.  
  1122.      retransmit the most recent routing update to  the  neighbor  that
  1123.  
  1124.      sent  the  acknowledgment.   If (N-A) is zero, the routing update
  1125.  
  1126.      has been acknowledged.  Note that only the  most  recent  routing
  1127.  
  1128.      update  must  be  acknowledged;  if  a  second  routing update is
  1129.  
  1130.      generated before the first routing update is  acknowledged,  only
  1131.  
  1132.      the second routing update must be acknowledged.
  1133.  
  1134.  
  1135.           If  a  negative  acknowledgment  is  received,  the  gateway
  1136.  
  1137.      subtracts  the  sequence  number negatively acknowledged, A, from
  1138.  
  1139.      its Send Sequence Number, N.  If this value (N-A)  is  less  than
  1140.  
  1141.      zero, then the gateway replaces its Send Sequence Number, N, with
  1142.  
  1143.      the sequence number negatively acknowledged plus  one,  A+1,  and
  1144.  
  1145.      retransmits the routing update to all of its neighbors.  If (N-A)
  1146.  
  1147.      is greater than or equal to zero, then the gateway  continues  to
  1148.  
  1149.      retransmit  the routing update using sequence number N.  In order
  1150.  
  1151.      to maintain the correct sequence numbers at all gateways, routing
  1152.  
  1153.      updates  must  be  retransmitted  to  all  neighbors  if the Send
  1154.  
  1155.  
  1156.  
  1157.                                    -18-
  1158.  
  1159.  
  1160.  
  1161.  
  1162.  
  1163.      DARPA Internet Gateway                             September 1982
  1164.      RFC 823
  1165.  
  1166.  
  1167.  
  1168.      Sequence Number changes, even if the routing information does not
  1169.  
  1170.      change.
  1171.  
  1172.  
  1173.           The gateway retransmits routing updates  periodically  until
  1174.  
  1175.      they  are  acknowledged  and  whenever  its  Send Sequence Number
  1176.  
  1177.      changes.  The gateway sends routing  updates  only  to  neighbors
  1178.  
  1179.      that are in the "up" state.
  1180.  
  1181.  
  1182.  
  1183.  
  1184.      4.4.4  Computing Routes
  1185.  
  1186.  
  1187.           A routing update  contains  a  list  of  networks  that  are
  1188.  
  1189.      reachable  through  this  gateway, and the distance in "number of
  1190.  
  1191.      hops"  to  each  network  mentioned.   The  routing  update  only
  1192.  
  1193.      contains information about a network if the gateway believes that
  1194.  
  1195.      it is as close or closer to that network then the neighbor  which
  1196.  
  1197.      is  to receive the routing update.  The network address may be an
  1198.  
  1199.      internet class A, B, or C address.
  1200.  
  1201.  
  1202.           The information inside a  routing  update  is  processed  as
  1203.  
  1204.      follows.   The gateway contains an N x K distance matrix, where N
  1205.  
  1206.      is the number of  networks  and  K  is  the  number  of  neighbor
  1207.  
  1208.      gateways.   An  entry  in this matrix, represented as dm(I,J), is
  1209.  
  1210.      the distance to network I from neighbor J as reported in the most
  1211.  
  1212.  
  1213.  
  1214.  
  1215.                                    -19-
  1216.  
  1217.  
  1218.  
  1219.  
  1220.  
  1221.      DARPA Internet Gateway                             September 1982
  1222.      RFC 823
  1223.  
  1224.  
  1225.  
  1226.      recent routing update from neighbor J.  The gateway also contains
  1227.  
  1228.      a vector indicating  the  connectivity  between  itself  and  its
  1229.  
  1230.      neighbor  gateways.   The  values  in this vector are computed as
  1231.  
  1232.      discussed above (see Section 4.4.2, Determining  Connectivity  to
  1233.  
  1234.      Neighbors).   The value of the Jth entry of this vector, which is
  1235.  
  1236.      the connectivity between the gateway and  the  Jth  neighbor,  is
  1237.  
  1238.      represented as d(J).
  1239.  
  1240.  
  1241.           The gateway copies the routing update received from the  Jth
  1242.  
  1243.      neighbor  into  the  appropriate row of the distance matrix, then
  1244.  
  1245.      updates its routes as follows.  The gateway calculates a  minimum
  1246.  
  1247.      distance  vector  which  contains  the  minimum  distance to each
  1248.  
  1249.      network  from  the  gateway.   The  Ith  entry  of  this  vector,
  1250.  
  1251.      represented as MinD(I) is:
  1252.  
  1253.  
  1254.        MinD(I) = minimum over all neighbors of d(J) + dm(I,J)
  1255.  
  1256.  
  1257.      where d(J) is the  distance  between  the  gateway  and  the  Jth
  1258.  
  1259.      neighbor,  and  dm(I,J)  is the distance from the Jth neighbor to
  1260.  
  1261.      the Ith network.  If the Ith network is attached to  the  gateway
  1262.  
  1263.      and  the  gateway  can  send  and  receive traffic on its network
  1264.  
  1265.      interface (see Section 4.4.2), then  the  gateway  sets  the  Ith
  1266.  
  1267.      entry of the minimum distance vector to zero.
  1268.  
  1269.  
  1270.  
  1271.  
  1272.  
  1273.                                    -20-
  1274.  
  1275.  
  1276.  
  1277.  
  1278.  
  1279.      DARPA Internet Gateway                             September 1982
  1280.      RFC 823
  1281.  
  1282.  
  1283.  
  1284.           Using the minimum distance vector, the  gateway  computes  a
  1285.  
  1286.      list  of  neighbor gateways through which to send traffic to each
  1287.  
  1288.      network.  The entry for a  given  network  contains  one  of  the
  1289.  
  1290.      neighbors that is the minimum distance away from that network.
  1291.  
  1292.  
  1293.           After updating its  routes  to  the  networks,  the  gateway
  1294.  
  1295.      computes  the  new  routing  updates to be sent to its neighbors.
  1296.  
  1297.      The gateway reports a network to a neighbor  only  if  it  is  as
  1298.  
  1299.      close  to  or closer to that network than its neighbor.  For each
  1300.  
  1301.      network I, the routing update contains the address of the network
  1302.  
  1303.      and the minimum distance to that network which is MinD(I).
  1304.  
  1305.  
  1306.           Finally, the gateway must determine whether it  should  send
  1307.  
  1308.      routing  updates to its neighbors.  The gateway sends new updates
  1309.  
  1310.      to its neighbors if every one of the following  three  conditions
  1311.  
  1312.      occurs:   1)  one  of the gateway's interfaces changes state,  2)
  1313.  
  1314.      one of the gateway's neighbor gateways changes state, and  3) the
  1315.  
  1316.      gateway  receives  a  routing  update  from  a  neighbor  that is
  1317.  
  1318.      different from the update that it had  previously  received  from
  1319.  
  1320.      that  neighbor.   The  gateway  sends  routing  updates  only  to
  1321.  
  1322.      neighbors that are currently in the "up" state.
  1323.  
  1324.  
  1325.           The gateway requests a routing update  from  neighbors  that
  1326.  
  1327.      are  in  the  "up"  state,  but  from which it has yet received a
  1328.  
  1329.  
  1330.  
  1331.                                    -21-
  1332.  
  1333.  
  1334.  
  1335.  
  1336.  
  1337.      DARPA Internet Gateway                             September 1982
  1338.      RFC 823
  1339.  
  1340.  
  1341.  
  1342.      routing update.  Routing updates are  requested  by  setting  the
  1343.  
  1344.      appropriate  bit  in  the routing update being sent [Appendix A].
  1345.  
  1346.      Similarly, if a gateway receives from a neighbor a routing update
  1347.  
  1348.      in  which the bit requesting a routing update is set, the gateway
  1349.  
  1350.      sends the neighbor the most recent routing update.
  1351.  
  1352.  
  1353.  
  1354.  
  1355.      4.4.5  Non-Routing Gateways
  1356.  
  1357.  
  1358.           A Non-routing Gateway is a gateway  that  forwards  internet
  1359.  
  1360.      traffic,  but  does  not  implement  the  GGP  routing algorithm.
  1361.  
  1362.      Networks that are behind a Non-routing Gateway are known a-priori
  1363.  
  1364.      to  Routing Gateways.  There can be one or more of these networks
  1365.  
  1366.      which are considered to be directly connected to the  Non-routing
  1367.  
  1368.      Gateway.   A  Routing  Gateway  will forward a datagram to a Non-
  1369.  
  1370.      routing Gateway if it is addressed to a network behind  the  Non-
  1371.  
  1372.      routing   Gateway.    Routing  Gateways  currently  do  not  send
  1373.  
  1374.      Redirects for  Non-routing  Gateways.   A  Routing  Gateway  will
  1375.  
  1376.      always  use  another  Routing Gateway as a path instead of a Non-
  1377.  
  1378.      routing Gateways if both exist and are the same  number  of  hops
  1379.  
  1380.      away from the destination network.  The Non-routing Gateways path
  1381.  
  1382.      will be used only when the Routing Gateway path is down; when the
  1383.  
  1384.      Routing Gateway path comes back up, it will be used again.
  1385.  
  1386.  
  1387.  
  1388.  
  1389.                                    -22-
  1390.  
  1391.  
  1392.  
  1393.  
  1394.  
  1395.      DARPA Internet Gateway                             September 1982
  1396.      RFC 823
  1397.  
  1398.  
  1399.  
  1400.      4.4.6  Adding New Neighbors and Networks
  1401.  
  1402.  
  1403.           Gateways  dynamically  add  routing  information  about  new
  1404.  
  1405.      neighbors   and  new  networks  to  their  tables.   The  gateway
  1406.  
  1407.      maintains a list of neighbor gateway addresses.  When  a  routing
  1408.  
  1409.      update  is  received, the gateway searches this list of addresses
  1410.  
  1411.      for the Internet source address of the  routing  update  message.
  1412.  
  1413.      If  the  Internet  source  address  of  the routing update is not
  1414.  
  1415.      contained in the list of neighbor  addresses,  the  gateway  adds
  1416.  
  1417.      this  address  to  the  list  of  neighbor addresses and sets the
  1418.  
  1419.      neighbor's connectivity status to "down."   Routing  updates  are
  1420.  
  1421.      not  accepted  from neighbors until the GGP polling mechanism has
  1422.  
  1423.      determined that the neighbor is up.
  1424.  
  1425.  
  1426.           This strategy of adding  new  neighbors  requires  that  one
  1427.  
  1428.      gateway   in  each  pair  of  neighbor  gateways  must  have  the
  1429.  
  1430.      neighbor's address configured in its tables.  The newest  gateway
  1431.  
  1432.      can be given a complete list of neighbors, thus avoiding the need
  1433.  
  1434.      to re-configure older gateways when new gateways are installed.
  1435.  
  1436.  
  1437.           Gateways obtain routing information about  new  networks  in
  1438.  
  1439.      several  steps.   The  gateway has a list of all the networks for
  1440.  
  1441.      which it currently maintains routing information.  When a routing
  1442.  
  1443.      update  is  received,  if the routing update contains information
  1444.  
  1445.  
  1446.  
  1447.                                    -23-
  1448.  
  1449.  
  1450.  
  1451.  
  1452.  
  1453.      DARPA Internet Gateway                             September 1982
  1454.      RFC 823
  1455.  
  1456.  
  1457.  
  1458.      about a new network, the gateway adds this network to the list of
  1459.  
  1460.      networks  for  which it maintains routing information.  Next, the
  1461.  
  1462.      gateway adds  the  new  network  to  its  distance  matrix.   The
  1463.  
  1464.      distance  matrix comprises the is the matrix of distances (number
  1465.  
  1466.      of hops) to networks as reported  in  routing  updates  from  the
  1467.  
  1468.      neighbor  gateways.   The  gateway  sets  the distance to all new
  1469.  
  1470.      networks to "infinity," and then  computes  new  routes  and  new
  1471.  
  1472.      routing updates as outlined above.
  1473.  
  1474.  
  1475.  
  1476.  
  1477.      4.5  Exterior Gateway Protocol
  1478.  
  1479.  
  1480.           The Exterior Gateway Protocol (EGP) is used to permit  other
  1481.  
  1482.      gateways  and  gateway systems to pass routing information to the
  1483.  
  1484.      DARPA Internet gateways.  The use of the EGP permits the user  to
  1485.  
  1486.      perceive  all  of  the networks and gateways as part of one total
  1487.  
  1488.      Internet system, even though the "exterior" gateways are disjoint
  1489.  
  1490.      and  may  use  a  routing  algorithm  that  is  different and not
  1491.  
  1492.      compatible with  that  used  in  the  "interior"  gateways.   The
  1493.  
  1494.      important elements of the EGP are:
  1495.  
  1496.  
  1497.      o Neighbor Acquisition
  1498.  
  1499.           The procedure by which a gateway requests that it  become  a
  1500.           neighbor  of  another  gateway.  This is used when a gateway
  1501.           wants to become a neighbor  of  another  in  order  to  pass
  1502.  
  1503.  
  1504.  
  1505.                                    -24-
  1506.  
  1507.  
  1508.  
  1509.  
  1510.  
  1511.      DARPA Internet Gateway                             September 1982
  1512.      RFC 823
  1513.  
  1514.  
  1515.  
  1516.           routing information.  This includes the capability to accept
  1517.           or refuse the request.
  1518.  
  1519.      o Neighbor Up/Down
  1520.  
  1521.           The procedure by which a gateway decides if another  gateway
  1522.           is up or down.
  1523.  
  1524.      o Network Reachability Information
  1525.  
  1526.           The facility used to pass routing and  neighbor  information
  1527.           between gateways.
  1528.  
  1529.      o Gateway Going Down
  1530.  
  1531.           The ability of a gateway to inform other gateways that it is
  1532.           going  down  and  no  longer  has  any  routes  to any other
  1533.           networks.  This permits a gateway to go down in  an  orderly
  1534.           way without disrupting the rest of the Internet system.
  1535.  
  1536.  
  1537.      A complete description of the EGP can be found  in  IEN-209,  the
  1538.  
  1539.      "Exterior Gateway Protocol" [10].
  1540.  
  1541.  
  1542.  
  1543.  
  1544.  
  1545.  
  1546.  
  1547.  
  1548.  
  1549.  
  1550.  
  1551.  
  1552.  
  1553.  
  1554.  
  1555.  
  1556.  
  1557.  
  1558.  
  1559.  
  1560.  
  1561.  
  1562.  
  1563.                                    -25-
  1564.  
  1565.  
  1566.  
  1567.  
  1568.  
  1569.      DARPA Internet Gateway                             September 1982
  1570.      RFC 823
  1571.  
  1572.  
  1573.  
  1574.      5  GATEWAY SOFTWARE
  1575.  
  1576.  
  1577.           The DARPA Internet Gateway  runs  under  the  MOS  operating
  1578.  
  1579.      system [9] which provides facilities for:
  1580.  
  1581.  
  1582.           o Multiple processes
  1583.           o Interprocess communication
  1584.           o Buffer management
  1585.           o Asynchronous input/output
  1586.           o Shareable real-time clock
  1587.  
  1588.  
  1589.      There is a MOS process for  each  network  that  the  gateway  is
  1590.  
  1591.      directly  connected  to.   A  data  structure  called  a NETBLOCK
  1592.  
  1593.      contains variables of interest for each network and  pointers  to
  1594.  
  1595.      local  network  routines.   Network  processes run common gateway
  1596.  
  1597.      code while  network-specific  functions  are  dispatched  to  the
  1598.  
  1599.      routines  pointed  to  in the NETBLOCK.  There are also processes
  1600.  
  1601.      for gateway functions which require their own timing, such as GGP
  1602.  
  1603.      and HMP.
  1604.  
  1605.  
  1606.  
  1607.  
  1608.      5.1  Software Structure
  1609.  
  1610.  
  1611.           The gateway software can be divided conceptually into  three
  1612.  
  1613.      parts:   MOS Device Drivers, Network software, and Shared Gateway
  1614.  
  1615.      software.
  1616.  
  1617.  
  1618.  
  1619.  
  1620.  
  1621.                                    -26-
  1622.  
  1623.  
  1624.  
  1625.  
  1626.  
  1627.      DARPA Internet Gateway                             September 1982
  1628.      RFC 823
  1629.  
  1630.  
  1631.  
  1632.      5.1.1  Device Drivers
  1633.  
  1634.  
  1635.           The gateway has a set of  routines  to  handle  sending  and
  1636.  
  1637.      receiving  data  for  each type of hardware interface.  There are
  1638.  
  1639.      routines for initialization,  initiation,  and  interruption  for
  1640.  
  1641.      both  the  transmit  and  receive sides of a device.  The gateway
  1642.  
  1643.      supports the following types of devices:
  1644.  
  1645.  
  1646.           a)  ACC LSI-11 1822
  1647.           b)  DEC IMP11a 1822
  1648.           c)  ACC LHDH 1822
  1649.           d)  ACC VDH11E
  1650.           e)  ACC VDH11C
  1651.           f)  Proteon Ring Network
  1652.           g)  RSRE HDLC
  1653.           h)  Interlan Ethernet
  1654.           i)  BBN Fibernet
  1655.           j)  ACC XQ/CP X.25 **
  1656.           k)  ACC XQ/CP HDH  **
  1657.  
  1658.  
  1659.  
  1660.  
  1661.      5.1.2  Network Software
  1662.  
  1663.  
  1664.           For each connected network, the gateway has a set  of  eight
  1665.  
  1666.      routines  which  handle  local  network  functions.   The network
  1667.  
  1668.      routines and their functions are described briefly below.
  1669.  
  1670.  
  1671.  
  1672.  
  1673.      _______________
  1674.      ** Planned, not yet supported.
  1675.  
  1676.  
  1677.  
  1678.  
  1679.                                    -27-
  1680.  
  1681.  
  1682.  
  1683.  
  1684.  
  1685.      DARPA Internet Gateway                             September 1982
  1686.      RFC 823
  1687.  
  1688.  
  1689.  
  1690.           Up.net    Perform  local  network  initialization  such   as
  1691.                     flapping the 1822 ready line.
  1692.  
  1693.           Sg.net    Handle specific  local  network  timing  functions
  1694.                     such as timing out 1822 Destination Deads.
  1695.  
  1696.           Rc.net    A message  has  been  received  from  the  network
  1697.                     interface.  Check for any input errors.
  1698.  
  1699.           Wc.net    A message has  been  transmitted  to  the  network
  1700.                     interface.  Check for any output errors.
  1701.  
  1702.           Rs.net    Set up a buffer (or buffers) to  receive  messages
  1703.                     on the network interface.
  1704.  
  1705.           Ws.net    Transmit a message to the network interface.
  1706.  
  1707.           Hc.net    Check the local network  header  of  the  received
  1708.                     message.    Perform  any  local  network  protocol
  1709.                     tasks.
  1710.  
  1711.           Hb.net    Rebuild the local network header.
  1712.  
  1713.  
  1714.           There are  network  routines  for  the  following  types  of
  1715.  
  1716.      networks:
  1717.  
  1718.  
  1719.           o  Arpanet (a,b,c,k)
  1720.           o  Satnet (d,e,k)
  1721.           o  Proteon Ring Network (f)
  1722.           o  Packet Radio Network (a,b,c)
  1723.           o  Rsre HDLC Null Network (g)
  1724.           o  Ethernet (h)
  1725.           o  Fibernet (i)
  1726.           o  Telenet X.25 (j) **
  1727.  
  1728.  
  1729.      Note: The letters in parentheses refer to the device drivers used
  1730.  
  1731.      _______________
  1732.      ** Planned, not yet supported.
  1733.  
  1734.  
  1735.  
  1736.  
  1737.                                    -28-
  1738.  
  1739.  
  1740.  
  1741.  
  1742.  
  1743.      DARPA Internet Gateway                             September 1982
  1744.      RFC 823
  1745.  
  1746.  
  1747.  
  1748.      for each type of network as described in the previous section.
  1749.  
  1750.  
  1751.  
  1752.  
  1753.      5.1.3  Shared Gateway Software
  1754.  
  1755.  
  1756.           The internet processing of a datagram is performed by a body
  1757.  
  1758.      of  code  which  is  shared  by the network processes.  This code
  1759.  
  1760.      includes  routines  to  check   the   IP   header,   perform   IP
  1761.  
  1762.      fragmentation, calculate the IP checksum, forward a datagram, and
  1763.  
  1764.      implement the routing, monitoring, and error reporting protocols.
  1765.  
  1766.  
  1767.  
  1768.  
  1769.      5.2  Gateway Processes
  1770.  
  1771.  
  1772.      5.2.1  Network Processes
  1773.  
  1774.  
  1775.           When the gateway starts up, each network process  calls  its
  1776.  
  1777.      local network initialization routine and read start routine.  The
  1778.  
  1779.      read start routine sets up two maximum network size  buffers  for
  1780.  
  1781.      receiving datagrams.  The network process then waits for an input
  1782.  
  1783.      complete signal from the network device driver.
  1784.  
  1785.  
  1786.           When a message has been received, the MOS  Operating  System
  1787.  
  1788.      signals  the  appropriate  network process with an input complete
  1789.  
  1790.      signal.  The network process wakes up and executes the  net  read
  1791.  
  1792.  
  1793.  
  1794.  
  1795.                                    -29-
  1796.  
  1797.  
  1798.  
  1799.  
  1800.  
  1801.      DARPA Internet Gateway                             September 1982
  1802.      RFC 823
  1803.  
  1804.  
  1805.  
  1806.      complete  routine.   After  the  message  has been processed, the
  1807.  
  1808.      network process waits for more input.
  1809.  
  1810.  
  1811.           The  net  read  complete  routine  is  the   major   message
  1812.  
  1813.      processing  loop  in  the  gateway.   The  following  actions are
  1814.  
  1815.      performed when a message has been received:
  1816.  
  1817.  
  1818.           o  Call Local Network Read Complete Routine
  1819.           o  Start more reads
  1820.           o  Check local Network Header
  1821.           o  Check Internet header
  1822.           o  Check if datagram is for the gateway
  1823.           o  Forward the datagram if necessary
  1824.           o  Send ICMP error message if necessary.
  1825.  
  1826.  
  1827.  
  1828.  
  1829.      5.2.2  GGP Process
  1830.  
  1831.  
  1832.           The GGP process periodically sends GGP echos to each of  the
  1833.  
  1834.      gateway's neighbors to determine neighbor connectivity, and sends
  1835.  
  1836.      interface  status  messages  addressed  to  itself  to  determine
  1837.  
  1838.      network  connectivity.   The  GGP  process also sends out routing
  1839.  
  1840.      updates when necessary.  The details of the algorithms  currently
  1841.  
  1842.      implemented  by  the  GGP  process  are  given  in  Section  4.4,
  1843.  
  1844.      Gateway-to-Gateway Protocol, and in Appendix C.
  1845.  
  1846.  
  1847.  
  1848.  
  1849.  
  1850.  
  1851.  
  1852.  
  1853.                                    -30-
  1854.  
  1855.  
  1856.  
  1857.  
  1858.  
  1859.      DARPA Internet Gateway                             September 1982
  1860.      RFC 823
  1861.  
  1862.  
  1863.  
  1864.      5.2.3  HMP Process
  1865.  
  1866.  
  1867.           The  HMP  process  handles  timer-based  gateway  statistics
  1868.  
  1869.      collection and the periodic transmission of traps.
  1870.  
  1871.  
  1872.  
  1873.  
  1874.  
  1875.  
  1876.  
  1877.  
  1878.  
  1879.  
  1880.  
  1881.  
  1882.  
  1883.  
  1884.  
  1885.  
  1886.  
  1887.  
  1888.  
  1889.  
  1890.  
  1891.  
  1892.  
  1893.  
  1894.  
  1895.  
  1896.  
  1897.  
  1898.  
  1899.  
  1900.  
  1901.  
  1902.  
  1903.  
  1904.  
  1905.  
  1906.  
  1907.  
  1908.  
  1909.  
  1910.  
  1911.                                    -31-
  1912.  
  1913.  
  1914.  
  1915.  
  1916.  
  1917.      DARPA Internet Gateway                             September 1982
  1918.      RFC 823
  1919.  
  1920.  
  1921.  
  1922.      APPENDIX A. GGP Message Formats
  1923.  
  1924.  
  1925.           Note that the GGP protocol is currently undergoing extensive
  1926.  
  1927.      changes to introduce the Exterior Gateway Protocol facility; this
  1928.  
  1929.      is the vehicle needed to permit  gateways  in  other  systems  to
  1930.  
  1931.      exchange  routing information with the gateways described in this
  1932.  
  1933.      document.
  1934.  
  1935.  
  1936.           Each GGP message consists of an Internet header followed  by
  1937.  
  1938.      one  of the messages explained below.  The values (in decimal) in
  1939.  
  1940.      the Internet header used in a GGP message are as follows.
  1941.  
  1942.  
  1943.      Version                  4.
  1944.  
  1945.      IHL                      Internet header length in 32-bit words.
  1946.  
  1947.      Type of Service          0.
  1948.  
  1949.      Total Length             Length of Internet header  and  data  in
  1950.                               octets.
  1951.  
  1952.      ID, Flags,
  1953.      Fragment Offset          0.
  1954.  
  1955.      Time to Live             Time to live in seconds.  This field  is
  1956.                               decremented   at   least  once  by  each
  1957.                               machine that processes the datagram.
  1958.  
  1959.      Protocol                 Gateway Protocol = 3.
  1960.  
  1961.      Header Checksum          The 16 bit one's complement of the one's
  1962.                               complement  sum  of  all 16-bit words in
  1963.                               the header.  For computing the checksum,
  1964.                               the checksum field should be zero.
  1965.  
  1966.  
  1967.  
  1968.  
  1969.                                    -32-
  1970.  
  1971.  
  1972.  
  1973.  
  1974.  
  1975.      DARPA Internet Gateway                             September 1982
  1976.      RFC 823
  1977.  
  1978.  
  1979.  
  1980.      Source Address           The address of the  gateway's  interface
  1981.                               from which the message is sent.
  1982.  
  1983.      Destination Address      The address of the gateway to which  the
  1984.                               message is sent.
  1985.  
  1986.  
  1987.  
  1988.  
  1989.  
  1990.  
  1991.  
  1992.  
  1993.  
  1994.  
  1995.  
  1996.  
  1997.  
  1998.  
  1999.  
  2000.  
  2001.  
  2002.  
  2003.  
  2004.  
  2005.  
  2006.  
  2007.  
  2008.  
  2009.  
  2010.  
  2011.  
  2012.  
  2013.  
  2014.  
  2015.  
  2016.  
  2017.  
  2018.  
  2019.  
  2020.  
  2021.  
  2022.  
  2023.  
  2024.  
  2025.  
  2026.  
  2027.                                    -33-
  2028.  
  2029.  
  2030.  
  2031.  
  2032.  
  2033.      DARPA Internet Gateway                             September 1982
  2034.      RFC 823
  2035.  
  2036.  
  2037.  
  2038.      ROUTING UPDATE
  2039.  
  2040.  
  2041.       0                   1
  2042.       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
  2043.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2044.      !Gateway Type   !  unused (0)   !                 ; 2 bytes
  2045.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2046.      !     Sequence Number           !                 ; 2 bytes
  2047.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2048.      !  need-update  !  n-distances  !                 ; 2 bytes
  2049.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2050.      !  distance 1   !   n1-dist     !                 ; 2 bytes
  2051.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2052.      !   net11       !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; 1, 2 or 3
  2053.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ;   bytes
  2054.      !   net12       !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; 1, 2 or 3
  2055.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ;   bytes
  2056.                                      .
  2057.                                      .
  2058.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2059.      !   net1n1      !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!  ; n1 nets at
  2060.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  ;   dist 1
  2061.                                      .                      ...
  2062.                                      .                  ; ndist groups
  2063.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                  ;    of nets
  2064.      !  distance n   !   nn-dist     !                  ; 2 bytes
  2065.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2066.      !   netn1       !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!  ; 1, 2 or 3
  2067.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  ;   bytes
  2068.      !   netn2       !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!  ; 1, 2 or 3
  2069.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  ;   bytes
  2070.                                 .
  2071.                                 .
  2072.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2073.      !   netnnn      !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!  ; nn nets at
  2074.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  ;  dist n
  2075.  
  2076.      Gateway Type             12 (decimal)
  2077.  
  2078.      Sequence Number          The  16-bit  sequence  number  used   to
  2079.                               identify routing updates.
  2080.  
  2081.      need-update              An 8-bit field.  This byte is set  to  1
  2082.  
  2083.  
  2084.  
  2085.                                    -34-
  2086.  
  2087.  
  2088.  
  2089.  
  2090.  
  2091.      DARPA Internet Gateway                             September 1982
  2092.      RFC 823
  2093.  
  2094.  
  2095.  
  2096.                               if the source gateway requests a routing
  2097.                               update from the destination gateway, and
  2098.                               set to 0 if not.
  2099.  
  2100.      n-distances              An   8-bit   field.    The   number   of
  2101.                               distance-groups reported in this update.
  2102.                               Each  distance-group   consists   of   a
  2103.                               distance  value  and  a  number of nets,
  2104.                               followed by the actual net numbers which
  2105.                               are reachable at that distance.  Not all
  2106.                               distances need be reported.
  2107.  
  2108.      distance 1               hop count (or  other  distance  measure)
  2109.                               which applies to this distance-group.
  2110.  
  2111.      n1-dist                  number of nets  which  are  reported  in
  2112.                               this distance-group.
  2113.  
  2114.      net11                    1, 2, or 3 bytes for the  first  net  at
  2115.                               distance "distance 1".
  2116.  
  2117.      net12                    second net
  2118.  
  2119.      ...
  2120.  
  2121.      net1n1                   etc.
  2122.  
  2123.  
  2124.  
  2125.  
  2126.  
  2127.  
  2128.  
  2129.  
  2130.  
  2131.  
  2132.  
  2133.  
  2134.  
  2135.  
  2136.  
  2137.  
  2138.  
  2139.  
  2140.  
  2141.  
  2142.  
  2143.                                    -35-
  2144.  
  2145.  
  2146.  
  2147.  
  2148.  
  2149.      DARPA Internet Gateway                             September 1982
  2150.      RFC 823
  2151.  
  2152.  
  2153.  
  2154.      ACKNOWLEDGMENT or NEGATIVE ACKNOWLEDGMENT
  2155.  
  2156.  
  2157.       0                   1                   2                   3
  2158.       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
  2159.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2160.      | Gateway Type  |  Unused       |        Sequence number        |
  2161.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2162.  
  2163.  
  2164.      Gateway Type             Acknowledgments are  type  2.   Negative
  2165.                               acknowledgments are type 10.
  2166.  
  2167.      Sequence Number          The  16-bit  sequence  number  that  the
  2168.                               gateway  is  acknowledging or negatively
  2169.                               acknowledging.
  2170.  
  2171.  
  2172.  
  2173.  
  2174.  
  2175.  
  2176.  
  2177.  
  2178.  
  2179.  
  2180.  
  2181.  
  2182.  
  2183.  
  2184.  
  2185.  
  2186.  
  2187.  
  2188.  
  2189.  
  2190.  
  2191.  
  2192.  
  2193.  
  2194.  
  2195.  
  2196.  
  2197.  
  2198.  
  2199.  
  2200.  
  2201.                                    -36-
  2202.  
  2203.  
  2204.  
  2205.  
  2206.  
  2207.      DARPA Internet Gateway                             September 1982
  2208.      RFC 823
  2209.  
  2210.  
  2211.  
  2212.      GGP ECHO and ECHO REPLY
  2213.  
  2214.  
  2215.  
  2216.       0                   1                   2                   3
  2217.       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
  2218.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2219.      | Gateway Type  |            Unused                             |
  2220.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2221.  
  2222.  
  2223.      Gateway Type             8 for echo message; 0 for echo reply.
  2224.  
  2225.      Source Address           In an echo message, this is the  address
  2226.                               of  the  gateway  on the same network as
  2227.                               the neighbor to which it is sending  the
  2228.                               echo message.  In an echo reply message,
  2229.                               the source and destination addresses are
  2230.                               simply  reversed,  and  the remainder is
  2231.                               returned unchanged.
  2232.  
  2233.  
  2234.  
  2235.  
  2236.  
  2237.  
  2238.  
  2239.  
  2240.  
  2241.  
  2242.  
  2243.  
  2244.  
  2245.  
  2246.  
  2247.  
  2248.  
  2249.  
  2250.  
  2251.  
  2252.  
  2253.  
  2254.  
  2255.  
  2256.  
  2257.  
  2258.  
  2259.                                    -37-
  2260.  
  2261.  
  2262.  
  2263.  
  2264.  
  2265.      DARPA Internet Gateway                             September 1982
  2266.      RFC 823
  2267.  
  2268.  
  2269.  
  2270.      NETWORK INTERFACE STATUS
  2271.  
  2272.       0                   1                   2                   3
  2273.       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
  2274.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2275.      ! Gateway Type  !                  unused                       !
  2276.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2277.  
  2278.      Gateway Type             9
  2279.  
  2280.      Source Address
  2281.      Destination Address      The address  of  the  gateway's  network
  2282.                               interface.   The  gateway  can  send Net
  2283.                               Interface Status messages to  itself  to
  2284.                               determine  if  it  is  able  to send and
  2285.                               receive   traffic   on    its    network
  2286.                               interface.
  2287.  
  2288.  
  2289.  
  2290.  
  2291.  
  2292.  
  2293.  
  2294.  
  2295.  
  2296.  
  2297.  
  2298.  
  2299.  
  2300.  
  2301.  
  2302.  
  2303.  
  2304.  
  2305.  
  2306.  
  2307.  
  2308.  
  2309.  
  2310.  
  2311.  
  2312.  
  2313.  
  2314.  
  2315.  
  2316.  
  2317.                                    -38-
  2318.  
  2319.  
  2320.  
  2321.  
  2322.  
  2323.      DARPA Internet Gateway                             September 1982
  2324.      RFC 823
  2325.  
  2326.  
  2327.  
  2328.      APPENDIX B. Information Maintained by Gateways
  2329.  
  2330.  
  2331.           In order to implement the shortest-path  routing  algorithm,
  2332.  
  2333.      gateways  must  maintain  information about their connectivity to
  2334.  
  2335.      networks  and  other  gateways.   This   section   explains   the
  2336.  
  2337.      information  maintained  by each gateway; this information can be
  2338.  
  2339.      organized into the following tables and variables.
  2340.  
  2341.  
  2342.      o  Number of Networks
  2343.  
  2344.           The number of  networks  for  which  the  gateway  maintains
  2345.           routing information and to which it can forward traffic.
  2346.  
  2347.      o  Number of Neighbors
  2348.  
  2349.           The number of  neighbor  gateways  with  which  the  gateway
  2350.           exchanges routing information.
  2351.  
  2352.      o  Gateway Addresses
  2353.  
  2354.           The addresses of the gateway's network interfaces.
  2355.  
  2356.      o  Neighbor Gateway Addresses
  2357.  
  2358.           The address of each  neighbor  gateway's  network  interface
  2359.           that is on the same network as this gateway.
  2360.  
  2361.      o  Neighbor Connectivity Vector
  2362.  
  2363.           A vector of the connectivity between this gateway  and  each
  2364.           of its neighbors.
  2365.  
  2366.      o  Distance Matrix
  2367.  
  2368.           A matrix of the routing updates received from  the  neighbor
  2369.           gateways.
  2370.  
  2371.  
  2372.  
  2373.  
  2374.  
  2375.                                    -39-
  2376.  
  2377.  
  2378.  
  2379.  
  2380.  
  2381.      DARPA Internet Gateway                             September 1982
  2382.      RFC 823
  2383.  
  2384.  
  2385.  
  2386.      o  Minimum Distance Vector
  2387.  
  2388.           A vector containing the minimum distance to each network.
  2389.  
  2390.      o  Routing Updates from Non-Routing Gateways
  2391.  
  2392.           The routing updates that would have been received from  each
  2393.           non-routing  neighbor  gateway which does not participate in
  2394.           this routing strategy.
  2395.  
  2396.      o  Routing Table
  2397.  
  2398.           A table containing, for each network, a list of the neighbor
  2399.           gateways on a minimum-distance route to the network.
  2400.  
  2401.      o  Send Sequence Number
  2402.  
  2403.           The sequence number that will  be  used  to  send  the  next
  2404.           routing update.
  2405.  
  2406.      o  Receive Sequence Numbers
  2407.  
  2408.           The sequence numbers that the gateway received in  the  last
  2409.           routing update from each of its neighbors.
  2410.  
  2411.      o  Received Acknowledgment Vector
  2412.  
  2413.           A  vector  indicating  whether  or  not  each  neighbor  has
  2414.           acknowledged  the sequence number in the most recent routing
  2415.           update sent.
  2416.  
  2417.  
  2418.  
  2419.  
  2420.  
  2421.  
  2422.  
  2423.  
  2424.  
  2425.  
  2426.  
  2427.  
  2428.  
  2429.  
  2430.  
  2431.  
  2432.  
  2433.                                    -40-
  2434.  
  2435.  
  2436.  
  2437.  
  2438.  
  2439.      DARPA Internet Gateway                             September 1982
  2440.      RFC 823
  2441.  
  2442.  
  2443.  
  2444.      APPENDIX C. GGP Events and Responses
  2445.  
  2446.  
  2447.           The following list shows the GGP  events  that  occur  at  a
  2448.  
  2449.      gateway  and  the  gateway's responses.  The variables and tables
  2450.  
  2451.      referred to are listed above.
  2452.  
  2453.  
  2454.  
  2455.      o  Connectivity to an attached network changes.
  2456.  
  2457.           a. Update the Minimum Distance Vector.
  2458.           b. Recompute the Routing Updates.
  2459.           c. Recompute the Routing Table.
  2460.           d. If any routing update has changed, send the  new  routing
  2461.              updates to the neighbors.
  2462.  
  2463.      o  Connectivity to a neighbor gateway changes.
  2464.  
  2465.           a. Update the Neighbor Connectivity Vector.
  2466.           b. Recompute the Minimum Distance Vector.
  2467.           c. Recompute the Routing Updates.
  2468.           d. Recompute the Routing Table.
  2469.           e. If any routing update has changed, send the  new  routing
  2470.              updates to the neighbors.
  2471.  
  2472.      o  A Routing Update message is received.
  2473.  
  2474.           a. Compare the Internet source address of the Routing Update
  2475.              message to the Neighbor Addresses.  If the address is not
  2476.              on the list, add it to the list  of  Neighbor  Addresses,
  2477.              increment  the  Number  of Neighbors, and set the Receive
  2478.              Sequence Number for this neighbor to the sequence  number
  2479.              in the Routing Update message.
  2480.  
  2481.           b. Compare the Receive Sequence Number for this neighbor  to
  2482.              the  sequence  number  in  the  Routing Update message to
  2483.              determine whether or not to accept this message.  If  the
  2484.              message  is  rejected,  send  a  Negative  Acknowledgment
  2485.              message.   If  the   message   is   accepted,   send   an
  2486.              Acknowledgment  message  and  proceed  with the following
  2487.              steps.
  2488.  
  2489.  
  2490.  
  2491.                                    -41-
  2492.  
  2493.  
  2494.  
  2495.  
  2496.  
  2497.      DARPA Internet Gateway                             September 1982
  2498.      RFC 823
  2499.  
  2500.  
  2501.  
  2502.           c. Compare the  networks  reported  in  the  Routing  Update
  2503.              message  to  the Number of Networks.  If new networks are
  2504.              reported, enter them in the network vectors, increase the
  2505.              number  of  networks,  and  expand the Distance Matrix to
  2506.              account for the new networks.
  2507.  
  2508.           d. Copy the routing update received into the appropriate row
  2509.              of the Distance Matrix.
  2510.  
  2511.           e. Recompute the Minimum Distance Vector.
  2512.  
  2513.           f. Recompute the Routing Updates.
  2514.  
  2515.           g. Recompute the Routing Table.
  2516.  
  2517.           h. If any routing update has changed, send the  new  routing
  2518.              updates to the neighbors.
  2519.  
  2520.      o  An Acknowledgment message is received.
  2521.  
  2522.              Compare the sequence number in the message  to  the  Send
  2523.              Sequence   Number.    If  the  Send  Sequence  Number  is
  2524.              acknowledged,  update   the   entry   in   the   Received
  2525.              Acknowledgment  Vector  for  the  neighbor  that sent the
  2526.              acknowledgment.
  2527.  
  2528.      o  A Negative Acknowledgment message is received.
  2529.  
  2530.              Compare the sequence number in the message  to  the  Send
  2531.              Sequence Number.  If necessary, replace the Send Sequence
  2532.              Number, and retransmit the routing updates.
  2533.  
  2534.  
  2535.  
  2536.  
  2537.  
  2538.  
  2539.  
  2540.  
  2541.  
  2542.  
  2543.  
  2544.  
  2545.  
  2546.  
  2547.  
  2548.  
  2549.                                    -42-
  2550.  
  2551.  
  2552.  
  2553.  
  2554.  
  2555.      DARPA Internet Gateway                             September 1982
  2556.      RFC 823
  2557.  
  2558.  
  2559.  
  2560.      REFERENCES
  2561.  
  2562.      [1]  Postel,  J.  (ed.),  "Internet  Protocol  -  DARPA  Internet
  2563.           Program  Protocol  Specification,"  RFC 791, USC/Information
  2564.           Sciences Institute, September 1981.
  2565.  
  2566.      [2]  Strazisar,  V.,   "Gateway   Routing:    An   Implementation
  2567.           Specification," IEN-30, Bolt Beranek and Newman Inc., August
  2568.           1979.
  2569.  
  2570.      [3]  Strazisar, V., "How  to  Build  a  Gateway,"  IEN-109,  Bolt
  2571.           Beranek and Newman Inc., August 1979.
  2572.  
  2573.      [4]  Postel, J.,  "Internet  Control  Message  Protocol  -  DARPA
  2574.           Internet   Program   Protocol   Specification,"   RFC   792,
  2575.           USC/Information Sciences Institute, September 1981.
  2576.  
  2577.      [5]  Postel, J., "Assigned  Numbers,"  RFC  790,  USC/Information
  2578.           Sciences Institute, September 1981.
  2579.  
  2580.      [6]  Littauer, B., Huang, A.,  Hinden,  R.,  "A  Host  Monitoring
  2581.           Protocol,"  IEN-197, Bolt Beranek and Newman Inc., September
  2582.           1981.
  2583.  
  2584.      [7]  Santos,  P.,  Chalstrom,   H.,   Linn,   J.,   Herman,   J.,
  2585.           "Architecture   of   a   Network   Monitoring,  Control  and
  2586.           Management System," Proc. of  the  5th  Int.  Conference  on
  2587.           Computer Communication, October 1980.
  2588.  
  2589.      [8]  Haverty, J., "XNET Formats for Internet Protocol Version 4,"
  2590.           IEN-158, Bolt Beranek and Newman Inc., October 1980.
  2591.  
  2592.      [9]  Mathis, J., Klemba, K., Poggio,  "TIU  Notebook-  Volume  2,
  2593.           Software Documentation," SRI, May 1979.
  2594.  
  2595.      [10] Rosen,  E.,  "Exterior  Gateway  Protocol,"  IEN-209,   Bolt
  2596.           Beranek and Newman Inc., August 1982.
  2597.  
  2598.  
  2599.  
  2600.  
  2601.  
  2602.  
  2603.  
  2604.  
  2605.  
  2606.  
  2607.                                    -43-
  2608.  
  2609.  
  2610.  
  2611.