next up previous contents
Next: 3.3 Multimedia Protocols Up: 3 Literature Review Previous: 3.1 Introduction to Internetworking

3.2 The Development of TCP/IP

This section will trace the development of TCP/IP through specific enhancements made to the Transmission Control Protocol. Version numbers of the networking code released by Berkeley Software Distribution will be used as milestones in TCP/IP's development, as most implementations of UNIX have tracked Berkeley's improvements. Figure 3.7 shows TCP/IP's timeline and the revision increments that will be considered here.

Figure 3.7: The TCP/IP Version Timeline

Figure 3.8: Number of computers connected to the Internet.

As Internet usage increased exponentially, so did the congestion problems. Comer relates the exponentiality of the expansion in chart form, the numbers are reproduced here as the logarithmic plot in figure 3.8gif. This growth manifested itself as periods of lowered bandwidth and increased delays, and caused researchers at Lawrence Berkeley Laboratories (LBL) to question the mechanism employed by the current implementation of TCP to combat congestion. Most of the improvements made to TCP were instigated by this group, led by Van Jacobson, who has achieved nearly deity status in networking circles. As Jacobson and Michael Karels relate in Congestion Avoidance and Control:

In October of '86, the Internet had the first of what became a series of 'congestion collapses'. During this period, the data throughput from LBL [Lawrence Berkeley Laboratories] to UC Berkeley (sites separated by 400 yards and two IMP hops) dropped from 32 Kbps to 40bps. We were fascinated by this sudden factor-of-thousand drop in bandwidth and embarked on an investigation of why things had gotten so bad. In particular, we wondered if the 4.3bsd (Berkeley UNIX) TCP was mis-behaving or if it could be tuned to work better under abysmal network conditions. The answer to both of these questions was ``yes''.[19]

The specific improvements made to TCP that are important within the context of this document are listed in chronological order in table 3.2.


4.2BSD Many of the implementations of TCP/IP at the time were pulled together to create the first widely available (and used) version of TCP/IP.
4.3BSD Tahoe Jacobson's landmark 1996 paper, Congestion Avoidance and Control spawned a number of congestion-related improvements:
4.3BSD Reno Improvements aimed at reducing CPU load and stack times.
4.4BSD Modifications for long, fat networks and gigabit throughput rates.
TCP ``VEGAS'' based upon 4.3BSD Reno source, it utilizes congestion anticipation to achieve a reported 40% to 70% improvement in throughput over Reno.

Table 3.2: Improvements in TCP

3.2.1 Early TCP: 4.2BSD

The Transmission Control Protocol and the Internet Protocol in their earliest incarnations are defined in two Internet Request For Comments (RFCs), RFC793[41] and RFC791[40], respectively. From the introduction of RFC793, the Transmission Control Protocol:

The Transmission Control Protocol (TCP) is intended for use as a highly reliable host-to-host protocol between hosts in packet-switched computer communication networks, and in interconnected systems of such networks.[41, p.1,]

And, more specifically:

TCP is a connection-oriented, end-to-end reliable protocol designed to fit into a layered hierarchy of protocols which support multi-network applications. The TCP provides for reliable inter-process communication between pairs of processes in host computers attached to distinct but interconnected computer communication networks. Very few assumptions are made as to the reliability of the communication protocols below the TCP layer. TCP assumes it can obtain a simple, potentially unreliable datagram service from the lower level protocols. In principle, the TCP should be able to operate above a wide spectrum of communication systems ranging from hard-wired connections to packet-switched or circuit-switched networks.[41, p.1,]

TCP uses layering to hide the details of its reliable, stream-based service from the application layer. It can effectively create a virtual point to point link between two separate processes, either running on the same machine or on separate machines, connected through a physical network. This connection is so reliable that it is often treated, from a programming perspective, as if it were between an application and a file residing on a local disk drive.

TCP works at the byte-level of data. It divides an incoming data stream into packets called segments; similar to datagrams in that each segment is packaged with a full header that is interpretable by TCP, but subtly different in that segments do not create discernible record boundaries, they merely represent sections of a continuous stream of data.

