Module 3
TCP, UDP and the Transport Layer
a. Introduction and Transport-Layer Services
A transport-layer protocol provides for logical communication between
application processes running on different hosts. By logical communication, we mean
that from an application’s perspective, it is as if the hosts running the processes were
directly connected; in reality, the hosts may be on opposite sides of the planet, connected
via numerous routers and a wide range of link types. Application processes use the
logical communication provided by the transport layer to send messages to each other,
free from the worry of the details of the physical infrastructure used to carry these
messages.
On the sending side, the transport layer converts the application-layer messages it
receives from a sending application process into transport-layer packets, known as
transport-layer segments in Internet terminology. This is done by (possibly) breaking the
application messages into smaller chunks and adding a transport-layer header to each
chunk to create the transport-layer segment. The transport layer then passes the segment
to the network layer at the sending end system, where the segment is encapsulated within
a network-layer packet (a datagram) and sent to the destination. It’s important to note that
network routers act only on the network-layer fields of the datagram; that is, they do not
examine the fields of the transport-layer segment encapsulated with the datagram. On the
receiving side, the network layer extracts the transport-layer segment from the datagram
and passes the segment up to the transport layer. The transport layer then processes the
received segment, making the data in the segment available to the receiving application.
More than one transport-layer protocol may be available to network applications.
For example, the Internet has two protocols—TCP and UDP. Each of these protocols
provides a different set of transport-layer services to the invoking application.
Recall that the transport layer lies just above the network layer in the protocol
stack. Whereas a transport-layer protocol provides logical communication between
processes running on different hosts, a network-layer protocol provides logical
communication between hosts. This distinction is subtle but important. Let’s examine this
distinction with the aid of a household analogy.
Consider two houses, one on the East Coast and the other on the West Coast, with
each house being home to a dozen kids. The kids in the East Coast household are cousins
of the kids in the West Coast household. The kids in the two households love to write to
each other—each kid writes each cousin every week, with each letter delivered by the
traditional postal service in a separate envelope. Thus, each household sends 144 letters
to the other household every week. (These kids would save a lot of money if they had e-
mail!) In each of the households, there is one kid—Ann in the West Coast house and Bill
in the East Coast house—responsible for mail collection and mail distribution. Each week
Ann visits all her brothers and sisters, collects the mail, and gives the mail to a postal-
service mail carrier, who makes daily visits to the house. When letters arrive at the West
Coast house, Ann also has the job of distributing the mail to her brothers and sisters. Bill
has a similar job on the East Coast.
In this example, the postal service provides logical communication between the
two houses—the postal service moves mail from house to house, not from person to
person. On the other hand, Ann and Bill provide logical communication among the
cousins—Ann and Bill pick up mail from, and deliver mail to, their brothers and sisters.
Note that from the cousins’ perspective, Ann and Bill are the mail service, even though
Ann and Bill are only a part (the end-system part) of the end-to-end delivery process.
Continuing with this analogy, note that Ann and Bill do all their work within their
respective homes; they are not involved, for example, in sorting mail in any intermediate
mail center or in moving mail from one mail center to another. Similarly, transport-layer
protocols live in the end systems. Within an end system, a transport protocol moves
messages from application processes to the network edge (that is, the network layer) and
vice versa, but it doesn’t have any say about how the messages are moved within the
network core.
Continuing with our family saga, suppose now that when Ann and Bill go on
vacation, another cousin pair—say, Susan and Harvey—substitute for them and provide
the household-internal collection and delivery of mail. Unfortunately for the two families,
Susan and Harvey do not do the collection and delivery in exactly the same way as Ann
and Bill. Being younger kids, Susan and Harvey pick up and drop off the mail less
frequently and occasionally lose letters (which are sometimes chewed up by the family
dog). Thus, the cousin-pair Susan and Harvey do not provide the same set of services
(that is, the same service model) as Ann and Bill. In an analogous manner, a computer
network may make available multiple transport protocols, with each protocol offering a
different service model to applications.
The possible services that Ann and Bill can provide are clearly constrained by the
possible services that the postal service provides. For example, if the postal service
doesn’t provide a maximum bound on how long it can take to deliver mail between the
two houses (for example, three days), then there is no way that Ann and Bill can
guarantee a maximum delay for mail delivery between any of the cousin pairs. In a
similar manner, the services that a transport protocol can provide are often constrained by
the service model of the underlying network-layer protocol. If the network-layer protocol
cannot provide delay or bandwidth guarantees for transport layer segments sent between
hosts, then the transport-layer protocol cannot provide delay or bandwidth guarantees for
application messages sent between processes.
Nevertheless, certain services can be offered by a transport protocol even when
the underlying network protocol doesn’t offer the corresponding service at the network
layer. For example, as we’ll see in this, a transport protocol can offer reliable data
transfer service to an application even when the underlying network protocol is
unreliable, that is, even when the network protocol loses, garbles, or duplicates packets.
As another example (which we’ll explore in when we discuss network security), a
transport protocol can use encryption to guarantee that application messages are not read
by intruders, even when the network layer cannot guarantee the confidentiality of
transport-layer segments.
Recall that the Internet makes two distinct transport-layer protocols available to
the application layer. One of these protocols is UDP (User Datagram Protocol), which
provides an unreliable, connectionless service to the invoking application. The second of
these protocols is TCP (Transmission Control Protocol), which provides a reliable,
connection-oriented service to the invoking application. When designing a network
application, the application developer must specify one of these two transport protocols.
To simplify terminology, we refer to the transport-layer packet as a segment. We
mention, however, that the Internet literature (for example, the RFCs) also refers to the
transport-layer packet for TCP as a segment but often refers to the packet for UDP as a
datagram. However, this same Internet literature also uses the term datagram for the
network-layer packet! For an introductory book on computer networking such as this, we
believe that it is less confusing to refer to both TCP and UDP packets as segments, and
reserve the term datagram for the network-layer packet.
Before proceeding with our brief introduction of UDP and TCP, it will be useful
to say a few words about the Internet’s network layer. The Internet’s network-layer
protocol has a name—IP, for Internet Protocol. IP provides logical communication
between hosts. The IP service model is a best-effort delivery service. This means that IP
makes its “best effort” to deliver segments between communicating hosts, but it makes no
guarantees. In particular, it does not guarantee segment delivery, it does not guarantee
orderly delivery of segments, and it does not guarantee the integrity of the data in the
segments. For these reasons, IP is said to be an unreliable service. We also mention here
that every host has at least one network-layer address, a so-called IP address.
Having taken a glimpse at the IP service model, let’s now summarize the service
models provided by UDP and TCP. The most fundamental responsibility of UDP and
TCP is to extend IP’s delivery service between two end systems to a delivery service
between two processes running on the end systems. Extending host-to-host delivery to
process-to-process delivery is called transport-layer multiplexing and DE multiplexing.
We’ll discuss transport-layer multiplexing and DE multiplexing. UDP and TCP also
provide integrity checking by including error detection fields in their segments’ headers.
These two minimal transport-layer services—process-to-process data delivery and error
checking—are the only two services that UDP provides! In particular, like IP, UDP is an
unreliable service—it does not guarantee that data sent by one process will arrive intact
(or at all!).
TCP, on the other hand, offers several additional services to applications. First
and foremost, it provides reliable data transfer. Using flow control, sequence numbers,
acknowledgments, and timers, TCP ensures that data is delivered from sending process to
receiving process, correctly and in order. TCP thus converts IP’s unreliable service
between end systems into a reliable data transport service between processes. TCP also
provides congestion control. Congestion control is not so much a service provided to the
invoking application as it is a service for the Internet as a whole, a service for the general
good. Loosely speaking, TCP congestion control prevents any one TCP connection from
swamping the links and routers between communicating hosts with an excessive amount
of traffic. TCP strives to give each connection traversing a congested link an equal share
of the link bandwidth. This is done by regulating the rate at which the sending sides of
TCP connections can send traffic into the network. UDP traffic, on the other hand, is
unregulated. An application using UDP transport can send at any rate it pleases, for as
long as it pleases.
A protocol that provides reliable data transfer and congestion control is
necessarily complex. We’ll need several sections to cover the principles of reliable data
transfer and congestion control, and additional sections to cover the TCP protocol itself...
The approach taken in this is to alternate between basic principles and the TCP protocol.
For example, we’ll first discuss reliable data transfer in a general setting and then discuss
how TCP specifically provides reliable data transfer. Similarly, we’ll first discuss
congestion control in a general setting and then discuss how TCP performs congestion
control. But before getting into all this good stuff, let’s first look at transport layer
multiplexing and DE multiplexing.
b. Multiplexing and DE multiplexing
At the destination host, the transport layer receives segments from the network
layer just below. The transport layer has the responsibility of delivering the data in these
segments to the appropriate application process running in the host. Let’s take a look at
an example. Suppose you are sitting in front of your computer, and you are downloading
Web pages while running one FTP session and two Telnet sessions. You therefore have
four network application processes running—two Telnet processes, one FTP process, and
one HTTP process. When the transport layer in your computer receives data from the
network layer below, it needs to direct the received data to one of these four processes.
Let’s now examine how this is done.
First recall that a process (as part of a network application) can have one or more
sockets, doors through which data passes from the network to the process and through
which data passes from the process to the network. The transport layer in the receiving
host does not actually deliver data directly to a process, but instead to an intermediary
socket. Because at any given time there can be more than one socket in the receiving
host, each socket has a unique identifier. The format of the identifier depends on whether
the socket is a UDP or a TCP socket, as we’ll discuss shortly.
Now let’s consider how a receiving host directs an incoming transport-layer
segment to the appropriate socket. Each transport-layer segment has a set of fields in the
segment for this purpose. At the receiving end, the transport layer examines these fields
to identify the receiving socket and then directs the segment to that socket. This job of
delivering the data in a transport-layer segment to the correct socket is called DE
multiplexing. The job of gathering data chunks at the source host from different sockets,
encapsulating each data chunk with header information (that will later be used in DE
multiplexing) to create segments, and passing the segments to the network layer is called
multiplexing. Note that the transport layer in the middle host must DE multiplex
segments arriving from the network layer below to either process P1 or P2 above; this is
done by directing the arriving segment’s data to the corresponding process’s socket. The
transport layer in the middle host must also gather outgoing data from these sockets, form
transport-layer segments, and pass these segments down to the network layer. Although
we have introduced multiplexing and DE multiplexing in the context of the Internet
transport protocols, it’s important to realize that they are concerns whenever a single
protocol at one layer (at the transport layer or elsewhere) is used by multiple protocols at
the next higher layer.
To illustrate the DE multiplexing job, recall the household analogy in the previous
section. Each of the kids is identified by his or her name. When Bill receives a batch of
mail from the mail carrier, he performs a DE multiplexing operation by observing to
whom the letters are addressed and then hand delivering the mail to his brothers and
sisters. Ann performs a multiplexing operation when she collects letters from her brothers
and sisters and gives the collected mail to the mail person.
Now that we understand the roles of transport-layer multiplexing and DE
multiplexing, let us examine how it is actually done in a host. From the discussion above,
we know that transport-layer multiplexing requires (1) that sockets have unique
identifiers, and (2) that each segment have special fields that indicate the socket to which
the segment is to be delivered. These special fields are the source port number field and
the destination port number field. Each port number is a 16-bit number, ranging from 0 to
65535. The port numbers ranging from 0 to 1023 are called well-known port numbers
and are restricted, which means that they are reserved for use by well-known application
protocols such as HTTP (which uses port number 80) and FTP (which uses port number
21). The list of well-known port numbers is given in RFC 1700 and is updated at
http://www.iana.org [RFC 3232]. When we develop a new application, we must assign
the application a port number.
It should now be clear how the transport layer could implement the DE
multiplexing service: Each socket in the host could be assigned a port number, and when
a segment arrives at the host, the transport layer examines the destination port number in
the segment and directs the segment to the corresponding socket. The segment’s data then
passes through the socket into the attached process. As we’ll see, this is basically how
UDP does it. However, we’ll also see that multiplexing/ DE multiplexing in TCP is yet
more subtle.
With port numbers assigned to UDP sockets, we can now precisely describe UDP
multiplexing/DE multiplexing. Suppose a process in Host A, with UDP port 19157,
wants to send a chunk of application data to a process with UDP port 46428 in Host B.
The transport layer in Host A creates a transport-layer segment that includes the
application data, the source port number (19157), the destination port number (46428),
and two other values (which will be discussed later, but are unimportant for the current
discussion). The transport layer then passes the resulting segment to the network layer.
The network layer encapsulates the segment in an IP datagram and makes a best-effort
attempt to deliver the segment to the receiving host. If the segment arrives at the
receiving Host B, the transport layer at the receiving host examines the destination port
number in the segment (46428) and delivers the segment to its socket identified by port
46428. Note that Host B could be running multiple processes, each with its own UDP
socket and associated port number. As UDP segments arrive from the network, Host B
directs (DE multiplexes) each segment to the appropriate socket by examining the
segment’s destination port number.
It is important to note that a UDP socket is fully identified by a two-tuple
consisting of a destination IP address and a destination port number. As a consequence, if
two UDP segments have different source IP addresses and/or source port numbers, but
have the same destination IP address and destination port number, then the two segments
will be directed to the same destination process via the same destination socket.
You may be wondering now, what is the purpose of the source port number? In
the A-to-B segment the source port number serves as part of a “return address”—when B
wants to send a segment back to A, the destination port in the B-to-A segment will take
its value from the source port value of the A-to-B segment. (The complete return address
is A’s IP address and the source port number.) As an example, recall the UDP server
program studied. In UDPServer.py, the server uses the recvfrom() method to extract the
clientside (source) port number from the segment it receives from the client; it then sends
a new segment to the client, with the extracted source port number serving as the
destination port number in this new segment.
In order to understand TCP demultiplexing, we have to take a close look at TCP
sockets and TCP connection establishment. One subtle difference between a TCP socket
and a UDP socket is that a TCP socket is identified by a four-tuple: (source IP address,
source port number, destination IP address, destination port number). Thus, when a TCP
segment arrives from the network to a host, the host uses all four values to direct
(demultiplex) the segment to the appropriate socket.
Before closing this discussion, it’s instructive to say a few additional words about
Web servers and how they use port numbers. Consider a host running a Web server, such
as an Apache Web server, on port 80. When clients (for example, browsers) send
segments to the server, all segments will have destination port 80. In particular, both the
initial connection-establishment segments and the segments carrying HTTP request
messages will have destination port 80. As we have just described, the server
distinguishes the segments from the different clients using source IP addresses and source
port numbers.
Each of these processes has its own connection socket through which HTTP
requests arrive and HTTP responses are sent. We mention, however, that there is not
always a one-to-one correspondence between connection sockets and processes. In fact,
today’s high-performing Web servers often use only one process, and create a new thread
with a new connection socket for each new client connection. (A thread can be viewed as
a lightweight subprocess.)
If the client and server are using persistent HTTP, then throughout the duration of
the persistent connection the client and server exchange HTTP messages via the same
server socket. However, if the client and server use non-persistent HTTP, then a new
TCP connection is created and closed for every request/response, and hence a new socket
is created and later closed for every request/response. This frequent creating and closing
of sockets can severely impact the performance of a busy Web server (although a number
of operating system tricks can be used to mitigate the problem). Readers interested in the
operating system issues surrounding persistent and non-persistent HTTP are encouraged
to see [Nielsen 1997; Nahum 2002].
Now that we’ve discussed transport-layer multiplexing and demultiplexing, let’s
move on and discuss one of the Internet’s transport protocols, UDP. In the next section,
we’ll see that UDP adds little more to the network-layer protocol than a
multiplexing/demultiplexing service.
c. Connectionless Transport: UDP
To motivate our discussion about UDP, suppose you were interested in designing
a no-frills, bare-bones transport protocol. How might you go about doing this? You might
first consider using a vacuous transport protocol. In particular, on the sending side, you
might consider taking the messages from the application process and passing them
directly to the network layer; and on the receiving side, you might consider taking the
messages arriving from the network layer and passing them directly to the application
process. But as we learned in the previous section, we haveto do a little more than
nothing! At the very least, the transport layer has to provide a
multiplexing/demultiplexing service in order to pass data between the network layer and
the correct application-level process.
UDP, defined in [RFC 768], does just about as little as a transport protocol can
do. Aside from the multiplexing/demultiplexing function and some light error checking,
it adds nothing to IP. In fact, if the application developer chooses UDP instead of TCP,
then the application is almost directly talking with IP. UDP takes messages from the
application process, attaches source and destination port number fields for the
multiplexing/demultiplexing service, adds two other small fields, and passes the resulting
segment to the network layer. The network layer encapsulates the transport-layer segment
into an IP datagram and then makes a best-effort attempt to deliver the segment to the
receiving host. If the segment arrives at the receiving host, UDP uses the destination port
number to deliver the segment’s data to the correct application process. Note that with
UDP there is no handshaking between sending and receiving transport-layer entities
before sending a segment. For this reason, UDP is said to be connectionless.
DNS is an example of an application-layer protocol that typically uses UDP.
When the DNS application in a host wants to make a query, it constructs a DNS query
message and passes the message to UDP. Without performing any handshaking with the
UDP entity running on the destination end system, the host-side UDP adds header fields
to the message and passes the resulting segment to the network layer. The network layer
encapsulates the UDP segment into a datagram and sends the datagram to a name server.
The DNS application at the querying host then waits for a reply to its query. If it doesn’t
receive a reply (possibly because the underlying network lost the query or the reply), it
might try resending the query, try sending the query to another name server, or inform the
invoking application that it can’t get a reply.
As we expect, e-mail, remote terminal access, and file transfer run over TCP—all
these applications need the reliable data transfer service of TCP. That early versions of
HTTP ran over TCP but that more recent versions of HTTP run over UDP, providing
their own error control and congestion control (among other services) at the application
layer. Nevertheless, many important applications run over UDP rather than TCP. For
example, UDP is used to carry network management data. UDP is preferred to TCP in
this case, since network management applications must often run when the network is in
a stressed state—precisely when reliable, congestion-controlled data transfer is difficult
to achieve. Also, as we mentioned earlier, DNS runs over UDP, thereby avoiding TCP’s
connection-establishment delays.
UDP and TCP are sometimes used today with multimedia applications, such as
Internet phone, real-time video conferencing, and streaming of stored audio and video.
We just mention now that all of these applications can tolerate a small amount of packet
loss, so that reliable data transfer is not absolutely critical for the application’s success.
Furthermore, real-time applications, like Internet phone and video conferencing, react
very poorly to TCP’s congestion control. For these reasons, developers of multimedia
applications may choose to run their applications over UDP instead of TCP. When packet
loss rates are low, and with some organizations blocking UDP traffic for security reasons,
TCP becomes an increasingly attractive protocol for streaming media transport.
Although commonly done today, running multimedia applications over UDP
needs to be done with care. As we mentioned above, UDP has no congestion control. But
congestion control is needed to prevent the network from entering a congested state in
which very little useful work is done. If everyone were to start streaming high-bit-rate
video without using any congestion control, there would be so much packet overflow at
routers that very few UDP packets would successfully traverse the source-to-destination
path. Moreover, the high loss rates induced by the uncontrolled UDP senders would
cause the TCP senders (which, as we’ll see, do decrease their sending rates in the face of
congestion) to dramatically decrease their rates. Thus, the lack of congestion control in
UDP can result in high loss rates between a UDP sender and receiver, and the crowding
out of TCP sessions. Many researchers have proposed new mechanisms to force all
sources, including UDP sources, to perform adaptive congestion control [Mahdavi 1997;
Floyd 2000; Kohler 2006: RFC 4340].
Before discussing the UDP segment structure, we mention that it is possible for an
application to have reliable data transfer when using UDP. This can be done if reliability
is built into the application itself (for example, by adding acknowledgment and
retransmission mechanisms, such as those we’ll study in the next section). We mentioned
earlier that the QUIC protocol implements reliability in an application-layer protocol on
top of UDP. But this is a nontrivial task that would keep an application developer busy
debugging for a long time. Nevertheless, building reliability directly into the application
allows the application to “have its cake and eat it too.” That is, application processes can
communicate reliably without being subjected to the transmission-rate constraints
imposed by TCP’s congestion-control mechanism.
The UDP segment structure is defined in RFC 768. The application data occupies
the data field of the UDP segment. For example, for DNS, the data field contains either a
query message or a response message. For a streaming audio application, audio samples
fill the data field. The UDP header has only four fields, each consisting of two bytes. As
discussed in the previous section, the port numbers allow the destination host to pass the
application data to the correct process running on the destination end system (that is, to
perform the demultiplexing function). The length field specifies the number of bytes in
the UDP segment (header plus data). An explicit length value is needed since the size of
the data field may differ from one UDP segment to the next. The checksum is used by the
receiving host to check whether errors have been introduced into the segment. In truth,
the checksum is also calculated over a few of the fields in the IP header in addition to the
UDP segment. But we ignore this detail in order to see the forest through the trees. We’ll
discuss the checksum calculation below.
The UDP checksum provides for error detection. That is, the checksum is used to
determine whether bits within the UDP segment have been altered (for example, by noise
in the links or while stored in a router) as it moved from source to destination. UDP at the
sender side performs the 1s complement of the sum of all the 16-bit words in the
segment, with any overflow encountered during the sum being wrapped around. This
result is put in the checksum field of the UDP segment. Here we give a simple example
of the checksum calculation. You can find details about efficient implementation of the
calculation in RFC 1071 and performance over real data in [Stone 1998; Stone 2000].
Note that this last addition had overflow, which was wrapped around. The 1s
complement is obtained by converting all the 0s to 1s and converting all the 1s to 0s.
Thus, the 1s complement of the sum 0100101011000010 is 1011010100111101, which
becomes the checksum. At the receiver, all four 16-bit words are added, including the
checksum. If no errors are introduced into the packet, then clearly the sum at the receiver
will be 1111111111111111. If one of the bits is a 0, then we know that errors have been
introduced into the packet.
You may wonder why UDP provides a checksum in the first place, as many link-
layer protocols (including the popular Ethernet protocol) also provide error checking. The
reason is that there is no guarantee that all the links between source and destination
provide error checking; that is, one of the links may use a link-layer protocol that does
not provide error checking. Furthermore, even if segments are correctly transferred across
a link, it’s possible that bit errors could be introduced when a segment is stored in a
router’s memory. Given that neither link-by-link reliability nor in-memory error detection
is guaranteed, UDP must provide error detection at the transport layer, on an end-end
basis, if the end-end data transfer service is to provide error detection. This is an example
of the celebrated end-end principle in system design [Saltzer 1984], which states that
since certain functionality (error detection, in this case) must be implemented on an end-
end basis: “functions placed at the lower levels may be redundant or of little value when
compared to the cost of providing them at the higher level.”
Because IP is supposed to run over just about any layer-2 protocol, it is useful for
the transport layer to provide error checking as a safety measure. Although UDP provides
error checking, it does not do anything to recover from an error. Some implementations
of UDP simply discard the damaged segment; others pass the damaged segment to the
application with a warning. That wraps up our discussion of UDP. We will soon see that
TCP offers reliable data transfer to its applications as well as other services that UDP
doesn’t offer. Naturally, TCP is also more complex than UDP. Before discussing TCP,
however, it will be useful to step back and first discuss the underlying principles of
reliable data transfer.
d. Principles of Reliable Data Transfer
In this section, we consider the problem of reliable data transfer in a general
context. This is appropriate since the problem of implementing reliable data transfer
occurs not only at the transport layer, but also at the link layer and the application layer as
well. The general problem is thus of central importance to networking. Indeed, if one had
to identify a “top-ten” list of fundamentally important problems in all of networking, this
would be a candidate to lead the list. In the next section, we’ll examine TCP and show, in
particular, that TCP exploits many of the principles that we are about to describe.
The service abstraction provided to the upper-layer entities is that of a reliable
channel through which data can be transferred. With a reliable channel, no transferred
data bits are corrupted (flipped from 0 to 1, or vice versa) or lost, and all are delivered in
the order in which they were sent. This is precisely the service model offered by TCP to
the Internet applications that invoke it.
It is the responsibility of a reliable data transfer protocol to implement this service
abstraction. This task is made difficult by the fact that the layer below the reliable data
transfer protocol may be unreliable. For example, TCP is a reliable data transfer protocol
that is implemented on top of an unreliable (IP) end-to-end network layer. More
generally, the layer beneath the two reliably communicating end points might consist of a
single physical link (as in the case of a link-level data transfer protocol) or a global
internetwork (as in the case of a transport-level protocol). For our purposes, however, we
can view this lower layer simply as an unreliable point to-point channel.
In this section, we will incrementally develop the sender and receiver sides of a
reliable data transfer protocol, considering increasingly complex models of the
underlying channel. For example, we’ll consider what protocol mechanisms areneeded
when the underlying channel can corrupt bits or lose entire packets. One assumption
we’ll adopt throughout our discussion here is that packets will be delivered in the order in
which they were sent, with some packets possibly being lost; that is, the underlying
channel will not reorder packets. The interfaces for our data transfer protocol. The
sending side of the data transfer protocol will be invoked from above by a call to
rdt_send(). It will pass the data to be delivered to the upper layer at the receiving side.
(Here rdt stands for reliable data transfer protocol and _send indicates that the sending
side of rdt is being called. The first step in developing any protocol is to choose a good
name!) On the receiving side, rdt_rcv() will be called when a packet arrives from the
receiving side of the channel. When the rdt protocol wants to deliver data to the upper
layer, it will do so by calling deliver_data(). In the following, we use the terminology
“packet” rather than transport-layer “segment.” Because the theory developed in this
section applies to computer networks in general and not just to the Internet transport
layer, the generic term “packet” is perhaps more appropriate here.
In this section, we consider only the case of unidirectional data transfer, that is,
data transfer from the sending to the receiving side. The case of reliable bidirectional
(that is, full-duplex) data transfer is conceptually no more difficult but considerably more
tedious to explain. Although we consider only unidirectional data transfer, it is important
to note that the sending and receiving sides of our protocol will nonetheless need to
transmit packets in both directions. We will see shortly that, in addition to exchanging
packets containing the data to be transferred, the sending and receiving sides of rdt will
also need to exchange control packets back and forth. Both the send and receive sides of
rdt send packets to the other side by a call to udt_send() (where udt stands for unreliable
data transfer).
We first consider the simplest case, in which the underlying channel is completely
reliable. The protocol itself, which we’ll call rdt1.0, is trivial. The finite-state machine
(FSM) definitions for the rdt1.0 sender and receiver. The FSM in defines the operation of
the sender, while defines the operation of the receiver. It is important to note that there
are separate FSMs for the sender and for the receiver. The sender and receiver FSM each
have just one state. The arrows in the FSM description indicate the transition of the
protocol from one state to another.
The event causing the transition is shown above the horizontal line labeling the
transition, and the actions taken when the event occurs are shown below the horizontal
line. When no action is taken on an event, or no event occurs and an action is taken, we’ll
use the symbol Λ below or above the horizontal, respectively, to explicitly denote the
lack of an action or event. The initial state of the FSM is indicated by the dashed arrow.
Although the FSMs have but one state, the FSMs we will see shortly have multiple states,
so it will be important to identify the initial state of each FSM.
A more realistic model of the underlying channel is one in which bits in a packet
may be corrupted. Such bit errors typically occur in the physical components of a
network as a packet is transmitted, propagates, or is buffered. We’ll continue to assume
for the moment that all transmitted packets are received (although their bits may be
corrupted) in the order in which they were sent.
Before developing a protocol for reliably communicating over such a channel,
first consider how people might deal with such a situation. Consider how you
yourselfmight dictate a long message over the phone. In a typical scenario, the message
taker might say “OK” after each sentence has been heard, understood, and recorded. If
the message taker hears a garbled sentence, you’re asked to repeat the garbled sentence.
This message-dictation protocol uses both positive acknowledgments (“OK”) and
negative acknowledgments (“Please repeat that.”). These control messages allow the
receiver to let the sender know what has been received correctly, and what has been
received in error and thus requires repeating. In a computer network setting, reliable data
transfer protocols based on such retransmission are known as ARQ (Automatic Repeat
reQuest) protocols.
Protocol rdt3.0 is a functionally correct protocol, but it is unlikely that anyone
would be happy with its performance, particularly in today’s high-speed networks. At the
heart of rdt3.0’s performance problem is the fact that it is a stop-and-wait protocol.
To appreciate the performance impact of this stop-and-wait behavior, consider an
idealized case of two hosts, one located on the West Coast of the United States and the
other located on the East Coast. The speed-of-light round-trip propagation delay between
these two end systems, RTT, is approximately 30 milliseconds. Suppose that they are
connected by a channel with a transmission rate, R, of 1 Gbps (109 bits per second).
The packet then makes its 15-msec cross-country journey, with the last bit of the
packet emerging at the receiver at t = RTT/2 + L/R = 15.008 msec. Assuming for
simplicity that ACK packets are extremely small (so that we can ignore their transmission
time) and that the receiver can send an ACK as soon as the last bit of a data packet is
received, the ACK emerges back at the sender at t = RTT + L/R = 30.008 msec. At this
point, the sender can now transmit the next message. Thus, in 30.008 msec, the sender
was sending for only 0.008 msec.
That is, the sender was busy only 2.7 hundredths of one percent of the time!
Viewed another way, the sender was able to send only 1,000 bytes in 30.008
milliseconds, an effective throughput of only 267 kbps—even though a 1 Gbps link was
available! Imagine the unhappy network manager who just paid a fortune for a gigabit
capacity link but manages to get a throughput of only 267 kilobits per second! This is a
graphic example of how network protocols can limit the capabilities provided by the
underlying network hardware. Also, we have neglected lowerlayer protocol-processing
times at the sender and receiver, as well as the processing and queuing delays that would
occur at any intermediate routers between the sender and receiver. Including these effects
would serve only to further increase the delay and further accentuate the poor
performance.
In a Go-Back-N (GBN) protocol, the sender is allowed to transmit multiple
packets (when available) without waiting for an acknowledgment, but is constrained to
have no more than some maximum allowable number, N, of unacknowledged packets in
the pipeline. We describe the GBN protocol in some detail in this section. But before
reading on, you are encouraged to play with the GBN animation (an awesome interactive
animation) at the companion Web site.
In practice, a packet’s sequence number is carried in a fixed-length field in the
packet header. If k is the number of bits in the packet sequence number field, the range of
sequence numbers is thus [0,2k - 1]. With a finite range of sequence numbers, all
arithmetic involving sequence numbers must then be done using modulo 2k arithmetic.
(That is, the sequence number space can be thought of as a ring of size 2k , where
sequence number 2k - 1 is immediately followed by sequence number 0.) Recall that
rdt3.0 had a 1-bit sequence number and a range of sequence numbers of [0,1]. Several of
the problems at the end of this explore the consequences of a finite range of sequence
numbers. We will that TCP has a 32-bit sequence number field, where TCP sequence
numbers count bytes in the byte stream rather than packets.
The receiver’s actions in GBN are also simple. If a packet with sequence number
n is received correctly and is in order (that is, the data last delivered to the upper layer
came from a packet with sequence number n - 1), the receiver sends an ACK for packet n
and delivers the data portion of the packet to the upper layer. In all other cases, the
receiver discards the packet and resends an ACK for the most recently received in-order
packet. Note that since packets are delivered one at a time to the upper layer, if packet k
has been received and delivered, then all packets with a sequence number lower than k
have also been delivered. Thus, the use of cumulative acknowledgments is a natural
choice for GBN.
In our GBN protocol, the receiver discards out-of-order packets. Although it may
seem silly and wasteful to discard a correctly received (but out-of-order) packet, there is
some justification for doing so. Recall that the receiver must deliver data in order to the
upper layer. Suppose now that packet n is expected, but packet n + 1 arrives. Because
data must be delivered in order, the receiver could buffer (save) packet n + 1 and then
deliver this packet to the upper layer after it had later received and delivered packet n.
However, if packet n is lost, both it and packet n + 1 will eventually be retransmitted as a
result of the GBN retransmission rule at the sender. Thus, the receiver can simply discard
packet n + 1. The advantage of this approach is the simplicity of receiver buffering—the
receiver need not buffer any out-of-order packets. Thus, while the sender must maintain
the upper and lower bounds of its window and the position of nextseqnum within this
window, the only piece of information the receiver need maintain is the sequence number
of the next in-order packet. This value is held in the variable expectedseqnum, shown in
the receiver FSM. Of course, the disadvantage of throwing away a correctly received
packet is that the subsequent retransmission of that packet might be lost or garbled and
thus even more retransmissions would be required.
Because of this window size limitation, the sender sends packets 0 through 3 but
then must wait for one or more of these packets to be acknowledged before proceeding.
As each successive ACK (for example, ACK0 and ACK1) is received, the window slides
forward and the sender can transmit one new packet (pkt4 and pkt5, respectively). On the
receiver side, packet 2 is lost and thus packets 3, 4, and 5 are found to be out of order and
are discarded.
Before closing our discussion of GBN, it is worth noting that an implementation
of this protocol in a protocol stack would likely have a structure similar to that of the
extended FSM. The implementation would also likely be in the form of various
procedures that implement the actions to be taken in response to the various events that
can occur. In such event-based programming, the various procedures are called (invoked)
either by other procedures in the protocol stack, or as the result of an interrupt. In the
sender, these events would be (1) a call from the upper-layer entity to invoke rdt_send(),
(2) a timer interrupt, and (3) a call from the lower layer to invoke rdt_rcv() when a packet
arrives. The programming exercises at the end of this will give you a chance to actually
implement these routines in a simulated, but realistic, network setting.
We note here that the GBN protocol incorporates almost all of the techniques that
we will encounter when we study the reliable data transfer components of TCP in Section
3.5. These techniques include the use of sequence numbers, cumulative
acknowledgments, checksums, and a timeout/retransmit operation.
The GBN protocol allows the sender to potentially “fill the pipeline” in
with packets, thus avoiding the channel utilization problems we noted with stop
and-wait protocols. There are, however, scenarios in which GBN itself suffers from
performance problems. In particular, when the window size and bandwidth-delay product
are both large, many packets can be in the pipeline. A single packet error can thus cause
GBN to retransmit a large number of packets, many unnecessarily. As the probability of
channel errors increases, the pipeline can become filled with these unnecessary
retransmissions. Imagine, in our message-dictation scenario, thatif every time a word was
garbled, the surrounding 1,000 words (for example, a window size of 1,000 words) had to
be repeated. The dictation would be slowed by all of the reiterated words.
e. Connection-Oriented Transport: TCP
Now that we have covered the underlying principles of reliable data transfer, let’s
turn to TCP—the Internet’s transport-layer, connection-oriented, reliable transport
protocol. In this section, we’ll see that in order to provide reliable data transfer, TCP
relies on many of the underlying principles discussed in the previous section, including
error detection, retransmissions, cumulative acknowledgments, timers, and header fields
for sequence and acknowledgment numbers. TCP is defined in RFC 793, RFC 1122, RFC
2018, RFC 5681, and RFC 7323.
TCP is said to be connection-oriented because before one application process can
begin to send data to another, the two processes must first “handshake” with each other—
that is, they must send some preliminary segments to each other to establish the
parameters of the ensuing data transfer. As part of TCP connection establishment, both
sides of the connection will initialize many TCP state variables associated with the TCP
connection.
The TCP “connection” is not an end-to-end TDM or FDM circuit as in a circuit
switched network. Instead, the “connection” is a logical one, with common state residing
only in the TCPs in the two communicating end systems. Recall that because the TCP
protocol runs only in the end systems and not in the intermediate network elements
(routers and link-layer switches), the intermediate network elements do not maintain TCP
connection state. In fact, the intermediate routers are completely oblivious to TCP
connections; they see datagrams, not connections.
A TCP connection provides a full-duplex service: If there is a TCP connection
between Process A on one host and Process B on another host, then application-layer data
can flow from Process A to Process B at the same time as application-layer data flows
from Process B to Process A. A TCP connection is also always point-to-point, that is,
between a single sender and a single receiver. So-called “multicasting” (see the online
supplementary materials for this text)—the transfer of data from one sender too many
receivers in a single send operation—is not possible with TCP. With TCP, two hosts are
company and three are a crowd!
Let’s now take a look at how a TCP connection is established. Suppose a process
running in one host wants to initiate a connection with another process in another host.
Recall that the process that is initiating the connection is called the client process, while
the other process is called the server process. The client application process first informs
the client transport layer that it wants to establish a connect a process in the server.
Recall Python client program does this by issuing the
commandclientSocket.connect((serverName,serverPort)) where serverName is the name
of the server and serverPort identifies the process on the server. TCP in the client then
proceeds to establish a TCP connection with TCP in the server. At the end of this section
we discuss in some detail the connection-establishment procedure. For now it suffices to
know that the client first sends a special TCP segment; the server responds with a second
special TCP segment; and finally the client responds again with a third special segment.
The first two segments carry no payload, that is, no application-layer data; the third of
these segments may carry a payload. Because three segments are sent between the two
hosts, this connection-establishment procedure is often referred to as a three-way
handshake.
Once a TCP connection is established, the two application processes can send
data to each other. Let’s consider the sending of data from the client process to the server
process. The client process passes a stream of data through the socket (the door of the
process). Once the data passes through the door, the data is in the hands of TCP running
in the client. TCP directs this data to the connection’s send buffer, which is one of the
buffers that is set aside during the initial three-way handshake. From time to time, TCP
will grab chunks of data from the send buffer and pass the data to the network layer.
Interestingly, the TCP specification [RFC 793] is very laid back about specifying when
TCP should actually send buffered data, stating that TCP should “send that data in
segments at its own convenience.” The maximum amount of data that can be grabbed and
placed in a segment is limited by the maximum segment size (MSS). The MSS is
typically set by first determining the length of the largest link-layer frame that can be sent
by the local sending host (the so-called maximum transmission unit, MTU), and then
setting the MSS to ensure that a TCP segment (when encapsulated in an IP datagram)
plus the TCP/IP header length (typically 40 bytes) will fit into a single link-layer frame.
Both Ethernet and PPP link-layer protocols have an MTU of 1,500 bytes. Thus, a typical
value of MSS is 1460 bytes. Approaches have also been proposed for discovering the
path MTU—the largest link-layer frame that can be sent on all links from source to
destination [RFC 1191]—and setting the MSS based on the path MTU value. Note that
the MSS is the maximum amount of application-layer data in the segment, not the
maximum size of the TCP segment including headers. (This terminology is confusing,
but we have to live with it, as it is well entrenched.)
Having taken a brief look at the TCP connection, let’s examine the TCP segment
structure. The TCP segment consists of header fields and a data field. The data field
contains a chunk of application data. As mentioned above, the MSS limits the maximum
size of a segment’s data field. When TCP sends a large file, such as an image as part of a
Web page, it typically breaks the file into chunks of size MSS (except for the last chunk,
which will often be less than the MSS). Interactive applications, however, often transmit
data chunks that are smaller than the MSS; for example, with remote login applications
such as Telnet and ssh, the data field in the TCP segment is often only one byte. Because
the TCP header is typically 20 bytes (12 bytes more than the UDP header), segments sent
by Telnet and ssh may be only 21 bytes in length.
TCP, like our rdt protocol uses a timeout/retransmit mechanism to recover from
lost segments. Although this is conceptually simple, many subtle issues arise when we
implement a timeout/retransmit mechanism in an actual protocol such as TCP. Perhaps
the most obvious question is the length of the timeout intervals. Clearly, the timeout
should be larger than the connection’s round-trip time (RTT), that is, the time from when
a segment is sent until it is acknowledged. Otherwise, unnecessary retransmissions would
be sent. But how much larger? How should the RTT be estimated in the first place?
Should a timer be associated with each and every unacknowledged segment? So many
questions! Our discussion in this section is based on the TCP work in [Jacobson 1988]
and the current IETF recommendations for managing TCP timers [RFC 6298].
Let’s begin our study of TCP timer management by considering how TCP
estimates the round-trip time between sender and receiver. This is accomplished as
follows. The sample RTT, denoted SampleRTT, for a segment is the amount of time
between when the segment is sent (that is, passed to IP) and when an acknowledgment
for the segment is received. Instead of measuring a SampleRTT for every transmitted
segment, most TCP implementations take only one SampleRTT measurement at a time.
That is, at any point in time, the SampleRTT is being estimated for only one of the
transmitted but currently unacknowledged segments, leading to a new value of
SampleRTT approximately once every RTT. Also, TCP never computes a SampleRTT
for a segment that has been retransmitted; it only measures SampleRTT for segments that
have been transmitted once [Karn 1987].
Recall that the Internet’s network-layer service (IP service) is unreliable. IP does
not guarantee datagram delivery, does not guarantee in-order delivery of datagrams, and
does not guarantee the integrity of the data in the datagrams. With IP service, datagrams
can overflow router buffers and never reach their destination, datagrams can arrive out of
order, and bits in the datagram can get corrupted (flipped from 0 to 1 and vice versa).
Because transport-layer segments are carried across the network by IP datagrams,
transport-layer segments can suffer from these problems as well.
TCP creates a reliable data transfer service on top of IP’s unreliable besteffort
service. TCP’s reliable data transfer service ensures that the data stream that a process
reads out of its TCP receive buffer is uncorrupted, without gaps, without duplication, and
in sequence; that is, the byte stream is exactly the same byte stream that was sent by the
end system on the other side of the connection.
We have just described a highly simplified version of how TCP provides reliable
data transfer. But even this highly simplified version has many subtleties. To get a good
feeling for how this protocol works, let’s now walk through a few simple scenarios..
Depicts the first scenario, in which Host A sends one segment to Host B. Suppose that
this segment has sequence number 92 and contains 8 bytes of data. After sending this
segment, Host A waits for a segment from B with acknowledgment number 100.
Although the segment from A is received at B, the acknowledgment from B to A gets
lost. In this case, the timeout event occurs, and Host A retransmits the same segment. Of
course, when Host B receives the retransmission, it observes from the sequence number
that the segment contains data that has already been received. Thus, TCP in Host B will
discard the bytes in the retransmitted segment.
f. Evolution of Transport-Layer Functionality
We’ve seen a rich evolution in the use of TCP over the past decade. We learned
that in addition to “classic” versions of TCP such as TCP Tahoe and Reno, there are now
several newer versions of TCP that have been developed, implemented, deployed, and are
in significant use today. These include TCP CUBIC, DCTCP, CTCP, BBR, and more.
Indeed, measurements in [Yang 2014] indicate that CUBIC (and its predecessor, BIC [Xu
2004]) and CTCP are more widely deployed on Web servers than classic TCP Reno; we
also saw that BBR is being deployed in Google’s internal B4 network, as well as on
many of Google’s public-facing servers.
And there are many (many!) more versions of TCP! There are versions of TCP
specifically designed for use over wireless links, over high-bandwidth paths with large
RTTs, for paths with packet re-ordering, and for short paths strictly within data centers.
There are versions of TCP that implement different priorities among TCPconnections
competing for bandwidth at a bottleneck link, and for TCP connections whose segments
are being sent over different source-destination paths in parallel. There are also variations
of TCP that deal with packet acknowledgment and TCP session establishment/closure
differently than we studied. Indeed, it’s probably not even correct anymore to refer to
“the” TCP protocol; perhaps the only common features of these protocols is that they use
the TCP segment format that we, and that they should compete “fairly” amongst
themselves in the face of network congestion! For a survey of the many flavors of TCP,
see [Afanasyev 2010] and [Narayan 2018].
If the transport services needed by an application don’t quite fit either the UDP or
TCP service models—perhaps an application needs more services than those provided by
UDP but does not want all of the particular functionality that comes with TCP, or may
want different services than those provided by TCP—application designers can always
“roll their own” protocol at the application layer. This is the approach taken in the QUIC
(Quick UDP Internet Connections) protocol [Langley 2017, QUIC 2020]. Specifically,
QUIC is a new application-layer protocol designed from the ground up to improve the
performance of transport-layer services for secure HTTP. QUIC has already been widely
deployed, although is still in the process of being standardized as an Internet RFC [QUIC
2020]. Google has deployed QUIC on many of its public-facing Web servers, in its
mobile video streaming YouTube app, in its Chrome browser, and in Android’s Google
Search app. With more than 7% of Internet traffic today now being QUIC [Langley
2017], we’ll want to take a closer look. Our study of QUIC will also serve as a nice
culmination of our study of the transport layer, as QUIC uses many of the approaches for
reliable data transfer, congestion control, and connection management.
Connection-Oriented and Secure. Like TCP, QUIC is a connection-oriented
protocol between two endpoints. This requires a handshake between endpoints to set up
the QUIC connection state. Two pieces of connection state are the source and destination
connection ID. All QUIC packets are encrypted, and as suggested, QUIC combines the
handshakes needed to establish connection state with those needed for authentication and
encryption (transport layer security topics that, thus providing faster establishment than
the protocol stack, where multiple RTTs are required to first establish a TCP connection,
and then establish a TLS connection over the TCP connection.
Streams. QUIC allows several different application-level “streams” to be
multiplexed through a single QUIC connection, and once a QUIC connection is
established, new streams can be quickly added. A stream is an abstraction for the reliable,
in-order bi-directional delivery of data between two QUIC endpoints. In the context of
HTTP/3, there would be a different stream for each object in a Web page. Each
connection has a connection ID, and each stream within a connection has a stream ID;
both of these IDs are contained in a QUIC packet header (along with other header
information). Data from multiple streams may be contained within a single QUIC
segment, which is carried over UDP. The Stream Control Transmission Protocol (SCTP)
[RFC 4960, RFC 3286] is an earlier reliable, message-oriented protocol that pioneered
the notion of multiplexing multiple application-level “streams” through a single SCTP
connection.
Reliable, TCP-friendly congestion-controlled data transfer. As illustrated in QUIC
provides reliable data transfer to each QUIC stream separately. shows the case of
HTTP/1.1 sending multiple HTTP requests, all over a single TCP connection. Since TCP
provides reliable, in-order byte delivery, this means that the multiple HTTP requests must
be delivered inorder at the destination HTTP server. Thus, if bytes from one HTTP
request are lost, the remaining HTTP requests can not be delivered until those lost bytes
are retransmitted and correctly received by TCP at the HTTP server—the so-called HOL
blocking problem that we encountered earlier. Since QUIC provides a reliable in-order
delivery on a per-stream basis, a lost UDP segment only impacts those streams whose
data was carried in that segment; HTTP messages in other streams can continue to be
received and delivered to the application. QUIC provides reliable data transfer using
acknowledgment mechanisms similar to TCP’s, as specified in [RFC 5681].
QUIC’s congestion control is based on TCP NewReno [RFC 6582], a slight
modification to the TCP Reno protocol that we studied. QUIC’s Draft specification
[QUIC-recovery 2020] notes “Readers familiar with TCP’s loss detection and congestion
control will find algorithms here that parallel well known TCP ones.” Since we’ve
carefully studied TCP’s congestion control in, we’d be right at home reading the details
of QUIC’s draft specification of its congestion control algorithm!
In closing, it’s worth highlighting again that QUIC is an application-layer
protocol providing reliable, congestion-controlled data transfer between two endpoints.
The authors of QUIC [Langley 2017] stress that this means that changes can be made to
QUIC at “application-update timescales,” that is, much faster than TCP or UDP update
timescales.
