DESIGN OF TCP/IP FOR THE TAC


                             IEN-166

                          Robert Hinden

                  Bolt Beranek and Newman Inc.

                          January 1981



































IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



                        Table of Contents


1   Introduction.......................................... 1
2   Overall Data Flow..................................... 2
2.1   Receiving Data...................................... 2
2.1.1   1822 Module....................................... 3
2.1.2   NCP Module........................................ 4
2.1.3   Internet Module................................... 4
2.1.4   TCP Module........................................ 5
2.1.5   Telnet Module..................................... 6
2.2   Sending Data........................................ 7
2.2.1   Telnet Module..................................... 7
2.2.2   TCP Module........................................ 8
2.2.3   Internet Module................................... 9
2.2.4   1822 Module....................................... 9
3   Control and Priority................................. 10
4   Data Structures...................................... 11
4.1   Message Block...................................... 11
4.2   Protocol Data Block................................ 13
5   1822 Protocol........................................ 16
6   Internet Protocol.................................... 17
6.1   Identifier Assignment.............................. 17
6.2   Option Support..................................... 17
6.3   Reassembly......................................... 17
6.4   Routing............................................ 19
6.5   Gateway to Gateway Messages........................ 20
6.6   Timeouts........................................... 21
7   Transmission Control Protocol........................ 21
7.1   Connection Opening and Closing..................... 21
7.2   Initial Sequence Number Assignment................. 22
7.3   Option Support..................................... 22
7.4   Urgent Data........................................ 23
7.5   End of Letter Handling............................. 23
7.6   Retransmissions.................................... 24
7.7   Acknowledgement and Window Strategy................ 24
7.8   Sequencing......................................... 25



                             FIGURES


Data and Control Flow..................................... 3
Message Block Format..................................... 12
Protocol Data Block Format............................... 15





                               -i-

IEN-166                                                 R. Hinden
                                               Bolt Beranek and Newman Inc.
                                                               January 1981


                  Design of TCP/IP for the TAC


1.  Introduction


     This  document  is  a  working  design  document   for   the

development  of  the  Transmission  Control  Protocol  (TCP)  and

Internet Protocol (IP) for the Terminal Access Controller  (TAC).

The  TAC  is  a terminal controller that supports the TCP and NCP

host to host protocols.  It will run in an H-316 computer with  a

Multi-Line  Terminal Controller (MLC) and an 1822 host interface.

It is based in part on the existing H-316 TIP.


     This document is meant as a guide for the implementation  of

the  TAC.   The  intent  is  not  to  write  a specification that

describes everything in fine detail, but to describe the  overall

system  and  how  its  pieces interact with each other.  Also, it

discusses changes to parts of the existing H-316 TIP.


     Everything in this document is subject to  change.   As  the

implementation and debugging proceed, new things will be learned.

This will force a re-evaluation  of  the  design  decisions  made

here.  Undoubtedly, some things will change.


     The document is written assuming a working knowledge of  the

316  TIP,  Internet  Protocol, Transmission Control Protocol, and

Network Control Protocol.  All numbers in this  document  are  in

decimal.



                               -1-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



2.  Overall Data Flow


     A basic premise in the design of TAC is that data should not

be  moved between buffers, rather the pointers to the data should

be passed between program modules.  Thus, when a message is  read

into  a  buffer,  pointers to it are passed between the different

protocol modules.  When a character is read from the MLC and  put

into  a  buffer,  the  protocol  modules  manipulate  the  buffer

pointers, not the data itself.  This is illustrated in Figure 1.




2.1  Receiving Data


     To receive data from the network,  a message  is  read  from

the  1822  host  interface  into  a Message Block (MBLK).  If the

message will not fit in one MBLK, the remainder will be read into

other  free MBLKs until the message has been completely read in.

All  the  MBLKs  containing  the  same  message  will  be  linked

together.   A  Protocol Data Block (PDB) will be created to point

to the MBLKs.  The pointers that are passed between the  protocol

modules  will  point  to  the PDBs.  More details on the PDBs and

