RFC 675
Specification of Internet Transmission Control Program
Okay bestie, let's start with the vibes 🎀. This is RFC 675, titled SPECIFICATION OF INTERNET TRANSMISSION CONTROL PROGRAM, the "December 1974 Version," dated December 1974. The authors are Vinton Cerf, Yogen Dalal, and Carl Sunshine, and it's a Network Working Group document with the labels NIC: 2 and INWG: 72 🧚. The title block doesn't list a category or status, and it doesn't say what it obsoletes or updates, so I'm not making any of that up 🙈.
1. Introduction ✨
Okay so this doc describes the functions the internetwork Transmission Control Program [TCP] has to perform, plus its interface to the programs or users who need its services 💅. A few basic assumptions about process to process communication get made, and they're listed here without further justification. If you want more, check out [CEKA74, TOML74, BELS74, DALA74, SUNS74] 📚.
The authors want to shout out R. Tomlinson (three way handshake and Initial Sequence Number Selection), D. Belsnes, J. Burchfiel, M. Galland, R. Kahn, D. Lloyd, W. Plummer, and J. Postel, whose good ideas and counsel had a beneficial effect (we hope) on this protocol design 🫶. In the early phases, R. Metcalfe, A. McKenzie, H. Zimmerman, G. LeLann, and M. Elie were super helpful at explaining the issues. Obviously, the authors remain responsible for any errors and misstatements that lurk in the nooks and crannies of the text 🙈.
Processes are the active elements of all HOST computers in a network. Even terminals and files or other I/O media are seen as communicating through processes, so all network communication is treated as inter-process communication 🦋.
A process may need to tell apart several communication streams between itself and another process [or processes], so each process may have a number of PORTs that it uses to talk to the ports of other processes 🌸.
Port names get picked independently by each operating system, TCP, or user, so they may not be unique. To get unique names at each TCP, we stick a NETWORK identifier and a TCP identifier onto a port name to make a SOCKET name that's unique across all the networks connected together 🔥.
A pair of sockets forms a CONNECTION that can carry data in either direction [i.e. full duplex]. A connection is uniquely identified by the <local socket, foreign socket> address pair, and the same local socket can join multiple connections to different foreign sockets [see Section 2.2] 💖.
Processes swap finite length LETTERS, so letter boundaries matter 💌. A letter might be too long to send in one go, so it may get broken into FRAGMENTS first. We assume fragments will normally get reassembled into a letter before they're passed to the receiving process. Throughout this document, it's fair to assume a fragment contains all or part of a letter, but a fragment never contains parts of more than one letter.
We specifically assume fragments travel from Host to Host through a PACKET SWITCHING NETWORK [PSN] [ROWE70, POUZ73]. This is probably unnecessary, since a circuit switched network could also work, but to be concrete, we explicitly assume the hosts are connected to one or more PACKET SWITCHES [PS] of a PSN [HEKA7O, POUZ74, SCWI71] 🍓.
Processes use the TCP by handing it letters. The TCP breaks these into fragments if necessary, then embeds each fragment in an INTERNETWORK PACKET. Each internetwork packet is then embedded in a LOCAL PACKET that's suitable for transmission from the host to one of its serving PS. The packet switches may do further formatting or other operations to deliver the local packet to the destination Host 🚀.
The term LOCAL PACKET is used generically here to mean the formatted bit string exchanged between a host and a packet switch. The format of bit strings exchanged between the packet switches in a PSN generally isn't our concern. If an internetwork packet is destined for a TCP in a foreign PSN, it gets routed to a GATEWAY that connects the origin PSN with an intermediate or the destination PSN. Routing of internetwork packets to the GATEWAY may be the responsibility of the source TCP or the local PSN, depending on the PSN Implementation 🧭.
One model of TCP operation is to imagine a basic GATEWAY associated with each TCP that provides an interface to the local network. This basic GATEWAY performs routing and packet reformatting or embedding, and may also implement congestion and error control between the TCP and GATEWAYS at or intermediate to the destination TCP 🌈.
At a GATEWAY between networks, the internetwork packet is unwrapped from its local packet format and examined to determine which network it should travel through next. Then it gets wrapped in a local packet format suitable for the next network and passed on to a new packet switch 🎁.
A GATEWAY is permitted to break up the fragment carried by an internetwork packet into smaller fragments if that's necessary for transmission through the next network. To do this, the GATEWAY produces a set of internetwork packets, each carrying a new fragment. The packet format is designed so that the destination TCP can treat fragments created by the source TCP or by intermediate GATEWAYS nearly identically 🧩.
The TCP is responsible for regulating the flow of internetwork packets to and from the processes it serves, so its host doesn't get saturated or overloaded with traffic 🛑. It's also responsible for retransmitting unacknowledged packets and for detecting duplicates. A consequence of this error detection/retransmission scheme is that the order of letters received on a given connection is also maintained [CEKA74, SUNS74]. To perform these functions, the TCP opens and closes connections between ports as described in Section 4.3. The TCP performs retransmission, duplicate detection, sequencing, and flow control on all communication among the processes it serves 👑.
2. The TCP INTERFACE to the USER 🎀
2.1. The TCP as a POST OFFICE 📮
The TCP acts a lot like a postal service, since it gives processes a way to exchange letters with each other. Sometimes a process may offer some service but not know in advance what its correspondents' addresses are. Think of a mail order house that opens a post office box which can accept mail from any source. Unlike the post box though, once a letter from a particular correspondent arrives, a port becomes specific to that correspondent until the owner of the port declares otherwise 💌.
In addition to acting like a postal service, the TCP insures end-to-end acknowledgment, error correction, duplicate detection, sequencing, and flow control 🫶.
2.2. Sockets and Addressing 🦋
We have borrowed the term SOCKET from ARPANET terminology [CACR70, MCKE73]. In general, a socket is the concatenation of a NETWORK identifier, TCP identifier, and PORT identifier. A CONNECTION is fully specified by the pair of SOCKETS at each end, since the same local socket may participate in many connections to different foreign sockets ✨.
Once the connection is specified in the OPEN command [see section 2.3.2], the TCP supplies a [short] Local Connection Name by which the user refers to the connection in subsequent commands. In particular, this makes it easier to use connections with initially unspecified foreign sockets 🧚.
TCP's are free to associate ports with processes however they choose. However, several basic concepts seem necessary in an implementation. There must be well known sockets [WKS] which the TCP associates only with the "appropriate" processes by some means. We envision that processes may "own" sockets, and that processes can only initiate connections on the sockets they own. [Means for implementing ownership is a local issue, but we envision a Request Port user call, or a method of uniquely allocating a group of ports to a given process, e.g. by associating the high order bits of a port name with a given process.] 🔐
Once initiated, a connection may be passed to another process that does not own the local socket [e.g. from logger to service process]. Strictly speaking, this is a reconnection issue, which might be more elegantly handled by a general reconnection protocol as discussed in section 3.3. To simplify passing a connection within a single TCP, such "invisible" switches may be allowed, as in TENEX systems 🎀.
Of course, each connection is associated with exactly one process, and any attempt to reference that connection by another process will be signaled as an error by the TCP. This prevents stealing data from or inserting data into another process' data stream 🛡️.
A connection is initiated by the rendezvous of an arriving internetwork packet and a waiting Transmission Control Block [TCB], which is created by a user OPEN, SEND, INTERPUPT, or RECEIVE call [see section 2.3]. The matching of local and foreign socket identifiers determines when a successful connection has been initiated. The connection becomes established when sequence numbers have been synchronized in both directions, as described in section 4.3.2 🤝.
It is possible to specify a socket only partially, by setting the PORT identifier to zero or by setting both the TCP and PORT identifiers to zero. A socket of all zero is called UNSPECIFIED. The purpose behind unspecified sockets is to provide a sort of "general delivery" facility [useful for logger type processes with well known sockets] 📬.
There are bounds on the degree of unspecificity of socket identifiers. TCB's must have fully specified local sockets, although the foreign socket may be fully or partly unspecified. Arriving packets must have fully specified sockets 🔍.
We employ the following notation:
x.y.z = fully specified socket with x=net, y=TCP, z=port
x.y.u = as above, but unspecified port
x.u.u = as above, but unspecified TCP and port
u.u.u = completely unspecified
with respect to implementation, u = 0 [zero]We illustrate the principles of matching by giving all cases of incoming packets which match with existing TCB's. Generally, both the local (foreign) socket of the TCB and the foreign (local) socket of the packet must match 🧩.
TCB local TCB foreign Packet local Packet foreign
(a) a.b.c e.f.g e.f.g a.b.c
(b) a.b.c e.f.u e.f.g a.b.c
(c) a.b.c e.u.u e.f.g a.b.c
(d) a.b.c u.u.u e.f.g a.b.cThere are no other legal combinations of socket identifiers which match. Case (d) is typical of the ARPANET well known socket idea, in which the well known socket (a.b.c) LISTENS for a connection from any (u.u.u) socket. Cases (b) and (c) can be used to restrict matching to a particular TCP or net 🌸.
2.3. TCP USER CALLS 📞
Part 1 ends here, bestie, so the user calls are coming up next in part 2 🧚💖
2.3.1 A Note on Style ✨
okay so this part sets the vibe for the whole USER/TCP interface 💅. The sections below functionally define it. The notation looks a lot like procedure or function calls in high level languages, but that isn't meant to rule out trap type service calls [e.g. SVC's, UUO's, EMT's,...] 🙈
The user calls described below list the basic functions the TCP will perform to support interprocess communication. Each implementation can define its own exact format, and it can bundle or trim the basic functions in single calls. Some implementations may want to automatically OPEN a connection on the first SEND, RECEIVE, or INTERRUPT the user issues for a given connection 🦋
The TCP has to do more than just accept commands. It also has to send information back to the processes it serves 💌 That communication has two parts:
- (a) general information about a connection [interrupts, remote close, binding of unspecified foreign socket].
- (b) replies to specific user commands indicating success or various types of failure.
How the signals reach user processes and the exact format of the replies will differ from one implementation to another. Still, it would promote common understanding and testing if everyone agreed on a common set of codes 🤝 Such a set of Event Codes is described in section 2.4 ✨
One more thing about error messages: "local" and "foreign" are ambiguous unless you know whether they're talking about the world as seen by the sender or by the receiver of the message 🧐 The authors tried a few approaches and finally landed on the convention that these references are as seen by the receiver of the message 🎀
2.3.2 OPEN CONNECTION 🌸
Format:
OPEN(local port, foreign socket [, timeout])We assume the local TCP knows the identity of the processes it serves, and that it checks whether a process is allowed to use the connection it asks for 🔐 Depending on the TCP implementation, the source network and TCP identifiers will either be supplied by the TCP itself or by the processes that serve it [e.g. the program which interfaces the TCP to its packet switch or the packet switch itself]. This is all about security, to the extent that no TCP can masquerade as another one, and so on. In the same way, no process can masquerade as another without the collusion of the TCP 🚫
If no foreign socket is specified [i.e. the foreign socket parameter is 0 or not present], then this makes a LISTENING local socket that can accept communication from any foreign socket 👂 Partial specification of foreign sockets is also possible, as described in section 2.2 🧩
If the specified connection is already OPEN, an error is returned. Otherwise, a full-duplex transmission control block [TCB] is created and partially filled in with data from the OPEN command parameters 💖 The TCB format is described in more detail in section 4.2.2 📖
No network traffic is generated by the OPEN command ✨ The first SEND or INTERRUPT, from either the local user or the foreign user, will cause the TCP to synchronize the connection 🔁
The timeout, if present, lets the caller set up a timeout for all letters transmitted on the connection. If a letter isn't successfully transmitted within the timeout period, the user is notified and can either ignore the condition [TCP will continue trying to transmit] or direct the TCP to close the connection 😬 The present global default is 30 seconds. Connections set up without specifying another timeout will retransmit every letter for at least 30 seconds before notifying the user ⏳ The retransmission rate may vary, and it's the responsibility of the TCP, not the user. Most likely it will be related to the measured time for responses to return from letters sent 📈
Depending on the TCP implementation, either the TCP returns a local connection name to the user, or the user specifies this local connection name themselves (in which case another parameter is needed in the call) 🏷️ The local connection name can then be used as a shorthand for the connection defined by the <local socket, foreign socket> pair 💜
Responses from the TCP which may occur as a result of this call are detailed in section 2.4 🌈
2.3.3 SEND LETTER 💌
Format:
SEND(local connection name, buffer address, byte count, EOL
flag [, timeout])This call causes the data in the indicated user buffer to be sent on the indicated connection 📬 If the connection hasn't been opened, the SEND is considered an error. Some implementations may let users SEND first, in which case an automatic OPEN would be done. If the calling process isn't authorized to use this connection, an error is returned 🚨
If the EOL flag is set, the data is the End Of a Letter, and the EOL bit will be set in the last packet created from the buffer 🔚 If the EOL f1ag is not set, subsequent SEND's will appear as part of the same letter. This extended letter facility should be used sparingly, because some TCP's may delay processing packets until an entire letter is received 🐢
If no foreign socket was specified in the OPEN, but the connection is established [e.g. because a listening connection has become specific due to a foreign letter arriving for the local port], then the designated letter is sent to the implied foreign socket 🎯 In general, users who OPEN with an unspecified foreign socket can use SEND without ever explicitly knowing the foreign socket address 🙌
However, if a SEND is attempted before the foreign socket becomes specified, an error will be returned. Users can use the STATUS call to find out the status of the connection 🔍 In some implementations, the TCP may notify the user when an unspecified socket is bound 🔔
If the timeout is specified, the current default timeout for this connection changes to the new one. This can affect not only all letters sent including and after this one, but also those which haven't been sent yet, since the timeout is kept in the TCB and not associated with each letter sent 🧠 Of course, a time is maintained for each internetwork packet formed, so the TCP can determine how long each one has been on the retransmission queue ⏱️
In the simplest implementation, SEND would not return control to the sending process until either the transmission was complete or the timeout had been exceeded. This simple method is highly subject to deadlocks and is not recommended 🚧 [For example, both sides of the connection try to do SEND's before doing any RECEIVE's.] A more sophisticated implementation would return immediately, letting the process run concurrently with network I/O, and also allowing multiple SENDs to be in progress at the same time 🏃♀️ Multiple SENDs are served in first come, first served order, so the TCP will queue the ones it can't service immediately 📋
NOTA BENE: In order for the process to tell apart error or success indications for different letters, the buffer address should be returned along with the coded response to the SEND request. We will offer an example event code format in section 2.4, showing the information which should be returned to the calling process 🚩
The semantics of the INTERRUPT call are described later, but this call can affect letters that have been given to the TCP but not yet sent 🛑 In particular, all such letters are flushed by the source TCP. So one of the responses to a SEND may be "flushed due to interrupt." 😭
Responses from the TCP which may occur as a result of this call are detailed in section 2.4 🌟
2.3.4 RECEIVE LETTER 📥
Format:
RECEIVE(local connection name, buffer address, byte count)This command allocates a receiving buffer associated with the specified connection. If no OPEN precedes this command, or the calling process isn't authorized to use this connection, an error is returned 🙅♀️
In the simplest implementation, control wouldn't return to the calling program until either a letter was received or some error occurred. But this scheme is highly subject to deadlocks [see section 2.3.3] 🥲 A more sophisticated implementation would let several RECEIVE's be outstanding at once. These would be filled as letters arrive 📨 This strategy permits increased throughput, at the cost of a more elaborate scheme [possibly asynchronous] to notify the calling program that a letter has been received 🚀
If there isn't enough buffer space to reassemble a complete letter, an indication that the buffer holds a partial letter will be given, and the buffer will be filled with as much data as it can hold 🧺
The remaining parts of a partly delivered letter will be placed in buffers as they become available via successive RECEIVES 🧩 If a number of RECEIVES are outstanding, they may be filled with parts of a single long letter, or with at most one letter each. The event codes associated with each RECEIVE will indicate what's in the buffer 🏷️
To tell apart several outstanding RECEIVES, and to handle the case where a letter is smaller than the buffer supplied, the event code comes with both a buffer pointer and a byte count showing the actual length of the letter received 📏
The semantics of the INTERRUPT system call are discussed later, but this call can affect outstanding RECEIVES too 💥 When the TCP receives an INTERRUPT, it flushes all data currently queued up waiting to be received by the receiving process. If no data is waiting, but several buffers have been made available by anticipatory RECEIVE commands, those buffers are returned to the process with an error indicating that any data that might have been placed in them has been flushed 🫧 This lets the receiving process synchronize its RECEIVES with the interrupt. That is, the process can tell apart RECEIVES issued before the INTERRUPT was received from those issued afterwards 🎀
Responses from the TCP which may occur as a result of this call are detailed in section 2.4 💫
2.3.5 CLOSE CONNECTION 👋
Format:
CLOSE(local connection name)This command closes the specified connection. If the connection isn't open, or the calling process isn't authorized to use this connection, an error is returned 🚪 Any unfilled receive buffers or pending send buffers are returned to the user with event codes indicating they were aborted due to the CLOSE. Users should wait for event codes for each SEND before closing the connection if they want to be certain that all letters were successfully delivered 📝
The user may CLOSE the connection at any time on their own initiative, or in response to various prompts from the TCP [remote close executed, transmission timeout exceeded, destination inaccessible] 🫶
Because closing a connection requires communication with the foreign TCP, connections may remain in the closing state for a short time. Attempts to reopen the connection before the TCP replies to the CLOSE command will result in errors 😤
Responses from the TCP which may occur as a result of this call are detailed in section 2.4 🌸
2.3.6. Interrupt 🚨
Format: INTERRUPT(local connection name)
Okay so INTERRUPT is basically the "wait, STOP" signal 🛑. A special control signal gets sent to the destination to say there's an interrupt condition. It can be used to simulate a "break" signal from terminals, or error or completion codes from I/O devices, for example 💅. What the receiving process does with the signal is unspecified, so that part is up to the process 🤷♀️.
The receiving TCP signals the interrupt to the receiving process right away when it arrives, and it also flushes any outstanding letters waiting to be delivered 🧹. It's possible to tell where in the letter stream this command was invoked, so the receiving TCP can flush only the data that came before it. That's a very precise move, iykyk 🧠. The sending TCP flushes any letters that are still pending transmission and returns a special error code to show that the flush happened 💀.
If the connection is not open, or the calling process isn't authorized to use this connection, an error gets returned 🙅♀️.
Responses from the TCP that might come back from this call are detailed in section 2.4.
2.3.7. Status 📊
Format: STATUS(local connection name)
This command returns a data block with the following info, and it's giving full connection report card 📋:
- local socket
- foreign socket
- local connection name
- receive window
- send window
- connection state
- number of letters awaiting acknowledgment
- number of letters pending receipt [including partial ones]
- default transmission timeout
Depending on the state of the connection, some of this info might not be available or meaningful 🫠. If the calling process isn't authorized to use this connection, an error gets returned. This is the main character protection part 💜: it stops unauthorized processes from snooping on a connection.
Responses from the TCP that might come back from this call are detailed in section 2.4.
2.4. TCP to User Messages 💌
2.4.1. Type Codes
Every message includes a type code that tells you which user call it applies to. The types are:
0- General message, does not apply to a particular user call1- Applies to OPEN2- Applies to CLOSE3- Applies to INTERRUPT10- Applies to SEND20- Applies to RECEIVE30- Applies to STATUS
2.4.2. Message Format [notional] 🧾
Every message includes these three fields:
- Type code
- Local connection name
- Event code
For message types 0-3 [General, Open, Close, Interrupt], these three fields are the only ones needed ✨.
For message type 10 [Send], one more field is needed:
- Buffer address
For message type 20 [Receive], three more fields are needed:
- Buffer address
- Byte count
- End-of-letter flag
For message type 30 [status], the additional data might include:
- Local socket, foreign socket
- Send window [measures buffer space at foreign TCP]
- Receive window [measures buffer space at local TCP]
- Connection state [see section 4.3.6]
- Number of letters awaiting acknowledgment
- Number of letters awaiting receipt
- Retransmission timeout
2.4.3. Event Codes 🎯
The event code tells the user which particular event the TCP wants to communicate.
Besides the event code, three flags can help sort the event into major categories and make event processing easier for the user 🫶:
- E flag: set if the event is an error
- L/F flag: indicates whether the event was generated by Local TCP, or Foreign TCP or the network
- P/T flag: indicates whether the event is Permanent or Temporary [retry may succeed]
Events are encoded into 8 bits, with the high order bits set to show the state of the E, L/F, and P/T flags, in that order 🔢.
These are the events specified so far, with their codes and flag settings. A * means a flag doesn't apply, or can take both values for that event. More events may be defined as people experiment 🧪.
0 0** general success
1 ELP connection illegal for this process
2 OF* unspecified foreign socket has become bound
3 ELP connection not open
4 ELT no room for TCB
5 ELT foreign socket unspecified
6 ELP connection already open
EFP unacceptable SYN [or SYN/ACK] arrived at foreign
TCP. Note: This is not a misprint, the local meaning is different
from foreign.
7 EFP connection does not exist at foreign TCP
8 EFT foreign TCP inaccessible [may have subcases]
9 ELT retransmission timeout
10 E*P buffer flushed due to interrupt
11 OF* interrupt to user
12 **P connection closing
13 E** general error
14 E*P connection resetHere are the events that can show up for each message type:
Type 0[general]: 2,11,12,14
Type 1[open]: 0,1,4,6,13
Type 2[close]: 0,1,3,13
Type 3[interrupt]: 0,1,3,5,7,8,9,12,13
Type 10[send]: 0,1,3,5,7,8,9,10,11,12,13
Type 20[receive]: 0,1,3,10,12,13
Type 30[status]: 0,1,13Note that events 6 (foreign), 7, and 8 are generated at the foreign TCP or in the network[s]. These same codes are also used in the error field of the internet packet [see section 4.2.1] 🌐.
3. Higher Level Protocols 🎀
3.1. Introduction
It's envisioned that the TCP will be able to support higher level protocols efficiently 🚀. It should be easy to interface existing ARPANET protocols like TELNET and FTP to the TCP, bestie 🙌.
3.2. Well Known Sockets 🔑
At some point, a set of well known 24 bit port numbers must be picked. The type of service linked to the well known ports might include:
- (a) Logger
- (b) FTP (File transfer protocol)
- (c) RJE (Remote job entry)
- (d) Host status
- (e) TTY Test
- (f) HELP - descriptive, interactive system documentation
WE RESERVE WELL KNOWN SOCKET 0 (24 bits of 0) for global messages aimed at a particular TCP but not related to any particular connection 🫧. We imagine this socket would be used for unusual TCP synchronization (e.g. RESET ALL) or for testing (e.g. sending letters to TRASHCAN or ECHO). This doesn't conflict with the rule that if a socket is 0, it's unspecified, since no user can SEND, CLOSE, or INTERRUPT on socket 0 🙅♀️.
3.3. Reconnection Protocol (RCP) 🦋
Port identifiers fall into two categories: permanent and transient 🧩. For example, a Logger process is usually given a port identifier that's fixed and well known. Transient processes will generally have IDs that get assigned dynamically.
In the distributed processing environment of the network, two processes that don't have well known port identifiers may still want to talk to each other 💬. This can be done with the help of a well known process using a reconnection protocol. This doc briefly outlines one, using the communication facilities the TCP provides. Basically, it's a way to swap port identifiers so a connection can be set up between a pair of sockets 🤝.
This kind of protocol can dynamically set up new connections so multiple processes can work on a problem together. It can also give a user process access to a server process through a logger, when the logger's end of the connection can't be invisibly passed to the server process 🎟️.
R. Schantz [SCHA74] wrote a paper on this subject that covers some of the issues with reconnection, and some of its ideas went into the protocol outlined below 📚.
On the ARPANET, a protocol was implemented that let a process connect to a well known socket (an implicit request for service), then get switched to another socket so the well known socket could be freed up for others. Since sockets in our TCP can have connections with more than one foreign socket, this might not be explicitly needed (i.e. connections <A,B> and <A,C> are distinguishable) 👯.
However, the well known socket may be on one network while the actual service socket(s) are on another network (or at least in another TCP). So invisibly switching a connection from one port to another within a TCP may not be enough to act as an "Initial Connection Protocol" 😬. Here's the vibe: a process wants to use socket N1.T1.Q to access well known socket N2.T2.P. But the process behind N2.T2.P will actually start a new process somewhere, which will use N3.T3.S as its server socket. The N(i) and T(i) may be distinct or the same. The user sends the relevant user info, like user name, password, and account, to N2.T2.P. The server starts the server process and sends the actual service socket identifier, N3.T3.S, to N1.T1.Q. Then the connection (N1.TI.Q,N2.T2.P) can be closed, and the user can do a RECEIVE on (N1.T1.Q,N3.T3.S). The serving process can SEND on (N3.T3.S,N1.T1.Q). There are lots of variations on this, with some involving the user process doing a RECEIVE on a different socket (e.g. (N1.T1.X,U.U.U)) while the server does a SEND on (N3.T3.S,N1.T1.X). Without going through all the sequence number synchronization and such, the exchange looks like this:
USER SERVER
1. RECEIVE(N2.T2.P,U.U.U)
1. SEND (N1.T1.Q,N2.T2.P)==>
<== 2. SEND(N2.T2.P,N1.T1.Q)
With "N3.T3.S" as data
2. RECEIVE(N1.T1.Q,N2.T2.P)
3. CLOSE(N1.T1.Q,N2.T2.P)==>
<:= 3. CLOSE(N2.T2.P,N1.T1.Q)
4. RECEIVE(N1.T1.Q,N3.T3.S)
<== 4. SEND(N3.T3.S,N1.T1.Q)At this point, a connection is open between N1.T1.Q and N3.T3.S 🎉. One variation: the user does an extra RECEIVE on (N1.T1.X,U.U.U) and sends the data "N1.T1.X" in the first user SEND. Then the server can start the real serving process and SEND on (N3.T3.S,N1.T1.X) without having to send the "N3.T3.S" data to the user. Or maybe both server and receiver exchange this data, for extra security on the final connection. (Otherwise, some wild process might try to connect to N1.T1.X just by RECEIVING on foreign socket U.U.U 👀.)
We don't propose any specific reconnection protocol here. We're leaving that to further deliberation, since it's really a user level protocol issue 🫶.
4. TCP Implementation 🔥
4.1. Introduction
Conceptually, the TCP is made up of several processes. Some of them handle USER/TCP commands, and others handle packets arriving from the network. The TCP also has an internal measurement facility that can be activated remotely 📏.
There are a few ways you could look at any particular TCP. It could be implemented as an independent process that serves lots of user processes 🧚. It could be seen as a set of re-entrant library routines that share a common interface to the local PSN, and common buffer storage 📦. It could even be seen as a set of processes, where some handle the user, some handle input of packets from the net, and some handle output of packets to the net 🌸.
4.2. TCP Data Structures
4.2.1 INTERNETWORK PACKET FONMAT ✨
okay so this is the packet layout, and it's giving "every bit has a job" 🎀 Here's the whole header, top to bottom:
8 bits: Internet information
2 bits: Reserved for local PSN use
2 bits: Header format (11 in binary)
4 bits: Protocol version number
8 bits: Header length in octets (32 is the current value)
16 bits: Length of text in octets
32 bits: Packet sequence number
32 bits: Acknowledgment number (i.e. sequence number of next octet
expected).
16 bits: Window size (in octets)
16 bits: Control InformationThe control information is 16 bits, listed from high to low order. Each flag is its own little main character 💅
SYN: Request to synchronize sending sequence numbers 🤝ACK: There is a valid acknowledgment in the 32 bit ACK field 🫶FIN: Sender will stop SENDing and RECEIVEing on this connection 👋DSN: The sender has stopped using sequence numbers and wants to initiate a new sequence number for sending. 🔄EOS: This packet is the end of a segment and therefore has a checksum in the 16 bit checksum field. If this bit is not set, the 16 bit checksum field is to be ignored. The bit is usually set, but if fragmentation at a GATEWAY occurs, the packets preceding the last one will not have checksums, and the last packet will have the checksum for the entire original fragment (segment) as it was calculated by the sending TCP. 🧩EOL: This packet contains the last fragment of a letter. The EOS bit will always be set in this case. 💌INT: The sender wants to INTERRUPT on this connection. ✋XXX: six (6) unused control bits 🌙
Then there's OD, which is three (3) bits of control dispatch. It decides what the control octet is actually doing:
000: Null (the control octet contents should be ignored}
001: Event Code is present in the control octet. These were
defined in section 2.4.3.
010: Special Functions
011: Reject (codes as yet undefined)
1XX: UnusedNext up is the 8 bit Control Data Octet. Its meaning depends on what OD says 👀
If CD is 000, this octet is to be ignored.
If CD is 001, this octet contains event codes defined in section 2.4.3.
If CD is 010, this octet contains a special function code, and these are the ones:
0: RESET all connections between Source and Destination TCPs
l: RESET the specific connection referenced in this packet
2: ECHO return packet to sender with the special function code
ECHOR (Echo Reply).
3: QUERY Query status of connection referenced in this packet
4: STATUS Reply to QUERY with requested status.
5: ECHOR Echo Reply
6: TRASH Discard packet without acknowledgment
>6: UnusedSpecial function packets that aren't about one particular connection (that'sRESET all,ECHO,ECHOR, andTRASH) are normally sent using socket zero, as described in section 3.2. Socket zero is where they live, bestie 🏠
If CD is 011, this octet contains an as yet undefined REJECT code. 🚧
If CD is 1XX, this octet is undefined. 🌫️
Now the addressing part, which is giving detailed and kind of iconic 🗺️ The destination network address length is 4 bits, counted in 4 bit units, and the current value is 1. The destination network address itself is also 4 bits:
1010-1111 are addresses of ARPANET, UCL, CYCLADES, NPL, CADC, and
EPSS respectively.Then we have the destination TCP address (16 bits), 8 bits of padding (just vibes, no info 🫧), and then the source side, which mirrors it: source network address length in 4 bit units (current value is 1), the source network address (as for destination address), and the 16 bit source TCP address. After that come the port addresses, and it's ending with the checksum 🏁
24 bits: Destination port address
24 bits: Source port address
16 bits: Checksum (if EOS bit is set)4.2.2 TRANSMISSION CONTROL BLOCK 🗂️
okay so this part is lowkey the most organised thing ever. It's highly likely that any implementation will share data structures between the TCP parts and use some asynchronous way of telling users when letters have been delivered 📬
One typical data structure is the Transmission Control Block (TCB). It gets created and maintained for the whole lifetime of a given connection. The TCB holds the following info (the field sizes are notional only and may vary from one implementation to another, so don't take them as gospel 🙅♀️):
16 bits: Local connection name
48 bits: Local socket
48 bits: Foreign socket
16 bits: Receive window size in octets
32 bits: Receive left window edge (next sequence number expected)
16 bits: Receive packet buffer size of TCB (may be less than
window)
16 bits: Send window size in octets
32 bits: Send left window edge (earliest unacknowledged octet)
32 bits: Next packet sequence number
16 bits: Send packet buffer size of TCB (may be less than window)
8 bits: Connection state
E/C - 1 if TCP has been synchronized at least once (i.e. has
been established, else O, meaning it is closed; this bit is
reset after FINS are exchanged and the user has done a CLOSE).
The bit is not reset if the connection is only desynchronized
on send or receive or both directions.
SS - SYNCed on send side (if set) else desynchronized
SR - SYNCed on receive side (if set, else desynchronized)The special flags are 16 bits and they're the secret sauce for tracking connection state 🍯
S1: SYN sent if set 📤S2: SYN verified if set ✅R: SYN received if set 📥Y: FIN sent if set 🏁C: CLOSE from local user received if set 🔒U: Foreign socket unspecified if set 🕳️SDS: Send side DSN sent if set 📨SDV: Send side DSN verified if set 🧾RDR: Receive side DSN received if set 📩
Initially, all bits are off [no pun intended] (i.e. SS, SR, E/C, S1, S2, R, F, C, SDS, SDV, RDR = 0). When R is set, so is SR. When S1 and S2 are both set, so is SS. SR is reset when RDR is set. SS is reset when both SDS and SDV are set. These bits are used to keep track of connection state and to help process arriving packets (e.g. can the sequence number be validated? Only if SR is set.) 🧠
Then the rest of the TCB is basically a giant list of pointers and timers, and it's giving busy but organised 🧚
16 bits: Retransmission timeout (in eighths of a second#]
16 bits: Head of Send buffer queue [buffers SENT from user to TCP,
but not packetized]
16 bits: Tail of Send buffer queue
16 bits: Pointer to last octet packetized in partially packetized
buffer (refers to the buffer at the head of the queue)
16 bits: Head of Send packet queue
16 bits: Tail of Send packet queue
16 bits: Head of Packetized buffer Queue
16 bits: Tail of Packetized buffer queue
16 bits: Head of Retransmit packet queue
16 bits: Tail of Retransmit packet queue
16 bits: Head of Receive buffer queue [queue of buffers given by user
to RECEIVE letters, but unfilled]
16 bits: Tail of Receive buffer queue
16 bits: Head of Receive packet queue
16 bits: Tail of receive packet queue
16 bits: Pointer to last contiguous receive packet
16 bits: Pointer to last octet filled in partly filled buffer
16 bits: Pointer to next octet to read from partly emptied packet
[Note: The above two pointers refer to the head of the receive
buffer and receive packet queues respectively]
16 bits: Forward TCB pointer
16 bits: Backward TCB pointer4.3 CONNECTION MANAGEMENT 🤝
4.3.1 INITIAL SEQUENCE NUMBER SELECTION 🎲
Okay, so the protocol doesn't stop anyone from reusing the same connection over and over again 🔁 Each new instance of a connection is called an incarnation of that connection. Now here's the drama: how does TCP tell duplicate packets from older incarnations apart? 😬 This gets really harmfully apparent if a connection is opened and closed in quick succession, or if it breaks with loss of memory and then gets reestablished.
The fix [TOML74] is that the initial sequence number [ISN] has to be picked so that a particular sequence number can never refer to an "old" octet. Once the connection is up, the sequencing mechanism TCP already has filters out duplicates, so we're good ✨
Before an association can be established or initialized, the two TCPs have to synchronize on each other's initial sequence numbers. So the solution needs a suitable way to pick an ISN, plus a slightly involved handshake to swap them. A "three way handshake" is necessary because sequence numbers aren't tied to a global clock in the network, and each TCP might pick its ISNs in a different way 🌍 The receiver of the first SYN has no way of knowing whether that packet was an old delayed one, unless it remembers the last sequence number used on the connection (and that's not always possible), so it has to ask the sender to verify the SYN 🙃
The "three way handshake" and the perks of a "clock-driven" scheme are discussed in [TOML74]. More on the subject, plus algorithms for building the clock-driven scheme, can be found in [DALA74] 📚🩷
4.3.2 ESTABLISHING A CONNECTION ✨
Okay so, the "three way handshake" is basically a one-way attempt to set up the connection 🎀 There's an initiator and a responder. BUT the TCPs still have to be able to connect even if both of them try at the same time 😭 Simultaneous attempts get treated like "collisions" in "Aloha" systems, and those conflicts get sorted out into one-way attempts. This scheme was picked because:
- (i) Connections will normally have a passive and an active end, so the mechanism should in most cases be as simple as possible 🧚
- (ii) It is easy to implement, because special cases don't have to be accounted for 💅
Here's what a three way handshake between TCPs A and B looks like 🦋
A B
--> <SEQ x><SYN> -->
<-- <SEQ y><SYN, ACK x+l> <--
--> <SEQ x+1><ACK y+l><DATA BYTES> -->Here's how it works, bestie. The receiver of a "SYN" can tell whether that "SYN" was real (and not some old duplicate) once a positive "ACK" comes back for its "SYN,ACK" sent in reply to the "SYN" 🌸 The sender of a "SYN" gets its verification when it receives a "SYN,ACK" whose "ACK" part references the sequence number it proposed in the original "SYN" [pun intended] 😭🫶
Now the messy bit. If a TCP is waiting for a response to its SYN but a SYN shows up instead, it always assumes that's a collision, and it goes back to the state it was in before it sent the SYN. Basically it forgets it ever sent one 🙈 It'll try to connect again after some time, unless it has to respond to an arriving SYN first. Even if the two TCPs have the same wait times, the random-ish delays in network transmission will usually be enough to avoid a collision on the next round of SYN attempts ✨
When a connection is being established, the state of the TCP is stored in 3 bits 🌈
S1 S2 RS1 = 1-- SYN sentS2 = 1-- My SYN verifiedR = 1-- SYN received
Next up are some examples of connection attempts. The state of the connection gets shown whenever a change happens 👑 We're specifically not showing the cases where connection sync happens with packets carrying both a SYN and data. We're doing that to keep the explanation simple, but we aren't ruling out an implementation that can handle data arriving in the first packet 💜 (That data has to be stored temporarily, without being acknowledged or delivered to the user, until the arriving SYN has been verified.)
The "three way handshake" now looks like this 🎀
A B
------------ ------------
S1 S2 R S1 S2 R
0 0 0 0 0 0
--> <SEQ x><SYN> -->
1 0 0 0 0 1
<-- <SEQ y><SYN, ACK x+l> <--
1 1 1 1 0 1
--> <SEQ x+1><ACK y+1>(DATA OCTETS) -->
1 1 1 1 1 1Here's the scenario for a simultaneous attempt to establish the connection, with no delayed duplicates showing up 🌊
A B
------------ ------------
S1 S2 R S1 S2 R
0 0 0 0 0 0
(M1) 1 0 0 --> <SEQ x><SYN> ...
(M2) 0 0 0 <-- <SEQ y><SYN) <-- 1 0 0
(M1) B returns no SYN sent --> 0 0 0
(M1) 1 0 0 --> <SEQ z><SYN> * --> 0 0 1
(M3) 1 1 1 <-- <SEQ y+1><SYN,ACK z+1> <-- 1 0 1
(M4) 1 1 1 --> <SEQ z+1><ACK y+1><DATA> --> 1 1 1Quick notes, because these matter 🫶 ... means a message doesn't arrive yet but is delayed somewhere in the network. State changes happen when a message arrives or when it leaves, depending on the case 💅 Packets carrying the SYN, INT, or DSN bits implicitly contain a "dummy" data octet. It's never handed to the user, but it still bumps the packet sequence numbers by 1, even when no real data is sent. This lets those control bits get acknowledged without also acknowledging any data that might be riding in the same packet 🧚 A packet with a FIN bit has a dummy octet right after its last octet of data (if there is any).
* Once in state 000, the sender picks a new ISN z when it tries to establish the connection again 🌸
4.3.3 HALF-OPEN CONNECTIONS ✨
Okay, so a connection counts as a "half-open" connection if one of the TCPs has closed its end without the other one knowing, or if the two ends have gone out of sync because of a crash that wiped out memory 🙈 These connections will automatically get reset if someone tries to send data in either direction. BUT half-open connections are expected to be pretty unusual, and the recovery procedure is kinda involved 😭
If one end of the connection doesn't exist anymore, any attempt by the other user to send data on it gets the sender the event code "Connection does not exist at foreign TCP". That error should tell the user process something's wrong, and the process is expected to CLOSE the connection 💀
Let's say user processes A and B are talking when a crash wipes out B's TCP memory 🍓 Depending on the operating system running B's TCP, there's a decent chance some error recovery mechanism exists. When the TCP comes back up, B will probably start over from the beginning or from some recovery point. So B will likely try to OPEN the connection again, or try to SEND on the connection it still thinks is open. In the second case, it gets the error message "connection not open" from its local TCP 😱 To try to establish the connection, B's TCP sends a packet containing SYN. A's TCP thinks the connection is already established, so it responds with the error "unacceptable SYN (or SYN/ACK) arrived at foreign TCP". B's TCP knows that error refers to the SYN it just sent out, so it should reset the connection and tell the user process about it ✨
Another possibility is that B is passive and only wants to receive data 🦋 In that case, A's data never reaches B, because B's TCP thinks the connection isn't established. So A's TCP times out and sends a QRY to B's TCP. B's TCP replies with STATUS saying the connection is not synched. A's TCP treats this as if an implicit CLOSE had happened, and it tells A's user process that the connection is closing. A is expected to respond with a CLOSE command to its own TCP 💅 A's TCP does not send a FIN to B's TCP, since that wouldn't get accepted on an unsynced connection anyway. Eventually A will try to reopen the connection, or B will give up and CLOSE. If B CLOSEs, B's TCP just deletes the connection, since as far as B's TCP is concerned it was never established. No message gets sent to A's TCP as a result 🌈
4.3.4 RESYNCHRONIZING A CONNECTION 🎀
The details of resynchronization haven't been specified yet, since this should be pretty rare during the initial testing stages 🧚
4.3.5 CLOSING A CONNECTION 🎀
okay so there are basically three ways a connection can end, and it's giving very "who closed first?" energy 💅
- a) The user initiates by telling the TCP to CLOSE the connection
- b) The remote TCP initiates by sending a FIN control signal
- c) Both users CLOSE simultaneously
Two bits keep track of the closing process: the "FIN sent" bit [F] and the "USER Closed" bit [C]. The control procedure uses these two bits to make sure the connection is properly closed 🔐✨
Case 1: Local user initiates the close 🌸
So both the F and C bits start at zero, but the C bit gets set the second the user calls "CLOSE." When the TCP sends out the FIN, the F bit gets set 🧚 All pending RECEIVES get terminated, and the user is told they were prematurely terminated ("connection closing") without data. Any pending SENDS get the same treatment with the same response, "connection closing." Rude but accurate 💀
Sending a FIN can get you several responses. The one you usually want is a matching FIN. When that comes in, the TCB CAN BE ELIMINATED 🗑️✨ If you get a "connection does not exist at foreign TCP" message back in response to the FIN, the TCB can also be eliminated. If nothing shows up, or "Foreign TCP inaccessible" arrives, the resolution is moot. You could just timeout and discard the TCB. Since the local user wanted to CLOSE anyway, this is probably fine, although it can leave a potential "half-open" connection on the other side. We deal with half-open connections in section 4.3.3 🫶
When the acknowledging FIN arrives after the connection state bits are set (F=1, C=1), the TCB can be deleted 💖
Case 2: TCP receives a FIN from the network 🦋
First things first, a FIN has to have a sequence number that lies in the valid receive window. If it doesn't, it gets discarded and the left window edge is sent back as the acknowledgment 🙈 If the FIN can be processed, it gets handled (possibly out of order, since it's taken as an imperative to shut the connection down). All pending RECEIVES and SENDS get answered by showing they were terminated by the other side's close request (i.e. "connection closing") 😭 The user is also told by an unsolicited event or signal that the connection has been closed. (In some systems, the user might have to request STATUS to find this out.) Finally, the TCP sends a FIN back in response 🔥
So because a FIN arrived, a FIN gets sent back, and the F bit is set. The TCB hangs around, though, until the local user does a CLOSE to acknowledge the unsolicited signal that the other side closed the connection. That means the C bit stays unset until this happens. If the C and F bits go from (F=1 C=O) to (F=l, C=1), the connection is closed and the TCB can be removed 🌈
Case 3: both users close simultaneously 👯
If this happens, both connections end up in the (F=1, C=1) state. When the FINs arrive, the connections will be shut down ✨ If one FIN fails to arrive, there are two choices. One is to insist on acknowledgments for FINs, in which case the missing one gets retransmitted. The other is to just let the half-open connection stick around (we prefer this one 🥰). It can time out on its own and go away after a while. If someone tries to reestablish the connection, the initiator will discover the open connection, because an "inappropriate SYN received" message will be sent by the TCP holding the "half-open" connection. The receiver of that message can tell the other TCP to reset the connection 🔄
We can't let the holder of the half-open connection reset automatically when it gets the SYN, because getting a SYN isn't necessarily prima facie evidence of a half-open connection. (The SYN could be a delayed duplicate 👻)
4.3.6. CONNECTION STATE and its relation to USER and INCOMING CONTROL REQUESTS 👑
okay this section is where things get organized 🗂️✨ To formalize what the TCP does when it gets commands from the User or Control info from the network, we define a connection to be in one of 7 states at any instant. These are the TCB Major States. Each Major State is just a handy name for a particular setting or group of settings of the state bits, like so 💜
S1 S2 R U F C # name
- - - - - - 0 no TCB
0 0 0 0/1 0 0 1 unsync
1 0 0 0 0 0 2 SYN sent
1 0 1 0/1 0 0 3 SYN received
1 1 1 0 0 0 4 established
1 0/1 1 0/1 1 1 5 FIN wait
1 1 1 0 1 0 6 FIN receivedThe connection moves from state to state as shown below. A transition from one state to another gets written like this:
[X, Y]<cause><action>which means there's a transition from state X to state Y because of <cause>. The action the TCP takes is specified as <action>. We use this notation for the important state transitions, often simplifying the cause and action fields to cover a bunch of situations at once 🍓 Figure 1 shows these transitions in traditional state diagram form. Section 4.4.6 and section 4.4.7 fully specify the effect of all User commands and Control information arriving from the network 🧚
[0,l] <OPEN> <create TCB>
[1,2] <SEND,INTERRUPT, or collision timeout> <send SYN>
[1,3] <SYN arrives> <send SYN,ACK>
[1,0] <CLOSE> <remove TCB>
[2,1] <SYN arrives (collision)> <set timeout, forget SYNs>
[2,0] <CLOSE> <remove TCB>
[2,4] <appropriate SYN,ACK arrives> <send ACK>
[3,4] <appropriate ACK arrives> <none>
[3,1] <error arrives or timeout> <(forget SYN)>
[3,5] <CLOSE> <send FIN>
[4,5] <CLOSE> <send FIN>
[4,6] <appropriate FIN arrives> <send FIN, inform user>
[5,0] <FIN or error arrives, or timeout> <remove TCB>
[6,0] <CLOSE> <remove TCB>4.4 STRUCTURE 0F THE TCP ✨
4.4.l. INTRODUCTION [See figure 2.1] 🌸
Okay bestie, so there are lots of ways to build TCP 💖 This doc gives us one conceptual framework to picture all the algorithms that make up the TCP design. In this picture, TCP is split into two parts: an interrupt or signal driven part (made of four processes), and a reentrant library of subroutines or system calls that connect the user process to TCP. The subroutines talk to the interrupt part through shared data structures (TCB's, shared buffer queues etc.). The four processes are the Output Packet Handler, which sends packets to the packet switch; the Packetizer, which formats letters into internet packets; the Input Packet Handler, which processes incoming packets; and the Reassembler, which builds letters for users. ✨
The real bottleneck is the pipe that arriving and departing packets have to squeeze through, which is the Host/Packet Switch interface 🚧 The interrupt driven TCP shares its limited packet buffers among all the TCB's, for both sending and receiving. For controlling buffer congestion, it looks better to treat incoming packets with higher priority than outgoing packets 👑 Packet buffers that can be freed by copying their contents into user buffers really do help cut down on congestion. Neither the packetizer nor the input packet handler should be allowed to hog all the available packet buffer space. The IMP has the same kind of problem when it allocates store and forward buffers and reassembly buffers. One policy is to let neither contender have more than, say, two-thirds of the space. The buffer allocation routines can enforce these limits and reject buffer requests when needed. Conceptually, the scheduler can keep an eye on how much storage the input and output routines are using, and can force either one to sleep if its buffer allocation goes over the limit. 😤
Let's walk through an example, because it's giving very clear picture energy 🎀 When a user runs a SEND call to the TCP service routines, the buffer with the letter gets placed on a SEND buffer queue tied to that user's TCB. A 'packetizer' process wakes up and looks through all the TCB's for 'packetizing' work. The packetizer keeps a roving pointer through the TCB list, so it can grab new buffers from each TCB queue and packetize them into output buffers. It takes no more than one letter at a time from any single TCB 🙌 It also tries to keep a non-empty queue of output packets, so the output handler never sits around idle waiting on the packetizing operation. Arriving packets compete with departing packets though, so we have to be careful that neither class takes over all of the shared packet buffer space. And since all the TCB's compete for space while serving their connections, neither input nor output packet space should be dominated by any one TCB. Main character energy must be shared 💅
When a packet is created, it goes onto a FIFO SEND packet queue tied to its origin TCB. The packetizer wakes the output handler, then maybe packetizes a few more buffers before going to sleep 😴 The output handler gets woken up either by a 'hungry' packet switch or by the packetizer. Either way, it uses a roving TCB pointer to pick the next TCB to serve. The send packet queue can act as a 'work queue' for the output handler. After a packet has been sent, but usually before its ACK comes back, the output handler moves the packet onto a retransmission queue tied to each TCB 🔁
Retransmission timeouts can point at specific packets, and the retransmission list can be searched for that exact packet 🔍 If an ACK comes in, the retransmission entry can be removed from the retransmit queue. The send packet queue holds only packets that are waiting to be sent for the first time. INTERRUPT requests can remove entries from both the send packet queue and the retransmit packet queue 🫶
Since packets are never in more than one queue at a time, it seems possible for INT, FIN or RESET commands to remove packets from the receive, send, or retransmit packet queues. The assurance is that a signal already issued to enter the reassembler, the packetizer or the output handler won't get confused by that removal. Ngl, that's a pretty clean design 🦋
Handling the INTERRUPT and CLOSE functions can still take some care, though, so the scheduler and the various processes don't get confused 😭 The scheduler has to keep status information for the processes, including the current TCB being serviced. When a local process issues an INTERRUPT, the output queue of letters tied to that local port reference gets deleted. But the packetizer might be working on that same queue at that exact moment! As usual, simultaneous reading and writing of the TCB queue pointers has to be blocked using some kind of semaphore or lockout mechanism 🔒 When the packetizer wants to serve the next send buffer queue, it has to lock out all other access to the queue, remove the head of the queue (assuming there are enough buffers for packetization), advance the head of the queue, and then unlock access to the queue.
Here's a little trick: if the packetizer only keeps a TCB pointer in a global place called CPTCB (current packetizer TCB address), and always uses the address in CPTCB to find the TCB whose send buffer queue it's checking, then removing the output buffer queue doesn't require changes to any working storage belonging to the packetizer. Even better, when a RESET or CLOSE arrives and clears a given TCB out of the system, it can update the CPTCB pointer, as long as the removal doesn't happen while the packetizer is still working on that TCB 🧚
Incoming packets get examined by the input packet handler. Here they're checked for valid connection sockets, and acknowledgments are processed. That can cause packets to be removed from the SEND or RETRANSMIT packet queues as needed 💜 As an example, look at what happens when a valid FIN request arrives on a particular TCB. If a FIN has not been sent before (i.e. F bit not set), then a FIN packet is constructed and sent, after the SEND buffer and SEND packet queues have been cleared out, along with the RETRANSMIT queue. Otherwise, if the F and C bits are both set, all the queues are emptied and the TCB is returned to free storage 🍓
Packets that should be reassembled into letters and sent to users get queued by the input packet handler on the receive packet queue, for the reassembly process to handle 🎀 The reassembler looks at its FIFO work queue and tries to move packets into user buffers. Those user buffers are queued up in an input buffer queue on each TCB. If a packet has arrived out of order, it can be queued up for processing in the correct sequence ✨ Each time a packet is moved into a user buffer, the left window edge of the receiving TCB moves to the right, so outgoing packets can carry the correct ACK information. If the SEND buffer queue is empty, the reassembler creates a packet to carry the ACK 🫶
As packets are moved into buffers and those buffers get filled, the buffers are dequeued from the RECEIVE buffer queue and handed to the user 💅 The reassembler can also be woken up by the RECEIVE user call, if it has a non-empty receive packet queue but an empty RECEIVE buffer queue. The awakened reassembler goes to work on each TCB, using a roving pointer, and goes back to sleep if it cycles through all the TCB's without finding any work 😴
4.4.2. INPUT PACKET HANDLER [See figure 2.2] 🦋
The Input Packet Handler wakes up when a packet arrives from the network. First it checks that the packet is for an existing TCB (i.e. the local and foreign socket numbers match those of existing TCB's) 🔎 If that check fails, an error message is constructed and queued on the send packet queue of a dummy TCB. A signal also goes to the output packet handler. Generally, things to be transmitted from the dummy TCB have a default retransmission timeout of zero, so they won't be retransmitted. (We use the idea of a dummy TCB so that all packets containing errors, or RESET, can be sent by the output packet handler, instead of making the originator of them interface with the net. These packets, as you'll notice, don't belong to any TCB.) 💀
The input packet handler looks out for control or error information and acts on it appropriately. Section 4.4.7 covers this in much greater detail, but as an example: if the incoming packet is a RESET request of any kind (i.e. all connections from a designated TCP, or a given connection), and it's believable, then the input packet handler clears out the related TCB(s), empties the send and receive packet queues, and prepares error returns for outstanding user SEND(s) and RECEIVE(s) on each reset TCB 🚨 The TCB's get marked unused and returned to storage. If the RESET refers to an unknown connection, it gets ignored 🙈
Heads up: a RESET that's believable really does wipe out the TCB and its queues, so the believability check matters a lot here. Section 4.4.7 has the deeper details.
Any ACK's contained in incoming packets are used to update the send left window edge, and to remove the ACK'ed packets from the TCB retransmit packet queue 💖 If the packet being removed was the end of a user buffer, then that buffer has to be dequeued from the packetized buffer queue, and the User gets informed. The packetizer is also signaled. Only one signal (or one per packet) has to be sent, depending on the scheduling scheme for the processes. See section 4.4.7 for a detailed discussion 🔥
The packet sequence number, the current receive window size, and the receive left window edge together determine whether the packet lies within the window or outside of it 🌈 Here's the math:
Let W = window size
S = size of sequence number space
L = left window edge
R = L+W-1 = right window edge
x = sequence number to be tested
For any sequence number, x, if
(R-x) mod S <= W
then x is within the window.A packet should be rejected only if all of it lies outside the window 🙅♀️ This is easily tested by letting x be, first, the packet sequence number, and then the sum of the packet sequence number and the packet text length, less one. If the packet lies outside the window, and there are no packets waiting to be sent, then the input packet handler should construct a dummy ACK and queue it for output on the send packet queue, and signal the output packet handler 📬 Successfully received packets get placed on the receive packet queue in the appropriate sequence order, and the reassembler gets signaled ⭐
Important: the window check can't be made if the associated TCB isn't in the 'established' state. So make sure you check for control and TCB state before doing the window check, bestie 🫶
4.4.3 REASSEMBLER [See figure 2.3] 🧚
okay so the Reassembler process gets activated by BOTH the Input Packet Handler AND the RECEIVE user call 💅 While it's asleep, if a bunch of signals show up, all but one can be tossed. This is important bestie because the reassembler has no idea where a signal came from 🙈 That way, "dangling" signals left over from TCBs that were already removed can't confuse it. Each signal just means "hey, there might be work to do" ✨ If the reassembler is already awake when a signal arrives, it could be necessary to put it in a "hyperawake" state 🔥 That way, even if the reassembler tries to quit, the scheduler will run it one more time. Main character energy for the scheduler 👑
When the reassembler wakes up, it looks at the receive packet queue for each TCB 🎀 If there are some packets sitting there, it checks whether the RECEIVE buffer queue is empty. If it is, the reassembler gives up on this TCB and moves on to the next one 💔 Otherwise, if the first packet matches the left window edge, that packet can be moved into the User's buffer 🦋 The reassembler keeps transferring packets into the User's buffer until the letter is completely transferred, or something makes it stop. Note that a buffer might be partly filled and then a sequence "hole" shows up in the receive packet queue 🙃 The reassembler MUST mark progress so the buffer can be filled up starting at the right place once the "hole" gets filled. Similarly, a packet might only be partially emptied when a buffer fills up, so progress in the packet has to be marked too 🌸
If a letter was successfully transferred into a User buffer, the reassembler signals the User that a letter has arrived and dequeues the buffer associated with it from the TCB RECEIVE buffer queue 💖 If the buffer is filled, the User gets signaled and the buffer gets dequeued just like before. The event code tells you whether the buffer holds all or part of a letter, as described in section 2.4 ✨
In every case where a packet is delivered to a buffer, the receive left window edge gets updated, and the packetizer is signaled 🧚 This updating MUST take account of the extra octet included in the sequencing for certain control functions [SYN, INT, FIN, DSN]. If the send packet queue is empty, the reassembler MUST create a packet to carry the ACK and place it on the send packet queue 🫶
Note that the reassembler never works on a TCB for more than one User buffer's worth of time, so that all TCB's get equal service ⭐
Scheduling the reassembler is a BIG issue 😭 Maybe running to completion will be good enough, or else it can be time sliced. In the latter case it picks up where it left off, but a new signal might have arrived and produced some possible work. That work gets processed as part of the old incomplete signal, so some wasteful processing could happen when the reassembler wakes up again 🥲 This is the general problem of trying to implement a protocol that's fundamentally asynchronous, but at least it's immune to harmful race-conditions. For example, if the reassembler "removed" the signal that woke it up just before going to sleep (so new arriving ones would get discarded), then a new signal could arrive at a critical time and not get recognized 💀 That would leave some work pending, and this could end in a deadlock [see previous comments on "hyperawake" state] 🚨
4.4.4 PACKETIZER [See figure 2.4] 🍓
The Packetizer process gets work from both the Input Packet Handler and the SEND user call 💅 The signal from the SEND user call means there's something new to send, while the one from the input packet handler means more TCP buffers might be available thanks to delivered packets 🦋 That second signal exists to prevent deadlocks in certain kinds of scheduling schemes. We assume the same treatment of signals as discussed in section 4.4.3 ✨
When the packetizer wakes up, it looks at the SEND buffer queue for each TCB 🎀 If there's a new or partial letter waiting to be packetized, it tries to packetize the letter, as long as the TCB buffer and window allow it 🌈 It packetizes no more than one letter for a TCB before servicing another TCB. For every packet it produces, it signals the output packet handler (to prevent deadlock in a time sliced scheduling scheme) 🔥 If a "run till completion" scheme is used, only one signal needs to be produced, the first time a packet is produced since waking up. If packetization isn't possible, the packetizer moves on to the next TCB 💫
If a partial buffer was transferred, the packetizer MUST mark progress in the SEND buffer queue 🫶 Completely packetized buffers get dequeued from the SEND buffer queue and placed on a Packetized buffer queue, so the buffer can be returned to the user when an ACK for the last bit comes in 💜
When the packetizer packetizes a letter, it MUST check whether it's the first piece of data being sent on the connection. If it is, it MUST include the SYN bit 🔑 Some implementations might not permit data to be sent with SYN, and others might discard any data received with SYN 👀
The Packetizer goes to sleep if it finds no more work at any TCB 😴
4.4.5 OUTPUT PACKET HANDLER [see figure 2.5] 📮
When it gets activated by the packetizer, the input packet handler, or some of the user call routines, the Output Packet Handler tries to transmit packets on the net (this might involve going through some other network interface program) 🚀 It looks at the TCB's in turn and transmits some packets from the send packet queue. These get dequeued and put on the retransmit queue, along with the time when they should be retransmitted ⏰
All data packets that get transmitted have the latest receive left window edge in the ACK field 💖 Error and control messages MAY have no ACK [ACK bit off], or MAY set the ACK field to refer to a received packet's sequence number 🧚
The RETRANSMIT PROCESS:
This process can be viewed either as a separate process or as part of the output packet handler 🎀 Its implementation can vary. It could either do its job by waking up at regular intervals, or when the retransmission time occurs for every packet put on the retransmit queue 🌸 In the first case, the retransmit queue for each TCB gets examined to see if there's anything to retransmit. If there is, a packet is placed on the send packet queue of the corresponding TCB, and the output packet handler gets signaled 💌
Another "demon" process keeps an eye on all user Send buffers and retransmittable control messages sent on each connection that haven't been acknowledged yet 👀 If the global retransmission timeout is exceeded for any of these, the User gets notified, and they MAY choose to continue or close the connection 😤 A QUERY packet MAY also be sent to ascertain the state of the connection [this facilitates recovery from half open connections as described in section 4.3.3] ✨
4.4.6 USER CALL PROCESSING 💅
OPEN [See figure 3.1]
- If the process calling does not own the specified local socket, return with
<type 1><ELP 1 "connection illegal for this process">. - If no foreign socket is specified, construct a new TCB and add it to the list of existing TCB's. Select a new local connection name and return it along with
<type 1><OLP 0 "success">. If there is no room for the TCB, respond with<type 1><ELT 4 "No room for TCB">. - If a foreign socket is specified, verify that there is no existing TCB with the same <local socket, foreign socket> pair (i.e. same connection). Otherwise return
<type l><ELP 6 "connection already open">. If there is no TCB space, return as in (2). Otherwise, create the TCB and link it with the others, returning a local connection name with the success event code.
Note: if a TCB is created, be sure to copy the timeout parameter into it, and set the "U" bit to 0 if a foreign socket is specified, else set U to 1 (to show unspecified foreign socket) 📝
SEND [see figure 3.2]
- Search for the TCB with the local connection name specified. If none is found, return
<type 10><ELP 3 "connection not open">🔍 - If a TCB is found, check the foreign socket specification. If it's not set (i.e. U = 1 in TCB), return
<type 10><ELT 5 "foreign socket unspecified">. If the connection is in the "closing" state (i.e. state 5 or 6), return<type 3><ELP 12 "connection closing">and do not process the buffer 🚫 - Put the buffer on the Send buffer queue and signal the packetizer that there's work to do 💫
INTERRUPT [see figure 3.3]
- Validate that the referenced connection exists, sending out error messages of the form
<type 3><ELP 3 "connection not open">or<type 3><ELT 5 "foreign socket unspecified">as appropriate. If the local connection refers to a connection that isn't accessible to the interrupting process, send<type 3><ELP 1 "connection illegal for this process">🙅 - If the connection is in the "closing" state (i.e. states 5 or 6), return
<type 3><ELT 12 "connection closing">and do not send an INT packet to the destination 🛑 - Any pending SEND buffers SHOULD be returned with
<type 10><ELP 10 "buffer flushed due to interrupt">. An INT packet SHOULD be created and placed on the output packet queue, and the output packet handler SHOULD be signaled ⚡
RECEIVE [See figure 3.4]
- If the caller does not have access to the referenced local connection name, return
<type 20><ELP 1 "connection illegal for this process">. And if the connection is not open, return<type 20><ELP 3 "connection not open"). If the connection is in the closing state (e.g. a FIN has been received or a user CLOSE is being processed), return<type 20><ELP 12 "connection closing">📭 - Otherwise, put the buffer on the receive buffer queue and signal the reassembler that buffer space is available 🎉
CLOSE [See figure 3.5]
- If the connection is not accessible to the caller, return
<type 2><ELP 1 "connection illegal for this process">. If there is no such connection, respond with<type 2><ELP 3 "connection not open">🙈 - If the R bit is 0 (i.e. connection is in state 1 or 2), simply remove the TCB 🗑️
- If the R bit is set and the F bit is set, then remove the TCB 🧹
- Otherwise, if the R bit is set but F is 0 (i.e. states 3 or 4), return all buffers to the User with
<type x><ELP 12 "connection closing">, clear all output and input packet queues for this connection, create a FIN packet, and signal the output packet handler. Set the C and F bits to show this action 🌙
STATUS [See figure 3.6]
- If the connection is illegal for the caller to access, send
<type 30><ELP 1 "connection illegal for this process">🚷 - If the connection does not exist, return
<type 30><ELP 3 "connection not open">🫥 - Otherwise, set status information from the TCB and return it via
<type 30><O-T 0 "status data...">📊
4.4.7 NETWORK CONTROL PROCESSING 🌈
The Input Packet Handler examines the header to see if there's any control information or error codes present 🔍 We won't go through the action taken for every special function code, because it's often implementation dependent. We do describe the ones that affect the state of the connection 💅 After the initial screening by the IPC [see section 4.4.2 and figure 2.2], control and error packets are processed as shown in figures 4.l-4.7. [ACK and data processing is done within the IPC.] 🦋
4.4.8 TCP ERROR HANDLING ✨
okay so error messages are CD=001 🙈 and they don't carry any user data 💀. Depending on the error, zero or more octets of error info can ride along in the packet text field 🎀. We're explicitly assuming that this data stays short enough to fall below the GATEWAY fragmentation threshold (probably 512 bits of data and header) 🧚, so no fragmentation drama. Errors usually point at a specific connection, so the source and destination socket identifiers matter here 🦋. The ACK field of an error packet holds the sequence number of the packet that caused the error, and the ACK bit is off 💅. [RESET and STATUS special functions may use the ACK field in the same way.] That's how the receiver of an error message can figure out which packet caused the problem 🔥. Error packets never get ACK'ed or retransmitted, periodt 💅.
4.5. BUFFER AND WINDOW ALLOCATION 👑
4.5.1 INTRODUCTION
okay so TCP manages buffer and window allocation on connections for two big reasons 🌸. One is sharing the limited TCP buffer space equitably among all connections (that's the multiplexing function). The other is limiting how much gets sent so the receiver doesn't get swamped (that's the flow control function) 🫶. For the full tea on how the window mechanism works, check out CEKA74 📚.
Good allocation schemes are literally one of the hardest problems in TCP design 😭, so tons of experimenting has to happen to get efficient, effective algorithms. That's why the suggestions here are merely initial thoughts 🙈. Different implementations are encouraged, with the hope that results can be compared and better schemes developed ✨.
Several of the measurements discussed in a later section are aimed at the performance of allocation mechanisms 📊. They should help figure out significant parameters and evaluate alternate schemes 💜.
4.5.2 The SEND Side
The window is determined by the receiver 👑. Right now the sender has no control over the SEND window size, and it never transmits beyond the right window edge 🙅. There's a possibility of specifying two more special function codes so the sender can ask the receiver to INCREASE or DECREASE the window size, without saying by how much 🦋. The receiver, of course, needn't satisfy this request 💅.
buffers must be allocated for outgoing packets from a TCP buffer pool 🧺. The TCP may not be willing to allocate a full window's worth of buffers, so buffer space for a connection may be less than what the window would permit. No deadlocks are possible even if there's insufficient buffer or window space for one letter, since the receiver will ACK parts of letters as they're put into the user's buffer. That advances the window and frees buffers for the rest of the letter 🔓.
It is not mandatory that the TCP buffer outgoing packets until acknowledgments for them are received, since it's possible to reconstruct them from the actual letters sent by the user 🤓.
However, for purposes of retransmission and processing efficiency, it is very convenient to do 💖.
4.5.3 The RECEIVE Side
At the receiving side there are two requirements for buffering 🧠:
(l) Rate Discrepancy:
If the sender produces data much faster or much slower than the receiver consumes it, little buffering is needed to keep the receiver at near maximum rate of operation. Simple queuing analysis says that when the production and consumption (arrival and service) rates are similar in magnitude, more buffering is needed to reduce the effect of stochastic or bursty arrivals and to keep the receiver busy 🎢.
(2) Disorderly Arrivals:
When packets arrive out of order, they must be buffered until the missing packets arrive, so that packets (or letters) are delivered in sequence 📦. We do not advocate the philosophy that they be discarded, unless they have to be, otherwise a poor effective bandwidth may be observed 🚫. Path length, packet size, traffic level, routing, timeouts, window size, and other factors affect how much packets come out of order. This is expected to be a major area of investigation 🔍.
The considerations for choosing an appropriate window are as follows:
Suppose that the receiver knows the sender's retransmission timeout, and that the receiver's acceptance rate is 'U' bits/sec, and the window size is 'W' bits. Ignoring line errors and other traffic, the sender transmits at a rate between W/K and the maximum line rate (the sender can send a window's worth of data each timeout period) ⏱️.
If W/K is greater than U, the difference must be retransmissions, which is undesirable. So the window should be reduced to W', such that W'/K is approximately equal to U. This may mean the entire bandwidth of the transmission channel isn't being used, but it's the fastest rate at which the receiver is accepting data, and the line capacity is free for other users 🛣️. This is exactly the same case where the rates of the sender and receiver were almost equal, so more buffering is needed. Thus we see that line utilization and retransmissions can be traded off against buffering ⚖️.
If the receiver doesn't accept data fast enough (by not performing sufficient RECEIVES), the sender may keep retransmitting, since unaccepted data won't be ACK'ed. In this case the receiver should reduce the window size to "throttle" the sender and inhibit useless retransmissions 🛑.
Receiver window control:
If the user at the receiving side is not accepting data, the window should be reduced to zero. In particular, if all TCP incoming packet buffers for a connection are filled with received packets, the window must go to zero to prevent retransmissions until the user accepts some packets 🥺.
Short term flow control:
Let F = the number of user receive buffers filled
B = the total user receive buffers
W = the long-term or nominal window size
W' = the window size returned to the sender
then a possible value for W' is
W' = W*[1-F/B]**aThe value of 'a' should be greater than one, in order to shut the window faster as buffers run out 🚪. The values of W' and F actually used could be averages of recent values, in order to get smooth control 🧈. Note that W' is constantly being recomputed, while the value of W, which sets the upper limit of W', only changes slowly in response to other factors 🐢.
The value of W can be large (up to half the sequence number space) to allow for good throughput on high delay channels 🌈. The sender needn't allocate W worth of buffer space anyway. The long-term variation of W to match flow requirements may be a separate question 🤔
This short-term mechanism for flow control allows some buffering in the two TCP's at either end (as much as they're willing to do), and the rest in the user process at the send side where the data is being created. So the cost of buffering to smooth out bursty traffic is borne partly by the TCP's and partly by the user at the send side. None of it is borne by the communication subnet 💸.
5. NETWORK MEASUREMENT PLANS FOR TCP 🔬
5.1 USERLEVEL DIAGNOSTICS
We have in mind a program that will exercise a given TCP, causing it to cycle through a number of states: opening, closing, and transmitting on a variety of connections 🔄. This program will collect statistics and will generally try to detect deviation from TCP functional specifications 🕵️♀️. Clearly there will have to be a copy of this program both at the local site being tested and at some site that has a certified TCP. So we'll have to produce a specification for this user level diagnostic program too 📝.
There needs to be a master and a slave side to all this, so the master can tell the slave what's going wrong with the test 🫡.
5.2 SINGLE CONNECTION MEASUREMENTS
Round trip delay times
Time from the moment the packet is sent by the TCP to the time the ACK is received by the TCP ⏰.
Time from the moment the USER issues the SEND to the time the USER gets the successful return code ✅.
Note: packet size should be used to tell one set of round trip times from another 📏.
Network destination, current configuration, and traffic load may also be issues of importance that must be taken into account 🛰️.
What if the destination TCP decides to queue up ACKs and send a single ACK after a while? How does this affect round trip statistics? 🤷♀️ What about out of order arrivals and the bunched ACK for all of them? 🧩
The histogram of round trip times includes retransmission times, and these must be taken into account in the analysis and evaluation of the collected data 📊.
Packet size statistics
Histogram of packet length in both directions on the full duplex connection 📦.
Histogram of letter size in both directions 💌.
Measure of disorderly arrival
Distance from the first octet of an arriving packet to the left window edge. A histogram of this measure gives an idea of how out of order packet arrivals are. It will be 0 for packets arriving in order 🎯.
Retransmission Histogram
Effective throughput
This is the effective rate at which the left edge of the window advances. The time interval over which the measure is made is a parameter of the measurement experiment. The shorter the interval, the burstier we'd expect the measure to be 💥.
It's possible to measure effective data throughput in both directions from one TCP by observing the rate at which the left window edge is moving on ACKs sent and received for the two windows 🔁.
Since throughput depends largely on buffer allocation and window size, we must record these values too 📝. Varying the window for a fixed file transmission might be a good way to discover how sensitive throughput is to window size 🔬.
Output measurement
The throughput measurement is for data only, but includes retransmission. The output rate should include all octets transmitted, and it'll give a measure of retransmission overhead 📈. The output rate also includes packet format overhead octets as well as data 🧾.
Utilization
The effective throughput divided by the output rate gives a measure of utilization of the communication connection 💯.
Window and buffer allocation measurements
Histogram of letters outstanding, measured at the instant of SEND receipt by TCP from the user, or at the instant of arrival of a letter for a receiving user 🪟.
Buffers in use on the SEND side upon packet departure into the net; buffers in use on the RECEIVE side upon delivery of a packet into a USER Buffer 🧮.
5.3 MULTICONNECTION MEASUREMENTS
Statistics on User Commands sent to the local TCP 📨.
Statistics of error or success codes returned [histogram of each type of error or return response] 📉.
Statistics of control bit use:
Counter for each control bit over all packets emitted by the TCP, and another for packets accepted 🎛️.
Count data carrying packets 📬.
Count ACK packets with no data 🙌.
Error packets distribution by error type code received from the net and sent out into the net 🚨.
5.4. MEASUREMENT IMPLEMENTATION PHILOSOPHY ✨
okay so the measurement stuff happens inside TCP 🎀 but you can totally steer it from outside, which is so iconic. A well known socket owned by the TCP takes control input that picks one or more measurement classes to collect. The data then gets sent periodically to a designated foreign socket that soaks it all up for later processing, kinda like how the ARPANET IMPs already do it 🦋. Each measurement class gets its own data packet format, so parsing and analyzing it is literally easier 💅.
We'd restrict access to TCP measurement control to a few designated sites [e.g. NMC, SU-DSL, BBN] 🔒. Easy fix: set up listening control connections on partially specified foreign sockets 🫶.
6. SCHEDULE OF IMPLEMENTATION 🗓️
(bestie, there's nothing in this section in the original, so nothing to spill here 🙈)
7. REFERENCES 📚
ok here are the receipts, keep these exact, no edits 🧾
- CEKA74
V. Cerf and R. Kahn, "A Protocol For Packet Network Intercommunication," IEEE Transactions on Communication, vol. C-2O, No. 5. May 1974, pp. 637-648.
- CERF74
V. Cerf, "An Assessment of ARPANET Protocols," in Proceedings of the Jerusalem Conference on Information Technology, July l974 [RFC#635, INWG Note # ***].
3.CESU74
V. Cerf and C. Sunshine, "Protocols and Gateways for the Interconnection of Packet Switching Networks," Proc. of the Subconference on Computer Nets, Seventh Hawaii International Conference on Systems Science, January 1974.
- HEKA70
F. Heart, R.E. Kahn, et al, "The Interface Message Processor for the ARPA Computer Network," AFIPS 1970 SJCC Proceedings, vol. 36, Atlantic City, AFIPS Press, New Jersey, pp. 551-567.
- POUZ74
L. Pouzin, "CIGALE, the packet switching machine of the CYCLADES computer network," Proceedings of the IFIP74 Congress, Stockholm, Sweden.
- ROWE74
L. Roberts and B. Wessler, "Computer Network Development to achieve resource sharing," AFIPS 1970, SJCC Proceedings, vol. 36, Atlantic City, AFIPS Press, New Jersey, pp. 543-549.
- POUZ73
L. Pouzin, "Presentation and major design aspects of the CYCLADES Computer Network," Data Networks: Analysis and Design, Third Data Communications Symposium, St. Petersburg, Florida, November 1973, pp. 80-87.
- SCWI71
R. Scantlebury and P.T. Wilkinson, "The Design of a Switching System to allow remote Access to Computer Services by other computers and Terminal Devices," Second Symposium on Problems in the Optimization of Data Communication Systems Proceedings, Palo Alto, California, 0ctober 1971, pp. 160-167.
- POST72
J. Postel, "Official Initial Connection Protocol," Current Network Protocols, Network Information Center, Stanford Research Institute, Menlo Park, California. January 1972 (NIC 7101).
- CACR70
C.S. Carr, S.D. Crocker, and V.G. Cerf, "Host-Host Communication Protocol in the ARPA Network," AFIPS Conference Proceedings, vol. 36, 1970 SJCC, AFIPS Press, Montvale, N.J.
- ZIEL74
H. Zimmerman and M. Elie, "Transport Protocol. Standard Host-Host Protocol for heterogeneous computer networks," INWG#61, April 1974.
- CRHE72
S. D. Crocker, J. F. Heafner, R. M. Metcalfe and J. B. Postel, "Function-oriented protocols for the ARPA Computer Network," AFIPS Conference Proceedings, vol. 41, 1972 FJCC, AFIPS Press, Montvale, N.J.
- DALA74
Y. Dalal, "More on selecting sequence numbers," INWG Protocol Note #4, October 1974.
- SUNS74
C. Sunshine, "Issues in communication protocol design -- formal correctness." INWG Protocol Note #5, October 1974
BELS74
D. Belsnes, "Note on single message communication," INWG Protocol Note #3. September 1974.
- TOML74
R. Tomlinson, "Selecting sequence numbers," INWG Protocol Note #2, September 1974.
- SCHA74
R. Schantz, "Reconnection Protocol", private communication; available from Schantz at BBN.
- POUZ74A
L. Pouzin, "A proposal for interconnecting packet switching networks, INWG Note #60, March 1974 [also submitted to EUROCOMP 74].
- DLMG74
D. Lloyd, M. Galland, and P. T. Kirstein, "Aims and objectives of internetwork experiments," to be published as an INWG Experiments Note.
- MCKE73
A. McKenzie, "Host-Host Protocol for the ARPANET," NIC # 8246, Stanford Research Institute [also in ARPANET Protocols Notebook NIC 7104].
- BELS74A
D. Belsnes, "Flow control in packet switching networks," INWG Note #63, October 1974.
FIGURE 1: TCB Major States 🌈
0-no TCB
\____________________________________________________________/
OPEN | A CLOSE CLOSE A
---------- | | ---------- ---------- |
set up TCB | | remove TCB remove TCB |
| | |
| | collision retry, |
SYN arrives __V____|__ SEND, INTER |
------------- / S1=0 \ ---------------- |
send SYN, ACK | S2=0 F=0 | send SYN |
______________________| R=0 C=0 |_____________________ |
| | U=0/1 | | |
| | | SYN arrives | |
| error,timeout | 1-OPEN | ----------- | |
| ------------- \__________/ collision; | |
| clear TCB A A set timeout | |
| _____________________| |_____________________ | |
__V____|__ _|___V__|_
/ S1=1 \ / S1=1 \
| S2=0 F=0 | | S2=0 F=0 |
| R=1 C=0 | SYN, ACK arrives | R=0 C=0 |
| U=0/1 | ACK arrives ---------------- | U=0 |
| | ----------- send ACK | |
| 3-SYN rcvd |_________________ _________________| 2-SYN sent |
\__________/ | | \__________/
| __V_____V__
| / S1=1 \
| CLOSE | S2=1 F=0 |
| -------- | R=1 C=0 | FIN arrives
| send FIN | U=0 | -------------------
| | | tell user, send FIN
| ________________|4-established|______________________
| | CLOSE \___________/ |
| | ------- |
__V_____V_ send FIN _______V__
/ S1=1 \ / S1=1 \
| S2=0/1 F=1 | timeout or | S2=1 F=1 |
| R=1 C=1 | FIN, error, arrives CLOSE | R=1 C=0 |
| U=0/1 | ------------------- ---------- | U=0 |
| | remove TCB remove TCB | |
| 5-FIN wait |_____________________ _____________| 6-FIN rcvd |
\__________/ | | \__________/
| |
____________________________V_____V_______________________
/ \
0-no TCBOkay bestie, this part is all diagrams 🦋 so we're going to look at them together, one at a time. ✨
Here's the big picture: how the TCP is built out of its pieces. 🎀
FIGURE 2.1: Structure of the TCP
| _____________ _______________ |
| | | | | |
| | | | INPUT PACKET |<---->|
| | REASSEMBLER | | HANDLER | |
| |_____________| |_______________| |
| |_______________ | |
| | | |
| _________ | | |
| | | __V_________V____ | NETWORK
|<=====| SYSTEM | | | | or
| | CALLS |<========| TCB's |<========| some
USERS |=====>| or | | and | | NETWORK
| | USER |========>|ASSOCIATED QUEUES|========>| INTERFACE
|<---->|INTERFACE| |_________________| | PROGRAM
| |_________| A A |
| | | |
| ______________| | |
| _______|_____ _______|_______ |
| | | | | |
| | PACKETIZER | | OUTPUT PACKET | |
| | | | HANDLER |<---->|
| |_____________| |_______________| |
| |
=======> Logical or physical flow of data (packets/letters)
-------> "Interaction"
NOTE: The signalling of processes by others is not shownNgl the middle of this one is giving main character energy 👑 Everything runs through the TCB and its queues, like it's the whole group chat. 💅
Next up is the address check, so the TCP can figure out which connection a packet is even for 🧚
FIGURE 2.2a: ________
Address Check / Begin \
\________/
|
_V_
.' '.
.' packet '.
.' foreign '.
___________________.' socket matches '.
| no '. a TCB local .'
| '. socket .'
| '. ? .'
| '.___.'
| | yes
| _V_
| .' '.
| .' packet '. ___
| .'local socket '. / \
| .' matches fully '.____\| YES |
| '. specified TCB .' / \___/
| '.fgn socket .'
| '. ? .'
_V_ '.___.'
.' '. | no
.' SYN, '. _V_
.'FIN,INT,DSN, '. .' '.
_____.'or text length>0 './_____ .' matches '.
| no '. or QUERY .' \ | .'partly spec. '.
| '. .' |___.' or unspec. TCB '.
| '. ? .' no '. foreign .'
| '.___.' '. socket .'
| | yes '. ? .'
| __________V_________ '.___.'
| | | | yes
| | Create error 7 | _V_
| | packet. Signal OPH | .' '.
| |____________________| .' packet '.
| | ______.' has SYN set '.
| ____V____ | no '. .'
| | | | '. ? .'
|_________\| discard |/________| '.___.'
/|_________|\ |
| _V_
_V_ / \
/ \ | YES |
| NO | \___/
\___/The picture is getting clearer, right? 🌸 Next is the input packet handler, which is where the real drama happens 😭
FIGURE 2.2b-1: _______
Input Packet Handler / Begin \
\_______/
|
________________________________________\|/_________________________
| A /|\ |
| | | |
| | _V_ |
| | .' '. _______ |
| | .' input '. | go to | |
| | .' packet '.____\| sleep | |
| | '.available.' no /|_______| |
| | '.__?__.' |
| | | yes |
| | _V_ |
| | .' '. |
| .->SPECIAL FUNCT. Fig 4.7 | .'address'. |
| | .->ERR Fig 4.5,4.6 |___.' check OK '. |
| | | .->SYN Fig 4.1,4.2 no '. ? .' |
| | | | .->INT Fig 4.3 '._____.' |
| | | | | .->FIN Fig 4.4 | yes ________|_
| | | | | | _V_ | discard |
| _|_|_|_|_|___________ .' '. |(or queue)|
| | | .' error '. |__________|
|<-| Control Processing |/_________.'or control '. A
|____________________|\ yes '. ? .' |
| '._____.' |
| (INT with data) | no |
| | |
V _V_ |
to "X" .' '. . |
in Fig 2.2b-2 .'(estab)'. .' '. |
_____.' R=S1=S2=1 '.----->.'seq.#'.--->|
| yes '. ? .' no '.OK .' no |
| '._____.' '.' |
| | yes |
| _______________ | |
| | Set S2=1, U=0 | V |
| | Notify user | .'. |
|<--| with event 2 | .'ACK'. |
| | if U was 1 |<-----'. OK .'--->'
| |_______________| yes '. .' no
| '
V
to "Y"
in Fig 2.2b-2Okay the second half of the input packet handler is up next, and it's where the ACKs and the receive buffer get sorted out 🌈
FIGURE 2.2b-2: Input Packet Handler (continued)
"Y"
|
.'. _V_
.'txt'. .' '. ______________________________
.'lgth>0 '. .'within '. |Use ACK to advance send window|
,<----'. or DSN .'<---'. window .'--->|Release ACK'ed packets from |
| no '. ? .' no '. ? .' yes |retransmit or send queues. If |
| '._.' '._.' |any packet had EB bit set |
| | yes |remove buffer from Packetized |
| ________V____________________ |buffer queue and inform user |
| |Create ACK packet. Put on | |(success). Signal Packetizer. |
|<-|Send packet queue. Signal OPH| |______________________________|
| |_____________________________| |
| |
| _____________________________________________|
| |
| |
| | "X"
| | |
| _V_ _V_ _____________________
| .' '. .'TCB'. |Put packet on |
| .' text '. yes .'Receive'. yes |Receive packet queue |
| .' length>0 '.-------->.' buffer '.------>|in the right order. |
| '. or DSN .' A '.available.' |Signal Reassembler. |
| '. ? .' | '. ? .' |_____________________|
| '._.' | '._.' |
| | no | | no |
| | | _V_ |
|________\| | .' '. |
/| | .' seq # '. ________ |
| | .' of packet '. yes |Discard | |
| | '. highest so .'---->|packet |----->|
| | '. far .' |________| |
| | '. ? .' |
| | '._.' |
| | | no |
| | _______V______________ |
| | |Discard packet with | |
| |_____|highest seq. no from | |
| |Receive packet queue. | |
| |______________________| |
| |
|_____________________________________________________|
|
V
to "Begin" in Fig 2.2b-1And that's the whole set of figures for this part, bestie 💖 I'm obsessed with how the packets loop back around to "Begin" 🔁✨
FIGURE 2.3-1: Reassembler 🧩
Okay bestie, this is the Reassembler, and it's giving puzzle master. Packets come in all out of order, and this flowchart is the whole routine for sorting them back into the right sequence before anything gets handed up to the user. Start at "Begin" and follow the arrows. Ngl, the loops are the best part. 💜
_______
/ Begin \
\_______/
|
|
|<----------------------------------------------.
| _____ | yes
______V_____ .' '. _|_
|Get ready | .' Receive '. yes .'any'.
|for next TCB|--------->.'Packet Queue '.-------->.' more '.
|____________| A '. empty ? .' A '.work?.'
| '._______.' | '._.'
| | no | | no
"R"------>---------' __V__ | ____V____
.' is '. | | Go to |
.' packet '. | | Sleep |
.--<----------------------'.DSN with no.' | |_________|
| yes '. data? .' |
| '.___.' |
| | no |
| __V__ |
| .' '. |
| .' Receive '. yes |
| .'Buffer Queue '.--->|
| '. empty ? .' |
| ________________ '._______.' |
| |Copy from packet| | no |<-------------"S"
| |to buffer until | __V__ |
| |one is exhausted| .'First'. |
| |Update receive | yes .' packet '. no |
| |window. |<----.'matches Recv '.--->'
| |________________| '.left window.'
| | '. edge ?.'
| __V__ '.___.'
| .'Send '.
| .' Packet '. yes _____________________________
| .' Queue empty '.---->|Create ACK packet containing |
| '. ? .' |new window. Signal OPH. |
| '._______.' |_____________________________|
| no | |
| | |
| '--------------------------->|
| |
V V
to "T" to "U"
in Fig 2.3-2 in Fig 2.3-2Okay so the Reassembler checks the Receive Packet Queue first, and if there's a DSN with no data it takes a little detour. Then it copies stuff into the receive buffer and updates the receive window, and if the Send Packet Queue is empty it makes an ACK with the new window. Iykyk, the diagram literally tells you exactly where to go next, so just follow the letters "T" and "U" to the next figure. ✨
FIGURE 2.3-2: Reassembler (continued) 🦋
Round two, and it's iconic. This one picks up from "T" and "U" and handles the DSN checks, the EOL bit, and whether the whole packet has been copied. Then it marks progress in the packet or the buffer and sends you right back to "R" or "S" in the first figure. Main character energy, no cap. 💅
"T" "U"
| |
| | _____________
___V____ ___ __V__ |Mark progress|
|process | yes .' '. yes .'whole'. no |in packet. |
| DSN |<-----.' DSN '.<-----.' packet '.--->|Return buffer|--->.
|________| '. set?.' '.copied?.' |to user. | |
| '._.' '.___.' |_____________| |
| | no |
'--------------->| |
| |
__V__ __________________________ |
.' EOL '. yes |Return buffer to user. | |
'. set? .'--------->|Return packet to free |--->|
'.___.' |storage. Signal Packetizer| |
no | |__________________________| |
| A |
__V__ | |
.' full'. | |
'. buffer.'--------------' |
'.___.' yes |
| no |
| |
___________________V__________________ |
|Mark progress in buffer. Return packet| |
|to free storage. Signal Packetizer. | ,--------'
|______________________________________| |
| |
| |
V V
to "R" in Fig 2.3-1 to "S" in Fig 2.3-1FIGURE 2.4: Packetizer 📦
Now we're on the sending side, and it's giving packing-your-suitcase vibes. The Packetizer decides how big each packet should be based on the send buffer, TCB buffer space, window, and other stuff, then copies data into packets until they're full. It sets the EOL bit when it needs to and keeps going until the send buffer is all copied. Bestie, the loop-back arrows are doing a lot here. 🧳
_______ ________________________
/ Begin \____________\| Get ready for next TCB |/___________________
\_______/ /|________________________|\ |
| |
__V__ _____ |
.'Send '. .' any '. |
no .' Buffer '. yes .' more '. yes |
.-------------'. Queue .'---->'. work .'-----'
| '.empty? .' A '. ? .'
____________V____________ '.___.' | '.___.'
|Pick packet size depend- | | | no
,-->|ing on send buffer, TCB | | ______V______
| |buffer space, window, etc| | | go to sleep |
| |_________________________| | |_____________|
| | |
| __V__ |
| .'Send '. |
| .' window '. no |
| '.has room ? .'--------------------->|
| '._______.' |
| | yes |
| __V__ |
| .' TCB '. |
| .' buffer '. no |
| .'space avail- '.---------------------'
| '. able ? .' A
| '._______.' |
| | yes |
| _____________V____________ _________|_______ ____________
| |Copy from Send buffer to | |Move buffer from | |Set EOL bit |
| |packet until packet full. | |Send queue to |<--|in packet |
| |Put packet on Send packet | |packetized queue | |header |
| |queue. Signal OPH. | |_________________| |____________|
| |__________________________| A A
| | | no |
| __V__ __|__ |
| .'whole'. .' EOL '. |
| .' Send '. yes .' set in '. yes |
| '. buffer .'----------->'. Send .'-----------'
| '.copied?.' '.buffer?.'
| '.___.' '.___.'
| | no
| _____________V__________
| |Note in TCB where in |
--|Send buffer we stopped. |
|________________________|FIGURE 2.5a: Output Packet Handler 📤
Here's the Output Packet Handler, and it's lowkey the hype-woman of the whole operation. It checks whether the ACK bit is set and, if so, puts the latest receive left window edge in the ACK. Then it transmits packets, and the ones that have been ACKed get returned to the buffer pool. Anything still waiting gets moved to the retransmit queue with a new retransmit time. It keeps cycling through TCBs until there's no more work. Periodt. 🔁
_______
/ Begin \
\_______/
|
|<--------------------------.
____________V___________ |
| Get ready for next TCB | |
|________________________| |
| |
,------------------------------------>| |
| __V__ _____ |
| _____ .'Send '. .' any '. |
| yes .' ACK '. no .' Buffer '. yes .' more '. yes |
| .-----'.bit set.'<------'. Queue .'---->'. work .'-----'
| | '.___.' '.empty? .' A '. ? .'
| | no |________ '.___.' | '.___.'
| | |__________ | | no
| ____V__________________ | | |
| |Put latest receive left| ________v______ | ______V______
| |window edge in ACK. |->|Transmit packet| | | go to sleep |
| |_______________________| |_______________| | |_____________|
| | |
| ________________ __V__ |
| |Return packet to| .'pckt '. |_________________
| |buffer pool as | no .'seq # to '. |
| |it has been |<------.'rgt of Send '. |
| |ACKed | '.left window.' |
| |________________| '. edge .' |
| | '.___.' |
| | | yes |
| | _______________V________________ |
| | |Move packet to retransmit queue;| |
| | |set new retrans. time for it. | |
| | |________________________________| |
| | | |
| '---------------------->| |
| __V__ |
| no .'Time '. yes |
-------------------------------.'to switch'.---------------------'
'.TCB's? .'
'.___.'FIGURE 2.5b: Retransmit Process 🔄
And the retransmit side is the comeback arc. The process checks whether any packet's retransmit time has come up for this TCB. If it has, the packet gets moved to the Send Packet queue and the OPH gets signaled. If not, it goes to sleep once there's no more work. Honestly, that's such a clean loop, I'm obsessed. 🫶
_______
/ Begin \
\_______/
|
|<----------------------------------.
____________V___________ |
| Get ready for next TCB | |
|________________________| |
| |
.-------------------------------->| |
| __V__ |
| .' Any '. _____ |
| .'packet's '. .' any '. |
| .'retrans. time'. no .' more '. yes |
| '. has occurred .'----->'. work .'-----'
| '. for this .' '. ? .'
| '. TCB ? .' '.___.'
| '.___.' |
| | yes | no
| | ______V______
| ________V________ | go to sleep |
| |Move packet to | |_____________|
'------------------------|Send Packet |
|queue. Signal OPH|
|_________________|FIGURE 3.1: 🌈
Okay, we're at the top of Section 3 now, and this figure is where the next part picks up. Stay tuned, bestie, it's about to get so good. ✨
OPEN
_______
/ Begin \
\_______/
|
__V__
.'User '. _______
.'permitted'. no | |
.' access to '.---->|error 1|------------.
'.this local .' |_______| |
'.socket?.' |
'.___.' |
| yes |
__V__ |
.' fgn '. |
yes .' socket '. no |
.-----'. specified .'----. |
| '. ? .' | |
__V__ '.___.' __V__ _______ |
_______ .'conn-'. .'space'. no | | |
| | yes .' ection '. '.for TCB.'---->|error 4|-->|
,-|error 6|<----'. already .' '.___.' |_______| |
| |_______| '.exists?.' | yes |
| '.___.' | |
| | no ____V__________ |
| _______ __V__ |Create TCB. Set| |
| | | no .'space'. |S1=S2=R=F=C=1 | |
|<-|error 4|<-----'.for TCB.' |Set U=1 | |
| |_______| '.___.' |_______________| |
| | yes | |
| | | |
| _________V__________ | |
| |Create TCB. Set U=0 | | |
| |Set S1=S2=R=F=C=1 | | |
| |____________________| | |
| | | |
| '-------------.-------------' |
| | |
| _____________________V__________________ |
| |Return local connection name and Success| |
| |________________________________________| |
| | |
----------------------------------->|<--------------------------------'
____V___
/ Return \
\________/okay the OPEN flow is the one where the connection gets set up, and it is SO well organised 🧚✨
FIGURE 3.2: SEND
_______
/ Begin \
\_______/
|
__V__
.'conn-'.
.' ection '. _________
.' legal for '. no | |
'. this process .'---------->| error 1 |-----------.
'. ? .' |_________| |
'._______.' |
| yes |
__V__ |
.'conn-'. _________ |
.' ection '. no | | |
.' open '.----------->| error 3 |---------->|
'. ? .' |_________| |
'._______.' |
| yes |
__V__ |
.' fgn '. _________ |
.' socket '. no | | |
'. specified .'------------>| error 5 |---------->|
'.(U=0)? .' |_________| |
'.___.' |
| yes |
__V__ |
.'conn-'. _________ |
.' ection '. yes | | |
'. closing ? .'------------>| error 12|---------->|
'.(F,C=1).' |_________| |
'.___.' |
| no |
____________________V________________________________ |
|Put buffer on Send Buffer queue and signal Packetizer| |
|_____________________________________________________| |
| |
|<-----------------------------------------'
____V___
/ Return \
\________/this one's SEND, the bit where your data gets queued up and the Packetizer gets a ping 💌🎀
FIGURE 3.3: INTERRUPT
_______
/ Begin \
\_______/
|
|
V
Same as SEND
| |
| |
____________________V_________________________ |
|Return any pending Send buffers with code 10. | |
|Create INT packet on outgoing packet queue. | |
|Signal Output Packet Handler. | |
|______________________________________________| |
| |
|<-----------------------------------------'
____V___
/ Return \
\________/INTERRUPT is giving "same as SEND" energy at the start, then it gets its own moment 🦋💜
FIGURE 3.4: RECEIVE
_______
/ Begin \
\_______/
|
__V__
.'conn-'.
.' ection '. _________
.' legal for '. no | |
'. this process .'---------->| error 1 |-----------.
'. ? .' |_________| |
'._______.' |
| yes |
_V_ |
.' '. |
.' '. |
.'connection '. |
.' state '. |
:___________________: _________ |
| | | | | |
1-4 | 5,6 | 0 '-------------------->| error 3 |-->|
| '---------------------. |_________| |
__________V__________ | |
|Put buffer on Receive| | _________ |
|Buffer queue. Signal | | | | |
|Reassembler | '----->| error 12|-->|
|_____________________| |_________| |
| |
|<------------------------------------------------'
____V___
/ Return \
\________/RECEIVE is the mirror image, where incoming data lands in the Receive Buffer queue and the Reassembler gets signalled 🌊💅
FIGURE 3.5: CLOSE
_______
/ Begin \
\_______/
|
__V__
.'conn-'.
.' ection '. _________
.' legal for '. no | |
'. this process .'---------->| error 1 |-----------.
'. ? .' |_________| |
'._______.' |
| yes |
_V_ |
.' '. |
.' '. |
.'connection '. |
.' state '. |
:___________________: _________ |
5| |3,4 |1,2,6 |0 | | |
| | | '------------------>| error 3 |-->|
,------------' | '-------------------. |_________| |
| ______________V______________________ | |
| |Return all buffers to user with error| | ___________ |
| |12; clear all packet queues, create | | |Remove TCB | |
| |FIN packet, signal Output Packet | '--->|Return |--->|
| |Handler, set C=F=1 | |Success | |
| |_____________________________________| |___________| |
| | |
--------------------->|<----------------------------------------'
____V___
/ Return \
\________/CLOSE is the big dramatic exit, the one where everything gets cleared out and the TCB gets removed. not me doing a full clean-up montage 🧹💀
FIGURE 3.6: STATUS
_______
/ Begin \
\_______/
|
__V__
.'conn-'.
.' ection '. _________
.' legal for '. no | |
'. this process .'---------->| error 1 |-----------.
'. ? .' |_________| |
'._______.' |
| yes |
__V__ __________ |
.'conn-'. |Return | |
.' ection '. no |state=0 or| |
'. open ? .'------------>|error 3 |--------->|
'._______.' |__________| |
| yes |
___________V___________ |
|Fill in reply from TCB.| |
|Return Success to user.| |
|_______________________| |
| |
|<-----------------------------------------'
____V___
/ Return \
\________/STATUS is the chill one, just filling in a reply from the TCB and vibing 🍃🌸
FIGURE 4.1:
okay bestie, we're picking up right where the STATUS diagrams left off 💖 these state machines are literally the main character of this whole doc 🧚
SYN (no ACK)
_______
/ Begin \
\_______/
|
_V_
.' '.
.' '.
.' S1, S2, R '.
.' ? '.
:___________________: 1,1,1 _________
__________ | | | | (states 4-6) | |
|Treat as a| 1,0,1 | | | '------------->| error 6 |-->.
|duplicate.|<-----------' | | |_________| |
|Retransmit| | | 1.0,0 |
|SYN, ACK | 0,0,0 | | (Syn sent) ________________ |
|__________| (listening) | '------------>|Collision: Clear| |
| | |S1, set timeout,| |
| _____________________V________________ |remove SYN from |-->|
| |Set R=S1=1. If U=1 set foreign socket | |retransmit queue| |
| |in TCB to match packet local socket. | |________________| |
| |Send SYN, ACK. Signal OPH. Fill in TCB| |
| |with send window, receive sequence #. | |
| |______________________________________| |
| | |
| | |
'----------------------->|<---------------------------------------'
___V__
/ Done \
\______/FIGURE 4.2:
SYN,ACK
_______
/ Begin \
\_______/
|
__V__
.' '.
.' State 2 '. no
'.S1=1;S2=R=0.'----------------.
'. ? .' |
'.___.' |
| yes |
__V__ _______V______
.' ACK '. no | |
.' correct '.-------->| send error 6 |
'. ? .' |______________|
'.___.' |
| yes |
_________V_________ |
|Set S2=R=1. Process| |
|ACK. Send ACK. | |
|___________________| |
| |
|<----------------------'
___V__
/ Done \
\______/FIGURE 4.3:
INT (from net)
_______ ____________
/ Begin \____\|Process ACK |
\_______/ /|(may set S2)|------.
|____________| |
|
__V__
____________ .' in '.
| Discard | no .' state 4 '.
.<-------| (or queue) |<-------'. S1=S2=R=1 .'
| |____________| '. F=0 ? .'
| '.___.'
| | yes
| __V__
| ____________ .' '.
| | ACK and | no .' within '.
|<-------| discard |<-------'. window .'
| |____________| '. ? .'
| '.___.'
| | yes
| ____________________________V_______________
| |Move Receive Left window edge to sequence |
| |number of INT. Return event 10 with any |
| |pending Receive buffers. Ruturn event 11 to |
| |user. Send ACK for INT. |
| |____________________________________________|
| |
| __V__
| see yes .'data '.
| Figure<----------.' in this '.
| 2.2 '.packet?.'
| '.___.'
| | no
'------------------------------------>|
___V__
/ Done \
\______/FIGURE 4.4:
FIN
_______ ____________
/ Begin \____\|Process ACK |
\_______/ /|(may set S2)|------.
|____________| |
|
__V__
.' '.
no .'S1=S2=R=1'.
.--------------'. (estab- .'
| '.lished).'
| '.___.'
| | yes
| __V__
______V_____ .' '.
| | no .' within '.
.-----------------| discard |<-------'. window .'
| |____________| '. ? .'
| '.___.'
| | yes
| __V__
| (state 4) 0 .'F bit'. 1 (state 5)
| .------------'. value .'------------.
| | '.___.' |
| _________________________V________ |
| |Return all user buffers (event 12)| _____________________V__
| |Clear all packet queues. Send FIN | |Return success to User's|
| |packet. Set F=1. Inform user | |CLOSE. Remove TCB. |
| |"connection closing" (event 12) | |________________________|
| |__________________________________| |
| | |
'----------------->|<-----------------------------------'
___V__
/ Done \
\______/FIGURE 4.5:
Error 6 (bad SYN)
_______
/ Begin \
\_______/
|
|
__V__
.' '.
.'refers to'.
.'current pckt?'. _________
.'(ACK matches seq '. no | |
'. # of packet on .'----------------->| discard |-----------.
'.retrans or send.' |_________| |
'. queues?) .' |
'._______.' |
| yes |
| |
_V_ |
.' '. 1 (state 3) |
.' value '.--------------------------------. |
'. of R.' bad SYN,ACK | |
'._.' | |
| | |
| 0 (state 2) | |
| bad SYN | |
__________________V__________________ _______V______ |
|Other side is established. Send RESET| |Clear S1, R | |
|(put error packet's seq. # in ACK | |Remove SYN,ACK| |
|field. Return all user buffers with | |from retrans | |
|code 14. Inform user with event 14 | |queue. | |
|_____________________________________| |______________| |
| | |
| V |
|<--------------------------------------------------'
___V__
/ Done \
\______/FIGURE 4.6:
Error 7,8
_______
/ Begin \
\_______/
|
__V__
.' '.
.'refers to'. _________
.' current '. no | |
'. packet (check .'---------------->| discard |-----------.
'. ACK)? .' A |_________| |
'._______.' | |
| yes | |
_V_ | |
.' '. | |
.' '. | |
.'connection '. | |
.' state '. | |
:___________________: | |
4| 5| 3| 2| 6| | |
.-------' | | | '------' |
| | | '-----------------------------. |
| | '-------------. | |
| | | | |
___V___ ____V_______ ______V_______ ________V_________ |
|Pass to| |Remove TCB. | |Clear S1, R. | |Discard. SYN will | |
|user | |Return | |Remove SYN,ACK| |be retrans to | |
|_______| |success to | |from transmit | |avoid receiver | |
| |user's CLOSE| |queue (go to | |having to queue it| |
| |____________| |state 1). | |__________________| |
| | |______________| | |
| V | V |
'------------------------------>|<---------------------------------'
___V__
/ Done \
\______/FIGURE 4.7:
RFC>>>Okay bestie, this is the RESET flowchart and it's giving main character energy 💖
Start at Begin 🎀 then check the Reset question, where a yes or no decides which path you take. The diamond about whether RESET is believable (checking the ACK field) is the real gatekeeper 👑 If it's not believable, you discard it 💀 and if it IS, you clear all the queues for this TCB and return event 14 for user buffers 🫶
RESET
_______
/ Begin \
\_______/
|
__V__
no .'Reset'. yes
.------------'. All ? .'------------------.
| '.___.' |
| _________V_________
| |Clear all TCB's for|
| |foreign TCP. Inform|
| |users with event 14|
| |___________________|
__V__ |
.' Is '. _________ |
.' RESET '. no | | |
.'believable ? '.------->| discard |------------->|
'.(check ACK .' |_________| |
'.field) .' |
'.___.' |
| yes |
________________V________________ |
|Clear all queues for this TCB. | |
|Return event 14 for user buffers.| |
|Inform User with event 14. | |
|_________________________________| |
| |
|<----------------------------------------'
___V__
/ Done \
\______/
[ This RFC was put into machine readable form for entry ]
[ into the online RFC archives by Alex McKenzie with ]
[ support from GTE, formerly BBN Corp. 2/2000 ]And that's the whole chart, iykyk 🦋 The footer at the bottom is just the archive folks getting it into machine-readable form, so it's not a protocol rule, but it's still part of the document 🌸
📦 where this page comes from
- ietf: rfc675 1974-12
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms