SlCUrtiTV CLASSIFICATION Of fHis PAfi When Data Entarad HEAD INSTRUCTl BEFORE COMPIETINC FORM te irNT S CAIALOü NUMULH REPORT IKKUMI NTATION PAGE i 2 GOVT tu i onT NUMBER Technical Note No 75 jt tYf'E Of REPORT «• PfcRIGO COVhRtD lJ X Lk r Single-Connection TCP Specification l Preliminary Documentation » r Technical Note- J 6 PERFORMING ORG REPORT NUMBER 6QIHTHAOT OR ©«AW -m » «4» VL c TJatnes E Mathis RFOPMING 00 ' rS 1 um ii i ii i 11111 irrrniffl j nun i pfifrirnn MDA903-7 C-0Ö93 Ur ARPA Order 4 r 2494 J Stanford Electronics Labora jes - Stanford University To 7 Stanford CA 94305 UjZd f ' - o 1— 11 10 PROGRAM ELEMENT PROJECT TASK AREA WORK UNIT NUMBERS 6T10 12 CONTROLLING OFf iCL NAME ANtf «ÖT5RWftft-• _« » 'U ——— Defense Advanced Research Projects Agency Information Processing Techniques Office 1400 Wilson Ave Arlington VA 22209 14 REPORT DATE 13 NO Of- PAGES January 25 1976 31 15 SECURITY CLASS of this report UNCLASSIFIED MONITORING AGENCY NAME ADORESS if diff from Controlling Office Mr Philip Surra Resident Representative Office of Naval Research Durand 165 Stanford University 15a DE CLASS PIC AT ION DOWNGRADING SCHEDULE IG DISTRIBUTION STATEMENT of thil report Reproduction in whole or in part is permitted for any purpose of the U S Government f' ÜBTTKäimÖN gfATEMEWrr 4 1 Approvad for public Mzaaa DISTRIBUTION STATEMENT of the ebstract WtMeittf'in DK' K gOi-if Oi '«iBiit «iuni fetmyff MAY fi '9T6 18 SUPPLEMENTARY NOTES ID D D C KLY WORDS Cnntrnue on reverse side if naceisary and identify by block number cir B Interconnection communication protocols packet radio network ARPANET p ABSTRACT Continue on reverse side if necessary and identify by block number An implementation scheme is described for a single connection user internetwork Transmission Control Program using the Cerf-Kahn protocol It is designed for a dedicated micro-processor and supports low delay low through-put interactive traffic In this preliminary documentation a detailed implementation specification is presented in an ALGOL-like notation along with a brief discussion of its functions user interface control variables and data structures DD Jrnl473 fOmON OF 1 NOV 65 IS OBSOLETE UNCLASSIFIED t jfUHITY CLASSIFICATION OF THIS PAGE Wftln pata tntmed V AttraiM fir ITU Whlti Sectloi DOC Bulf Secüan «H4««0'JNCE $ n O JUSmiCAllONy» JüSmiCAllÖN Single-Connection TCP Specification Preliminary Documentation iy oisTHij ' mwxiwm certs J E flathis A Digital Systems Laboratory Stanford University Stanford California 94385 January 25 1978 Technical Note #75 DIGITAL SYSTEMS LABGRATGRY DeDt of Electrical Engineering Dept of Computer Science M Stanford University Stanford California This researches supported by the Defense A S d7 8 f Projects Agency under ARPA Order No 2494 Contract No nDA903-7GC 0093 The views and conclusions contained in this document are those of the author Ind should not be interpreted as necessarily representing h« official policies either express or implied of the Defense A vancld Research Projects Agency or the United States Government TCP0 implementation January 2S 1976 Table of Contents Sec t i on Page Subsect ion 1 INTRODUCTION 2 DESCRIPTION of TCP FUNCTIONS 1 3 USER-TCP INTERFACE 2 4 TCP STRUCTURE 3 4 1 OPERATING ENVIRONMENT A 2 NETWORK INTERFACE 4 3 PROCESS INTERACTION 4 4 CONNECTION CONTROL VARIABLES 4 5 INPUT PACKET HANDLER 3 5 5 1 8 5 USER INTERFACE LOGIC DOCUMENTATION le G TCP INPUT PROCESS LOGIC DOCUMENTATION 7 TCP OUTPUT PROCESS LOGIC DOCUMENTATION 22 8 ARPANET INTERFACE LOGIC DOCUMENTATION 26 References 07 1 INTRODUCTION This document describes a prelifninary implementation scheme for a sinrjle-connect ion internetMork Transmission Control Program TCP It is designed to operate on a dedicated small computer with minimal operating system assistance and to support low delay low through-put interactive traffic Although assumed to be attached to the ARPANET via a local or remote host interface 11 only minimal changes are necessary for connection to the Packet Radio Network using the Channel Access Protocol 2 Detailed knowledge is assumed of the internetwork TCP protocol and the reader is referred to the official specification t3 4 for justification and further discussion of the details of the protocol NOTE There have been several changes to the protocol that are not listed in the December 1374 revision 3 Among these addition of the Beginning Of Segment B0S3 bit and Timestamping in effect tT3 bit in the control information word addition of a 32 bit field for timestamping information and sending an ACKnowledgement for FIN requests The final specification will be available by February 197G 2 DESCRIPTION of TCP FUNCTIONS For maximum size reduction only the single-connection user subset of functions are implemented Unsupported functions are 1 Unspecified sockets - On doing an OPEN the user must fully specify the destination NET TCP and PORT socket addresses eliminating connections analogous to the NCP listening connection needed only by server and logger processes To permit a host to provide service serially through a single channel TCP this function may be implemented leter 2 Re-assembly of fragmented segments - Packets must have both the Beginning Of Segment BOS and End Of Segment EOS control bits asserted If not on passing through a gateway the segment was broken into fragments it should be discarded without processing The re-construction of segments has yet to be resolved but it can be avoided by limiting segment length by receive window size control to less than the gateway fragmentation threshold Though in the future it may become necessary to implement it for 3 ECHO and TRASH special functions - Being solely experimentation purposes ECHO and TRASH special TCP0 implementation January 25 197G functions are not implemented Messages containing these special functions are ignored If the cost penalty mainly storage capacity is not too high these functions will be implemented later 4 Timestamping - The timestamping control bit is ignored and the contents of the returning packet's times tamp field will be undefined 5 Parameter change Status socket - Being strict'y single-connection there is no Parameter change Status socket Note - this socket is distinct from the Uell Known Socket 0 Except for these restictions the TCP insures end-to-end acknowledgement error correction duplicate detection sequencing and flow control providing the user process a reliable error-free logical communications channel 5 USER-TCP INTERFACE Five primitives comprise the USER TCP interface It is intended that these routines be called via a subroutine jump or supervisor call and indicate command acceptance or rejection on exit Uhen complete the user will be notified of the final disposition of OPEN SEND and CLOSE requests This allows user processing to proceed asynchronously and in parallel with TCP processing 1 OPEN CONNECTION Used to establish a connection the OPEN primitive is passed the address of the foreign and local socket ids If a connection already exists the OPEN is rejected and an error returned to the caller After checking the request and socket ids the control variables are initialized and an Initial Sequence Number ISN is chosen Since we can remember the last sequence number used on the previous connection it is not necessary to choose a clock-based ISN but rather just continue Cf 33 section 4 3 1 for more on ISN selection After notifying the Net Output Process to send a SYN control is returned to the caller Uhen the connection is ready for use the user process is noti fled 2 SEND LETTER This call causes the data contained in the user buffer to be sent on the connection The buffer address and length are stored In a common data area the output process notified of work pending and control returned to the caller After the TCP0 implementation January 25 1976 data has been packetized and sent but not ACKnowlcdged the user process is notified Letter boundaries are ignored every data packet has the End Of Letter EOL bit set If the connection is not established the data is queued for sending later There can be at most one outstanding send The mechanics of sending data is covered In section xx 3 RECEIVE LETTER - The user process Is notified when data arrives on the connection and It is moved Into user buffers by a RECEIVE RECEIVE is called with a buffer pointer and maximum byte count and returns the actual byte count Again letter boundaries are ignored After delivery to the user an ACKnowledgement Is sent to the sender The exact details of moving data into the user buffer is covered later in section xxx 4 INTERRUPT - A special control signal is sent to the destination indicating an interrupt condition All unsent or unacknowledged data will be flushed If the connection is not established an error is returned 5 CLOSE CONNECTION - This command causes the connection to be closed If it is not open an error is returned Pending unsent or received data is flushed no more accepted and a FIN sent to the remote TCP Control is returned to the caller and the user Is notified when the close is finalized The exact process of closing a connection is covered later in section xxx TCP STRUCTURE 4 1 OPERATING ENVIRONMENT The TCP is designed to operate under a very simple operating system structure Each process has a process control table containing space for its run-time stack status save area and an external event scoreboard To signal a process of some event the signalling process sets a bit in the called process' scoreboard Each process is responsible for periodically polling its scoreboard and acting appropriately After processing the signal the process then clears the flag bit Each process runs to completion and context switching happens only when a process expllctly releases control The or ly operating system primitive is one that causes the context to switch to the next active process All processes run at the same priority level - TCP0 Implementation January 25 197B Using a scoreboard has three important restrictions It Is not possible to maintain temporal ordering of signals multiple signals of the same type are condensed into one and it is not possible to transfer any data along with the signal The first two restrictions are not critical to the TCP implementation indeed a TCP implementation running under a normal message queueing operating system must go to some effort to remove extraneous signals resulting from process asynchrony The third restriction requires putting data associated with an event in a global I oca ion known to both processes There must also be I O devices and their associated device driver routines It is assumed that the devices are interrupt driven though programmed device polling is possible at reduced data rates The following devices are needed 4 2 1 Net input device - 2 Net output device - 3 Hardware timer - t NETWORK INTERFACE To allow the TCP to be used with computer networks of different structure and interfacing requirements all network dependent code is concentrated in three routines Uhile designed for the ARPANET and Packet Radio Network this partitioning should be adequate for most other network configurations The most obvious exreption is the Very Distant Hosts in the ARPANET which require an additional watchdog process to provide control functions for the IMP-HOST line protocol used Cf 11 appendix F The routines and their functions are INITIALIZENETUÜRK - Called on system initialization this routine initializes the device driver routines and performs the HOST-NETUORK start-up sequence It returns when the network is ready to deliver accept messages to from the host computer NETINPUT - Passed the address of a packet buffer this routine initiates action to accept a message from the network It performs the network-dependent processing of the NETUORKHOST message header e g in the ARPANET it would verify that the message is of type 9 regular packet and not a special IflP-HOST message Control returns to the caller when a valid message is received NETOUTPUT - Called with the address of a message to send this routine performs the network-dependent formatting of the HOST-NETUORIC message header Transmission of the meseage January 25 197B TCP0 implementation into the netuork is started and control caller when the output is completed 4 3 returned to the PROCESS INTERACTION The TCP is composed o t- Processes appropriate evice rivers and a set of r-ca lable f nterruptable running Transmisston Control B'0«- f flags The TCP INPUT process o completion and ' X f 8 the user proces of neu handles incommg •• 8 and either error packet or CP r data received or slgna • « ' ° 7prP0 Cess is the only process that various control packets The P Jf ou ut pr0CesS la the only IKe receives data from the •♦ ' J e TCP OUTPUT process on command sender of data to « ° klack eo e est the input process or sends error packets °r control packet on req responsible for data on request of the user W» Jal The NeWk device tv i irrerulrutt-r foTa et etransmission A 4 CONNECTION CONTROL VARIABLES • x - i' «« inral to a sDecific connection Is Kept in 0 ' ■ n Cont o he follouing are the fields of the ransmission Control Bbioc KB UUOJ 1 and their length DHOST - 16 s The local PSN address of the • «on o r gateway «' 'P'' ' «• e TCP address if eS 'Vrerutre 'destination NET In the local id is used to Cf bisection determine the local gateway address DNET - 8 bits The destination network Id 4 2 1 for list of assigned network ids OTCP - 16 bits The destination TCP id OPORT - 24 bits The destination PORT id Along with OTCP they form the deetinatlon socket DNET and SNET - 8 bits The network id of the local network STCP - IB bits The TCP id of the local TCP SPORT - 24 bits The local PORT id Along with SNET and STCP they form the local socket number TCP0 implementation January 25 197B CONNECTlONSTATfc - 8 bits The actions performed by the TCP depend upon what has happened previously There are six connection states in a user TCP They are 1 exi st CLOSED - The connection as such does not 2 SYNSENT - The user process has done an OPEN and a SYN has been sent to the foreign TCP in an attempt to establish a connection We wait for the ACKnowledgement of our SYN before going to the ESTABLISHED state and notifying the user process that the connection is usable 3 SinULINIT - After sending a SYN to establish a connection we received a SYN without an ACKnowledgement of our SYN from the foreign TCP This represents an attempt by both ends to open the connection simultaneously Ue send an ACKnowledgement of the SYN we received and initialize the connection dependent variables We wait for the ACKnowledgement of our SYN before going to the ESTABLISHED state and notifying the user process that the connection is usable 4 ESTABLISHED - The three-way handshake to synchronize the connection was successful and the connection is usable for data transfers 5 FINUAIT - The user process nas done a CLOSE and we have sent out the FIN Ue wait for the FIN to timeout or to receive a FIN and ACKnowledgement of our FIN before going to the CLOSED state G FINRECEIVED - Ue have received a FIN from the foreign TCP The user is notified of the remote close and we send a FIN and ACKnowledge the receive FIN Ue now wait for an ACKnowledgement of our FIN or Its timeout before going to the CLOSED state RCVSEQ - 32 bits The next sequence number expected RCVUS - IB bits The receive window size INITSEQ - 32 bits The initial receive sequence number used by the foreign TCP Thi8 is used to detect old duplicates of the SYN that established the connection SNDSEQ - 32 bits The next sequence number to send SNOWS - QG bits The send window size TCP8 implementation January 25 197G LASTUGEQ - 32 bits The window last sequence number used to update send LSUEDGE - 32 bits The left send window edge sequence number INPUTHEAD - 16 bits The pointer to the head of the reassembly ring buffer BUFFERPOIK rtR - 16 serd buffer bits The address of receive data the start of the user's BUFBYTEC'JUNT - 16 bits The number of bytes in the user's send buffer The byte count and buffer pointer are set when the ueer does a send and are updated as the output process -emoves and sends data RTXUAKEUP - 16 bits Count of the number of retransmissions sent tithout receiving any new ACKs It is cleared when a valid ACK comes in Uhen the number of retransmissions exceeds a preset value the user is notified of TCP not responding RTXPOINTER 16 bits The pointer retraneilsslon ring buffer RTXCOUNT - 16 bit» The number retransmiss'on ouffer of to the head of the bytes of data In the RTXCONTROL - do bits' It ror-tains the control field of the control packet queued up to be retransmitted If zero then no control packet queued up Only one control packet can be queued for retransmission RTXCNTRLSEQ- 32 bitsJ The send sequence number of packet queued up to be retransmitted the control RTXDATASEQ - 32 bits The send cequence number of the data byte at the head of the retransmission ring buffer In addition there are several -issembly-time constants the size of various buffers that set NAXPACKEFSIZE - The maximum number of data bytes that can be put in the text field of a internet packet MAXPACKETSIZE internetwork header length and length of local PSN control fields determine the size of the send packet buffer MAXRCYUS - The maximum receive window size the reassembly ring buffer is set by the eize of MAXRTXCOUNT - The maximum amount of data queued up to be retransmitted This determines the size of the retransmission ring buffer • January 25 37S TCP0 implementation There are also They are several buffers associated uiith the connection RCVPKTBUFFER - The buffer that incoming packets are written into by the network device driver REASSflBUFFER -- The ring buffer where input data is stored pending deliver to the user process reassembled ami REASSMFLAGS - A boolean vector that indicates which elements of the reassembly buffer contain a data octet SENDPKTBUFFER - The buffer that outgoing packets are constructed in and sent out by the network device driver RTXBUFFER - The buffer enqueued A 5 where data waiting to be ACKnowledged Is INPUT PACKET HANDLER After initializing the local network interface the TCP INPUT process is awakened when a packet arrives from the network The packet is checked for an internetwork message malformed packets are simply discarded The validity check involves verifying that the message Is long enough to contain the TCP packet header and he packet header version number is correct The BOS and EOS control biiö must both be asserted the current implementation can not handle fragmented segments The checksum is finally calculated and detectably damaged packets are discarded they will be re-transmitted by the sender After validation the message is checked for special function or error information and processed appropriately In this preliminary specification their handling is not aetailed but the TCP must be sensitive to RESET ALL RESET and QUERY special functions and all error condi t ions Packets without control dispatch refer to specific connections the foreign and local sockets are checked against those of the single connection we serv'ec If different an error message connection noniexistent is constructed and queued to be sent by the Net Output Process If in the SYNSENT state and we receive a SYN with INT DSN or FIN then the SYI i is malformed and an error is returned If the packet acknowledges the SYN we sent the connection is synchronized He ACKnowledge the received SYN initialize the Transmission Control Block and notify the user of connection establishment If instead of an ACK the packet contains only a SYN then we have a simultaneous attempt by both sides to open the connection Cf 133 section A 3 2 for details of SYN collision The new connection state is SIMULINIT TCP0 implementation January 25 197G In the SII1UL1NIT state if we receive a SYN it is first checked to see if it is a duplicate of the SYN that caused the state chanqe to SinULINIT If so then just ADCnouledcje receipt Otherwise we have two different SYNs and can not tell which is valid so we send back an errcr and reinitialize If instead of a SYN we get an ADCnow I edge of our SYN the connection has been established by a four-way handshake Notify the user and process any data that may accompany the ACK Once the- connection is established errors are sent for all SYNs received except for duplicates of the original TCF0 Implementation 5 January 25 137G USER INTERFACE LOGIC DOCUMENTATION OPEN OPb'NBLOCKPOINTER i if CONNECT IONSTATE notequal CLOSED then return connection already open error Tove socket addresses into control block convert DNET DTCP address into local PSN host gateway address RCVUS «riAXRCVUS INITCONNECTIGN comment- return to caller notify user process when connection becomes established or on error condition return ok SEND u'lFFEPADDRESS BUFFERLENGTH comment- put buffer pointer and length into TCB for send process if BUFBYTECOUNT notequal 8 then return too many SENDs error el se beg i n PUFFERPOiNTERj- BUFrrRAOORESS BUFB t TECOUNT -BUFFERLENGTH notify TCP OUTPUT PROCESS to send data end return ok INTERRUPT if CONNECT IONSTATE rotequal ESTABLISHED return connection not open error then notify TCP OUTPUT PROCESS to flush send data notify TCP OUTPUT PROCESS to send INT return ok RECEIVE BUFFERADDRESS BUFFERLENGTH result BYTECOUNT j If CONNECTIONSTATE notequal ESTABLISHED then return connection not opened error PTR -BUFFERADDRESS BYTECOUNTt-0 while BYTECOUNT BUFFERLENGTH and REASSflFLAGSdNPUTHEAD begin user buffer PTR i- REASSHBUFFER INPUTHEAD 10 __ _ V -_ _ - - - _ -V - - „ - _ - -s do TCre mpiementation January 25 1375 REASSMFLAGS INPUTHEAO - FALSE PTR 3PTR4l INPUTHEAP - INPUTHEAD l HOD IIAXRCVUS B'YTECOUNTJ-BYTECOUNT I end RCVSEQ - RCVSEQ 5YTEC0UNT notify TCP OUTPUT PROCESS to send ACIO if REASSMFLAGS INPUTHEAO then notify user process of data remaining to be received return ok CLOSE case CONNECT IONSTATE -SYNSENT DELETECONNECTION of -SIMULINIT «ESTABLISHED begin CONNECriONSTATE FINUAIT notify TCP OUTPUT PROCESS to flush send data notify TCP OUTPUT PROCESS to send FIN end -CLOSED -FINUAIT -FINRECEIVED return ok 11 TCP0 Implementation B January 25 1978 TCP INPUT PROCESS LOGIC DOCUMENTATION TCP INPUT PROCESS wait for network interface initialization LOOP NET1NPUT RCVPKTBUFFER if packet length greaterthan or equal minifrum permitted and packet header version number equal 0 then begin comment- packet verified as a TCP message If packet BOS bit -1 and packet EOS bit -1 then begin comment- unfragmented message process if CHECKSUM RCVPKTBUFFER - 8 then comment- checksum ok packet not damaged if packet Control Dispatch bits equal 8 then HANDLEREGULARPACKET HANDLESPECIALPACKET end else comment- fragmented message code to do fragment reassembly goes in here but for now just log error end el se comment- garbage packet log error goto LOOP CHECKSUM PACKETPOINTER comment- computes the IB bit I's com ment sum of the header and text fields of the packet i the sum is 8 then the packet is not hopefully damaged HANDLEREGULARPACKET if ADDRESSCHECK then beg i n comment- packet is for this cornection process according to connection state case CONNECT IONSTATE of -SYNSENT If packet SYN bit -1 then begin If packet FIN INT or D5N bits -1 12 — - - ■ ■■ ■- — ■ J J_ —_ ■ _ -_ - J then TCP8 implementation January 25 1978 comment- should not have these control bits set return unacceptable SYN error XniTERROR EFP USYN el Be if packet ACK bit -1 then begin if ACCEPTABLEACK then beg i n SETTCB notify TCP OUTPUT PROCESS to send ACK CONNECTIONSTATE ESTABLISHEÖ notify user of conroction established HANDLEACK end XniTERROR EFP USYN end el se LUinuien l- £M iitu i icmcOuS äiiciitpiö lü Open ilia connection begin CONNECTiuNSTATEr-SinULINiT SETTCB notify TCP OUTPUT PROCESS to send ACK end end -SlflULINIT if packet SYN bit -1 then begin if packet seq number equal 1N1TSEQ then comment- duplicate of first SYN don't send an error but force an ACKnowlodgement notify TCP OUTPUT PROCESS to send ACK else beg i n comment- we have received two different SYNs and can't tell which to believe so send error message and reinitialize connection and trg again Kfll TERROR EFP USYN 1NITC0NNECTI0N end end else if packet ACK bit -1 then if ACCEPTABLEACK and INRCVUINDOW then beg i n comment- acknowledged our SYN so connection now synchronized CONNECT ION TATE ESTABLI SHED notify user of connection established 13 TCP0 implefnentation January 25 197B N0RMALCA5E end -ESTABLISHED if packet SYN bit -1 then begin if packet seq number equal INITSEQ then begin comment- duplicate of the original SYN that established connection force an ACK and process any data notify TCP OUTPUT PROCESS to send ACK If INRCVUINDOU then NORMALCASE end else comment- unacceptable SYN XhlTERROR EFP USYN c -d else oeg i n if INRCVUINDOU then NORriALCASE else notify TCP OUTPUT PROCESS to send ACK end 1NUAIT f INRCVUINDOU and packet FIN bit 1 then beg i n comment- we have sent a FIN and now have received a FIN Acknowledge FIN and see if can delete the connect ion RCVSEQ packet seq number packet text length RCVSEQ RCVSEQ CONTROLLENGTH RCVPKTBUFFER CONNECT 1ONSTATE -FINRECEIVED notify TCP OUTPUT PROCESS to send ACK if packet ACK bit - 1 and ACCEPTABLEACK then HANDLEACK end -FINRECEIVED if INRCVUINDOU and packet ACK bit -1 if ACCEPTABLEACK then HANDLEACK end else XhlTERROR EFP NONK return 14 then TCP8 implementation January 2B 197B INRCVUINDOU comment- determines if any part of the packet that just came In lies inside the receive window ACCEPTABLEACK comment- return TRUE if packet ACKs something we sent that has rot yet been ACKed i e LSUEDGE - ACKfield - SNOSEQ NORhALCASEj comment- this processes the normal case of putting new data into the right place in the circular reassembly buffer also processes other possible things in packet packst ACK bit -1 and ACCEPTABLEACK then HANOLEACK packet INI bit - 1 then HANDLEINT packet text length greater than 0 then HANÜLEDATA packet DSN bit » 1 then KANDLEDSN packet FIN bit - 1 then HÄNDLERIN return HANDLEACK comment- correlates the ACK that came in and window etc with what we have already put in the control block it Is where confirming ACKs will remove data from the Retransmission ring buffer if PRECEDE LASTU5EQ packet sequence number then begin comment- update the send window size if this Is the latest packet we have seen SNDUS « packet window size field LASTUSEQ - packet sequence number end comment- convert next sequence number expected to sequence number of last octet ACKnow'edged ThPRFD - packet ACK field - 1 15 TCP8 implementation January 25 1976 LSUEDGE - packet ACK field if RTXCONTROL notequal 0 then comment- see if control ACKed if PRECEDE RTXCNTRLSEQ TflPSEQ then beg i n ■ comment- if our FIN was ACKed delete the connection if RTXCONTROL • FIN packet then DELETEC0NNECT10N RTXCONTROL -8 end if RTXCOUNT notequal 8 then comment- see if any data is ACKed and If so remove them if PRECEDE RTXÜATASEQ TMPSEQ then begin COUNTs-TflPSEQ - RTXDATA5EQ 1 RTXCOUNT RTXCOUNT - COUNT RTXP01NTER - RTXPOINTER COUNT MOD MAXRTXCOUNT RTXDATASEQ «RTXDATASEQ COUNT end return SETTCB comment- fills received information into control block from arr iving SYN packet RCVSEQ is the next sequence number expected SNDUS is the send window size INITSEG is the initial receive sequence number used LASTUSEQ is the last sequence number used to update send window LSUEDGE is the left send window edge SNDUS « packet window size 1NITSEQ » packet seq number LASTUSEQ - packet seq number RCVSEQ - packet seq number 1 return HANDLEDATA comment- this routine moves data from the input packet Into the circular reassembly buffer IB _ „_ „ - TCP8 implementalion January 25» 197G INPUTHEAD is a pointer to the head of the reassembly buffer RCVSEQ is the left receive window edge sequence number PINDEX is the index into the text field of the Input packet REAGSflBUFFER is the actual reassembly buffer and REASShFLAGS is a vector of flags indicating which bytes in the REASSriBUFFER contain valid user dat flAXRCVUS is the length of the reassemble buffer PINDEX -0 START » packet seq number if PRECEDE START RCVSEQ begin PINDEX »RCVSEO-START START -RCV3EQ end then PTR - START - RCVSEQ INPUTHEAD MOO MAXRCVWS AMOUNT - MIN RCVUS packet text length for I - PINDEX until AMOUNT PINDEX - 1 do begin REASSHFLAGS PTR -TRUE REASSflBUFFER PTR - packet text field indexed by I PIR - PTR l MOD MAXRCVUS end ' if START - RCVSEQ then notify USER of new data received at left window edge return HANDLEINT RCVSEQ - packet seq number 1 notify TCP OUTPUT PROCESS to send ACK flush receive data notify USER of INTERRUPT request return HÄNDLERIN comment- handle a valid FIN arriving when connection ESTABLISHED CONNECT IONSTATE -FINRECEIVEO notify TCP OUTPUT PROCESS to flush send data 17 ___ m TCP8 implementation January 25 1976 notify USER of remote close RCVSEQ - packet seq number packet text length RCYSEQ -RCVSEQ ♦ CONTROLLENGTH RCVPKTBUFFER notify TCP OUTPUT PROCESS to send ADO notify TCP OUTPUT PROCESS to send FIN return HANDLEDSNs comment- method for handling DSN is yet unresolved return ADDRESSCHECK comment- returns TRUE if the packst is for the one valid connection the foreign NET TCP PORT address and the local PORT adaresses must agree with those of the open connection if CONNECT IONSTATE - CLOSED return FALSE then if packet source NET field notequal DNET return FALSE then if packet source TCP field notequal DTCP return FALSE then if packet source PORT field notequal DPORT return FALSE • then If packet destination NET field notequal SNET return FALSE then if packet destination TCP field notequal STOP return FALSE then If packet destination PORT field notequal SPORT return FALSE else return TRUE then HANDLESPECIALPACKETi comment- handle special functions or error message packets 18 TCP0 implementation January 25 197G case packet control dispatch field of -SPECIALFUNCT10N beg i n case packet control data octet of -RESETALL if packet source TCP field - DTCP RESETCONNECTION -RESET If ADDRESSCHECK and ACCEPTABLEACK RESETCONNECTION then then -QUERY if ADDRESSCHECK then send status message end -ERROR if ADDRESSCHECK then beg i n comment- process error directed at uc case packet control data octet -USYN if CONNECT IONSTATE - SYNSENT send a reset of then if CONNECT IONSTATE - SIHULINIT INITCONNECTION -NONX -1NACC begin case CONNECT IONSTATE -SIMULINIT INITCONNECTION then of -ESTABLISHED if INRCVUINDOU then notify user process of error -FINUAIT if INRCVUINDOU then DELETECONNECTION end end return 19 TCP0 implementation January 25 1976 INITCONNECTION comment- initialize connection state CONNECT IONSTATEr-SYNSENT notify TCP OUTPUT PROCESS to flush send data flush receive data comment- pick initial sequence number by adding a constant to last sequence number used on previous connection SNDSEQj-SNDSEQ 1 notify TCP OUTPUT PROCESS to send SYN return CONTROLLENGTH packet buffer comment- returns the nurrber of octets used In the packet by control functions COUNT -0 if packet SYN bit -1 COUNT -1 if packet INT bit -li COUNT -COUNT 1 If packet FIN bit -1 COUNT C0UNT 1 if packet OSN bit -1 COUNT -COUNT 1 return COUNT then then then then PRECEDE PARfll PARMZ comment- returns true if PARf12 - 2 16 PARfll PARMl and PARf12 both being 32 bit numbers this is just a special InwlndoM test that returns true if PARfll precedes or equals PARt12 in the circular sequence number space XniTERROR ERROR CODE comment- send an error message to the remrte TCP the error code is passed as a parameter see 3 section 2 4 3 about possible error codes swap source destination socket ids put input packet sequence number in ACK field set Control Dispatch to indicate error present put ERROR CODE in control octet notify TCP OUTPUT PROCESS to send error packet wait for completion of error send set error send complete flag to false return 28 r - -- „ ■ „-_ _ - t - - TCP9 implementation »snuary 25 197B DELETECONNECTION comment- set the connection state to CLOSED notify the ueer of close completion and flush all the queues and stuff CONNECTIONSTATE -CLOSED notify user process of CLOSE completion notify TCP OUTPUT PROCESS to flush send data return 21 -- - - TCP0 implementation 7 January 25 197B TCP OUTPUT PROCESS LOGIC DOCUrENTATION TCP OUTPUT PROCESS comment- initial ize Net interface 1NITIALIZENETU0RK notify TCP INPUT PROCESS of initialization complete LOOP uait for uork to process if need to send error then begin move packet from RCVPKTBUFFER into SENDPKTBUFFER SENDPACKET notify TCP INPUT PROCESS that error has been sent set need to send error flag to false end if need to flush send data then begin comment- flush the send data and retransmission queues first remove any outstanding SENDs if need to send data then begin set need to send data flag to false notify USER of eend completion ready for new send end BUFBYTECOUNT -0 comment- then remove any data or control to be retransmitted RTXCOUNTs-e RTXC0NTR0L »8 RTXUAKEUP -8 set need to retransmit data flag to false set need to retransmit control flag to false set need to flush send data flag to false end if need to send SYN INT or FIN then beg i n womment- construct a packet and add the appropriate control bits INITIALIZEPACKET if need to send SYN then set packet SYN bit 1 if need to send INT then set packet INT bit -1 if need to send FIN then set packet FIN bit -1 set need to send SYN INT and FIN flags to false 72 -—' -- TCP8 Implementation Januarg 25 1978 SENDPACKST RTXCNTRLSEQi-SNOSEQ RTXCONTROL - packet control word field SNDSEQJ-SNDSEQ ♦ CONTPOLLENGTH SENDPKTBUFFER end If need to send data then begin comment- SPACELEFT is emount of space left in send window ' f tXCOUNT is the number of bytes in the retransmission queue MAXRTKCOUNT is the length of the retranamisslon queue buffer RTXSPACE is amount of space left in retransmission queue MAXPKTSIZE is maximum number of data bytes In packet BUFBYTECOUNT Is number of bytes in user send buffer BUFFERP01NTER is address of start of user send buffer SPACELEFT rN0US - SNDSEQ LSUEDGE RTXSPACE -nA TXCGUNT - RTXCOUNT COUNT - MIN ACELEFT BUFBYTECOUNT RTXSPACE MAXPKTSIZE If COUNT notequal 8 then beg i n INITIALIZEPACKET If RTXCOUNT - 8 then RTXDATASEG -SNDSEQ PKTPTR - Index of start of packet text area for h-l until COUNT do beg i n copy byte from user buffer into packet • copy byte from buffer into retransmission queue BUFFERPOINTER -BUFFERPOINTER 1 RTXPOINTER - RTXPOINTER 1 MOD MAXRTXCOUNT PKTPTR -PKTPTR 1 BUFBYTECOUNT -BUFBYTECOUNT-1 RTXCOUNT «RTXCÜUNT 1 end set packet text length equal COUNT SENDPACKET SNDSEQ -SNDSEH COUNT If BUFBYTECOUNT - 8 then begin set need to send data flag to false notify USER of send completion ready for next send end end If need to retransmit data and CONNECT IONS TÄTE - ESTABLISHED then begin comment- RTXUAKEUP counts the number of retransmissions sent without receiving any ACKs back It Is cleared 23 TCP0 implementation January 25 197G in HANOLEACK when a valid one comes in and incremented by the clock interrupt routine before notifying the SEND process to retransmit data or control if the data remains on the retransmission queue too long the user is noti fied if RTXUAKEUP greaterthan maximuin allowed then comment- the foreign TCP has failed to ACK data that has been waiting it is assumed that the destination is not responding notify USER that destination TCP not responding ei se begin comment- now retransmit the data queued up SPACELEFTJ SNDUS - RTXDATASEQ L5UEDGE COUNT » MIN SPACELEFT RTXCOUNT MAXPKTSIZE if COUNT notequal 0 then begin 1NIT1AUZEPACKET RTXPTRt-RTXPOINTER PKTPTR - index of start of packet text area for h«l until COUNT do SENDPKTBUFFER PKTPTR -RTXBUFFER RTKPTRJ PKTPTR PKTPTR 1 RTXPTR - RTXPTR 1 MOO MAXRTXCOUNT end packet sequence number 5■ RTXDATASEQ packet text length - COUNT SENDPACKET end end set need to retransmit data flag to false end if need to retransmit control then beg i n if RTXCONTROL notequal 0 then begin if RiXUAKEUP greaterthan maximum allowed then begin notify USER that destination TCP not responding if RTXCONTROL equals FIN racket then comment- a FIN packet has timed-out so close the connection anyway DELETECONNECTION end else begin SPACELEFT -SNDUG - RTXCNTRLSEQ LSUEDGE 24 TCP8 implementation January 25 197G if SPACELEFT greaterthan 8 then beg i n 1NITIALIZEPACKET packet sequence number RTXCNTRLSEQ packet control word - RTXCONTROL SENDPACKET end end end set need to retransmit control flag to false end if need to send ACK begin INIT1ALIZEPACKET SENDPACKET end then goto LÜÜP IN1TIALIZEPACKET comment- initialize the internet header move SNDSEQ into packet seq field move foreign socket id into packet move local socket id into packet move RCVUS nto packet zei o ut rest of packet header if njed to send ACK then begin comment- piggyback ACK onto data or control packet set packet ACK bit «D put receive left windou edge in AC field set need to send ACK flag to fals' end return SENDrACKET comment- calculate a checksum and put it in the header and then sent It put zero in packet checksum field packet checksum fieId I-CHECKSUM 3ENDPKTBUFFER NETOUTPUT SENDPKTBUFFER return 25 TCP0 implementation 8 January 25 1976 ARPANET INTERFACE LOGIC DOCUHENTATION 1NIT1ALIZENETUORK comment- initialize the device drivers and send NOPs to IMP reset network device driver construct IMP NOP message for I »1 untiI 4 do begin comment- send four NOPs to the ItIP give NOP message to network driver to send wait until message sent end return NET INPUT PACKETBUFFER comment- start input from ItIP LOOP start message input from IHP wai t untiI f inished if message not on experimental links 155-158 goto LOOP then if message type notequal regular or minimum effort goto LOOP comment- return message to TCP return NETOUTPUT PACKETBUFFER initialize 1 HP-HOST header give to network device driver to send wait until message sent return 26 then TCP0 implementation January 25 197G References 1 Bolt Beranek and Newman Inc Interface Message Processor Report No 1822 December 1975 2 R C Sunlin Packet Radio Channel Access Protocol Program Packet Radio Note No 144 29 September 1975 3 V Cerf Y Dalai C Internet Transmission Control December 1374 Revised 4 V Cerf R Kahn A Protocol for Packet NetMork Interconnection IEEE Transactions on Communication Vol COfl22 Number G May 1974 27 Sunshine Program Specification of INUG Note No '7 DISTRIBUTION ARPA Director 2 copies ATTN Program Management Advanced Research Projects Agency 1400 Wilson Boulevard Arlington VA 22209 ARPA IPT 1400 Wilson Boulevard Arlington _ VA__ 22209 Mr David H Dahm Burroughs Corporation Burroughs Place P 0 Box 418 Detroit Ml 48232 Mr B A Creech Manager New Product Development Burroughs Corporation 460 Sierra Madre Villa Pasadena CA 91109 Dr Robert Kahn Mr Steven Walker Cahledata Associates Bell Laboratories Dr Elliot N Pinson Head Computer Systems Research Dept Bell Laboratories 600 Mountain Avenue Murray Hill New Jersey 07974 Dr Samuel P Morgan Director Computing Science Research Bell Laboratories 610 Mountain Avenue Murray Hill New Jersey 07974 Mr Paul Baran Cabledata Associates Inc 701 Welch Road Palo Alto CA 94304 California University - Irvine Prof David J Färber University of California Irvine CA 92664 California University - Los Angeles Dr C S Roberts Head The Interactive Computer Systems Research Department Bell Laboratories Holmdel New Jersey 07733 Professor Gerald Estrin Computer Sciences Department School of Engineering and Applied Science Los Angeles CA 90024 Bolt Beranek and Newman Inc 50 Moulton Street Cambridge Massachuse11s achusetts 02138 Professor Leonard Kleinrock University of California 3732 Boelter Hall Los Angeles CA 90024 Mr Mr Mr Mr Mr Mr Jerry D Durchfiel R- Clements A McKenzie J McQuillan R Tomlinson D Waiden Burroughs Corporation Dr Wayne T Wilner Manager Burroughs Corporation 3978 Sorrento Valley Boulevard San Diego CA 92121 Mr William E Nay or University of California 3804-D Boelter Hall Los Angeles CA 90024 Collins Radio Group 1200 N Alma Road Richardson JTexas 75080 Mr Don Heaton Mr Frederic Weigl Defense Communications Engineering Center Dr Harry Helm DCEC R-520 1860 Wiehle Avenue Res ton VA 222090 Dr Richard L Shuey General Electric Research and Development Center 0 - Box 8 v Schenectady New York Mr Knut S Kongelbeck Staff Engr Hughes Aircraft Company 8430 Fall brook Avenue Canoga Park CA 91304 Mr Allan J Stone Hughes Aircraft Corporation Bldg 150 M S A 222 P 0 Box 90515 Los Angeles CA 90009 General Electric P- ones Airodft Company i97m 12301 A Bell Isle General Electric Company Electronics Laboratory Electronics Park Syracuse New York 13ZÖI Hughes Aircraft Company Attn B W Campbell 6 El 10 Company Technical Document Center Centinela and Teale Streets Culver City CA 90230 Dr Mr Ronald S Taylor General Electric Company 175 Curtner Avenue San Jose CA 95125 General Motors Corporation Computer Science Department Serai Motors Research Laboratories General Motors Technical Center uf rrpn MI 48090 Dr G-orge C Dodd Assistant Head Sr FredKrull Supervisory Research Engineer Mr John Boyse Associate Senior Research Engineer Hawaii University of The ALOHA System 2540 Dole Street Holmes 486 Mnnnlulu Hawaii Mgi Professor Norman Abramson IBM Dr Patrick Mantey Manager User Oriented Systems International Business Machines Corp K54-282 Monterey and Cottle Roads San Jose CA 95193 Dr Leonard Y Liu Manager Computer Science International Business Machines Corp K51-282 Monterey and Cottle Roads San Jose CA 95193 Mr Harry Reinstein International Business Machines Corp 1501 California Avenue Palo Alto Ca 94303 Illinois University of Mr John D Day University of Illinois Center for Advanced Computation Ti4 Advanced Computation Bldg Urbana Illinois 61801 Institut de Recherches d'Informatique et d'Automatique 1RIA Reseau Cyclades 78150 Rocquencourt France Mr Louis Pouzin Mr Hubert Zimmerman _ Infonihition Sciences Institute university of Southern California 4676 Admiralty Way Marina Del Rey CA 90291 Dr Mr Dr Mr Mr Dr Mr Mr Marty J Cohen Steven D Crocker Steve Kimbleton Keith Uncapher Derek Barber Donald Davies Roger Scantlebury P Wilkinson National Security Agency 9800 Savage Road Ft Meade MD 20755 London University College Professor Peter Kirstein UCL Department of Statistics Computer Science 43 Gordon Square London WC1H OPD England Mr Dan Edwards Mr Ray McFarland Massachusetts Inititute of Technology Dr J C R Licklider MIT Project MAC - PTD 5 5 lechnology Square Cambridge Massachusetts National Physical Laboratory Computer Science Division IQS ington Middlesex England Norwegian Defense Research Establishment P 0 Box 25 2007 Kjeller Norway Mr Yngvar 6 Lundh Mr P Spilling 02139 MITRE Corporation Mr Michael A Padlipsky MITRE Corporation 1820 Dolly Madison Blvd Westgate Research Park McLean VA 22101 Oslo University of Prof Dag Belsnes EDB-Sentret University of Oslo Postbox 1059 Blindern Oslo 3 Norway Rand Corporation 1700 Main Street Santa Monica CA 90406 Network Analysis Corporation Beechwood Old Tappan Road Glen Cove New York 11542 Mr S Gaines Mr Carl Sunshine Mr Wushow Chou Mr Frank Howard Rennes University of National Bureau of Standards Mr Robert P Blanc National Bureau of Standards Institute for Computer Sciences and Technology Washington D C 20234 M Gerard LeLann Reseau CYCLADES U E R d'Informatique B P 25A 35031-Rennes-Cedex France Mr Ira W Cotton National Bureau of Standards Building 225 Room B216 Washington D C 20234 fn 'trfrrir ' Stanford Research Institute 333 Ravenswood Avenue Menlo Park _CA 94025 Ms E J Fein er Augmentation Research Center Xerox Palo Alto Research Center 3333 Coyote Hill Road Palo Alto CA 94304 Mr David Boggs Dr William R Sutherland Dr Jon Postel Augmentation Research Center Mr D Nielsen Director Telecommunication Sciences Center Dr David Retz Telecommunication Sciences Center System Development Corporation Dr G D Cole System Development Corporation 2500 Colorado Avenue Santa Monica CA 90406 Telenet Communications Inc 1666 K Street NW Washington D C 20006 Dr Holger Opderbeck Dr Lawrence G Roberts Dr Barry Wessler STANFORD UNIVERSITY Digital Systems Laboratory Mr Ronald Crane Mr Yogen Dalai Ms Judith Estrin Professor Michael Flynn Mr Richard Karp Mr James Mathis Mr Darryl Rubin Mr Wayne Warren Digital Systems Laboratory Distribution Computer Science Department - 1 copy Computer Science Library - 2 copies Digital Systems Laboratory Library - 6 copies Engineering Library - 2 copies IEEE Computer Society Repository - 1 copy Electrical Engineering Dr John Linvill Transaction Technology Inc Dr Robert Metcrlfe Director of Technical Planning Transaction Technology Inc 10880 Wüshire Blvd Los Angeles CA 90024 Defense Communication Agency Dr Franklin Kuo 4819 Reservoir Drive Washing on D C 20007 —■— „ -„ ic as ' ■ i — Bai