MBLKs can be found in the section on "Data Structures".










                               -2-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981





                          +---------+
                          +         +
         +--------------- + Message + <-------------------+
         |+-------------- + Buffers + <------------------+ \
         ||               +         +                     \ \
         VV               +---------+                      \ \
        +---+                                               \ \
   +--- +   + Tumble                                         \ \
   |+-- +   + Table         +-----+    +----+                 \ \
   ||   +---+               |     |    |    |                  \ \
   ||                     +>| TCP |<-->| IP |<-+                \ \
   VV         +--------+  | |     |    |    |  |   +------+      \ \
 +++++++      |        |  | +-----+    +----+  |   |      |    +++++++
 | MLC |<---->| Telnet |<-+                    +-->| 1822 |<-->| IMP |
 +++++++      |        |  | +-----+            |   |      |    +++++++
   ||         +--------+  | |     |            |   +------+      /\/\
   ||                     +>| NCP |<-----------+                 / /
   ||   +---+               |     |                             / /
   |+-->+   + Tumble        +-----+                            / /
   +--->+   + Table                                           / /
        +---+                                                / /
          ||             +----------+                       / /
          ||             +          +                      / /
          |+-----------> + Message  + --------------------+ /
          +------------> + Buffers  + ---------------------+
                         +          +
                         +----------+


            Control ----->                    Data ----->
                                                   ----->

                Figure 1 . Data and Control Flow


2.1.1  1822 Module


     The 1822 module is given a pointer to a  PDB.   This  module

will act directly on the message if it is an 1822 control message

(i.e., a RFNM).  It will update the appropriate data structure to

initiate  the  action  to  be taken.  If the PDB contains an 1822




                               -3-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



data message, it will be passed on to the next  protocol  module.

Which  module is passed to depends on the Link number in the 1822

message.  The Link number is the upper 8 bits of the "Message ID"

field in the 1822 leader.  The Link number to protocol mapping is

as follows:



          Link #          Protocol

          0               NCP Control
          2-71            NCP Data
          155             Internet



2.1.2  NCP Module


     The NCP module implements the ARPANET  Host-Host  Protocol.

Its  function  is  essentially  identical to the H-316 TIP's NCP.

The only difference is that it will be modified to work with  the

new  PDB  and MBLK data structures.  This will be done with a new

interface and hopefully will have a small impact  on  efficiency.

When  the  NCP  module  is  done with a message, it will pass the

pointer to the PDB to the Telnet Module.




2.1.3  Internet Module


     When the Internet Protocol (IP) module gets a pointer  to  a

PDB it first checks the checksum in the IP header and then checks

that the destination address is correct (it should be the address


                               -4-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



of  the  TAC running the code).  If either of these checks fails,

the datagram is discarded.  Also, if the destination address  was

incorrect  an  IP  error report will be sent to the source of the

datagram.  The next check is  whether  or  not  the  datagram  is

fragmented.   If  so, then the IP module will perform reassembly.

This  is  described  in  detail  in  the  section  on   "Internet

Protocol".   When  the IP module gets a complete datagram (either

received whole or reassembled) it will pass it  on  to  the  next

protocol  module.   Which  module it is depends on the "Protocol"

field in the Internet header.  If a datagram is  received  for  a

protocol  that  is  not supported, it will be discarded and an IP

error  report  sent  to  the  datagram  source.   The   protocols

supported are as follows:

          Protocol #      Protocol Name

          3               Gateway to Gateway Protocol
          6               Transmission Control Protocol
          71              Packet Core
          20              TAC Monitoring



2.1.4  TCP Module


     When the Transmission Control Protocol (TCP) receives a  PDB

it  first  checks the checksum of the message and the validity of

the TCP header.  If the message that passes this check is  for  a

valid  connection,  and  its  sequence number is in the receiving

window, the TCP module will set it up for  the  open  connection.




                               -5-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



The  data  will be sequenced if necessary at this point.  This is

described in detail in the section on the  "Transmission  Control

Protocol".   The  next module is then informed that there is data

to be processed.


     Flow control is implemented by using the TCP Acknowledgement

(ACK)  and  the  Window  size  parameters.   A  fixed  number  of

characters will be buffered for each connection.   As  characters

are  accepted they will be ACKed until the limitation is reached.

