HOW TO BUILD A GATEWAY

                       Virginia Strazisar

                            IEN #109

                         August 31, 1979

                        TABLE OF CONTENTS

 1.  Introduction...............................................1

 2.  Information Maintained by Gateways.........................1

 3.  Initialization.............................................3

 4.  Determining Connectivity to Networks.......................3

 5.  Determining Connectivity to Neighbors......................4

 6.  Exchanging Routing Information.............................4

 7.  Computing Routes...........................................5

 8.  Forwarding Traffic.........................................7

 9.  Non-Routing Gateways.......................................7

10.  Adding New Neighbors and Networks..........................8

11.  Communications with Hosts..................................9

12.  Future Modifications......................................10

13.  Packet Formats............................................11

14.  Examples..................................................19

15.  Tables and Variables......................................23

16.  Events and Responses......................................25

1.  Introduction

This is a description of how to implement a gateway.  The gateway
forwards internet traffic formatted as  described  in  IEN  #111,
"Internet Protocol".  The gateway polls its attached networks and
neighbor  gateways  to  determine  its connectivity to them, then
exchanges this information with its neighbor gateways in order to
compute routes to each network in the catenet.  When gateways  or
network interfaces fail, the gateways compute alternate routes to
the networks.

The  design  for  this  gateway  routing  strategy was originally
presented  in  IEN  #30,  "Gateway  Routing,  An   Implementation
Specification".   That  document  gives an overview of the design
and explains some of the decisions made in designing this routing
strategy.  Since IEN #30 was released, this routing strategy  has
been  implemented  in  several  gateways.  During implementation,
several modifications were made to  the  original  design,  thus,
those  sections of IEN #30 covering the detailed specification of
the design are obsolete and are replaced by this document.

2.  Information Maintained by Gateways

Gateways must maintain information about  their  connectivity  to
networks  and  other  gateways.  The functional description below
explains how this information is obtained  and  modified  by  the
gateways.   For  the purpose of explaining the gateway functions,
this information is  organized  into  the  following  tables  and
variables.

Number of Networks

