Donald Davies' Legacy -- reminisced by members of his team
Mr Derek L A Barber CEng FIEE MBCS MRTS
Erstwhile Director of the European Informatics Network
The presentation will review the origins of packet switching and the political and technical issues that coloured the adoption of what is now, essentially, the basis of today's communications technologies.
Last year the IEEE gave awards to four people involved in the early development of packet switching. Donald Davies, who sadly died soon afterwards, was one of these.
When Donald became Superintendent of the Computer Science Division at the NPL, he initiated the design & construction of a local area packet switched network connecting laboratories across the site.
As one of Donald's two Deputy Directors, I had responsibility for the Packet Switching work, which was managed by Roger Scantlebury, with Peter Wilkinson as head of the software development team.
However, in 1970, I was appointed Director of the Executive Body of the COST-11 project and David Yates replaced me as Donald Davies' Deputy Director. David is the author of Turing's Legacy, a history of Computing at NPL.
The COST-11 European Informatics Network was a twelve nation project based on a five node international packet switched network.
COST-11 was proposed by the 'Senior Officials' group on which the UK was represented by Brian Oakley.
After describing the COST-11 project, a brief account of subsequent activities will complete the presentation.
A Brief History of the NPL Network
Mr Roger A Scantlebury BSc Grad.Inst.P
Associate Director of Mercator Software Ltd
Work on the NPL network started in 1966 when Donald Davies became Superintendent of Computer Science Division.
Donald called me into his office and asked me to lead a 3-man team to put together a theoretical design for a data communication network based on a working paper he had produced describing the 'packet switching' approach he had been considering.
The team consisted of Keith Bartlett, Peter Wilkinson and myself. Keith had a background in digital circuit design and was a member of the ACE computer team, Peter came to us with expertise in real-time software design, and I had some background in computers and logic design having joined the original ACE team in 1955.
Our first approach was to design a 'packet-switch' -- the core element of the technology which we needed to prove was a feasibility. We would then turn our attention to the 'Interface' function that we assumed would be necessary to connect the 'then-known' terminal and computer population, into the packet-switching network.
Jointly we had absolutely no knowledge of telecommunications technology -- at that time being largely vested in the analogue telephone network. We were, indeed, uniquely qualified. It is probably because of this that we were able to ignore any constraints about 'band-width', cost of channels or the difficult history of stored-program telephone exchanges, that beset our contemporaries in the telecomms industry -- both telephony and message switching!
Our starting point was the current mini-computer technology, the burgeoning micro-circuit chip industry, and the newly introduced p.c.m. digital telephone technology. Indeed the latter was probably crucial because it revealed to us that it is possible to squirt data at megabit rates down twisted pair cable of the kind that proliferates beneath the streets of our cities (and within the office buildings that populate them).
Taking these ingredients we cooked up a design for a packet switch. We assumed that switches would be sited rather like telephone exchanges, but with high-speed links between them. The local area would be connected into this back-bone or trunk network via the 'Interface' function, supporting terminal devices and computers alike.
This was well before the PC was launched, and the typical terminal was the electro-mechanical 'teletype' or the VDU -- sometimes called the 'glass-teletype'. About the only clue to what would eventually happen was the idea that small offices might, one day, use a small computer like the PDP-8. Ah, happy days...
Computers would ideally converse in 'packet-mode', although at that time low-speed dial asynchronous connections were the norm. (We assumed this is how the local area Interface would support the terminal population -- assembling character-mode streams into packets, and disassembling in the other direction.) User's computers would connect to the Interface computer, not because they needed packet assembly, but in order to isolate the trunk network from any 'ill-behaviour' of user's machines.
Our first design was reported in a paper written at the end of 1966 and published at the ACM symposium "On Operating System Principles", held in Gatlinburg, Tennessee in 1967. This design assumed
- Megabit links between 'nodes' (switches) -- probably numbering between 3 and 5 per node
- Special digital hardware to control direct input to and output from main memory of complete packets (packet-DMA)
- Simple real-time operating system, and special application software dealing with buffer assignment, packet routing and housekeeping.
Using this model we were able to demonstrate, on paper at least, that the technology was feasible, with through-put in the region a hundred packets per second and a transit delay in the milli-second region.
Two things then happened
- I met Larry Roberts of ARPA -- and pointed out how our approach would provide the connectivity his network of co-operating computer systems would need
- We needed to prove that the local area (Interface) function was not only feasible but was also utilitarian. (What are the design impacts for such 'networked' computer systems ?)
We therefore set about designing and building the NPL Network -- a real working system that would hopefully provide the Laboratory with advance computing and data-processing services -- well, that was how we sold the idea -- the rest was immense fun...
Peter will speak about the two phases of the network design, the first essentially just the Interface (PAD) function, the second a full-blown packet switching system, which served the Laboratory for many years until it was eventually replaced with a commercial product.
I defer to Peter on the software aspects of the system, and will therefore say a bit about the data-transmission equipment that was designed and built in-house -- of necessity since no product of the kind we envisaged, existed in those days.
We determined that as the NPL site was private, we would use 1 megabit/s links everywhere -- well bandwidth is cheap when you don't have to pay for it! We could not use the telephone wiring and therefore had to cable the buildings specially. In an act of sheer prescience Derek Barber , my then Boss, had had a network of cables laid between all the main buildings (the site covered 78 acres and had dozens of buildings).
We designed and built digital line-drivers, user interface boxes, multiplexors, and the DMA I/O channel for the Packet Switching machine. The machine chosen for switch was the Honeywell DDP516 (by chance the same machine chosen by BBN for ARPA). The digital system was built using the then available 7400 series TTL technology. The system first went 'live' early in 1969, and exhibited a sustained capacity of around 200 packets per second. The network grew in the next few years to a subscriber population of about 200 users and 20 computer services.
This network was not designed as a LAN in the sense of the later Token Ring or Ethernet, but from a user perspective it behaved in much the same way. (Interestingly enough though, the modern versions of Ether-switches are harking back to our architecture). When user-services were attached to the network providing database capability, storage, computing facilities, text and message handing, etc, our users had in the early 1970s many of the same facilities that we now take for granted on our office networks today. Only the Internet was missing...
During the 1970s we collaborated with the ARPA community and became the UK centre for the European Informatics Network (who's director was Derek Barber). We used the NPL network to link the ARPA network and the EIN network, and participated in the research of linking computers attached to different networks (strangely, for some reason, we were not very popular with the PTTs or IBM).
Now, my good friend Vint Cerf of ARPA took me aside one day and suggested that we collaborate, together with our colleagues from the French network group at IRIA , and suggest the design of a 'protocol' that could be used between the computers connected to different networks. He called it an inter-network protocol. From this small beginning was born TCP/IP. He dubbed the collection of such consenting computers 'an internet'. And the rest, as they say, is history...
NPL Development of Packet Switching
Dr Peter T Wilkinson CEng MIEE
Director of Corporate Information Solutions Ltd
This talk will give a broad overview of the design and development of the NPL Network system and software, complementing those by Derek Barber and Roger Scantlebury.
An initial feasibility study into Donald Davies' packet switching concept, which began in earnest in early 1967, was based on a very simple outline design for a packet switching node, network, routing mechanism and protocols. It proved that existing computers, supported by a limited amount of specialised hardware, could cost-effectively implement a "national data network" backbone using 1.5 Mb/s links. Later studies then began to examine a putative 18 node UK network in more detail.
From this early work sprang three parallel lines of activity at NPL:
- continuation of the feasibility studies
- "political" national/international developments
- design and development of the NPL campus network, the first packet switched network in the UK
The feasibility studies continued with an attempt to apply queuing theory to study overall network performance. This proved to be intractable so we quickly turned to simulation. Roger Healey wrote & ran a simulation on NPL's central computer and we studied various traffic patterns, winding up traffic levels and finding that our 18 node network's performance collapsed dramatically as its saturation limit was approached.
Donald Davies, with characteristic inventiveness, suggested an "Isarithmic" control mechanism to overcome that problem, which was built into the simulation. These studies continued for some time, both at NPL under Dr Wyn Price and at Plessey under an extramural research contract, as more complex networks and protocols were evaluated.
Discussion of the political lobbying in the UK to get support from UK Post Office for a national network development, contact with the ARPANET team and later national/international developments I will leave to my colleagues, who were more directly involved. However, it soon became clear that progressing from theoretical to practical activities would only be possible at a local level and Donald succeeded in persuading NPL management to support the development of the NPL Network on-campus.
We had made further, more detailed theoretical network designs (see the IFIP'68 papers) and later used these as a basis for planning the NPL Network. As Roger will explain, the network hardware involved use of the BS4421 handshaked interface, 1 Mb/s links, flow control/error recovery at hardware link level and a hierarchy of multiplexers, all of which terminated at a single Honeywell DDP516 minicomputer. The network was therefore a "logical star".
We had the luxury of developing two versions of the network, the first (commencing in 1969) acted as an "Interface Computer" (using the term from our IFIP'68 paper, or in other words a packet assembler/disassembler). It thus provided hardware-supported "virtual calls" between "unintelligent" data sources/sinks (which also included external computers). The software was entirely home-grown and written in the Honeywell assembly language (DAP16). The "Interface Computer" software was supported by a purpose-built real time executive with a modular, hierarchical structure, based upon the principles of co-operating sequential processes communicating by means of message-passing. The approach proved effective and the Mark I network came into operation during 1971 but (a) did not have the functionality required to support external computer services effectively and (b) performance was not up to expectation because the overheads imposed by the executive in handling message-passing and process switching proved too high (later machines like the GEC4000 were to provide hardware support for similar functions).
A Mark II network was therefore designed and developed. This used the same hardware and network, but with an additional design of I/O unit to interface the subscriber computers. The logical network structure was redesigned so that these subscriber computers communicated via a central packet switch. New packet protocols and a virtual call protocol were defined. "Unintelligent" devices were supported by a logically distinct "terminal processor" (i.e. Interface Computer). However, both packet switch and terminal processor shared the same hardware communications system and were supported as logical software partitions on the single central DDP516.
At the same time the software was re-designed from scratch. By then we had available a high-level machine-oriented language, PL516, created by Brian Wichmann and Donald Bell from Nicklaus Wirth's original PL360. This was indeed a big improvement on DAP16. A new executive was designed, again based upon the notion of co-operating sequential processes but this time adopting Dijkstra's semaphore notion and a strict hierarchical structure corresponding to his "THE" operating system. This executive was more complex but it permitted the applications software it supported to operate very efficiently. In the end we found that we could handle the complete throughput of a packet in under 1,000 executed instructions (of the DDP516 simple one-address order code).
This software also proved very robust. It came into service in 1973/74 and remained in operation, essentially unchanged and without error until replaced by a commercially available system in the mid-1980's. The "Mark II" network became the "invisible plumbing" for increasingly sophisticated and widely used Laboratory computing services from the mid-70's. Working with me, at various times, on the software development were Keith Wilkinson (no relation and, sadly, now deceased), Rex Haymes, Carol Walsh (later Mrs Corby), Alan Gardner (seconded for a year to NPL by Post Office Telephones, just to show that they really did care!) and John Laws (now at DERA Malvern).
The ideas of "logical hierarchies" (essentially, data abstractions) which proved so effective in designing the software also apply very naturally to higher organisational levels of the system and we began to use them to describe the logical layers of network functionality and the protocols that support them. The same concepts appear in the ISO 7-layer model but that, as they say, is another story...