As  the  ACK  value  is  advanced,  the  window  will  be  shrunk

correspondingly.   When  the  next  module  takes  data  from the

message, buffer space becomes  available.   This  causes  TCP  to

advance  its  window, thus allowing the distant host to send more

data.


     Normally the new ACK and window values will be sent out with

the  next  data  message  from  that  connection.   If nothing is

pending for this connection, a message with just the updated  ACK

and window values will be sent.  This is described in more detail

in the section "Transmission Control Protocol".




2.1.5  Telnet Module


     The Telnet module is given a pointer to a PDB when there  is

data  to  be  processed.   This  data  may be from the NCP or TCP




                               -6-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



protocol modules.  It takes characters out of  the  MBLKs,  looks

for Telnet commands, and outputs them to the MLC.  This output is

done using the existing TIP's "Tumble Tables".   This  will  work

using  "OIs",  which means that every time an "OI" comes in for a

port, Telnet will check if there is another character to output.




2.2  Sending Data


     Data that is sent out to the network normally comes in  from

the  MLC  and  is  received  in "Tumble Table" format.  This is a

block which is filled by the MLC.  Its format  is  one  word  for

each  character  input.   The  low  order byte of the word is the

character and the high order byte is the  line  number  that  the

character came in on.


     When the block is  received  it  is  passed  to  the  Telnet

module.   This  module   takes  the  characters out and processes

them.  As this is happening another block is being filled by  the

MLC.




2.2.1  Telnet Module


     When the Telnet Module gets a character for a port, it first

checks  if there is an open connection for that port.  If not, it

discards the character and outputs a bell character to the  port.



                               -7-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



Next,  it  checks to see if there is room in the MBLK for another

character.  If not, then the character is discarded and the  bell

rung.   If  there is room, the character is put into the MBLK and

the proper pointers are advanced.  Telnet then indicates  to  the

next  protocol  module  that there is data to send.  Depending on

which protocol is being used for the connection, this  is  either

the NCP or TCP module.




2.2.2  TCP Module


     When the TCP module gets a signal that  there  is  new  data

that  should  be  sent,  it  first checks if there is room in the

sending window to send more data.  This done by checking  if  the

last  sent  but  unacknowledged  data is at the right edge of the

sending window.  If there is no room, then nothing will be  sent.

Otherwise, the TCP module will adjust the pointers in the PDB and

MBLKs to point to the correct data and update the TCP header.


     Flow control in the sending direction is done by maintaining

three  pointers  in  the  PDB.  These are pointers to data in the

MBLKs.  They are pointers to the last ACKed character,  the  last

sent  but  unACKed character, and the last not-yet-sent character

in the MBLK.  As data is ACKed, sent, or put into the  MBLK,  the

appropriate pointer is advanced.





                               -8-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



     When the TCP module is ready to send the data, it checks  to

see  if  the  1822  module can send the data (i.e., there are not

more than eight outstanding messages).  If the data can be  sent,

then  the  TCP module will compute a checksum for the message and

pass a PDB pointer to the IP module.




2.2.3  Internet Module


     When the IP module gets a pointer to a PDB it  first  checks

to  see  if  it  knows  where  to  send  the  datagram.   If  the

destination is on the same  network  as  the  TAC,  the  Internet

module  will use that as the address.  If the destination is on a

different network, then it  will  send  it  to  a  gateway.   The

procedure  to  decide  which  gateway to use is discussed in more

detail in the section "Internet Protocol".


     The IP module will then build an IP leader in the  MBLK  and

compute  the checksum of the leader.  It will then pass a pointer

to the message to the 1822 module.




2.2.4  1822 Module


     When the 1822 module gets a pointer to a PDB, it will always

send  the message it contains to the destination specified in the

PDB.  The destination host will either be  a  server  host  or  a



                               -9-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



gateway.   The  1822  module  will  keep  track  of the number of

outstanding (no RFNMs received) messages sent to  a  host.   This

will  be  used by the NCP and TCP protocol modules to insure that

the IMP will never block the TAC's host interface due  to  having

more than eight outstanding messages.


     When the 1822 module sends the message,  it  will  build  an

