Bill is the creator of 386BSD and is doing independent work on the Simplified Internet Gigabit Networking Architecture (SIGNA), a software-only experimental platform. He can be reached at wjolitz@ cardio.ucsf.edu or on CompuServe at 76703,4266.
For a computer system to interoperate on a network, its protocol implementation must function identically to all other protocol implementations. Specifications of this behavior are documented so that implementors can understand the fine points of operation, while avoiding intimate study of hundreds of different implementations.
Although rigid protocol specifications ensure network interoperability, they also limit the extent to which a protocol can be altered to suit new circumstances. This constraint, in turn, determines the life cycle of surrounding networks in which the protocol is used. If freedom of implementation isn't constrained, implementations become too costly for widespread use. If implementations are too narrow, they may become successful, but eventually languish for lack of flexibility. Thus, rigidly static standards are a two-edged sword, as evidenced by the current crisis of exhausted network address space on the Internet.
Network addresses identify computers (or hosts). While for convenience they may be given human-usable names, these names are for our eyes only. All network addresses are converted internally to a unique machine-interchangeable identifier, which is then used in negotiating a packet through a series of computer networks (collectively known as the internetwork or catenet) from the source host sending the packet to (cross your fingers) a destination host computer that ultimately receives the packet.
On the Internet, such addresses are broken into two fields--the network portion to which the host is connected, and the host portion used to uniquely locate the host on its local network; see Figure 1. It's the responsibility of the Internet's routing mechanism to actually steer packets from the source network to a destination network, whereupon the remaining host portion of the destination address is then used to direct the message to its destination. The two fields together provide a unique identifier for the system worldwide (analogous to that of a name, residence address, and zip code).
The TCP/IP protocol suite, originally designed to replace the venerable NCP protocol used in the ARPAnet, was thought to have more than adequate room for expansion. Since the original ARPAnet NCP used 16-bit network addresses, it was thought that a 32-bit network address space (which provided 65,536 times as many addresses as NCP) would suffice. Instead of a few hundred distinct computer networks totalling in the millions of computers, however, hundreds-of-thousands of distinct computer networks now exist, each with from 1 to 50,000 computers present.
Networks are now considered useful as management entities. This "dynamic-network" concept directly impacted the fixed address-space allocation mechanism thought satisfactory for TCP/IP. Where once you might have handed out a single host address, you now could hand out a network-number assignment corresponding to hundreds or thousands of host addresses. This increase in networks is rapidly consuming the four billion values contained in the TCP/IP address space. (According to the Internet Protocol Transition Workbook: The Catenet Model for Internetworking, the designers of TCP/IP weren't unacquainted with this possibility, since at the time, other designers working at the network-link layer--that is, Ethernet--thought a 48-bit address space preferable. To limit the overhead of address fields, it was decided to restrict the maximum length of the host portion of the Internet address to 24 bits; this does not include the network field, which was 8 bits for 256 networks. The possibility of true, variable-length addressing was considered. At one point, it appeared that addresses might be as long as 120 bits each for source and destination. The overhead in the higher-level protocols for maintaining tables capable of dealing with the maximum possible address sizes was considered excessive.)
In the early days of the ARPAnet, a typical computer (such as a Honeywell mini) had limited total memory, usually 32 Kbytes. Additionally, the per-packet protocol overhead of large addresses was a significant consideration, since the network backbone consisted of a 56-Kbit/second coax link handling many terminal sessions. The actual data payload of a single byte corresponding to a keystroke made the 40-byte TCP/IP header overhead appear excessive. As such, the historical reasons for deciding on fixed addressing were not unreasonable: simplicity (for use in situations such as bootstrapping) and limited bandwidth (due to use of terminal sessions).
Today, the backbones of the Internet--1.5 Mbit/sec. (T1) and 45 Mbit/sec. (T3) links--handle an average data payload of 8 Kbytes or more (up to 64 Kbytes), with file and application-information transfers dominating. As such, the addition of even 30 bytes more per packet is a trivial price to pay for broader scope. Even the most economical of workstations and PCs sold today would barely notice the additional cost in increased packet overhead; yet the fixed design of Internet address space inherently limits the number of systems which can use this communications architecture.
What is necessary is an interoperable, extensible protocol which could be redefined as needed, without reimplementing all of the networking software yet again. This protocol would have to be redeployed, replacing the existing Internet "installed base." (This is unlikely due to sheer numbers.)
At first glance, "extensible interoperability" seems a heretical concept. After all, interoperability achieved success by cleaving to a rigid design. However, looking at analogous work often yields insight into an apparently contradictory goal. During the '70s, one trend in language design was "extensible" languages, which let you build more elaborate operators, data types, and syntax, as a means of tailoring the expression of the program to fit its specific needs. Here lie some of the roots of object-oriented programming--specifically, polymorphism.
Designing a protocol can be considered akin to designing a programming language. Instead of denoting the syntax, we denote state diagrams and the details of information exchanged. Like the famous Backus-Naur Formulation (BNF) of language grammars, protocols can also be diagramed. They can be designed with degrees of extensibility incorporated into the design and specification. If the usage of a protocol varies greatly, its actual expression will shift to accommodate the new use dynamically. These polymorphic protocols are just one mechanism by which the extensible-interoperability paradigm can be made concise.
The power of a good paradigm stems from its essential applicability in any area of a discipline. Extensible interoperability provides the framework in which a wide range of familiar computer concepts in other areas, such as polymorphism, are examined, analyzed, and transformed to resolve an apparently intractable problem in a completely different area, in this case, networking.
The Open Systems Interconnect (OSI) was chartered by ISO as the sole, officially sanctioned internetworking protocol standard for adoption worldwide. By now, OSI was expected to displace ad hoc standards like TCP/IP. But the transition from TCP/IP to OSI seems as distant as ever, and TCP/IP is therefore compelled to stretch well beyond its design limits.
OSI is an example of a standard spanning too large a gap in time with too broad a mandate. (Like the DoD's Euclid and Ada languages, OSI isn't "compact.") In addition, the lack of reverse compatibility made the transition uninteresting and painful--no matter how good a standard looks on paper, testing occurs in the field, and no amount of paperwork can compel people in the field to transfer to other protocols if the transition process is too painful.
In the case of address space, OSI has no limitation like that of TCP/IP. Because of its origins in the telecommunications sphere, where international phone numbers have variable lengths, OSI's two network protocols, CONS and CLNP, allow for large network addresses. To the designers' credit, a considerable amount of work has been undertaken throughout the OSI protocol stack to avoid future limitations inherent to its design.
Despite this care, OSI, like TCP/IP, is still, in essence, a product of the "fixed-estimate" philosophy of design, since some portions are always of fixed size (for example, the size of the header field is 255 bytes). Thus, the "flag-day" phenomenon is not obviated in future use. It may be unlikely, since the limits have been made much larger, but they still exist. Remember, the prior limits were also thought sufficient--until they were found inadequate.
Due to economic and logistical dictates, this flag-day approach to protocol conversion is no longer as feasible as it was when the much-smaller ARPAnet was operational. For example, in the case of the Internet (growing at a current rate of 30 percent annually), if we launched a new network protocol today, the millions of extant hosts would grow to tens-of-millions by the time the new protocol was in place, resulting in a "Red Queen's Race." Another problem is the ever-increasing speed of technological change, which makes it impossible to anticipate even short-term needs.
This isn't new to the computer industry, where the cost of obsolescence is a common thing. Unlike the past hardware-driven economics, future economics will be driven more by the scope of certain standards. At this point, the transition to extensible dynamic standards becomes mandatory, with the Internet address-space limitation a good current case example.
The Internet address-space limitation dilemma illustrates the power of polymorphic protocols. By relying on the paradigms, not on the creation of new protocols, we can keep the solution light and tractable. By working at the network layer of the OSI 7-layer model, we can design a replacement for the IP datagram in Figure 1, using as a basis for the extensible portion the extant IP Options portion. IP options are a variable-length extension of the IP header, which contains a sequence of possible optional data fields with byte-sized tags, padded out to 32-bit aligned boundaries. These add information for special treatment of the IP datagram, of which they're a part.
By turning all fields of a datagram into Options fields (which may be of variable length), we're no longer bound by representational limits or data-field bounds. This incurs a substantial cost, since header size and decoding and encoding time will increase. We can, however, mitigate these costs by providing a suggested content, ordering, and placement for certain classes of datagram denoted by a "class" option. Optionally, an implemented class subrange can be returned in a control message to suggest a preference.
If the datagram class is unknown, a successive field interpreter of the datagram options list can be used to ensure interoperability. Unknown options can thus be immediately passed back via a control message using exactly the same mechanism as in today's IP (ICMP).
One key point here is the attempt to uncouple the protocol-interchange abstractions (packet formats) from the actual implementations and their current use, and to leave open a means by which a future variation won't "break" older implementations. While this example might appear similar to mechanisms used in higher levels of the OSI (presentation) and XNS (application) protocols, they aren't the same. In this example, we're still dealing with network-layer information below the transport layer.
This technique could also be used in a limited "reverse-compatibility" mechanism, by implementing a dual-stack arrangement at the network layer to attempt communications via the extensible format first, otherwise falling back to the traditional IP. Migration to a new network protocol could then occur as a three-phase project, over the course of a decade. A dual-stack implementation would be replaced first by a hybrid (transmission and high-level migration with compatibility kept intact), then by a second-generation consolidated implementation (no compromises for reverse compatibility).
At this stage, the advantages of dynamic, extensible polymorphic protocols are difficult to quantify. However, that value might become clearer if we glance at other limits in TCP/IP that have begun to loom on the horizon; for example, the packet size itself (64 Kbytes is pretty small), TCP sequence and windowfield size (impacting gigabit networking over long distances), and source and destination ports (each currently 16 bits, impacting the number of applications accessible on a machine). How many flag days should we allocate to these, or others not yet of immediate concern? Perhaps fixed-format protocols are merely the computer equivalent of the buggy whip. In any case, it's probably time to explore new ideas and approaches in this area--before it's too late.
Barker, Paul and Colin J. Robbins. "You Cannot Promote OSI Applications over OSI Networks." ConneXions (May, 1993).
Crocker, David. "The ROAD to a new IP." ConneXions (November, 1992).
Crocker, David. "Letters to the Editor: 'Responding to "Internet 2000 (10/92).'" ConneXions (February, 1993).
"A Generic Ultimate Protocol (GUP)." ConneXions (November, 1992).
Stallings, William. Networking Standards: A Guide to OSI, ISDN, LAN, and MAN Standards. Reading, MA: Addison-Wesley, 1993.
U.S. Department of Defense. Internet Protocol Transition Workbook: The Catenet Model for Internetworking. Washington, D.C.: July 1978.
Proposals on the Internet Address Dilemma
TCP/IP is an example of accidental success. Intended solely for the purposes of tying together the second-generation, DoD-sponsored computer-research community, its "strength through simplicity" approach has been remarkably effective. Tiny TCP/IP implementations have been done in as little as six pages of C code ("tiny tcp"), yet supercomputers routinely use more elaborate implementations of the same protocol to shoot gigabits of application data to each other, achieving massive computational feats in coordination. However, the address-space limit inherent in the design of TCP/IP is a concern to both standards working groups and the Internet community.
In an attempt to extend the standard, many proposals focus on amending the TCP/IP address-space limit. These include TUBA (use the OSI protocols to attach to the existing Internet applications layer), SIP (minimize the existing IP header and use the space recovered from jettisoning features to stick on more address bits), PIP (a completely novel internetworking protocol that attempts functionality enhancements beyond current IP), EIP (add more address bits via IP options), IPAE (encapsulate mode address bits in the existing IP datagram), and Nimrod (separate routing mechanism from the existing IP host number, which is left unchanged).
One proposal, GUP, is akin to our concept of polymorphic protocols. GUP discusses the possibility of using triplets of the form <type,length,value>, but takes degrees of freedom to the utmost (an enforced variable-length approach) and is permanently hindered by the inability to increase performance as needed. (You have to iterate through the variable-length fields instead of using ready-made, arranged groupings.)
There's little consensus as to how to solve this dilemma. Since the list of answers runs the gamut from redistribution methods (SIP) to entirely new protocols (PIP), don't expect any agreement soon--just ad hoc solutions.
--W.F.J.
Copyright © 1994, Dr. Dobb's JournalInternet Addresses
Extensible Interoperability
Whatever Happened to OSI?
Polymorphic Protocols: A Simple Example
The Value of Polymorphic Protocols
References
Figure 1: IP datagram format.