The experimental BBN-Haverty TCP/IP stack

The TCP/IP stack for V6 Unix done by Jack Haverty at Bolt Beranek & Newman (BBN) appears to be the first TCP/IP stack ever done for Unix. It consisted of a user mode TCP/IP daemon that connected over Rand ports to user processes. There was a standard network library that abstracted the communication with the daemon into a few straightforward procedure calls (TCP_init(), TCP_open(), etc.).

Although Jack's work showed that it conceptually worked, it also made clear that the PDP11/40 with perhaps 256KB of core was too small a machine: the continuous swapping of the daemon and port buffers made the setup painfully slow.

The idea of a user mode TCP/IP daemon was used again in the follow-on BBN-Wingfield implementation. This implementation had the TCP/IP daemon in C, and ran on a PDP11/70 using a full NCP Unix kernel and the await() and capac() extensions pioneered by Haverty.

Source code

The source of the experimental BBN-Haverty TCP/IP Unix has survived as a printout in its March 1979 form. There is currently no machine readable version available.

Emulation

Currently no emulation for this Unix version is available.

History

This section is based on a large post by Jack Haverty on the Internet History mailing list.

The Haverty TCP effort was part of a large project in 1976/77, building a research system for network security that involved a client/server architecture. BBN had a bunch of LSI-11 systems (used in a variety of projects, such as the SRI Packet Radios) that were clients of a server running on a PDP-10 TENEX system. The goal was to move that server function to a much cheaper machine and it was thought at the time that a PDP-11/40 running Unix was suitable option.

Jim Mathis at SRI had developed a TCP implementation for the LSI11 computers used in experimental Packet Radio network. It was known as "TCP11". The implementation was a TCP version 2.5, written in Macro-11, and designed to run on top of "MOS", which was SRI's homegrown operating system for the LSI11. All of this work was done under DARPA funding.

So the plan became to port the Mathis TCP stack to Unix. DARPA directed SRI to provide BBN with the source of TCP11, which SRI happily provided. The project to perform the port was assigned to Jack Haverty. Jack left MIT and joined BBN in the summer of 1977, and his first assignment was to get TCP running on a PDP-11/40 with V6 Unix and Rand ports installed.

Jack recalls: When I began that project, I didn't know much about Unix. I had seen people using it, but hadn't used it myself. I recall that my first impression was that to use Unix you typed strings of gibberish at the console, which somehow made sense to the system. The Unix command language was (is still) pretty complex. I used to speak it fluently, but that was a long time ago... Most of my prior work was on PDP10s and PDP11s at MIT in Licklider's group. I also had written a lot of code that used the ARPANET in the 70's, but hadn't done any of the system programming work on NCP. I hadn't heard of TCP either.

So I guess I was the perfect choice to implement TCP in Unix... anyway that's what I was assigned to do, working with Randy Rettberg (who didn't know anything about Unix either).

I had to learn how the kernel worked. Since there was no open-source Unix at the time, the kernel came from AT&T with lots of restrictions about keeping it confidential, but with no documentation of the internals of the kernel itself. The source code was provided, but it was difficult to figure out the "big picture" of how it operated.

The ARPANET came to the rescue -- I found documentation of some Unix internals that were apparently used in courses at the University of Woolongong -- these would become known as "the Lions book"

Porting TCP11 to Unix

The TCP11 stack supported a single connection at a time and consisted of a connection state machine and packet handling code. It needed extension to multiple concurrent connections for its Unix role.

Fully integrating the TCP11 stack into the V6 kernel looked unfeasible. The extended TCP11 stack was some 10KB {?} in size and including buffers would not fit in the 64KB of address space offered by the PDP11/40.

Because of this Jack decided to put the TCP11 stack in a daemon process that communicated with an IMP on the one hand and with client processes on the other.

The daemon consisted of the TCP11 stack and a support layer that interfaced the stack with standard Unix system calls and provided task scheduling services. However, standard V6 Unix offered very little in terms of IPC facilities. The Rand ports offered a way for a client to connect to the daemon, but this was not enough to make the daemon itself work. Jack had to add several more extensions to the kernel, which are discussed below.