1822  leader  in  the MBLK.  It will then send the message to the

IMP via the host interface hardware.




3.  Control and Priority


     The code in the TAC will run either at the  interrupt  level

or  at  the background loop.  The interrupt routines will support

the host interface, MLC, and clock.  In addition,  high  priority

protocol routines will run at the task interrupt level.


     The background loop will contain most of the TAC code.   The

protocol  modules  will  run  here.  They will be executed in the

following order:  1822 Input, IP Input,  TCP  Input,  NCP  Input,

Telnet  Input,  Telnet Output, NCP Output, TCP Output, IP Output,

and 1822 Output.


     Each protocol module will have  an  input  queue.   When  it

runs,  it  checks  for  an  entry  on  its  queue.   If  it finds

something, it takes it off the queue and processes it.   Some  of



                              -10-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



the  protocol  modules  will be written to process all entries on

their queue before exiting; others will  process  one  entry  and

then  exit.   The  NCP,  TCP, and Telnet modules will process one

entry.  The 1822 and IP modules will process all entries.




4.  Data Structures


     A new system of  buffers  will  be  used  in  the  TAC.   It

consists  of  two  types  of blocks, the Message Block (MBLK) and

Protocol Data Block (PDB).  These are used both for receiving and

transmitting  messages  and for buffering characters on input and

output.


     The structure of these buffers is such that when a  protocol

module  is  passed a message it is given a pointer to a PDB.  The

PDB includes a link to the first MBLK.  The main function of  the

PDB  is  to save frequently accessed things in the message and to

point to the message.  The MBLKs  contain  the  actual  message.

They also have fields to facilitate reassembly and sequencing.




4.1  Message Block


     The main function of the Message Block  (MBLK)  is  to  hold

messages.   It will be used for all protocols.  If a message will

not fit in one MBLK, then the remainder will be put into a second



                              -11-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



MBLK.  The second will be linked to the first.  The length of the

MBLK will be either 30 or 60 words.  The 30 word MBLK is used for

sending data and the 60 word MBLK is used for receiving.


     The header of the MBLK consists of 4 words.   See  Figure  2

for  the  format  of  the  block.  The "Link" is used to point to

other MBLKs.  The "Offset" field  is  used  for  reassembling  IP

fragments  and  sequencing  TCP data.  During these operations it

contains the offset of where this data is relative to the data in

the  previous  MBLK.   Zero  means that there is no missing data.

This is discussed in detail in the section on "Reassembly".


      1             0 0             0
      5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
     +---------------+---------------+
  0  |             Link              |  Pointer to next MBLK
     +---------------+---------------+
  1  |             Offset            |  Used in reassembly and sequencing
     +---------------+---------------+
  2  |    Length     |   Flags       |  Length of Data, Bit flags
     +---------------+---------------+
  3  |       Pointer to Data         |  Pointer to current data
     +---------------+---------------+
  4  |                               |  Area which holds message
  .  |       Data                    |
  .  |                               |
  .  |            Area               |
     |                               |
  n* |                               |
     +---------------+---------------+

                 Figure 2 . Message Block Format



_______________
* Where "n" is either 29 or 59, depending whether  the  block  is
used for sending or receiving.



                              -12-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



     The "Length" and  "Pointer  to  Data"  fields  are  used  to

indicate  where and how much data is in the MBLK.  The meaning of

these  is  always  relative  to  the  protocol  module  currently

processing  the message.  For example:  when a message is read in

from the host interface the "Pointer to Data" will point  to  the

1822  leader  and the "Length" will be the length of all the data

in this MBLK.  When the 1822 module is ready to pass the data  to

the next protocol module, it adjusts these fields to refer to the

data after the 1822 leader.  In this way, a protocol module  need

not know what, if any, protocol preceded it.


     The "Flags" is a bit field containing such things as End  of

message,  I/O  in  progress, Read or Write, small or large block,

etc.  The "Data Area" is where the actual message is stored.  The

small  size  MBLK (30 words) is sized to contain an 1822, IP, and

TCP leader, but no data.  The large size (60 words)  can  contain

the leaders plus up to 60 bytes of data.




