Sequenced Packet Protocol

Xerox Network Systems (XNS) is a computer networking protocol suite developed by Xerox within the Xerox Network Systems Architecture. It provided general purpose network communications, internetwork routing and packet delivery, and higher level functions such as a reliable stream, and remote procedure calls. XNS predated and influenced the development of the Open Systems Interconnection (OSI) networking model, and was very influential in local area networking designs during the 1980s.

XNS was developed by the Xerox Systems Development Department in the early 1980s, who were charged with bringing Xerox PARC's research to market. XNS was based on the earlier (and equally influential) PARC Universal Packet (PUP) suite from the late 1970s. Some of the protocols in the XNS suite were lightly modified versions of the ones in the Pup suite. XNS added the concept of a network number, allowing larger networks to be constructed from multiple smaller ones, with routers controlling the flow of information between the networks.

The protocol suite specifications for XNS were placed in the public domain in 1977. This helped XNS become the canonical local area networking protocol, copied to various degrees by practically all networking systems in use into the 1990s. XNS was used unchanged by 3Com's 3+Share and Ungermann-Bass's Net/One. It was also used, with modifications, as the basis for Novell NetWare, and Banyan VINES. XNS was used as the basis for the AppleNet system, but this was never commercialized; a number of XNS's solutions to common problems were used in AppleNet's replacement, AppleTalk.

Description

Overall design

In comparison to the OSI model's 7 layers, XNS is a five-layer system, like the later Internet protocol suite.

The Physical and Data Link layers of the OSI model correspond to the Physical layer (layer 0) in XNS, which was designed to use the transport mechanism of the underlying hardware and did not separate the data link. Specifically, XNS's Physical layer is really the Ethernet local area network system, also being developed by Xerox at the same time, and a number of its design decisions reflect that fact. The system was designed to allow Ethernet to be replaced by some other system, but that was not defined by the protocol (nor had to be).

The primary part of XNS is its definition of the Internal Transport layer (layer 1), which corresponds to OSI's Network layer, and it is here that the primary internetworking protocol, IDP, is defined. XNS combined the OSI's Session and Transport layers into the single Interprocess Communications layer (layer 2). Layer 3 was Resource Control, similar to the OSI's Presentation.

Finally, on top of both models, is the Application layer, although these layers were not defined in the XNS standard.

Basic internetwork protocol

The main internetwork layer protocol is the Internet Datagram Protocol (IDP). IDP is a close descendant of Pup's internetwork protocol, and roughly corresponds to the Internet Protocol (IP) layer in the Internet protocol suite.

IDP uses Ethernet's 48-bit address as the basis for its own network addressing, generally using the machine's MAC address as the primary unique identifier. To this is added another 48-bit address section provided by the networking equipment; 32-bits are provided by routers to identify the network number in the internetwork, and another 16-bits define a socket number for service selection within a single host. The network number portion of the address also includes a special value which meant "this network", for use by hosts which did not (yet) know their network number.

Unlike TCP/IP, socket numbers are part of the full network address in the IDP header, so that upper-layer protocols do not need to implement demultiplexing; IDP also supplies packet types (again, unlike IP). IDP also contains a checksum covering the entire packet, but it is optional, not mandatory. This reflects the fact that LANs generally have low-error rates, so XNS removed error correction from the lower-level protocols in order to improve performance. Error correction could be optionally added at higher levels in the protocol stack, for instance, in XNS's own SPP protocol. XNS was widely regarded as faster than IP due to this design note.

In keeping with the low-latency LAN connections it runs on, XNS uses a short packet size, which improves performance in the case of low error rates and short turnaround times. IDP packets are up to 576 bytes long, including the 30 byte IDP header. In comparison, IP requires all hosts to support at ''least'' 576, but supports packets of up to 65K bytes. Individual XNS host pairs on a particular network might use larger packets, but no XNS router is required to handle them, and no mechanism is defined to discover if the intervening routers support larger packets. Also, packets can not be fragmented, as they can in IP.

The Routing Information Protocol (RIP), a descendant of Pup's ''Gateway Information Protocol'', is used as the router information-exchange system, and (slightly modified to match the syntax of addresses of other protocol suites), remains in use today in other protocol suites, such as the Internet protocol suite.

XNS also implements a simple echo protocol at the internetwork layer, similar to IP's ping, but operating at a lower level in the networking stack. Instead of adding the ICMP data as payload in an IP packet, as in ping, XNS's echo placed the command directly within the underlying IDP packet. The same might be achieved in IP by expanding the ICMP Protocol field of the IP header.

Transport layer protocols