The  number  of  networks for which the gateway maintains routing
information and to which it can forward  packets.   The  gateways
maintain  and  exchange  routing  information  indexed by network
numbers.  Thus, the Number of Networks also  corresponds  to  the
highest  numbered network to which the gateway can route traffic.
(Network numbers are listed in IEN #117, "Assigned Numbers".)


Number of Neighbors

The number of neighbor gateways with which the gateway  exchanges
routing  information.   A  neighbor  gateway  of gateway X is any
gateway that has an interface on the same network as  gateway  X.
If  gateway  X  and  its  neighbor  have more than one network in
common, then each neighbor gateway  interface  on  a  network  to
which  gateway  X  is  attached  is  considered  to be a separate
neighbor.



                              - 1 -

Gateway Addresses

The address of the  gateway  on  each  network  to  which  it  is
attached.

Neighbor Addresses

The addresses of the neighbor gateways.

Connectivity to Neighbors

A  vector  of  the status of connectivity between the gateway and
each of its neighbor gateways.  The connectivity is determined by
polling the neighbors.

Routing Updates

The routing updates that are sent to the neighbor gateways.  Each
routing update contains the distance from  the  gateway  to  each
network.  There is one routing update for each neighbor.

Distance Matrix

A  matrix  of  the  routing  updates  received  from  each of the
neighbor gateways.  Routing updates contain the distance  from  a
gateway to each network.

Minimum Distance Vector

A  vector  of  the minimum distance to each network.  Distance is
measured in networks traversed;  a gateway  which  is  physically
attached  to  a  network  is  zero hops from that network; if the
gateway must send through one other gateway to get to a  network,
then it is one hop from that network.

Routing updates from non-routing neighbor gateways

A  routing  update  for  each  neighbor  gateway  that  does  not
participate in this routing scheme.  This is the update that  the
gateway  would  receive  from  this  neighbor if the neighbor did
participate in routing.

Routing Table

A table containing, for each network,  a  list  of  the  neighbor
gateways on a minimum length route to that network.






                              - 2 -

Send Sequence Number

The  sequence  number  that  the gateway will use to transmit the
next routing update to its neighbors.

Receive Sequence Numbers

The sequence number that the gateway received in the last routing
update from each of its neighbors.  There is  a  sequence  number
for each neighbor.

3.  Initialization

The gateway is initialized with the following information:

The gateway's address on each network to which it is attached.

The addresses of its neighbors.

A  routing  update from each of its neighbor gateways that do not
participate in routing.

Initially, the  gateway  should  assume  that  all  its  neighbor
gateways are down, that it is disconnected from networks to which
it is attached, and that the distance reported in routing updates
from  each  neighbor  to each network is infinity (see "Computing
Routes").

4.  Determining Connectivity to Networks

The gateway must determine its connectivity to networks to  which
it is physically attached.  The gateway is connected to a network
if  it  can send and receive internet packets on its interface to
that network.  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
data  packets can be sent and received on the host interface.  In
these networks, the gateway can simply check  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 complex, it may be necessary for
the gateway to send traffic to itself  to  determine  if  it  can
communicate  with  the  network.  In these networks, the gateways
can periodically poll the network to  determine  if  the  network
interface is operational.

For  purposes  of  computing distances and routes to networks, if
the  gateway  can  send  and  receive  traffic  on  its   network
interface, then its distance to the network is zero; if it cannot
send  and  receive traffic on the interface, then its distance to


                              - 3 -

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.

5.  Determining Connectivity to Neighbors

A neighbor gateway is in one  of  three  states:   up,  down,  or
recovering.   In  the  latter  case, the gateway has communicated
with its neighbor, and  is  in  a  waiting  period  to  determine
whether  it  will  be  able  to  continue to communicate with the
neighbor.  This state exists to prevent a gateway  from  using  a
neighbor  gateway  to forward traffic when communications between
it and the neighbor are extremely lossy.  The gateway  determines
its connectivity to each neighbor gateway as follows.  Initially,
the  neighbor is assumed to be "down".  The gateway sends an echo
packet (see "Packet Formats") to the  neighbor  gateway  every  N
seconds  and  increments  a  count of echo packets outstanding to
that neighbor.  When the gateway receives an  echo  reply  packet
from  the  neighbor,  it  clears  the  count  of outstanding echo
packets.  If that neighbor was "down", the gateway  starts  an  X
second  timer and sets the neighbor's status to "recovering".  If
after X seconds, the neighbor's  status  is  still  "recovering",
then  the  neighbor's status is changed to "up".  If the count of
echo packets outstanding  to  a  neighbor  is  equal  to  Z,  the
neighbor's  status  is set to "down".  As probes are sent every N
seconds, a neighbor's status is changed to "down" if it does  not
respond within (N * Z) seconds.  Note that the waiting period, X,
during  which  the neighbor's status is "recovering" should be at
least several times the  interval  (N  *  Z  seconds)  needed  to
declare  the neighbor "down".  This prevents the neighbor gateway
from cycling rapidly between the "up" and "down" states.

The gateway maintains a vector of the connectivity between it and
its neighbors.  This vector is used in  computing  distances  and
routes to networks.  The vector contains K entries where K is the
number  of neighbors.  If the state of the Jth neighbor is either
"down" or "recovering", then the Jth entry of the vector  is  set
to  infinity;  if  the state of the Jth neighbor is "up" then the
Jth entry of the vector is set to one.

6.  Exchanging Routing Information

The gateway receives and transmits routing  information  reliably
using   sequence   numbered  packets  and  a  retransmission  and
acknowledgement scheme.  This scheme works as follows.  For  each
neighbor,  the  gateway remembers the Receive Sequence Number, R,
that it received in the most  recent  routing  packet  from  that
neighbor.   This  value  is  initialized  by  setting  it  to the
sequence number received in the  first  routing  packet  received


                              - 4 -

from  a neighbor after that neighbor's status is set to "up".  On
receipt  of  a  routing  packet  from  a  neighbor,  the  gateway
subtracts  the  Receive  Sequence  Number,  R,  from the sequence
number in the routing packet, S. If this value (S-R)  is  greater
than  or  equal  to  zero,  then  the gateway accepts the routing
packet, sends an acknowledgement 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 packet and sends a negative acknowledgement
to the neighbor with sequence number R.

The gateway has a Send Sequence Number, N,  for  sending  routing
packets  to  all  of  its neighbors.  This sequence number can be
initialized  to  any  value.   The  Send   Sequence   Number   is
incremented  each  time  a  new  routing  update  is created.  On
receiving an acknowledgement 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  acknowledgement.  If (N-A) is zero, the routing update
has been acknowledged.  Note that only the  most  recent  routing
update  need  be  acknowledged;  if  a  second  routing update is
generated before the first routing update is  acknowledged,  only
the second routing update need be acknowledged.

If  a negative acknowledgement 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 update to all 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  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, not to neighbors that are "down" or "recovering".
Examples of the sequence number strategy are given below.

7.  Computing Routes

A  routing  update contains the number of networks that a gateway
is reporting about followed by a list of the distances  to  these
networks,  indexed  by network number.  Assuming that the gateway
has checked the sequence number of a routing update that  it  has


                              - 5 -

received and has decided to accept the update, the information in
the update is processed as follows.

The  gateway  contains  a  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 d(I,J), is the distance to
network I from neighbor J as reported in the most 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 "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, containing 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) + d(I,J)

where  d(J)  is  the  distance  between  the  gateway and the Jth
neighbor and d(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 "Determining Connectivity to Networks"),  then  the  gateway
sets the Ith entry of the minimum distance vector to zero.

Using the minimum distance vector, the gateway computes a list of
neighbor  gateways through which to send traffic to each network.
The entry for network I contains all neighbors such that:

        MinD(I) = d(J) + d(I,J)

In other words, the entry for network I  contains  all  neighbors
such  that the distance from the gateway to the neighbor plus the
distance from the neighbor to the network is equal to the minimum
distance from the gateway to the network.

After updating its routes to the networks, the  gateway  computes
the  new  routing updates to be sent to its neighbors as follows.
For each neighbor, J, the gateway  constructs  a  routing  update
which is a N entry vector where N is the number of networks.  The
Jth entry of this vector is:

        MinD(I) if MinD(I) less than or equal to d(I,J)
        infinity if MinD(I) greater than d(I,J)



                              - 6 -

where  d(I,J)  is  the  distance from the Jth neighbor to the Ith
network and MinD(I) is the minimum distance from the  gateway  to
the  Ith  network.   In  other  words,  the  gateway  reports its
distance to a network to a neighbor only if it is as close to  or
closer to a network than its neighbor.

Finally,  the  gateway  must  determine  whether  it  should send
routing updates to its neighbors.  The gateway maintains  a  copy
of  the  most  recent routing updates that it sent to each of its
neighbors.  The gateway computes the new routing updates to  send
to  each  of  its neighbors.  If any of these routing updates are
different than the preceding updates, then the gateway sends  new
routing  updates to its neighbors.  If no routing information has
changed since the last routing update was sent, then the  gateway
does  not  need  to  send new routing updates.  The gateway sends
routing updates only to neighbors that are currently in the  "up"
state.

The  gateway  requests routing updates from neighbors that are in
the "up" state, but have not yet sent a  routing  update  to  it.
Routing  updates  are requested by setting the appropriate bit in
the routing update being sent (see "Packet Formats").  Similarly,
if a gateway receives a routing update from a neighbor  in  which
the bit requesting a routing update is set, the gateway sends the
neighbor the most recent routing update.

8.  Forwarding Traffic

On  receipt of a packet to be forwarded, the gateway extracts the
internet destination network  field  from  the  packet.   If  the
gateway  is attached to the network, and its network interface is
operational, then the gateway  simply  composes  the  appropriate
local  network  header  for the destination network and sends the
packet.

If the gateway is not connected to the network, then the  gateway
checks  the list of the neighbors on the route to the destination
network.  If there are no neighbors on the list, then the gateway
drops the packet and sends the  internet  source  a  "destination
unreachable" message (see "Communications with Hosts").

If  there are one or more neighbors on a route to the destination
network, then the gateway  sends  the  packet  to  one  of  these
neighbors.   If  there  is  more  than  one  neighbor,  then  the
neighbors are used in a round robin fashion.

9.  Non-Routing Gateways

Non-routing gateways are gateways that forward internet  traffic,
but  that  do  not  participate in this routing scheme.  Whenever


                              - 7 -

possible,  traffic  is  forwarded  only  through  gateways   that
participate  in  this  routing  scheme.  Non-routing gateways are
used to forward traffic only if they provide the only route to  a
network.   These  gateways  are  used  as  follows.   Consider  a
gateway, G1.  The only non-routing gateways that it needs to know
about are its neighbor gateways, as these are the  gateways  from
which  it  would  normally  receive  routing  updates.   For each
non-routing neighbor gateway of gateway G1, compute  the  routing
update  that  would  be sent to G1 assuming that all gateways and
network connections are operational.  These routing  updates  are
assembled  in  G1.   The  gateway, G1, first computes its minimum
distance vector  as  explained  above,  using  only  the  routing
updates  from  neighbors  that  participate  in  routing.  If the
minimum distance to any network is infinity, i.e. the network  is
unreachable  via  any  of  the routing gateways, then the minimum
distance to that network is re-computed using the routing  update
compiled  for  the non-routing neighbor gateway.  For purposes of
computing the minimum distance to a  network,  the  gateway,  G1,
assumes that the distance between itself and the neighbor gateway
is  zero.   After  computing  the  minimum  distance  vector, the
gateway compiles the list of neighbor gateways through  which  to
send  traffic  to  each  network and sends routing updates to its
neighbors as  explained  above  (see  "Computing  Routes").   The
gateway does not send routing updates to the non-routing neighbor
gateways.

10.  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 packet.  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.  The gateway accepts the routing
update, sets the neighbor's  connectivity  status  to  "up",  and
computes  new routes as explained above.  The gateway also begins
polling this new neighbor to monitor its connectivity.  Note that
this strategy requires that one gateway in each pair of  neighbor
gateways  must  have  the  neighbor's  address  assembled  in its
tables.  The newest gateway can  be  given  a  complete  list  of
neighbors,  thus  avoiding the need to re-assemble older gateways
when new gateways are installed.

Gateways  obtain  routing  information  about  new  networks   as
follows.  The gateway maintains a count of the number of networks
for  which  it currently contains routing information, N.  When a
routing update is received, the gateway compares this  number  to
the  number  of networks reported in the routing update, M.  If M


                              - 8 -

is greater than N, then the gateway updates the count of networks
for which it maintains routing information  to  include  the  new
networks.   Next,  the  gateway  expands  its  distance matrix to
include the number of networks reported.  The distance matrix  is
the  matrix  of  distances  to  networks  as  reported in routing
updates from the neighbor gateways.  In expanding the matrix, the
gateway assumes the distance to all  new  networks  is  infinity.
After  expanding  the matrix, the gateway computes new routes and
new routing updates as outlined above.

Note that expanding neighbor address tables and distance matrices
may present an implementation problem.  In practice, these tables
can be assembled to contain some maximum number of neighbors  and
networks.   If  a  new  neighbor  cannot  be added to a gateway's
tables, then routing updates or echo packets from  that  neighbor
should be ignored.  The new neighbor will assume that the gateway
is  down  and  will  not use it to forward traffic.  If a gateway
cannot add a new network to its  routing  tables,  it  can  still
accept  routing  updates  containing  information  about  the new
network, but it will be  unable  to  route  traffic  to  the  new
network.  The routing updates that it sends to its neighbors will
not  contain  information  about  the  new  network.   Whenever a
gateway receives a  routing  update  that  does  not  report  the
distance  to  a  network,  the  gateway  should  assume  that the
distance is infinity.

11.  Communications with Hosts

The  gateway  sends  messages  to  internet  hosts   in   several
situations:    when   the   gateway  cannot  reach  the  internet
destination,  when  the  gateway  does  not  have  the  buffering
capacity to forward a packet, and when the gateway can direct the
host  to  send  traffic on a shorter route.  These situations are
explained in more detail below.  The formats  for  messages  sent
from  a  gateway  to  a  host  are  given  in the section "Packet
Formats".

If, according to the information in the gateway's routing tables,
the network specified in the  internet  destination  field  of  a
packet  is  unreachable,  i.e.  the  distance  to  the network is
infinity, the gateway sends a destination unreachable message  to
the  internet  source  host  of the packet.  In addition, in some
networks, the gateway may be able to determine  if  the  internet
destination  host is unreachable.  Gateways in these networks may
send destination unreachable messages to the source host when the
destination host is unreachable.

The gateway may discard internet packets if it does not have  the
buffer  space  needed to queue the packets for output to the next
network on the route to the destination network.  If the  gateway


                              - 9 -

discards  a  packet,  it  sends  a  source  quench message to the
internet source host of the packet.  The source quench message is
a request to the host to cut back the rate at which it is sending
traffic to the internet destination.  The gateway sends a  source
quench message for every message that it discards.  On receipt of
a  source quench message, hosts should cut back the rate at which
they are sending traffic to the specified destination until  they
no  longer  receive source quench messages from the gateway.  The
hosts can then gradually increase the  rate  at  which  they  are
sending  traffic  to  the  destination  until  they again receive
source quench messages from the gateway.

The gateway sends a redirect message to a host in  the  following
situation.   A  gateway,  G1,  receives an internet packet from a
host on a network to which the gateway is attached.  The gateway,
G1, checks its routing table and obtains the address of the  next
gateway,  G2,  on  the route to the packet's internet destination
network, X.  If G2 and the host identified by the internet source
address of the packet are on the same network, a redirect message
is sent to the host.  The redirect message advises  the  host  to
send  its traffic for network X directly to gateway G2 as this is
a shorter path to the  destination.   The  gateway  forwards  the
original data packet to its internet destination.

12.  Future Modifications

As  there  are  now  many networks planned or implemented, and as
these networks may be assigned a wide range of  network  numbers,
it  is  no  longer  feasible  to  maintain routing information in
tables indexed by network numbers.  Gateways will be modified  to
use  a  hash  table scheme to convert network numbers to internal
indices to reference routing tables.  The information in  routing
updates  exchanged  by  the gateways will no longer be indexed by
network number.  The format of routing updates will  be  modified
to  include  both  the  network  number  and  the distance to the
network.  These modifications will be documented  in  a  separate
note.















                             - 10 -

13.  Packet Formats

Gateway  to  gateway  and  gateway to host communications use the
version 4 internet protocol.  The first octet of the data portion
of the packet is a gateway type field; the value  of  this  field
determines  the  format  of  the  remaining  data.  The format of
internet packets is explained in IEN #111,  "Internet  Protocol".
Unless  otherwise noted under the individual format descriptions,
the values of the internet header fields are as follows:

Version                 4

IHL                     Internet header length in 32-bit words;
                        this is 5.

Type of Service         0

Total Length            Length of internet header and data in
                        octets.

Identification, Flags,
Fragment Offset         Used in fragmentation, see IEN #111.

Time to Live            Time to live in seconds; as this field
                        is decremented at each machine in which
                        the packet is processed, the value in
                        this field should be at least as great as
                        the number of gateways which this packet
                        will traverse.  (This must be considered
                        in the messages sent to hosts.)

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.  This
                        checksum may be replaced in the future,
                        see updates of the Internet Protocol
                        Specification.

Source Address          The address of the gateway that composes
                        the packet.  Unless otherwise noted, this
                        can be any of the gateway's addresses.

Destination Address     The address of the gateway or host to
                        which the packet should be sent.





                             - 11 -

                         Routing Update

 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       !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! NU !     N    !  Distance 1   !  Distance 2   !  Distance 3   !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                                .
                                .
                                .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!  Distance N-3 !  Distance N-2 !  Distance N-1 !  Distance N   !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Gateway Type            1

Sequence Number         The 16-bit sequence number used to transmit
                        routing updates.

NU                      A 1-bit field.  This bit is set if the
                        source gateway requests a routing update
                        from the destination gateway.

N                       The number of networks for which distances
                        are reported in this update.

Distance 1..N           A set of octets that are the values in
                        the routing update for distances to
                        network numbers 1 through N.  The network
                        numbers are listed in IEN #117, "Assigned
                        Numbers".  If the Ith network is unreachable,
                        the distance to the network is infinity,
                        which is represented as 177 (octal).

















                             - 12 -

           Acknowledgement or Negative Acknowledgement

 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            2 for acknowledgement; 10 (decimal) for
                        negative acknowledgement.

Sequence Number         The 16-bit sequence number that the gateway
                        is acknowledging or negatively acknowledging.







































                             - 13 -

                 Destination Unreachable Packet

 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  !     Code      !           unused              !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!      Internet Header + 64 bits of Original Data Packet        !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Destination Address     The source network and address from the
                        original data packet.

Gateway Type            3

Code                    0 = net unreachable; 1 = host unreachable.

Internet Header + 64 bits
of Data Packet          The internet header plus the first 64 bits
                        of the original data packet.  This data is
                        used by the host to match the message from
                        the gateway to the appropriate process.
                        If a higher level protocol uses port numbers,
                        they are assumed to be in the first 64 data
                        bits of the original data packet.



























                             - 14 -

                      Source Quench Packet

 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                        !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!      Internet Header + 64 bits of Original Data Packet        !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Destination Address     The source network and address of the
                        original data packet.

Gateway Type            4

Internet Header + 64 bits
of Data Packet          The internet header plus the first 64 bits
                        of the original data packet.  This data is
                        used by the host to match the message from
                        the gateway to the appropriate process.
                        If a higher level protocol uses port numbers,
                        they are assumed to be in the first 64 data
                        bits of the original data packet.





























                             - 15 -

                         Redirect Packet

 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 Network!           Gateway Address                     !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!      Internet Header + 64 bits of Original Data Packet        !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Destination Address     The source network and address of the
                        original data packet.

Gateway Type            5

Gateway Network         Address of the gateway to which traffic
Gateway Address         for the network specified in the
                        internet destination network field of
                        the data packet should be sent.

Internet Header + 64 bits
of Data Packet          The internet header plus the first 64 bits
                        of the original data packet.  This data is
                        used by the host to match the message from
                        the gateway to the appropriate process.
                        If a higher level protocol uses port numbers,
                        they are assumed to be in the first 64 data
                        bits of the original data packet.






















                             - 16 -

                    Echo or Echo Reply Packet

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

Source Address          In an echo packet, the address of the
                        gateway on the same network as the neighbor
                        to which it is sending the echo packet.
                        In an echo reply packet, the source and
                        destination addresses are simply reversed.

Gateway Type            8 for echo packet; 0 for echo reply.





































                             - 17 -

                   Net Interface Status Packet

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

Source Address
Destination Address     The address of the gateway's network
                        interface.  The gateway can send Net
                        Interface Status Packets to itself to
                        determine if it is able to send and
                        receive traffic on its network interface.


Gateway Type            9



































                             - 18 -

14.  Examples

The following examples illustrate the sequence number scheme
used for sending and receiving routing updates.

Example 1:

Gateway G has three neighbors:  A, B and C.
Gateway G's Send Sequence Number is 5.
Connectivity between gateway G and gateway A was broken and is
now restored; thus, A has not received the last update from G.
Gateway A's Receive Sequence Number for G is 3.
Gateway B's Receive Sequence Number for G is 4.
Gateway C's Receive Sequence Number for G is 4.

Initially, gateway G has the following values in its tables:

Send Sequence   Received Acknowledgement from Neighbors
                   A   B   C
     5             N   N   N  (N for no, Y for yes)


G (5) ---> A       G sends routing update 5 to its neighbors
G (5) ---> B
G (5) ---> C
A (ACK 5) ---> G   A computes (sequence number received in
                   packet - Receive Sequence Number) = (5-3); as
                   this is greater than or equal to zero, A
                   acknowledges routing update 5 and replaces
                   Receive Sequence Number for G with 5

B (ACK 5) ---> G   B computes (sequence number received in
                   packet - Receive Sequence Number) = (5-4); as
                   this is greater than or equal to zero, B
                   acknowledges routing update 5 and replaces
                   its Receive Sequence Number for G with 5

C (ACK 5) ---> G

On receipt of these acknowledgements, G computes (Send Sequence
Number - sequence number acknowledged) = (5-5).  As this value
is zero, G notes that each of its neighbors has acknowledged
its routing update.









                             - 19 -

Gateway G now has the following values in its tables:

Send Sequence   Received Acknowledgement from Neighbors
                   A   B   C
     5             Y   Y   Y

Gateway A's Receive Sequence Number for G is 5.
Gateway B's Receive Sequence Number for G is 5.
Gateway C's Receive Sequence Number for G is 5.











































                             - 20 -

Example 2:

Gateway G has three neighbors:  A, B, and C.
Gateway G's Send Sequence Number is 24.
Gateway A has been disconnected from gateway G for some long time,
thus, it has missed many updates from G and G's Send Sequence Number
has now wrapped around.
Gateway A's Receive Sequence Number for G is 500.
Gateway B's Receive Sequence Number for G is 23.
Gateway C's Receive Sequence Number for G is 23.

Initially, gateway G has the following values in its tables:

Send Sequence   Received Acknowledgement from Neighbors
                   A   B   C
     24            N   N   N  (N for no, Y for yes)

G (24) ---> A       G sends routing update 24 to all its neighbors
G (24) ---> B
G (24) ---> C
A (NAK 500) ---> G  A computes (sequence number received in
                    packet - Receive Sequence Number) = (24-500);
                    as this is less than zero, A sends a negative
                    acknowledgement with sequence number 500

On receipt of the negative acknowledgement, gateway G computes
(Send Sequence Number - sequence number negatively acknowledged)
= (24-500).  As this value is less than zero, G replaces its Send
Sequence Number with 501 and retransmits the routing update with
this sequence number.

G (501) ---> A
G (501) ---> B
G (501) ---> C
A (ACK 501) ---> G  A computes (sequence number received in
                    packet - Receive Sequence Number) = (501-500);
                    as this is greater than or equal to zero,
                    A acknowledges sequence number 501 and
                    replaces its Receive Sequence Number for G
                    with 501

B (ACK 24) ---> G   B receives the update from G with sequence
                    number 24; B computes (sequence number received
                    in packet - Receive Sequence Number) = (24-23);
                    as this is greater than or equal to zero,
                    B acknowledges sequence number 24 and replaces
                    its Receive Sequence Number for G with 24

C (ACK 24) ---> G



                             - 21 -

On receipt of these acknowledgements, G computes (Send Sequence
Number - sequence number acknowledged) = (501-24).  As this value
is non-zero, G retransmits the routing update to these neighbors.

G (501) ---> B
G (501) ---> C
B (ACK 501) ---> G  B computes (sequence number received in
                    packet - Receive Sequence Number) = (501-24);
                    as this is greater than or equal to zero,
                    B acknowledges sequence number 501 and
                    replaces its Receive Sequence Number for G
                    with 501


C (ACK 501) ---> G

On receipt of these acknowledgements, G computes (Send Sequence
Number - sequence number acknowledged) = (501-501).  As this value
is zero, G notes that each of its neighbors has acknowledged
its routing update.

Gateway G now has the following values in its tables:

Send Sequence   Received Acknowledgement from Neighbors
                   A   B   C
     501           Y   Y   Y

Gateway A's Receive Sequence Number for G is 501.
Gateway B's Receive Sequence Number for G is 501.
Gateway C's Receive Sequence Number for G is 501.






















                             - 22 -

15.  Tables and Variables

The following is a list of variables  and  tables  in  a  typical
gateway implementation.

1.  Number of Networks

2.  Number of Neighbors

3.  Gateway Addresses

The addresses of the gateway's network interfaces.

4.  Neighbor Gateway Addresses

The address of each gateway network interface that is on the same
network as this gateway.

5.  Neighbor Connectivity Vector

A vector of the connectivity between this gateway and each of its
neighbors.   It  contains  K  entries  where  K  is the Number of
Neighbors.  Values in this vector are computed  as  explained  in
"Determining Connectivity to Neighbors".

6.  Distance Matrix

A  matrix  of  the  routing  updates  received  from the neighbor
gateways.

7.  Minimum Distance Vector

A vector containing the minimum distance to each network.  It  is
computed as described in "Computing Routes".

8.  Routing Updates

A  set  of  vectors giving the distance from this gateway to each
network.  There is a separate vector to be sent to each neighbor.
These are computed as described in "Computing Routes".

9.  Routing Updates from Non-Routing Gateways

The routing updates that  would  have  been  received  from  each
neighbor  gateway  that  does  not  participate  in  this routing
strategy.   These  are  computed  as  described  in  "Non-Routing
Gateways".





                             - 23 -

10.  Routing Table

A  table  containing,  for  each  network, a list of the neighbor
gateways on a minimum distance route to  the  network.   This  is
computed as described in "Computing Routes".

11.  Send Sequence Number

The  sequence  number  that will be used to send the next routing
update.

12.  Receive Sequence Numbers

The sequence numbers  that  the  gateway  received  in  the  last
routing update from each of its neighbors.

13.  Received Acknowledgement Vector

A vector indicating whether or not each neighbor has acknowledged
the sequence number in the most recent routing update sent.
































                             - 24 -

16.  Events and Responses

The following is a list of the events that occur at a gateway and
the  gateway's  responses.   The variables and tables referred to
are listed above.  This is a general guide for an implementation;
see  the  sections  above  for  the  details   of   the   various
computations.

1.   Connectivity  to  a network to which the gateway is attached
changes.

        1.  Update the Minimum Distance Vector.

        2.  Recompute the Routing Updates.

        3.  Recompute the Routing Table.

        4.  If any routing  update  has  changed,  send  the  new
        routing updates to the neighbors.

2.  Connectivity to a neighbor gateway changes.

        1.  Update the Neighbor Connectivity Vector.

        2.  Recompute the Minimum Distance Vector.

        3.  Recompute the Routing Updates.

        4.  Recompute the Routing Table.

        5.   If  any  routing  update  has  changed, send the new
        routing updates to the neighbors.


3.  A Routing Update Packet is received.

        1.  Compare the internet source address  of  the  Routing
        Update  Packet 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 Packet.

        2.  Compare the Receive Sequence Number for this neighbor
        to  the  sequence  number in the Routing Update Packet to
        determine whether or not to accept this packet.   If  the
        packet  is  rejected,  send  a  Negative  Acknowledgement
        Packet.    If   the   packet   is   accepted,   send   an
        Acknowledgement  Packet  and  proceed  with the following
        steps.


                             - 25 -

        3.  Compare the number of networks  reported  on  in  the
        Routing  Update Packet to the Number of Networks.  If the
        number of networks in the  packet  is  greater  than  the
        Number  of Networks, then replace Number of Networks with
        the  number  of  networks  in  the  packet.   Expand  the
        Distance Matrix to account for the new networks.

        4.  Copy the routing update received into the appropriate
        row of the Distance Matrix.

        5.  Recompute the Minimum Distance Vector.

        6.  Recompute the Routing Updates.

        7.  Recompute the Routing Table.

        8.   If  any  routing  update  has  changed, send the new
        routing updates to the neighbors.

4.  An Acknowledgement  or  Negative  Acknowledgement  Packet  is
received.

        1.  Compare the sequence number in the packet to the Send
        Sequence Number.  If necessary, replace the Send Sequence
        Number,  and retransmit the routing updates.  If the Send
        Sequence Number is acknowledged, update the entry in  the
        Received Acknowledgment Vector for the neighbor that sent
        the acknowledgement.

5.  A data packet is received.

        1.   Forward the data packet using the information in the
        Routing Table entry for the packet's destination network.

        2.  If the destination is unreachable, send a Destination
        Unreachable Packet to the internet  source  of  the  data
        packet.

        3.   If the data packet is discarded because there are no
        buffers available in the  gateway,  then  send  a  Source
        Quench  Packet to the internet source of the data packet.

        4.  If the gateway to which  the  data  packet  is  being
        forwarded  and  the  data packet's internet source are on
        the same network, send a Redirect Packet to the  internet
        source of the data packet.






                             - 26 -