4.2  Protocol Data Block


     The Protocol Data Block is a header block for  one  or  more

MBLKs  that make up a message.  It contains pointers to the first

MBLK, pointers to  specific  leaders  in  the  MBLKs,  frequently

accessed items from the message, and a link to the next PDB.





                              -13-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



     As previously stated, it is pointers to PDBs that are passed

between  protocol modules.  When a protocol module gets a PDB, it

expects to find one PDB, which points to one or more MBLKs.   The

data  in  the  MBLKs  is  expected  to  be  in  sequence and non-

fragmented.  This requires that each protocol module insure  that

the  data  it  passes  to the next module be contiguous.  This is

best described with the following example:


     When the Internet module gets  two  fragments  of  the  same

datagram,  it needs to reassemble them before it can pass them to

the next protocol module.  What it does  is  to  take  the  MBLKs

containing  the  second  fragment  and  link them into the proper

places in the list of MBLKs of the first fragment.   As  it  does

this,  it adjusts the fields in the MBLKs to point to the correct

data.  When it has linked  in  all  the  MBLKs  from  the  second

fragment,  it puts the PDB, which controlled the second fragment,

back on the free list of PDBs.


     The TCP module performs a similar operation to sequence  the

data before it passes it to the Telnet module.  The format of the

PDB is shown in Figure 3.


     The first field in the PDB, "Link to next PDB", is a pointer

to another PDB.  This is used for reassembly and sequencing.  The

next field in the PDB is the address field.  This is  either  the

source of the message if it was received or the destination if it



                              -14-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981





      1             0 0             0
      5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
     +---------------+---------------+
   0 |    Link to next PDB           |  Pointer to next PDB
     +---------------+---------------+
   1 |   Network     |   Host        |  Source / Destination
     +---------------+---------------+  Address
   2 |               |   IMP         |
     +---------------+---------------+
   3 |        Identification         |  IP Identification
     +---------------+---------------+
   4 |     Flags     |   Protocol    |  Bit flags, Protocol #
     +---------------+---------------+
   5 |          Time Stamp           |  Time stamp for aging
     +---------------+---------------+
   6 |    Pointer to 1st Leader      |  Usually 1822
     +---------------+---------------+
   7 |    Pointer to 2nd Leader      |  Usually IP or NCP
     +---------------+---------------+
   8 |    Pointer to 3rd Leader      |  Usually TCP
     +---------------+---------------+
   9 |    Pointer to first MBLK      |  Pointer to first MBLK
     +---------------+---------------+
  10 |    Protocol                   |  Variables used by each
     +                               +  protocol module
  11 |      Variables                |
     +                               +
  12 |         Area                  |
     +                               +
  13 |                               |
     +---------------+---------------+


              Figure 3 . Protocol Data Block Format


is to be  sent.   The  "Identification"  field  is  the  internet

identification  which  is  used in assembling internet fragments.

The "Flags" field is a bit array used for  things  like  datagram

complete,  EOL,  Urgent, Read or Write, block free, in use, hole,

etc.  The "Protocol"  field  is  the  host-to-host  protocol  the




                              -15-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



message  is  for.   The "Time Stamp" field is used for timing out

messages.


     The "Pointer Leader" fields are used to point  to  different

leaders  in  the MBLKs.  This is done to make it easier to find a

particular  leader  in  the  message.   They  are  set  up  by  a

particular  protocol  message  and  refer  to  different  leaders

depending on which protocols are in use.


     The "Pointer to first MBLK" field  is  the  pointer  to  the

first  MBLK  of  the message.  The "Protocol Variables Area" is a

temporary area that any protocol  module  can  use  while  it  is

processing  the  PDB.   As  long as it controls the PDB, no other

module will change these fields.




5.  1822 Protocol


     All 1822 data messages will be passed directly to  the  next

protocol  module.  When the 1822 module gets a control message it

will call a routine supplied to it by the next  protocol  module.

For  example,  the  NCP module will supply a routine to be called

when the 1822 module receives a "RFNM" on  an  NCP  link  number.

The  routines  will  be  called  with a pointer to the PDB of the

message.  When the routine returns the 1822 module  will  discard