There are two primary transport layer protocols, both very different from their Pup predecessor:

* Sequenced Packet Protocol (SPP) is an acknowledged transport protocol, analogous to TCP; one chief technical difference is that the sequence numbers count the packets, and not the bytes as in TCP and PUP's BSP; it is the direct antecedent to Novell's IPX/SPX.
* Packet Exchange Protocol (PEP) is a connectionless non-reliable protocol similar in nature to UDP and the antecedent to Novell's PXP.

XNS, like Pup, also uses EP, the ''Error Protocol'', as a reporting system for problems such as dropped packets. This provided a unique set of packets which can be filtered to look for problems.

Application protocols

Courier RPC

In the original Xerox concept, application protocols such as remote printing, filing, and mailing, etc., employed a remote procedure call protocol named Courier. Courier contained primitives to implement most of the features of Xerox's Mesa programming language function calls. Applications had to manually serialize and de-serialize function calls in Courier; there was no automatic facility translate a function activation frame into an RPC (i.e. no "RPC compiler" was available). Because Courier was used by all applications, the XNS application protocol documents specified only courier function-call interfaces, and module+function binding tuples. There was a special facility in Courier to allow a function call to send or receive bulk data.

Initially, XNS service location was performed via broadcasting remote procedure-calls using a series of expanding ring broadcasts (in consultation with the local router, to get networks at increasing distances.) Later, the Clearinghouse Protocol 3-level directory service was created to perform service location, and the expanding-ring broadcasts were used only to locate an initial Clearinghouse.

Due to its tight integration with Mesa as an underlying technology, many of the traditional higher-level protocols were not part of the XNS system itself. This meant that vendors using the XNS protocols all created their own solutions for file sharing and printer support. While many of these 3rd party products theoretically could talk to each other at a packet level, there was little or no capability to call each other's application services. This led to complete fragmentation of the XNS market, and has been cited as one of the reasons that IP easily displaced it.

Authentication

The XNS protocols also included an Authentication Protocol and an Authentication Service to support it. Its "Strong credentials" were based on the same Needham–Schroeder protocol that was later used by Kerberos. After contacting the authentication service for credentials, this protocol provided a lightweight way to digitally sign Courier procedure calls, so that receivers could verify the signature and authenticate senders over the XNS internet, without having to contact the Authentication service again for the length of the protocol communication session.

Printing

Xerox's printing language, Interpress, was a binary-formatted standard for controlling laser printers. The designers of this language, John Warnock and Chuck Geschke, later left Xerox PARC to start Adobe Systems. Before leaving, they realized the difficulty of specifying a binary print language, where functions to serialize the print job were cumbersome and which made it difficult to debug errant printing jobs. To realize the value of specifying both a programmable and easily debug-able print job in ASCII, Warnock and Geschke created the Postscript language as one of their first products at Adobe.

Remote Debug Protocols

Because all 8000+ machines in the Xerox corporate Intranet ran the Wildflower architecture (designed by Butler Lampson), there was a remote-debug protocol for microcode. Basically, a peek and poke function could halt and manipulate the microcode state of a C-series or D-series machine, anywhere on earth, and then restart the machine.

Also, there was a remote debug protocol for the world-swap debugger. This protocol could, via the debugger "nub", freeze a workstation and then peek and poke various parts of memory, change variables, and continue execution. If debugging symbols were available, a crashed machine could be remote debugged from anywhere on earth.

History

Origins in Ethernet and PUP

In his final year at Harvard University, Bob Metcalfe began interviewing at a number of companies and was given a warm welcome by Jerry Elkind and Bob Taylor at Xerox PARC, who were beginning to work on the networked computer workstations that would become the Xerox Alto. He agreed to join PARC in July, after defending his thesis. In 1970, while couch surfing at Steve Crocker's home while attending a conference, Metcalfe picked up a copy Proceedings of the Fall Joint Computer Conference off the table with the aim of falling asleep while reading it. Instead, he became fascinated by an article on ALOHAnet, an earlier wide-area networking system. By June he had developed his own theories on networking and presented them to his professors, who rejected it and he was "thrown out on my ass."

Metcalfe was welcomed at PARC in spite of his unsuccessful thesis, and soon started development of what was then referred to as "ALOHAnet in a wire". He teamed up with David Boggs to help with the electronic implementation, and by the end of 1973 they were building working hardware at 3 Mbit/s. The pair then began working on a simple protocol that would run on the system. This led to the development of the PARC Universal Packet (Pup) system, and by late 1974 the two had Pup successfully running on Ethernet. They filed a patent on the concepts, with Metcalfe adding several other names because he believed they deserved mention, and then submitted a paper on the concept to Communications of the ACM on "Ethernet: Distributed Packet Switching for Local Computer Networks", published in July 1976.