Reliability is insured by a sliding-window acknowledgement and retransmission mechanism. All data sent by TCP must be acknowledged by the receiver at the other end of the connection. TCP maintains a variable-sized window of data that is allowed to exist unacknowledged in the network at any given time. If this limit is reached, no data is sent until an acknowledgement is received. If no data has been acknowledged in a certain amount of time, as detected by the expiration of the Retransmission Time Out (RTO) timer, TCP assumes that the data has become somehow lost or destroyed, and retransmits all of the data in the window.

The original method for calculating the RTO time was rather crude, and could adapt to network loads of at most 30% (equations 3.1, 3.2 and 3.3):




In the above equations, is calculated by passing the measured round trip times (RTT) through what is essentially a low pass filter, rejecting quick changes in the measured round trip times. With usually defaulting to 0.9 and taking its suggested value of 2, 4.2BSD's RTO calculation mechanism left much to be desired during the congestion collapses of the mid 1980's.

3.2.2 4.3BSD Tahoe

4.3BSD Tahoe grew out of optimizations suggested in Jacobson's Congestion Avoidance and Control.[19] This paper set the standard for protocol optimization, and influenced a great deal of subsequent internetworking protocols, including the one developed as part of this MQP. The fundamental points are itemized below:


Much of the time, earlier implementations of TCP would end up initially ``shocking'' a network by sending too much data right off the start. Taking a cue from a standard practice in electrical equipment design where the in-rush of electrical current into a device is desirably limited and slowly increased during a turn-on phase, Jacobson and his fellow researchers created a slow-start mode for TCP that exponentially increases the size of a congestion window. The exponential increase was enough to let TCP feel-out a connection's bandwidth and delay statistics while allowing the network to acclimate itself to the increase in load. Figure 3.2.2 shows Tahoe's slow-start mechanism theoretical throughput vs. time in comparison to 4.2BSD's.

Figure 3.9: The slow-start algorithm of 4.3BSD Tahoe TCP

Retransmission Time Out Estimator


Jacobson's group also made changes to the Retransmission Time Out (RTO) estimation algorithms. The modified algorithm takes RTT variance ( ) into account instead of using a constant value as indicated in the previous section (EQ: 3.3):


The new RTO estimator is capable of adapting to much greater loads. In addition, the entire algorithm was tweaked to utilize integer arithmetic based on computation with scaled powers of two, instead of fractional floating point arithmetic, further reducing CPU load.

Karn's Exponential RTO Back-off Algorithm

Quite often, TCP implementations would worsen network congestion due to multiple, successive retransmits. The RTO estimator is only updated upon receipt of an acknowledgement; if data is continually lost due to high network loading, the data will be retransmitted at constant intervals. Phil Karn, in his implementation of TCP/IP for extremely low-bandwidth, high-delay amateur packet radio usage, developed a strategy that handles multiple retransmits with an exponential back-off of the RTO timer for each successive retransmit.

Dynamic Congestion Window Sizing

Tahoe offered a means of combating congestion through dynamically altering the size of the protocol's sliding window. The algorithm followed three simple rules:

  1. If the RTO expires, set the congestion window size to half of its current size.
  2. Increase the congestion window size by 1 segment for each acknowledgement.
  3. Send the minimum of the receiver's advertised window and congestion window.

The performance of 4.3BSD Tahoe was outstanding. In a Usenet news message, Jacobson expressed the details:

I don't know what would constitute an ``official'' confirmation but maybe I can put some rumors to bed. We have done a TCP that gets 8Mbps between Sun 3/50s (the lowest we've seen is 7Mbps, the highest 9Mbps - when using 100Ethernet exponential back-off makes throughput very sensitive to the competing traffic distribution.) The throughput limit seemed to be the Lance chip on the Sun - the CPU was showing 10-15time. I don't believe the idle time number (I want to really measure the idle time with a uprocessor analyzer) but the interactive response on the machines was pretty good even while they were shoving 1MB/s at each other so I know there was some CPU left over.[Article 167, comp.protocols.tcp-ip, March 1988][21]