the message.




                              -16-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



6.  Internet Protocol


6.1  Identifier Assignment


     When  the  Internet  module  gets  a  message  to  send,  it

generates a value for the "Identifier" (ID) field in the internet

header.  It does this by keeping a 16-bit counter called  the  ID

counter.   When it needs a new value it increments the counter by

one and uses the result.  The ID counter will not be  initialized

when  the TAC is reloaded or restarted, to insure that the values

are sequential.




6.2  Option Support


     The Internet module will only actively  support  the  "Error

Report"  IP  option.  None of the other currently defined options

will require any action to be performed by the TAC.




6.3  Reassembly


     When the Internet module gets a  PDB  which  is  a  datagram

fragment, it must reassemble it.  It first looks at the fragments

on the Internet-Reassembly queue to see if there  are  any  other

fragments  of  the  same datagram.  It does this by comparing the

source address, ID, and protocol number of the two fragments.  If




                              -17-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



it  does  not find a match, it adds the new PDB to the queue.  At

this point, it also puts a time stamp in the PDB.  This  will  be

used to timeout unassembled fragments.


     The actual reassembly process consists of adding  the  MBLKs

of  the  new datagram to the list of MBLKs of the datagram on the

queue.  This  is  done  using  the  "Offset",  "Length"  and  the

"Pointer  to  Data"  fields  in  the  MBLK.  At this point in the

processing of the fragment, the fragment consists of one or  more

MBLKs linked together.  The IP header will always be in the first

MBLK.  The "Offset" fields in the MBLKs are all zero (there is no

missing  data  in  the new fragment itself).  The "Length" fields

contain the length of the IP data (not including the  IP  header)

in  each MBLK.  The "Pointer to Data" fields point to the IP data

in each MBLK.


     The MBLKs of the new datagram are added to the  datagram  on

the  queue by comparing the "Fragment Offset" in the IP header of

the new datagram to the "Fragment Offset" in the IP header of the

datagram  on  the  reassembly  queue.  This is done by taking the

first MBLK on the list and adding the "Fragment Offset" from  the

IP  header to the "Length" and "Offset" fields in the first MBLK.

If this sum is greater than  the  "Fragment  Offset"  in  the  IP

header  of  the  new datagram, then the MBLKs of the new datagram

should go before the first MBLK of the datagram in  the  original




                              -18-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



fragment.   If  not, then they should be added in after.  In this

case,  the comparative process is repeated with the rest  of  the

MBLKs on the list.  When the proper place is found, the new MBLKs

are linked in and the  fields  of  the  new  and  old  MBLKs  are

adjusted.   If  the  new  fragment overlaps the existing, then by

adjusting the "Pointer to Data" and "Length" fields, the  overlap

can  be  skipped.   This  may  result  in one or more MBLKs being

discarded.


     When the datagram is completely reassembled, it can then  be

taken  off  the  Reassembly queue and passed to the next protocol

module.




6.4  Routing


     The decision about where to send a datagram is twofold.   If

the  destination  host  is  on  the same net as the TAC, then the

datagram is sent directly to that host.  If not, then it must  be

sent to a gateway.


     The  Internet  module  will  maintain  a  table  that   will

facilitate  routing  messages  to  hosts  on other networks.  The

table is a list of all networks (256) and the gateways to get  to

the networks.  This table, called the Network-Gateway table, will

be  initially  loaded  into  the  TAC  and  will  be  dynamically




                              -19-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



maintained by the TAC.


     When the Internet module needs to find an address, it  looks

in  the  Network-Gateway table to get the gateway address for the

network it wants to send to.  If it finds an address it uses it.

If  the entry for the network it wants is empty (i.e., no gateway

address  specified),  then  the  Internet  module  will  use   an

arbitrary gateway.


     If the Internet module receives a Redirect  message  from  a

gateway, it will update the Network-Gateway table to indicate the

correct gateway.  This will insure that the Network-Gateway table

contains current information.


     If a gateway goes down  during  a  connection  the  Internet

module  will  clear  that  network's entry in the Network-Gateway

table.  It will then try an arbitrary gateway.   If  at  a  later

time,  the Internet module receives a Redirect message telling it