Client processes made use of a library to connect to the daemon. The client library hid all of the IPC complexity and offered a simple function call API, roughly modeled on the TCP implementation done for TENEX. {?}

Extending the kernel

The problem that had to be overcome was that standard V6 Unix relied exclusively on blocking I/O: there was no mechanism to wait for data to arrive on any of a number of open files or pipes.

Jack recalls: Randy and I had to invent a minimalist new function for the Unix kernel to make it possible to write TCP. The basic requirement was that a process (the TCP daemon) be able to have multiple simultaneous I/O activities without the risk of the TCP daemon process being blocked waiting in a read or write on any particular file descriptor.

Of course it all had to fit into the PDP-11/40 kernel space, which meant very, very few instructions. That led to the definitions of two new kernel calls: await() and capac().

The semantics of await() were simple - it was like a "sleep" call but you could specify to be awakened when one or more of a set of I/O channels had changed. For input, that meant there was some data ready to be read. For output, that meant that there was some buffer space available to write data. In essence it was a forerunner of the modern select() system call. The complementary capac() system call allowed a process to determine exactly how much data could be read or written without blocking.

In the words of Jack Haverty: With these two functions, it was possible to implement the TCP stack as a daemon process. From our ARPANET experience, these were the minimum functions needed to enable Unix to be used in network environments. They weren't the ideal API, but they would fit in the 11/40.

First TCP on Unix

Although it was an implementation of TCP2.5 and not the later TCP4, this implementation was probably the first TCP on Unix. Again in the words of Jack Haverty:

My old yellowed lab notebooks have been aging in the basement but they're still readable. Some salient entries:

July 27, 1977: "got TCP11 Unix version to assemble" September 16, 1977: "TCP and Al Spector's TCP can talk fine"

So, if you're curious about when "the first Unix TCP" was created, I'd set September 16, 1977 as the date. That's when my 11/40 TCP first successfully communicated with a TCP on a different machine (an LSI-11). Al Spector was one of the engineers working on that LSI-11 component.

This was a time of rapid change in the TCP world, and as we (the handful of people who did those first TCP implementations) gained experience, we changed the TCP protocol and progressed through TCP 2.5, 2.5+, 2.5+epsilon, and eventually TCP 4 (which is still largely what we have in 2016). I maintained this TCP implementation to track those modifications until March 1979.

Performance issues

Jack soon discovered that the performance of this implementation left to be desired. In initial trials it could achieve 11 bits per second. The main cause for this was the lack of core memory which meant that system was constantly swapping buffers and programs to disk. The relatively low speed of the RK05 drive did not help.

As clients programs and the daemon alternated to run, they tended to push each other out of core to the disk swap area. A second source of inefficiency was that pipes and ports were implemented as a specialization of standard, unnamed files. When disk buffer space ran out, the pending data in a pipe or port was written out to disk and read back as needed. This second issue was mitigated by reducing the capacity of pipes and ports and protecting their buffers from being written out.

On the later and larger PDP-11's these issues were less prominent: more main memory meant that the daemon and clients could stay resident in core most of the time, and there was a more generous pool of disk buffers available.

Legacy

The Defense Communications Engineering Center (DCEC) was tasked with bringing research projects into production where appropriate and it needed a usable TCP implementation for V6/V7 Unix. The BBN-Haverty implementation looked like a reasonable start for this.

Ed Cain, who was a manager at DCEC, initiated a project to build a TCP4 stack for V6/V7 Unix on the larger PDP11 machines with split I/D capability and more memory. This became the BBN-Wingfield implementation, later maintained by DCEC itself until the mid eighties.

Jack Haverty had kept Vint Cerf aware of his experiences and convinced him of the need to get a "real" Unix TCP implementation for the newer, more capable 32-bit machines. User-level TCP worked, but it really should be integrated into the kernel, which could be done with the newer machines.

As a result, DARPA gave BBN a contract for an all new TCP implementation for 4.x BSD. This yielded the BBN-Gurwitz implementation.