[ih] "network unix"

[Jack Haverty]

On 09/27/2016 03:24 PM, Paul Ruizendaal wrote:
> Hi all,
> 
> I'm interested in "Network Unix" as described in RFC681 and here https://archive.org/details/networkunixsyste243kell. My purpose is to understand the early history of networking in Unix, much in the style of Warren Toomey's work on early Unix in general (see http://minnie.tuhs.org/cgi-bin/utree.pl).
> 
> Would anybody know if the source code of this Network Unix survived to the present?
> 
> Many thanks,
> 
> Paul
> _______


Paul also asked me about this off-list, and we thought that my
recollections of the "early history of networking in Unix" might be of
interest to other historians using this list as an archaeological
resource.  So below is what I recently sent to him.  It's all first hand
from my personal experience.  File it under "Networking in the Stone Age
of Computing".

Enjoy,
/Jack Haverty

-----------------------------------

Hi Paul,

Sorry this reply took so long.  I wanted to do a little digging in the
boxes in my basement before answering.

Re: Unix TCPs et al:

I left MIT and joined BBN in the summer of 1977, and my first assignment
was to get TCP running on a PDP-11/40 with V6 Unix.

The TCP effort was part of a large project building a research system
for network security that involved a client/server architecture.   We
had a bunch of LSI-11 systems (used in a variety of projects, the SRI
Packet Radios being developed at that time) 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 someone (not me) thought that the
PDP-11/40 was suitable.  It was there in the lab when I started working
on the TCP implementation.

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 PDP-10s and PDP-11s at MIT in Licklider's
group.  I also had written a lot of code that used the ARPANET in the
70s, 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).

Learning Unix was necessary, and of course a bit of a learning curve.  I
anticipated the need to poke around inside the Unix kernel in order to
implement TCP.   The "network unix" that did NCP at the time wasn't
viable as a base since it wouldn't run on the PDP-11/40.

So I had to learn how the kernel worked.  Since there was no open-source
Unix at the time, the kernel came from ATT 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.  It described the core mechanisms of things like inodes,
forking, etc.  That helped a lot to understand the kernel source code.

The /40 design utilized a single address space for instructions and
data, so everything had to fit in 32KB of memory (yes K, not M or G).
Other machines, e.g., the 11/45 or 11/70, implemented "i-d separation".
This caused instructions to be fetched from a different address space
than data.  That meant that the effective address space for the kernel
was 64K instead of 32K on those larger machines.

Where the NCP kernel mods could fit in a "64KB machine", there wasn't
enough room in the 32K world for much at all after the basic V6 kernel,
which took up most of the memory.  I managed to add what was needed to
get TCP running but it was a struggle.  Every trick in the books was
needed - e.g., I went through the entire kernel and changed all of the
"panic" messages (what it printed out on the console when it crashed) so
they were just short 3 or 4 letter codes rather than sentences.  Every
byte saved helped.

The bulk of the TCP software therefore had to be in user space, with
absolute minimal additions to the Unix kernel.  There just wasn't space
for much.  That was the primary factor influencing the design.   The
design was specific to that 11/40 Unix -- not intended as a general
purpose implementation for Unix on other platforms.

Jim Mathis at SRI had developed a TCP implementation for the LSI-11s
that were the computers used in Packet Radios.  The implementation was a
TCP version 2.5, written in assembler (Macro-11), and designed to run on
top of MOS, which was SRI's operating system for the LSI-11.

All of this work was done under ARPA funding, with Vint Cerf as the ARPA
program manager.  Vint directed SRI to provide me with the LSI-11 TCP,
which Jim happily provided and helped explain how it worked.

So I took Jim's TCP and started to get it running as a user process on
the 11/40.  The core "TCP engine" with the state machine, packet
handling et al was straightforward since the LSI-11 and PDP-11/40 were
essentially the same instruction set.  The bulk of the work was in the
interfaces between that engine and the outside world: the network
interface (a DEC IMP-11A) and the program that was using TCP (Telnet,
FTP, etc.)

With TCP as a user process, and its "customers" other user processes,
the obvious way to interconnect the two is by use of the Unix "pipes"
mechanisms - or actually the "ports" mechanisms developed by Rand to
enable pipe-like interconnects between unrelated processes.

That's where we ran into a Unix deficiency.  Unix had been designed with
the concept of "pipes" as a basic element.  You pump data from a
keyboard or other source into a program, it does its computation, and
pushes the results back out a pipe.  You can string pipes and programs
together.  Each program waits for something to come through its input
pipe ("stdin") and then computes and answer which is sends through the
output pipe ("stdout"), and then goes to read the next input.  If there
is no input, the kernel simply suspends the process until the next input
arrives.