to use a new gateway to get  to  a  network,  it  will  set  that

network's  entry  in  Network-Gateway  table to the new gateway's

address.




6.5  Gateway to Gateway Messages


     The Internet module will support the  "Gateway  to  Gateway"

protocol  in  a  passive  sense.   If  it receives a "Destination



                              -20-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



Unreachable  Packet"  or  a  "Redirect  Packet"  it   will   take

appropriate  action.   If  it  receives  anything  else,  it will

discard the message.   In  particular,  if  the  Internet  module

receives  a  "Source  Quench Packet" it will discard the message.

This strategy  is  used  due  to  the  TAC's  limited  amount  of

buffering.   The  buffers  would soon fill up because of the data

not being acknowledged (in TCP).  This will effectively limit the

transmission.




6.6  Timeouts


     Internet  fragments  will  be  discarded  if  they  are  not

reassembled   within   60   seconds.   When  a  new  fragment  is

reassembled into an existing one, the "Timeout" field in  PDB  of

the  existing  fragment  will  be  updated with the current time.

This will, in effect, reset the timer for that fragment.




7.  Transmission Control Protocol


7.1  Connection Opening and Closing


     The TCP module will have a finite state machine  which  will

be  used for establishing and closing connections.  The procedure

to  open  a  connection  is  to  pass  the  required  information

(Destination  address,  socket, etc.) to the TCP module.  It will



                              -21-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



then run the finite state machine, which will set up the required

data  structures and open the connection.  Closing the connection

will be done in a similar way.  The states of  the  finite  state

machine  will  be  similar  to what is described in "IEN-129, DOD

Standard Transmission Control Protocol".


     All TCP Port numbers assigned by the TAC will consist of the

upper  8  bits  set to the terminal number for the connection (1-

64.) and the lower 8 bits set to 23.  All connections made to  or

from the TAC will use this format.




7.2  Initial Sequence Number Assignment


     The TCP module will maintain a 32-bit counter that  will  be

used  to  generate  Initial  Sequence Numbers (ISN).  The counter

will be incremented by a constant  value  every  time  the  H-316

clock  ticks,  which  is  every  25.6MS.   The  counter  will  be

incremented by 64.  This  will  then  wrap  around  approximately

every  4.55 hours.  When the TCP module needs an ISN it reads the

counter and gets a value.




7.3  Option Support


     The TCP  module  will  understand  the  format  of  all  TCP

options.   It  will support the "No-Operation" and "End of Option



                              -22-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



List" options.  It will not support the "Buffer Size" option.  If

it  receives  a  "Buffer  Size" option with anything greater than

size one, it will not accept the connection but will reset it.




7.4  Urgent Data


     When the TCP module receives a message with a  valid  Urgent

Pointer,  it  sets  a bit in the "Flag" word in the PDB and saves

the offset to the end of the urgent data.  When the next protocol

module  takes data out of the MBLK it will get an indication that

the data it is getting is urgent.


     Likewise, when the TCP module is given  data  to  send,  the

protocol module supplying the data can include an indication that

the data is urgent.  The TCP module will include this information

in all messages it sends until the urgent data is sent.




7.5  End of Letter Handling


     The TCP module will not do anything special when it receives

a  message  with  End of Letter (EOL) set.  The TCP module always

presents all data to the next protocol module as soon  as  it  is

available.  Consequently, no special handling is necessary.







                              -23-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



     The TCP module will accept data  to  be  sent  with  an  EOL

indication.   It will send this data with EOL set in the message.

No additional data will be sent in the message.  If the  data  is

required  to  be  retransmitted,  it will be transmitted with EOL

preserved.




7.6  Retransmissions


     Data that is transmitted by the  TCP  module  will  be  held

until  it  has  been  ACKed by the remote host.  If an ACK is not

received  for  the  data  within  three  seconds   it   will   be

retransmitted.   All data in the buffer that is not ACKed will be

retransmitted (except if EOL is set; see previous  section).   If

the   data   is  still  not  ACKed  for  another  seven  seconds,

retransmission will occur again.  This  procedure  will  continue

using  the  series 3,7,15,15,30 .  If there is still no ACK, then