PUP to XNS

By 1975, long before PUP was complete, Metcalfe was already chafing under the stiff Xerox management. He believed the company should immediately put Ethernet into production, but found little interest among upper management. A seminal event took place when professors from MIT's famed Artificial Intelligence Laboratory approached Xerox in 1974 with the intention of buying Ethernet for use in their lab. Xerox management declined, believing Ethernet was better used to help sell their own equipment. The AI Lab would then go on to make their own version of Ethernet, Chaosnet.

Metcalfe eventually left Xerox November 1975 for Transaction Technology, a division of Citibank tasked with advanced product development. However, he was lured back to Xerox seven months later by David Liddle, who had recently organized the Systems Development Division within Xerox specifically to bring PARCs concepts to market. Metcalfe immediately began re-designing Ethernet to work at 20 Mbit/s and started an effort to re-write Pup in a production quality version. Looking for help on Pup, Metcalfe approached Yogin Dalal, who was at that time completing his thesis under Vint Cerf at Stanford University. Dalal was also being heavily recruited by Bob Kahn's ARPANET team (working on TCP/IP), but when Cerf left to join DARPA, Dalal agreed to move to PARC and started there in 1977.

Dalal built a team including William Crowther and Hal Murray, and started with a complete review of Pup. Dalal also attempted to remain involved in the TCP efforts underway at DARPA, but eventually gave up and focussed fully on Pup. Dalal combined his experience with ARPANET with the concepts from Pup and by the end of 1977 they had published the first draft of the Xerox Network System specification. This was essentially a version of Pup with the added concept of sockets and an internetwork, which allowed routers to forward packets across connected networks.

By early 1978 the new system was working, but management was still not making any move to commercialize it. As Metcalfe put it:

When I came back to Xerox in 1976, we were about two and a half years from product shipment and in 1978 we were about two and a half years from product shipment.

When no further action was forthcoming, Metcalfe left the company at the end of 1978.

Impact

Last used by Xerox for communication with the DocuTech 135 Publishing System, XNS is no longer in use, due to the ubiquity of IP. However, it played an important role in the development of networking technology in the 1980s, by influencing software and hardware vendors to seriously consider the need for computing platforms to support more than one network protocol stack simultaneously.

A wide variety of proprietary networking systems were directly based on XNS or offered minor variations on the theme. Among these were Net/One, 3+, Banyan VINES and Novell's IPX/SPX. These systems added their own concepts on top of the XNS addressing and routing system; VINES added a directory service among other services, while Novell NetWare added a number of user-facing services like printing and file sharing. AppleTalk used XNS-like routing, but had incompatible addresses using shorter numbers.

XNS also helped to validate the design of the 4.2BSD network subsystem by providing a second protocol suite, one which was significantly different from the Internet protocols; by implementing both stacks in the same kernel, Berkeley researchers demonstrated that the design was suitable for more than just IP. Additional BSD modifications were eventually necessary to support the full range of Open Systems Interconnection (OSI) protocols.

See also

* Protocol Wars

* Xerox Character Code Standard

References

;Citations

;Bibliography

*
*
*
* ''Xerox System Integration Standard - Internet Transport Protocols'' (Xerox, Stamford, 1981)
* ''Xerox System Integration Standard - Courier: The Remote Procedure Call Protocol'' (Xerox, Stamford, 1981)
* Oppen, D.C., and Dalal, Y.K., The Clearinghouse: A Decentralized Agent for Locating Named Objects in a Distributed Environment. Palo Alto: Xerox Corporation, Office Systems Division, 1981 October: Tech Report OSD-T8103.
* Israel, J.E, and Linden, T.A, Authentication in Xerox's Star and Network Systems. Palo Alto: Xerox Corporation, Office Systems Division, 1982 May: Tech Report OSD-T8201.
* ''Office Systems Technology - a look into the world of the Xerox 8000 Series Products: Workstations, Services, Ethernet, and Software Development", (Edited by Ted Linden and Eric Harslem), Tech Report Xerox OSD-R8203, November 1982. A compendium of 24 papers describing all aspects of the Xerox STAR Workstation and Networking Protocols, most of them were reprints of journal and conference publications.
{{refend

External links

Xerox Network Systems Architecture: Introduction to Xerox Network Systems

Xerox Network Systems Architecture: General Information Manual

Example of an actual implementation in kernel space

Network protocols
Network Systems
XNS based protocols