This works well for the classic time-sharing terminal usage where a
human interacts with a program.  But networking is fundamentally
different - you always have two participants generally on different
computers connected by the network.  When the system is idle, there's no
way to tell which participant is going to send data next.

For example, if you consider a basic Telnet connection, there would be
user sitting at a terminal interacting with a program on some remote
computer.  The TCP software would be in the middle.  When things
"quieted down" and the user, or the program, was thinking, the TCP would
want to go idle, and sleep.  To do that it would simply execute a "read"
command to wait for the next data to arrive, and the Unix kernel will
make the process dormant until that data is ready.  But does the TCP
read from the user side, expecting the user to type next?  Or does it
read from the network side, expecting the remote program (actually the
remote TCP) to send next?  There's no way to tell.

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) be able to have multiple simultaneous I/O activities
without the risk of the TCP process being blocked waiting in a read or
write on any particular I/O channel.

Of course it all had to fit into the 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 other words, the process could do a READ or WRITE
without danger of being blocked by the kernel.

CAPAC was the complementary function that allowed a process to determine
exactly how much data it could READ or WRITE without blocking.

With these two functions, it was possible to implement the TCP as a user
process.   Randy and I actually wrote a paper about this:

Haverty, J.F. and Rettberg, R.D., "Interprocess communications for a
server in UNIX", Proceedings IEEE Computer Society International
Conference on Computer Communications Networks, September 1978, 312-315.

That paper talked specifically about Unix and the AWAIT and CAPAC
primitives.  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!

With AWAIT and CAPAC implemented, I brought up the LSI-11 TCP inside our
11/40 and got it running and communicating with the other TCPs for the
project, using the ARPANET for transport.

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 changed the 11/40 TCP to track those modifications.

It's hard to believe, but I actually still have a binder with a
line-printer listing of that Unix TCP which was running on the 11/40.
It's dated March 30, 1979.   That's probably about the time we ended
that project that was using TCP and decommissioned the 11/40.

I've been meaning to scan that listing and get it online.....maybe this
winter.

The 11/40 implementation was far from being high performance.  Shortly
after I got it running I did some performance tests with a stopwatch.
That TCP could achieve the blazing fast speed of 11 bits/second.  Yes,
bits....

That motivated a bit more digging around in the Unix kernel.  What I
discovered was that the pipes/ports implementation was also pretty
basic.  It was built on top of the file system, and a pipe was basically
a file with a few pointers kept in the kernel to make sure that the
reader never got ahead of the writer.  The problem was that, since it
was just a file, the kernel felt obliged to write it out to disk, and it
would block the reader/writer processes as needed to wait for the disk
I/O.  Our PDP-11/40 had an RK05 cartridge disk, which was far from being
fast.  Hence, 11 bits/second was the result.

Changing a few more kernel "panic" messages freed up a few more bytes
and I added a few more instructions to prevent the file from ever being
written to disk.

Vint and I were working closely at the time, so I had kept him aware of
these obstacles and the need to get a "real" TCP implementation for the
newer, more capable machines.  User-level TCP worked, but it really
should be integrated into the kernel, which could be done with the newer
machines.

Vint added several TCP-related tasks to our contract at BBN.  One was
the Vax TCP (which Rob Gurwitz took on).  Another was the HP-3000 TCP
(HP/UX variant of Unix) which John Sax and Winston Edmond built.  In
addition, Ed Cain, who was a manager at the Defense Communications
Engineering Center (DCEC), initiated a project to build TCP for the
11/70 Unix, which Mike Wingfield and Al Nemeth did.

So there were 4 separate Unix TCP implementations done at BBN.  My 11/40
one was first, and proved that although you could implement TCP on 11/40
Unix, it was not appropriate for general use in more powerful systems.
The others happened mostly concurrently.  Rob's Vax implementation was
probably started second, with the HP and 11/70 versions not far behind.
This was part of a concerted effort on DARPA (and DCA/DCEC's) part to
make Unix implementations more widely available so that it would be
easier for people to start using TCP.

ARPA was also funding the work at Berkeley to create BSD Unix, and all
of this prior work was made available to them (in the same way that I
got Jim Mathis' LSI-11 TCP for possible use in Unix).  But I have no
idea what of that, if anything, they might have used in creating their code.

Hope this helps!

/Jack