the user will be notified.   The  retransmissions  will  continue

every  30  seconds until either the user closes the connection or

the TCP module receives an ACK.




7.7  Acknowledgement and Window Strategy


     The Acknowledgement (ACK) and Window parameters are used  to

control  how  much data the remote host can send to the TAC.  The




                              -24-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



TCP module will ACK data up to the limit it is willing to  buffer

for a connection.  Data received after this limit is reached will

be discarded.  As the data  is  received,  but  before  the  next

protocol  module  takes  it out of the buffer, the window will be

closed by the amount received.  When the buffer limit is reached,

the  TCP module will not ACK any new data and will be advertising

a zero window.  When the next protocol module takes data  out  of

the  buffer,  the  window  will  be  opened.  This will allow the

remote host to send more data.


     When data is sent on the connection,  the  current  ACK  and

Window  values  are  always included in the same message.  In the

case where no data is being sent and the ACK and/or Window values

have changed, a different strategy is used.  When the ACK pointer

is advanced, the TCP module will wait one second to see if  there

is  data to send.  If there has been no data sent for one second,

then the ACK will be sent without data.  A new window value  will

not  be  sent  until  the  buffer  is  at least half empty.  This

strategy is designed to insure that the remote host sends  blocks

of data and to eliminate unnecessary retransmissions.




7.8  Sequencing


     When the TCP module gets a data message for a connection, it

must  insure that the data is sequenced before it passes the data



                              -25-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



to the next protocol module.  The sequencing is done by comparing

the  sequence  number  of the message to the current "Left Window

Edge" (LWE) and  manipulation  of  the  "offset",  "length",  and

"pointer  to  data" fields of the MBLKs that make up the message.

For each connection a list is maintained of MBLKs that are  being

sequenced.  The MBLKs are in order but there may be missing data.


     When the TCP module is  ready  to  sequence  the  data,  the

message  consists  of a PDB, followed by one or more MBLKs linked

together.  The "pointer to data" field points to the  actual  TCP

data.   The  "offset" fields are all zero because the data in the

message is sequential relative to itself.  The "length" field  is

the amount of data in each MBLK.


     The sequencing is done by  linking  the  MBLKs  of  the  new

message into the sequencing list for the connection for which the

data message is intended.  This is done via the following steps:


     1.  Subtract  the  LWE  from  the  Sequence  number  of  the
         message.   The  result is the offset from the LWE.  Then
         set the "offset" field of the first MBLK to this result.
         If it is zero, this means that there is no missing data.
         Otherwise, the result is the amount of missing data.

     2.  Add the MBLKs to the existing list.   If  there  are  no
         MBLKs  on  the list, then the new MBLKs become the list.
         Otherwise, the insertion is done in the following steps:

              a) Find the position in which to add the  new  MBLK
                 by  adding together the "offset" and "length" of
                 first MBLK in the list.  If "offset" of new MBLK
                 is  less  than  the  sum, then the new MBLK goes
                 before the MBLK in  the  list.   Otherwise,  add



                              -26-

IEN-166                                                 R. Hinden
                                     Bolt Beranek and Newman Inc.
                                                     January 1981



                 "offset"  and  "length"  of the next MBLK in the
                 list to the previous sum. Repeat this  procedure
                 until a fit is found or the end of list.

              b) Link the new MBLK into the list.

              c) Subtract  the  ("offset"  +  "length")  of   the
                 previous MBLK from "offset" of the new MBLK.

              d) Subtract the ("offset" + "length")  of  the  new
                 MBLK from "offset" of the next MBLK.


0verlapping data will be handled by adjusting the "length"  field

in the MBLKs as the new MBLKs are linked in.


     The result of these operations is  a  list  of  MBLKs.   The

"offset"  field  in the MBLKs contains the number of missing data

bytes before it.  When the MBLK is at the front of  the  list,  a

zero  "offset"  means  the data is sequenced and can be passed to

the next protocol module.  As data is taken by the next  protocol

module,   the   "length"  field  of  the  first  MBLK  should  be

decremented.  When it is zero, the block  is  empty  and  can  be

discarded.


















                              -27-