3.2.3 4.3BSD Reno

4.3BSD Reno implements both fast recovery/retransmit and header prediction, improvements arguably specific to TCP/IP but bearing little relevance to other communications protocols. Study of these will be avoided here, since the design of this MQP's protocol isn't affected by either enhancement.

3.2.4 4.4BSD with Extensions for High Performance

Internet Request For Comments number 1323 (RFC1323)[28] specified a set of extensions to TCP that attempt to extend its usability on networks with large bandwidth capability and long delay times. Below are listed the relevant suggested optimizations:

The optimizations are presented with the idea that TCP's performance relies on the product of the utilized bandwidth and the round trip delay time, yielding a measure of the amount of data present in the network at any given time. This calculation (equation 3.5) is elucidated in RFC1323:

TCP performance depends not upon the transfer rate itself, but rather upon the product of the transfer rate and the round-trip delay. This ``bandwidth*delay product'' measures the amount of data that would ``fill the pipe;'' it is the buffer space required at sender and receiver to obtain maximum throughput on the TCP connection over the path, i.e., the amount of unacknowledged data that TCP must handle in order to keep the pipeline full. TCP performance problems arise when the bandwidth*delay product is large. We refer to an Internet path operating in this region as a ``long, fat pipe,'' and a network containing this path as an ``LFN'' (pronounced ``elephan(t)''). [28, p.2,]


Window Scaling Option

TCP currently uses a 16-bit unsigned integer in the header of each TCP segment to communicate the size of the receive buffer to the sender. With this limitation, the maximum amount of data allowed in the network's buffers at any one time is 64KBytes; up until recently this hasn't had any detrimental effect on TCP's performance. Even utilizing the full bandwidth of a 10Mbps Ethernet, the round trip time required to fill the window would be in excess of 50ms, an event rarely witnessed on a LAN. However, recent advancements in physical-layer networking technology have made gigabit throughput rates realizable. In the case of a full-bandwidth, 1Gbps transfer rate, TCP's window size would necessitate a round trip time no longer than ; clearly, the effective bandwidth achievable with TCP is theoretically limited by the round trip time delay as . Thus, with a low 1ms RTT, TCP's ultimate achievable bandwidth is 524Kbps.

The TCP window scaling extends the window size to 32 bits, and is predicted to yield acceptable performance for quite some time into the future, tolerating a 34 second round trip time on a 1Gbps link.

Round Trip Time Measurement (RTTM)

Originally, the designers of TCP discarded the idea of per-sequence timestamps because of the compute power required to retrieve data from the system clock. The difficulty in obtaining accurate measurement of round trip time intervals necessary for the determination of the retransmission time was compounded by this lack of timestamps. These days, CPU power has grown to the point where time-stamping is cheap. The implementation of RTTM for TCP adds increased accuracy with very little impact on the compute time budget.

Protect Against Wrapped Sequences (PAWS)

Links with large products utilizing the TCP window scaling option could generate windows so large that there is potential to wrap the 32-bit per-segment sequence number around while data is still waiting in network queues. If this happened, two different segments, both numbered zero, would exist on the network at the same time, making proper acknowledgement impossible.

PAWS makes use of the new TCP timestamps to take both the sequence number and the departure time of segments into account, weeding out duplicate sequence numbers.

3.2.5 The Future: TCP Vegas?

TCP Vegas gif is an implementation of TCP developed at the University of Arizona from 4.3BSD Reno source code. It promises increased throughput over that of the existing TCP implementations largely due to its congestion anticipation mechanism. Vegas's congestion anticipation algorithm dynamically varies the size of the congestion window by monitoring the utilized bandwidth for small changes. This method contrasts with Reno's congestion avoidance mechanism that needs to create losses to vary the congestion window size, Vegas attempts to predict congestion.

Listed below are brief major implementation details:

next up previous contents
Next: 3.3 Multimedia Protocols Up: 3 Literature Review Previous: 3.1 Introduction to Internetworking

Mike Andrews
Wed Mar 19 16:07:58 EST 1997