Pup: An Internetwork Architectureby David R. Boggs, John F. Shoch, Edward A. Taft, and Robert M. Metcalfe1CSL-79-10July 1979, revised October 1979Abstract: Pup is the name of an internet packet format (PARC Universal Packet), a hierarchyof protocols, and a style of internetwork communication. The fundamental abstraction is anend-to-end media-independent internetwork datagram. Higher levels of functionality areachieved by end-to-end protocols that are strictly a matter of agreement among thecommunicating end processes.This report explores important design issues, sets forth principles that have guided the Pupdesign, discusses the present implementation in moderate detail, and summarizes experiencewith an operational internetwork. This work serves as the basis for a functioning internetworksystem that provides service to about 1000 computers, on 25 networks of 5 different types,using 20 internetwork gateways.Key words and phrases: computer networks, protocols, packet switching, internets,network interconnection, gateways, datagrams, virtual circuits, fragmentationAccepted for publication in IEEE Transactions on Communications, April 1980.1Present affiliation: Computer Systems Laboratory, Stanford University, Stanford, California 94305.XEROXPALO ALTO RESEARCH CENTER3333 Coyote Hill Road / Palo Alto / California 94304Ip!DqXHEor@2siF9q t+uvut 7H5B3` G1+,8$*D(XX&#8"#qt0 bM ut#u drFb?wHqXHdsF4: c>QKPUP: AN INTERNETWORK ARCHITECTURE11. IntroductionResearch in network interconnection techniques has been motivated by the desire to permitcommunication among diverse, geographically distributed computing resources and usersinterconnected by a wide variety of network technologies.It is the purpose of an internetwork architecture to provide a uniform framework forcommunication within a heterogeneous computing, communication, and applications environment.The work described in this paper represents one internetwork architecture, known as Pup, inwidespread regular use within Xerox. The name referred originally to the abstract design of astandard internetwork datagram (the PARC Universal Packet), but has expanded in usage to includethe whole hierarchy of internetwork protocols as well as a general style for internetworkcommunication.To assist in understanding the design of the Pup protocols, it is useful to characterize brieflythe environment in which this architecture has evolved.The computational environment includes a large number of Alto'' minicomputers [Kay, 1977;Thacker et al., 1979] and other personal computers capable of high-quality interaction with humanusers. Supporting these are various specialized server systems that are shared among many usersand provide access to expensive peripherals such as large disks, magnetic tapes, and high-qualityprinters. Additionally, there are several general-purpose time sharing systems providing customaryservices for terminal users.The communications environment includes several different individual network designs. Thedominant one is the Ethernet'' communications network, a local-area broadcast channel with abandwidth of 3 megabits per second [Metcalfe & Boggs, 1976]. Long-haul communication facilitiesinclude the Arpanet, the ARPA Packet Radio network, and a collection of leased lines implementingan Arpanet-style store-and-forward network. These facilities have distinct native protocols andexhibit as much as three orders of magnitude difference in bandwidth.The applications to be supported include a wide range of activities: terminal access to the timesharing services, electronic mail, file transfer, access to specialized data bases, documenttransmission, software distribution, and packet voice, to name just a few. We would also like tofacilitate more ambitious explorations into the area generally referred to as distributed computing.''This paper is organized as follows. In section 2 we discuss some of the design issues whichhave emerged in the formulation of the Pup architecture, while section 3 provides more detail onthe protocols themselves. Section 4 describes briefly some of our operational experience with thepresent implementation. The final section presents a retrospective critique of the work, highlightingsome areas which merit further attention.*R-xyFxyxy xy 0/-;+){x9$:7%yx .5\-,3' 0%;.7,U*S{xI (D%+6#*9!JD8&Gyx*v2.AE 5+:8;$ K mJ 84(V INd) , >SGPUP: AN INTERNETWORK ARCHITECTURE22. Design principles and issuesConstructing an architecture for internetwork protocols is, first and foremost, an exercise indesign: identifying individual issues, exploring alternative solutions, and then knitting these piecestogether to form the final result. Along the way, many compromises are made as one trades offamong different criteria: functionality, efficiency, generality, ease of implementation, extensibility,and others. In this section we enumerate some of the major design issues confronted in the development ofa network architecture and describe, in general terms, the choices made in the development of Pup.(Several of these and other issues are enumerated in [Cerf & Kirstein, 1978] and [Postel, 1980].)From this discussion the broad outlines of Pup will emerge; the section that follows provides morespecific detail about the actual design.2.1. The basic model: individual networks connected with gatewaysAs with most internetwork models, one envisions a collection of heterogeneous networks,connected with a set of internetwork gateways to form a loosely coupled system known generally asan internet [Cerf & Kahn, 1974; Sunshine, 1977a; Cerf & Kirstein, 1978]. An internet shouldprovide the ability for any two hosts to communicate, so long as their own local networks areinterconnected.An important feature of the Pup internet model is that the hosts are the internet. Most hostsconnect directly to a local network, rather than connecting to a network switch such as an IMP, sosubtracting all the hosts would leave little more than wire. Gateways are simply hosts in theinternet that are willing to forward packets among constituent networks. Thus, most of theproperties of the internet are primarily artifacts of host software. The architecture must scalegracefully, and in particular must allow for the existence of a degenerate internet consisting of asingle local network and no gateways.2.2. SimplicityOne of the guiding principles in designing Pup has been the desire for simplicity. Pup is aframework for computer communications research, and simplicity is one of the best ways tominimize restrictions and maximize flexibility for experimentation. Attempting deliberately toeliminate unneeded complexity helps to keep the design open-ended. This in turn makes it easierto incorporate the existing diverse collection of networks and hosts and to accommodate newalternatives as the technology matures. Keeping the design simple helps to avoid building intechnological anachronisms.A second motivation for this principle is the desire to foster efficient implementations of theprotocols in the host machines, which are typically quite small. Software overhead must be kept*ZxyFxyxy xy .b;(6u{XA3&x<0{x4.{xA,@*R(A{x%Lyx#O!~[Ia?$%[{X xB%4 C mC 8H;"XdK >\ PUP: AN INTERNETWORK ARCHITECTURE3low in order to sustain high-bandwidth local communication, which constitutes the bulk of thetraffic; yet the same software must support the full generality of internetwork communication.2.3. Datagrams versus virtual circuitsThere are two major approaches to providing an interface to packet-switched communications:accepting individual datagrams, or providing a higher level of service in the form of a virtual circuit.The two interfaces are not unrelated, since a virtual circuit interface is usually implemented within anetwork by the use of datagrams. In some sense, datagrams provide access to a network at a lowerlevel, closer to its underlying capabilities. Datagrams are particularly useful in many kinds oftransaction-oriented protocols. Furthermore, the task of the internet is significantly simplified if itneed only transport independent, individually-addressed datagrams, without having to maintain thestate required to support virtual circuits. If the internet provides a datagram interface, virtual circuitinterfaces can be provided by adding appropriate mechanisms at the end points.Therefore, the basic function provided by the Pup internet is the transport of datagrams; thissimple abstraction is the foundation of Pup. The internet does not guarantee reliable delivery ofdatagrams (called Pups''); it simply gives its best efforts'' to deliver each one, and allows the endprocesses to build protocols which provide reliable communications of the quality they themselvesdesire [Metcalfe, 1973]. The internet has no notion of a connection. It transports each Pupindependently, and leaves construction of a connectionif that is the appropriate interprocesscommunication modelto the end processes. Keeping fragile end-to-end state out of the packettransport system contributes to reliability and simplicity.2.4. Individual networks as packet transport mechanismsIndividual networks within the internet can be viewed simply as packet transport mechanisms.As links in the internet they give their best efforts to deliver internet packets, but they do notguarantee reliable delivery. Packets may be lost, duplicated, delivered out of order, after a greatdelay, and with hidden damage. A network can have any combination of bandwidth, delay, errorcharacteristics, topology, and economics; the routing algorithm should attempt to take thesecharacteristics into consideration.Encapsulation is an invertible, network-dependent transformation performed on a Pup to permitit to be carried transparently through a network: an abstract Pup is presented at one end,encapsulated for transmission through the net, and decapsulated at the other end, yielding theoriginal Pup. For some networks, encapsulation consists merely of adding headers and trailers.More elaborate transformations may be necessary to pass a Pup through other networks (forexample, using low-level acknowledgments or error correction because the network has a high lossrate). Encapsulation and decapsulation take place in a network-specific driver in which is vested allknowledge of the encapsulation technique. The internet specification has nothing to say aboutencapsulation except that it be invisible.*\xyFxyxy xy ]&PUP: AN INTERNETWORK ARCHITECTURE42.5. Internetwork gatewaysWe distinguish two kinds of gateways: media translators and protocol translators. Mediagateways are hosts with interfaces to two or more packet transport mechanisms among which theyforward internet datagrams, using the appropriate encapsulation for each. These are the heart ofany datagram-based internet. Protocol gateways are hosts which speak two or more functionallysimilar but incompatible higher-level protocols used to transport information within networks,mapping one higher-level abstraction into the other. (It's clear that a media gateway is just doingprotocol translation at the link level, but the distinction is useful given the importance of internetdatagrams in this architecture.) In the Pup internet, media gateways are by definition simple, since all that is required of thetranslation process is that it preserve the semantics of internetwork datagrams. Protocol gatewaysare usually more difficult, even when the protocols are similar, since such higher-level protocolsprovide richer and more specialized semantics and it is not always clear how one should map thefunctionality of one protocol into another. Development of higher-level protocol translatorsbetween different network and internet architecturese.g., between the Arpanet File TransferProtocol (FTP) and the Pup-based FTPis a thorny task, but one that must be confronted wheninterconnecting systems that do not share the necessary lower-level primitives. 2.6. A layered hierarchy of protocolsLayering of protocols is one of the most effective means for structuring a network design: eachlevel uses the functions of the lower level, and adds some functionality of its own for possible useby the next level. Provided that suitable interfaces are maintained, an implementation at one levelcan be modified without impacting the overall structure; this helps to simplify both the design andthe implementation.Pup protocols are organized in a hierarchy, as shown in figure 1; the details of this figure willbe presented in section 3. A level represents an abstraction, to be realized in different ways indifferent hosts. There are four levels of interest, but there may be more than one protocol at anylevel except level 1, representing a different use of the underlying layers. (The numbering oflayersand, indeed, the choice of points at which to divide the layersis arbitrary; there is norelationship between Pup's numbering and that of other designs such as the Open SystemsArchitecture.)The level 0 abstraction is a packet transport mechanism. There are many realizations: anEthernet channel, the Arpanet, the ARPA Packet Radio Network, our store-and-forward leased linenetwork, and others. Level 0 protocols include specifications such as hardware interfaces, electricaland timing characteristics, bit encodings, line control procedures, and network-dependent packetformatting conventions. Associated with each packet transport mechanism is a convention forencapsulating Pups.*[xyFxyxy xy (@d">/C;E97+74+5[,13&S0V.P)8{X%%xG#d!*:JcAPv\A2- +5C  mB 8$yx +K*6Dd =\ PUP: AN INTERNETWORK ARCHITECTURE5<==xyFxyxy xy ?X eW (G?XGW;(HGW;G!WIs2GW,IGs, +Gs,G,G, +G"s,IG2G$2G-,IG$, +G$,G/,G/, +G8,IG/2G:2 GF,IG:, dG:,G:/W/'t/2/H<,IJu,IH<JuDuG>G= +G=G :=G := +G)>G :DuG+WDuG4;>G+W= +G+W=G6t=G6t= dGA>G6tDu G#@-@7@ H<>F>C>W|s  <u!W! "s <#u#+WA$ @55X 4 <4;u3@t?X >; <=u<#u!= :!W"s3#u2!=0/.4;6t8:!==#u)!-$ W!=#u5=s3W0:.,Y+W,Y,t.-0.3/5=!W,Y#.%0(3*;5=:5=93807.6t,Y9Gr9G9G V9G9G:9G9G9G#9G(9G,t9G09G5X9G99G>;9GB9GG9GG&t9GB&t9G>;&t9G9&t9G5X&t9G0&t9G,t&t9G(&t9G#&t9G&t9G&t9G:&t9G&t9G V&t9G&t9Gr&t9G&t9G8;9Gr8;9G8;9G V8;9G8;9G:8;9G8;9G8;9G#8;9G(8;9G,t8;9G08;9G5X8;9G98;9G>;8;9GB8;9GG8;9GGJ9GBJ9G>;J9G9J9G5XJ9G0J9G,tJ9G(J9G#J9GJ9GJ9G:J9GJ9G VJ9GJ9GrJ9GJ9Gz"I4EOx,/ M>A- ,I Af?  e ;t0- ;t- s|,Y.0 3!5=x?%|5=&W3&0't.(,YtQ4 KRPUP: AN INTERNETWORK ARCHITECTURE6The level 1 abstraction is an internet datagram. The realization of this abstraction consists ofthe format of a Pup, a hierarchical addressing scheme, and an internetwork routing algorithm.There is only one box at level 1: the internet datagram protocol; it is this layer of commonalitywhich unifies all of the different networks that might be used at level 0, and which makes availablea uniform interface to all of the layers above. It is the purpose of this level to provide mediaindependence while maintaining the common properties of the underlying packet networks.The level 2 abstraction is an interprocess communication mechanism: a way to move bitswithout saying much about their form or content. Various level 2 protocols provide manycombinations of reliability, throughput, delay, and complexity. These protocols can be divided intotwo classes according to the amount and lifetime of state information kept by the communicatingend processes. Connectionless protocols support short-lived interactions; the end processes maintainlittle state, and usually only during the exchange of a few Pupsno more than a few seconds.Connection-based protocols support sustained interactions, generally requiring substantial state to bemaintained at both ends, and for longer periodsminutes to hours.Level 3 adds structure to the data moved at level 2, as well as conventions for how processesinteract. For example, the File Transfer Protocol (FTP) consists of a set of conventions for talkingabout files and a format for sending them through a level 2 byte stream protocol connection. Theseare sometimes referred to as function-oriented protocols [Crocker et al., 1972].Above level 3 the dividing lines become blurred, and individual applications evolve with theirown natural decomposition into additional layers. With respect to layering of protocols, Pup issimilar in many ways to the ARPA Internet and TCP design [Cerf & Kahn, 1974] and the OpenSystems Architecture [Zimmermann, 1980]. Unlike the Open Systems Architecture (and others),Pup often has several alternative boxes which all rest on a lower level and offer differentfunctionality and interfaces to the next higher level.2.7. Naming, addressing, and routingNames, addresses and routes are three important and distinct entities in an internet [Shoch,1978]:The name of a resource is what one seeks,an address indicates where it is, anda route is how to get there.A name is a symbol, such as a human-readable text string, identifying some resource (process,device, service, etc.) An address is a data structure whose format is understood by level 1 of theinternet, and which is used to specify the destination of a Pup. A route is the information neededto forward a Pup to its specified address. Each of these represents a tighter binding of information:names are mapped into addresses, and addresses are mapped into routes. Error recovery shouldsuccessively fall back to find an alternate route, then an alternate address, and then an alternatename.*\xyFxyxy xy 05]#PUP: AN INTERNETWORK ARCHITECTURE7The mapping from names to addresses is necessarily application-specific, since the syntax andsemantics of names depend entirely on what types of entities are being named and what use isbeing made of them. This is dealt with at the appropriate higher levels of protocol.An address field, as contained in a Pup, is one of the important elements of commonality inthe internet design. An end process sends and receives Pups through a port identified by ahierarchical address consisting of three parts: a network number, a host number, and a socketnumber. This structure reflects the attitude that the communicating parties are the end processes,not the hosts' protocol handlers; among other things, this permits alternate implementations of ahigher-level protocol to coexist in a single machine. (In contrast, the ARPA Internet project [Postel,1980] takes the position that the socket abstraction does not belong at the internet level; therefore,ARPA Internet addresses contain only network and host numbers. When a packet arrives, it is firstdemultiplexed by the protocol type field in the internet header; higher-level protocols such as theTCP, datagram protocol, and packet voice protocol then impose their own concept of socket if theyfind it usefulwhich, as a practical matter, they all do.)The actual process of routing a packet through the Pup internet uses a distributed adaptiverouting procedure. The source process specifies only the destination address and not the path fromsource to destination. The internetwork gateways route Pups to the proper network, a network thenroutes Pups to the proper host, and a host routes Pups to the proper socket. This routing process is associated with Level 1 in the protocol hierarchy, the level at whichpacket formats and internet addresses are standardized. The software implementing level 1 issometimes referred to as a router. Thus, the routing table itself is kept at level 1; a very simple host(or gateway) would need only levels 0 and 1 in order to route Pups. But the routing table alsorequires periodic updating, as gateways exchange and distribute their current routing information;this routing table maintenance protocol is found logically at level 2 of the hierarchy.Gateways provide internet routing tables to individual hosts as well as to each other. Hosts usethis routing information to decide where to send outgoing packets destined other than to a directly-connected network.2.8. Flow control and congestion controlAlthough the terms are often confused, flow control and congestion control attack two verydifferent problems in packet-switched communication. Flow control is a mechanism used toregulate the behavior of a specific source and destination pair, so that the source does not send dataat a rate greater than the receiver can process it. In an internet architecture, flow control remainsthe responsibility of the end-to-end protocols, particularly those at level 2 supporting regular streamtraffic.Congestion control is a network-wide mechanism, used to control the number and distributionof packets in the network so as to prevent system overload. Internet congestion control is necessaryto help protect the gateways from being burdened with excessive traffic.*\xyFxyxy xy /yx>;{ xA9Y7:5[I3&({x {x0L.N,W*R%8({xH%7(#4.!~{x9IH(<[{X( x{ x{xG .8 mf 8X4'TdH =]58PUP: AN INTERNETWORK ARCHITECTURE8The Pup datagram-based internet model does not require that the internet successfully deliverevery packet that has been accepted. Therefore, an intermediate gateway which suddenlyencounters a period of severe congestion is free to discard packets, although the system should beengineered to make this an uncommon event.If a gateway is forced to discard an incoming packet because of congestion, it should attempt toreturn some information to the source: an error Pup (negative acknowledgment) indicating that apacket had to be discarded in mid-route. This error Pup is simply returned to the source port, asidentified in the discarded Pup; this is a good illustration of the value of including the socketnumber as part of the standard internet address. The source process can use this information tomodify its transmission strategiesfor example, to reduce its offered load (the rate at which itattempts to send Pups along the congested path) and thereby help to relieve the congestion.Long-term congestion should eventually be reflected in the routing information exchangedamong gateways, discouraging subsequent traffic from attempting to pass through a badly congestedarea.2.9. Reliable transportDefining datagrams to be less than perfectly reliable is realistic since it reflects thecharacteristics of many existing packet transport mechanisms. Probabilistic transmission is basic tothe theory of operation of network designs such as Ethernet. Even in networks nominally designedto deliver correctly sequenced, error-free packets, occasional anomalies may result from certainhardware or software failures: an Arpanet IMP may crash while holding the only copy of a packet,or an X.25 virtual circuit may be reset.As mentioned previously, the Pup internet always has the option of discarding packets torelieve congestion, though this is certainly not an optimal strategy. This point is of considerablepractical importance when one considers the complicated measures required to avoid deadlockconditions in the Arpanetconditions which are a direct consequence of attempting to providereliable delivery of every packet in a store-and-forward network [Metcalfe, 1973; McQuillan &Walden, 1977]. Packet management strategies that attempt to guarantee perfect reliability must bedesigned to operate correctly under worst case conditions, whereas strategies that have the option ofdiscarding packets when necessary need operate correctly only under most conditions. The idea isto sacrifice the guarantee of reliable delivery of individual packets and to capitalize on the resultingsimplicity to produce higher reliability and performance overall.For some applications, perfectly reliable transport is unnecessary and possibly even undesirable,especially if it is obtained at the cost of increased delay. For example, in real-time speechapplications, loss of an occasional packet is of little consequence, but even short delays (or worse,highly variable ones) can cause significant degradation [Cohen, 1977; Sproull & Cohen, 1978].*WxyFxyxy xy / R;=#9@7X5[R3&-{X*Sx$%F(Y %2/#>"!+yx/J(*{x$Q7$vTA8% Z${ x$ ={x mE# 8AF#;D!dN ?=X"PUP: AN INTERNETWORK ARCHITECTURE9Reliable delivery requires maintaining state information at the source and destination. Theactions of a large class of simple servers, such as giving out routing tables or converting names intoaddresses, are idempotent (i.e., may be repeated without incremental effects), and a client of thatservice can simply retransmit a request if no response arrives. These protocols reduce to a simpleexchange of Pups, with an occasional retransmission by the client, but with no state retained by theserver. (The server may choose to retain answers to the last few requests to improve response time,but this optimization is invisible to the protocol.)On the other hand, many applications such as file transfer and terminal connection do dependupon fully reliable transmission. In these cases, it is perfectly reasonable to build a reliable end-to-end protocol on top of the internet datagrams. Ultimately, reliability (by some definition) is alwaysrequired; the issue is where it should be provided. The Pup attitude is that it is the responsibilityof the end processes to define and implement whatever form of reliable transport is appropriate tothe situation.2.10. Packet fragmentationIt is inevitable that some process will want to send an internet packet which is too large to bedirectly encapsulated for transmission through an intermediate network that has a smaller maximumpacket size. This problem is usually approached with one of two forms of packet fragmentation[Shoch, 1979a].With internetwork fragmentation, an internet-wide design specifies the operations to beperformed on a packet that is too large for a network it is about to enter. The internet datagram isfragmented into a number of smaller internet datagrams, thereafter to be transported independentlyand reassembled at the ultimate destination. This is the approach taken, for example, in the ARPAInternet design. It requires every destination to have procedures for reassembly.Alternatively, one may use intranetwork fragmentation (or network-specific fragmentation):when presented with an oversize packet, the network-specific driver undertakes to fragment thepacket in a manner specific to that network, to be reassembled by the corresponding driver as thepacket exits the network (e.g., at the next gateway). This approach confines the fragmentation andreassembly procedures to the level 0 modules of hosts directly connected to the network in whichfragmentation is required.The Pup design does not attempt to provide any form of general internetwork fragmentation.This complex issue has been simply legislated out of existence by requiring that every agent in theinternet handle Pups up to a standard maximum size, using network-specific fragmentation wherenecessary. *SGxyFxyxy xy (GcD?$B6.@dJ>/4;R 9+>7f5[&@3&\0 +m{X(x'9%Y#I{!xJ{x#!D#?YyvxRA{x{x <"C W mK 8SMJd =Ta PUP: AN INTERNETWORK ARCHITECTURE102.11. Broadcast packetsBroadcast packets are a particularly useful means for locating available resources or distributinginformation to many hosts at once. Some local networks, such as the Ethernet, directly supporttransmission of broadcast packets. In store-and-forward systems, however, specialized algorithms arerequired to propagate a packet efficiently to all hosts [Dalal, 1977; Dalal & Metcalfe, 1978]; noexisting store-and-forward networks support any technique besides brute-force transmission of apacket to every node, though such a capability is now being implemented in the Arpanet.Broadcasts may also be expensive since every host that receives one must expend someresources, if only to discard it. In networks where a broadcast involves generating more than onepacket, there is the additional cost of creating and transporting the extra copies. Because of theirpotentially high cost, internet-wide broadcasts are not presently supported in the Pup design. Nor isit clear that such a capability would be desirable, since it would not extend well to a very largeinternet. The problem of locating distant resources in the internet at reasonable cost is a topic ofcurrent research.But Pups can be broadcast on a single network; they are frequently used to locate nearbyresources, or to permit gateways to announce their presence on a network. Implementation of thebroadcast procedure is left to the network-specific driver, using the best technique available on thatnet.2.12. Privacy and securityIt must be recognized that in practical internet environments, packets may be delivered to thewrong host, intercepted by another host, or generated by a host masquerading as some other host.To prevent this would require one to interpose some agent between hosts and the internet and tospecify a secure access control procedure. This would significantly increase the complexity of theinternet, and truly suspicious users would probably not trust it anyway.Processes are encouraged, however, to ensure the privacy and authenticity of theircommunication by whatever end-to-end encryption techniques seem appropriate [Needham &Schroeder, 1978]. Particularly vulnerable components, such as gateways and servers, should takeprecautions to protect their own integrity, but ultimate responsibility rests with the end processes.The Pup internet does not attempt to protect users from traffic analysis or from malicious replay ofprevious traffic.*MxyFxyxy xy ;xE{XBxK@dW>/&?;M9]7;5[T3&M0S.^,M*RW (%X##=!~33I{XvxMA` J*9 H mH<I 8$2OeTd .>NPUP: AN INTERNETWORK ARCHITECTURE113. ImplementationThe preceding section has outlined some of the important properties of the Pup architectureand the internetworking issues it addresses. What follows is a more detailed description of thepresent design of the four major layers in the system.3.1. Level 0: packet transportAn individual network moves network-specific packets among hosts; the addressing schemes,error characteristics, maximum packet sizes, and other attributes of networks vary greatly. Aninternetwork packet transport mechanism, however, moves Pups between hosts. The level 0 codewhich transforms a network into an internet packet transport mechanism is called a network driver.A machine connected to a single network, therefore, has one level 0 network driver; a gatewayhas one driver for each directly-connected network. Only the driver knows about the peculiaritiesof a network's hardware interface and low-level protocol.The interface between levels 0 and 1 is very simple. Level 1 passes down a Pup and anetwork-specific host address, and the driver encapsulates the Pup and does its best to deliver it tothe specified host. When a Pup arrives at a host, the driver decapsulates it and passes it up to level1; if for any reason the Pup looks suspicious (as determined by network-specific error checking), thedriver discards it.Every packet transport mechanism must be able to accept a maximum-size Pup; if the actualnetwork cannot directly encapsulate a packet of that size for transmission, the driver must includesome form of intranetwork fragmentation.A network driver may also be asked to broadcast a packet to all other hosts on that net. Onsome networks this is straightforward; on others it may require use of a reverse-path forwardingalgorithm [Dalal & Metcalfe, 1978] or brute-force replication of the packet to each destination.The transport mechanisms don't have to be perfectly reliable, but they should be successfulmost of the timea packet loss rate of less than 1 percent is usually acceptable. A networkoperating for a short time in a degraded mode with a higher loss rate is harmless, so long as theprobability is low that Pups will transit more than one net that is in this condition. However, if anetwork's inherent error characteristics are unfavorable, the driver should take steps to improve itsperformance, perhaps by incorporating a network-specific low-level acknowledgment andretransmission protocol.To date, there have been five major types of networks integrated into the Pup architecture,each with a different level 0 driver.Ethernet. Local Ethernet facilities can very easily serve as transport mechanisms for Pups: a Pupfits in an Ethernet packet with only a few additional words of encapsulation (see figure 2), andrequires no fragmentation. These systems have good reliability, high speed, and can send broadcastpackets [Metcalfe & Boggs, 1976; Shoch & Hupp, 1979; Shoch, 1979b]. *\pqFpqpq pq ;pTrXQ~p*1OI-3M6GsXDApDB 0/?]=Rs p;mK98P794'.2F0d Z./\+)K ',7%[(#&S 3-%;#8RTZIa~g'h.I  M % rpN ;% E dD I=]PUP: AN INTERNETWORK ARCHITECTURE12<==pqFpqpq pq ;pd16 ^ XGKG@G7Q 5N.7J4= VG4; VG5. T ; R 9U 7Y 5ZW 1~r%p0 /I03 -)9 *"0qp (c &uE $@4+ " ] %> $ rp!qpsp *3 [3. &? $= U A& R.. EKd(9 d=\3PUP: AN INTERNETWORK ARCHITECTURE14line network, a Telenet-based packet transport mechanism would not be cost-effective except underconditions of very light traffic volume. We would prefer to use a service that provided simple,unreliable datagrams; if there were an appropriate interface, we could dismantle our leased linestore-and-forward network.3.2. Level 1: internetwork datagramsThis is the level at which packet formats and internetwork addresses are standardized. It is thelowest level of process-to-process communication.3.2.1. Pup formatThe standard format for a Pup is shown in figure 3. The following paragraphs highlight thesorts of information required at the internet datagram level.The Pup length is the number of 8-bit bytes in the Pup, including internetwork header (20bytes), contents, and checksum (2 bytes).The transport control field is used for two purposes: as a scratch area for use by gateways, andas a way for source processes to tell the internet how to handle the packet. (Other networks callthis the facilities'' or options'' field.) The hop count subfield is incremented each time the packetis forwarded by a gateway. If this ever overflows, the packet is presumed to be travelling in a loopand is discarded. A trace bit is specified, for potential use in monitoring the path taken by apacket.The Pup type is assigned by the source process for interpretation by the destination process anddefines the format of the Pup contents. The 256 possible types are divided into two groups. Sometypes are registered and have a single meaning across all protocols; Pups generated or interpretedwithin the internet (e.g., by gateways) have types assigned in this space. Interpretation of theremaining unregistered types is strictly a matter of agreement between the source and destinationprocesses.The Pup identifier is used by most protocols to hold a sequence number. Its presence in theinternetwork header is to permit a response generated within the internet (e.g., error or traceinformation) to identify the Pup that triggered it in a manner that does not depend on knowledgeof the higher-level protocols used by the end processes.Pups contain two addresses: a source port and a destination port. These hierarchical addressesinclude an 8-bit network number, an 8-bit host number, and a 32-bit socket number. Hosts areexpected to know their own host addresses, to discover their network numbers by locating a gatewayand asking for this information, and to assign socket numbers in some systematic way not legislatedby the internet protocol.*VpqFpqpq pq ;pN.T K,4IBGB sX$>p]<18sX5\pH3'=0s p)".),sp#(*SZ(4sp-%^#spB!Jsp"202 s p%)':v s pBA  s p ?+4 ` m8 8s psp)4C Yd  =W"PUP: AN INTERNETWORK ARCHITECTURE15<==pqFpqpq pq ;pd16 ^ X VJ#GG$U#H V@#G V=_#$=$U V6#G:>$> VQ<#G:M VW#GU C9 V GK0 VGK V V#G V#G:zd sp#2@$26$2J$/D $/: $/N $ VN $ VD $ V: $2@m$26$ 2@$ $4;Ff 4;D4;!@<N:R>!8 !@5E3\1~I/IG-@* sp8(D"&uY$@B" L3(2l=#7bJsX  p? mB 8 Ysp* sp$`dX \ H>]7PUP: AN INTERNETWORK ARCHITECTURE17<==pqFpqpq pq ;pd16 ^ X's|U4OJ;tH;tA'sA'sJ$ V.C V$]:G:EGsEGEG9E$9J$E$r9R$N$r9N$9N$9Wl$9Wl$W$r9[$ S$ J9$r K C#LOr$%D-#:d:G9$qG:#$*G#$*G%69$r%6$76$%1$7-U$r%-1$%-1$%$N$%($7$q$r.*.2U$.)q$.!1 V1+,$ V9 :GrGs9G9Gr$rr$:$r $r $: $rrM$ri$:$rr$r$ G V$ V$ d+,$!V y$-1$%xY:VPV+/ Gr )& )7 V +M3{MVx,8{,8rpWrU rT:ssT:UR$9 9U3 $/3 $r $rpN rM rKV rII$9 9LO $sKVsI/* $;t'$9<p(U<* <+ <-U C;s*A(Ux_W 9 9q#=r!V$rpRsRB19<p19;t0$9C;s4A2<p2<4 <698 s!8T$9p srps @$#@$ Y $#R$9Q @$P3 r$!VI$9H $;t0 @$F0$9;t7 $j $%:T$90 @$;t' $D'$9;t. r$!Vz#x;VpD VBr :sDBr5p; 5=r >s=r=;pq  ssVq5p" 5! >s"=!rC$9rCk V$Ck$]pD @$(:$](< V$5W:$9);9.<$9.|5("8$9(" V$5W"$])p".$r1$]j V$T$9 V$r |dUtY6Zk*F`tPUP: AN INTERNETWORK ARCHITECTURE18Routing information is maintained in a manner very similar to the Arpanet-style adaptiveprocedures [McQuillan, 1974]. The initial metric used for selecting routes is the hop count''thenumber of intermediate networks between source and destination. The protocol for updating therouting tables involves exchanging Pups with neighboring gateways and rests logically at level 2 ofthe protocol hierarchy. This is an example of a connectionless protocol which doesn't requireperfectly reliable transmission for correct operation. Changes in internetwork topology may causedifferent gateways' routing tables to become momentarily inconsistent, but the algorithm is stable inthat the routing tables rapidly converge to a consistent state and remain that way until anotherchange in topology occurs.A host which is not a gateway still implements a portion of this level 2 routing update protocol:it initially obtains an internetwork routing table from a gateway on its directly-connected network,and it obtains updated information periodically. If there is more than one gateway providingconnections to other networks, the host can merge their routing tables and thus be able to select thebest route for packets directed to any network.3.3. Level 2: interprocess communicationGiven the raw datagram facility provided at level 1, we can begin to build data transportprotocols, tailored to provide appropriate levels of reliability or functionality for real applications. These protocols generally fall into two categories: those in which a connection is established fora sustained exchange of packets, and those in which individual packets are exchanged on aconnectionless basis. Connection-style protocols usually transport data very reliably, andtransparently.EFTP: the Easy File Transfer Protocol. This is a very simple protocol for sending files. Each dataPup gives rise to an immediate acknowledgment, and there is at most one Pup outstanding at atime. This protocol is an indirect descendent of the one outlined in [Metcalfe & Boggs, 1976]. Itssimplicity makes this piece of communication mechanism easy to include under conditions of verylimited resources. For example, we have implemented a complete EFTP receiver in 256 words ofassembly language, for use in a network-based bootstrap and down-line loading process. Rendezvous & Termination Protocol (RTP). This is a general means to initiate, manage, andterminate connections in a reliable fashion [Sunshine & Dalal, 1978]. In normal use, an RTP userinitiates a connection by communicating with a well-known socket at some server. That server willspawn a new port to actually provide the service, and the RTP will establish contact with this port.It employs a non-reusable connection identifier to distinguish among multiple instantiations of thesame connection and to cope with delayed packets without making assumptions about maximumpacket lifetimes. RTP also synchronizes Pup identifiers for use in managing the connection.*XpqFpqpq pq ;pPBNGLHJQ^HAE6,CFA}`?H=@!:7-80-6t W4?/.sX(+lp+.)7h'b$$5"YPUP: AN INTERNETWORK ARCHITECTURE19Byte Stream Protocol (BSP). This is a relatively sophisticated protocol for supporting reliable,sequenced streams of data. It provides for multiple outstanding packets from the source, and uses amoving window flow control procedure. User processes can place mark bytes in the stream toidentify logical boundaries and can send out-of-band interrupt signals. RTP and BSP combinedperform a function similar to that of the TCP, with which they share a certain degree of commonancestry [Cerf & Kahn, 1974; Postel, 1980].Connectionless protocols do not attempt to maintain any long-term state; they usually don'tguarantee reliability, but leave it up to the designer to construct the most suitable system. Theirsimplicity and ease of implementation make them extremely useful.Echo. A very simple protocol can be used to send test Pups to an echo server process, which willcheck them and send back a reply. Such servers are usually embedded in gateways and other serverhosts, to aid in network monitoring and maintenance. The server is trivial to implement on top ofthe level 1 facilities.Name lookup. Another server provides the mapping from string names of resources to internetworkaddresses; this is accomplished by a single exchange of packets. This service is often addressed witha broadcast Pup, since it is used as the first step in locating resources. (The name lookup serviceitself, of course, must be located at a well-known address. To be useful, it must be widelyavailable; therefore it is typically replicated at least once per network.)Routing table maintenance. The internetwork routing tables are maintained by Pups exchangedperiodically among internetwork gateways and broadcast for use by other hosts.Page-level file access. The Woodstock File Server (WFS), one of the family of file servers availableon the internet, provides page-at-a-time access to a large file store [Swinehart et al., 1979]. Theprotocols used for this do not require establishment of a connection, but merely exchange requestand response Pups that each carry both commands and file data. This arrangement supportsrandom-access, transaction-oriented interactions of very high performancefrequently better thanthat obtained using local file storage, because the file server's disks are much faster than thosetypically connected to personal computers. Gateway monitoring and control. There is no single network control center, but individual gatewaysmay be queried from a monitoring program run on any user machine. With suitable authentication,the user may assume remote control of the gateway so as to perform operations such as changingparameters and loading new versions of the software.Other connectionless protocols are used to access a date and time server, an authenticationserver, and a mail check server integrated with an on-line message system. These protocols aredesigned to be as cheap as possible to implement (i.e., without connection overhead) so that such*[pqFpqpq pq ;p Srp@ Q{P OF&s p M5sp JU H+EXAC#6.@A =rp5s p :!@ 8[ 6s 2r p; 0bG .-P +J )K %rpB #N rp3 Qsp lY 7D =# /3 + r pE @ R7' 4* sps psp#dJ f=\%PUP: AN INTERNETWORK ARCHITECTURE20servers may be replicated extensively and accessed routinely without consuming excessive resources.For example, instances of some of these servers are present in all gateway hosts so as to maximizetheir availability.3.4. Level 3: application protocolsArmed with a reasonable collection of data transport protocols at level 2, one can begin toevolve specific applications at level 3. These are supported by various function-oriented protocols[Crocker et al., 1972].Telnet. Terminal access to remote hosts is provided with an internetwork Telnet protocol, whichmakes use of the combination of the Rendezvous & Termination Protocol (RTP) and the ByteStream Protocol (BSP) at level 2. Using the notion of a virtual terminal, Telnet implementationsmap characteristics of actual terminals into a network-independent representation; a mark byte inthe stream and an out-of-band interrupt, for example, are used to signal an attention.'' (Thisapproach is a subset of the Arpanet Telnet protocol, without any of its options such as RCTE[Davidson, et al., 1977; Feinler & Postel, 1978].)FTP. The RTP and BSP are again combined as the foundation for an internetwork File TransferProtocol (FTP), supporting stream-oriented access to files. The underlying byte streams providereliable communication, and the major task of FTP is to communicate commands and responses andto sort out different representations of data in different file systems. FTP implementations havebeen embedded within existing time-sharing systems, and also constitute the core of dedicated, high-capacity file servers.Printing. Among the important shared resources in the internet are high-quality printing servers.Rather than using the fully developed BSP and FTP, the specialized task of sending unnamed,standard format document files to a printer makes use of the more restricted but much simplerEFTP.CopyDisk. Given high-performance networks and simple gateways that can forward Pups amongthem efficiently, it is perfectly reasonable to copy entire disk packs through the internet. TheCopyDisk protocol negotiates between the participating machines to ensure that the disks arecompatible, and handles error recovery should something break down.Remote graphics. Personal display-oriented computers such as the Alto can be used to provide aconvivial front end for large programming systems such as Interlisp. The Alto Display protocol isused for exchanging descriptions of graphical structures as well as text; it is similar to the ARPANetwork Graphics Protocol, but with extensions to support raster-scanned graphics [Sproull &Thomas, 1974; Teitelman, 1977; Sproull & Cohen, 1978].*[pqFpqpq pq ;pS):Q{!AOFIsX#FspN D>@$B sp >-rpH ;H 96+ 7Y 5YK 3$Cq 0p sp" -rp= *F (*4 &t(: $?P "  .rpH %6 <!  rpR ~F IX C 8rpN 6, Cq p9# d6 f>\PUP: AN INTERNETWORK ARCHITECTURE21Additional applications have included cooperative editing of common documents from multiplemachines, audio communication and packet voice, and many others. As users create new applications, these systems tend to develop their own natural layering offunction. Some may require new protocol designs in the existing hierarchy; the Pup architecturepermits this degree of flexibility down to the level of the simple internetwork datagram. As we gainexperience with new systems, common pieces of design will begin to emerge that might be of moregeneral use; they will eventually find their way into an appropriate place in this hierarchy ofcommunications protocols.*pqFpqpq pq ;p[ B mJ 87)"CNId O?=RPUP: AN INTERNETWORK ARCHITECTURE224. Evolution, actual experience, and performanceThe Pup architecture emerged against a background of Arpanet protocols. Many of itsimportant ideasand those of its key relative, TCPfirst appeared during the course of a series ofmeetings of the International Network Working Group (IFIP TC-6 WG6.1) during 1973. Pup andTCP share a number of important principles, most notably that of reliable end-to-end transmissionthrough an internet. Pup subsequently diverged from TCP as the desire for implementation withinXerox required decoupling it from TCP's long and sometimes painful standardization process.The fundamentals of the Pup design crystallized in 1974 and have remained essentiallyunchanged since then. During this interval many higher-level protocols have been developed, theimplementations have evolved considerably, and the internetwork system has grown to includeapproximately 1000 hosts, attached to 25 networks of 5 different types, using 20 internetworkgateways. The system is in regular use, is quite stable, and requires little regular maintenance orattention.From a functional point of view, this internetwork architecture has been able to fulfill theneeds of a very diverse community. While the bulk of all traffic is carried by means of a fewstandard protocols, it has proven extremely valuable to be able to define new protocolsaiming atdifferent points in the space of performance, cost, and functionalityand to fit them into theinternet protocol hierarchy at any of several levels.In terms of performance, the internetwork gateways impose very little overhead because theyare so simple. In regions of the internet where multiple high-bandwidth local networks areinterconnected directly by a single minicomputer-based gateway, there is almost no noticeabledifference between intranet and internet performance. Total throughput in an individual gateway ishigh, ranging from 400 to 1000 kilobits per seconds (depending on the particular implementation),and the typical delay experienced by maximum-length Pups in the case just mentioned is 2 to 5milliseconds.These figures don't represent limits to what is achievableeven with the relatively low-poweredmachines now being used as gatewaysbecause the gateway software has not been highly tuned forthis application but rather is based on general-purpose software packages that are also used in manyother hosts. But the current performance is adequate because the internetwork traffic load istypically only a tiny fraction of the capacity of the underlying local network channels. There existsone Alto-based gateway that interconnects three 3-megabit per second Ethernet channels as well asseveral 9.6-kilobit per second leased lines and a Packet Radio interface. In general the bottlenecksare not the gateways but rather the slower communication channels; discard of Pups due tocongestion in gateways is almost exclusively due to overload of the 9.6-kilobit per second lines.As might be expected, most of the traffic in our local networks is intranetworkthat is,consisting of Pups whose source and destination are on the same network. For example,measurement of one such network has shown a typical volume of 2.2 million packets per day, 72percent of which are intranetwork packets [Shoch & Hupp, 1979]. Furthermore, of the remaining*[pqFpqpq pq ;pS'rX1Op1#M8*Kn PI9 VG8(D'4B:@e`>0?;%89a7 5\<3'L0I.U,5*S P(*1%?#(;!PJ3* DLvIA)5 !EK I mE 8O!77#:dN  =\1PUP: AN INTERNETWORK ARCHITECTURE2328 percent, more than half consist of traffic to or from another nearby local network connected viaa single gateway. (This site is served by multiple local networks because it is too large to cover witha single one using existing Ethernet technology, and also because it would exhaust a singlenetwork's address space.) The rest of the trafficsome 250,000 packets per dayis transported toor from other campuses in the internet, mostly via the leased line network.The higher-level protocols, such as the Byte Stream and FTP, are generally limited inperformance by the processor capacity or the secondary storage bandwidth at the source anddestination. For example, our BCPL implementation of BSP can maintain a data stream at the rateof about 500 kilobits per second between end processes running on Alto minicomputers, at whichpoint both machines are CPU-bound. While it is certainly adequate for most applications, we findthis performance somewhat disappointing, and we view it as an indication that BSPthoughsubstantially simpler than, say, TCPis still too complicated a protocol for high-performancecommunication.The Pup architecture allows individual networks to be added to the internet system on an adhoc basis, with no need for central control or coordination except to assign new network numbers.Users sharing a local network can assemble gateways and lease lines to other nearby gateways; theyare encouraged to make multiple intergateway connections to provide alternate routes and therebyreduce the probability of being isolated. The gateway software has evolved to the point where ifone starts a copy of it on a host having at least one connection to the existing internet, it willautomatically obtain the files and other information it needs, announce its availability to the rest ofthe internet, and begin forwarding Pups.5. A retrospective critique, possible improvements, and future researchWhile the architecture works extremely well, there are some lessons to be learned from thisexperience.5.1. Addressing and routingThe size of address fields is a question of continuing controversy. An eight-bit networknumber supports up to 256 nets; that is fine for now, but eventually it should be made larger. Todate, 256 hosts per net has not been a problem, though it is likely to become one (for example,when the Arpanet's new 24-bit addressing convention starts to receive wide use). We have avoidedvariable-length address fields in the Pup design because they increase per-packet processing costs.If an internetwork system becomes extremely large, the number of networks becomes so greatthat it is no longer practical for all hosts to keep routing table entries for all possible destinationnetworks. Area routing strategies may be employed to attack this problem [McQuillan, 1974].Alternatively, one may adopt a scheme in which the local routing table becomes a cache of recently*[pqFpqpq pq ;pS8+Q}B&OH[M#>JKHRFt6$D?#qp0 B F?B==;k]96 7K s4p>2S0bO.-)8+11)K'( crXHpQ  [sX pC'; $; mY 8\T,;5'dF | d>\PUP: AN INTERNETWORK ARCHITECTURE24used routing information, with routes to specific networks computed and maintained as needed.The problem of locating routes to distant parts of the internet is an area of current research.One could consider revising the entire notion of a hierarchical address space. Under thecurrent design, it is sometimes necessary to change the host number of a machine which is movedfrom one net to anotheran operational annoyance. It is conceivable that every host could begiven a unique address within a flat address space; a more sophisticated mechanism would then beneeded to map addresses into routes, since there would no longer be a network number as part ofthe address (except perhaps as a hint, to improve performance).We view with some disfavor non-hierarchical organizations in which internet addresses consistof a concatenation of network-specific addresses [Sunshine, 1977b]. Such arrangements have theeffect of fixing the path to a given destination and blur the distinction between addressing androuting.Socket numbers, which are now 32 bits wide, could easily shrink to 16. Originally, 32 bits wereassigned to allow inclusion of a unique subfield to distinguish among multiple instantiations of aconnection; we now recognize that a better approach is to use a distinct connection identifier at thetime a connection is established, as mentioned earlier in the presentation of the Rendezvous &Termination Protocol.Using hop counts as the metric for routing decisions has worked remarkably well. An obviousdrawback, however, is that it considers a hop through a 9.6-kilobit per second phone line equally asgood as a hop through a 3-megabit per second Ethernet link. As the topology becomes more richlyconnected, this will increasingly become a problem. We intend eventually to change the routingalgorithms to reflect some consideration of bandwidth and delay, using known techniques based onresearch into adaptive distributed routing algorithms in the Arpanet and elsewhere.We have given little consideration to source routing or other forms of advice (e.g., class ofservice) provided to the internet routing procedures by source processes. In providing suchfacilities, one must take great care not to compromise the simplicity of the basic internet datagramsor violate the layering of protocols.5.2. Congestion control and utilization of low-bandwidth channelsThe current congestion control techniques must be regarded as primitive. Discarding Pups and(where possible) notifying the source process when congestion occurs has the virtue of simplicity,and we believe it is a good general approach; but the present design has several defects.Insufficient information is returned to the source process to enable it to make an informed decisionabout how to proceed; further, the discard of Pups is haphazard, and no provision is made forfairness. Congestion occurs most often at the entry to slow channels, and under overload conditionsthe perceived performance of paths through those channels is highly variable.*WpqFpqpq pq ;pO]M?KmYI8,3G8%DHB\@d?>/B;M9spG75[F3&N0S.M,*RI(5/%Y#W!~]ISZ>[ u%sXA pH mS 8HDD'=dM ?>XPUP: AN INTERNETWORK ARCHITECTURE25This is a situation in which it would be appropriate to perform a relatively large amount ofcomputation per packet in order to optimize the utilization of the communication bandwidth. Forexample, the network-specific driver for a leased telephone circuit could examine the source anddestination addresses of Pups to deduce the existence of conversations'', and use this informationto share the slow channel more effectively. (The Arpanet IMPs deduce conversations in preciselythis way, though for purposes having to do primarily with flow control rather than congestioncontrol.)In the same vein, techniques such as code compression, elimination and regeneration ofidentical internet headers in successive packets, etc., may be implemented in the network-specificdrivers for the slow channels, with minimal impact on the end-to-end protocols. Such techniquesare used widely in virtual circuit designs, and their applicability is sometimes cited as an advantageof virtual circuits over datagrams [Roberts, 1978]. But there is no reason they can't be employed ina datagram-based internet, so long as the necessary additional computation is done in the rightplace.The important point is that optimizing the utilization of the communication channel isappropriate only when the channel bandwidth is scarce compared to the computation required toperform such optimization. Where the processing capacity of the end machines is itself the scarceresourceas we have observed in the local network environmentsuch techniques are highlyinappropriate.5.3. Pup types in the internet headerThe distinction between registered and unregistered Pup types at the level of internet datagramshas not turned out to be particularly useful, except in a few cases: Pups of type error'' and trace''may be generated from within the internet without knowledge of the higher-level protocols beingemployed by the end processes.5.4. Performance of reliable end-to-end protocolsPresent implementations of the Byte Stream Protocol include fairly sophisticated adaptive flowcontrol heuristics that also try to take note of any packets lost due to internet congestion. Thisapproach has worked reasonably well in enabling a source to adapt to the conditions encounteredalong the path to a particular destination. However, use of networks with highly variablebehaviorsuch as the wide-ranging delays experienced when using the Packet Radio networkcanconfound these heuristics. Under unusual circumstances, the flow control procedures have beenobserved to move suddenly into very unfavorable operating regions. The difficulty involving theRadionet has since been solved, but the general design of simple, effective flow control andcongestion control procedures is just a very hard problemparticularly procedures intended toadapt dynamically to and make good use of different networks whose performance may vary by*\pqFpqpq pq ;pT@IR \O TMKKl;qp I7$9GD:B;'@cU >.P;V9>!75ZK 3%5(0W .)/, 'sX%#p&:!~bIJsX1ApB H_ +/ m9# 8)5\K,1dB p =]4PUP: AN INTERNETWORK ARCHITECTURE26nearly three orders of magnitude.The step from raw Pups to a byte stream may be too large. The Byte Stream Protocol does toomuch for many applications; it is complex enough that few systems have ever implemented theentire specification. As discussed previously, performance of the BSPwhen compared to someother systemsis reasonable; but it does not give a user the full capacity of the underlyingnetworks. In a high-bandwidth local network environment, paying attention to per-packetprocessing overhead is of extreme importance.We have consideredbut have not yet implementeda proposal for an intermediate level offunctionality: a Reliable Packet Protocol (RPP) that takes care of connection establishment andprocesses flow control information, but tries not to dictate how a client program should do buffermanagement. It ensures reliable delivery (i.e., each packet once and only once), but may deliverpackets to the client out of order, and does not deliberately attempt to hide packet boundaries. ABSP connectionwhere that is what is desiredmay then be re-implemented as a veneer on top ofan RPP connection.5.5. Access to the internetThe present Pup architecture can be characterized as open'': users and applications arepermittedand indeed encouragedto take advantage of the internet for routine communication.Access to the internet is uncontrolled; as in many network designs, responsibility for access controlrests with the host systems, and whatever accounting is performed is for the services rendered byindividual servers. In our research and development environment this is ideal, but obviously insome other environments it might not be.5.6. ConclusionsThe success of Pup as an internetwork architecture depends on a number of importantprinciples. Key among these is the layering of function in such a way that applications may makeuse of the internet at any of several levels, with the ability to choose among alternative protocols ateach level or to develop new ones where necessary. Simple internetwork datagrams constitute thelevel at which media independence (through encapsulation) is achieved; they are also the unit ofdirect process-to-process communication. This is crucial both to flexibility and to performance,particularly in an internetwork environment dominated by relatively lightweight hosts and high-bandwidth local networks.During 1976 the Pup internet reached a level of functionality roughly equivalent to thatprovided by the standard Arpanet protocolsbyte streams, Telnet, and FTP. From that time to thepresent we have concentrated on building servers and constructing applications to access themthrough the internet. We are just beginning to explore that area of interprocess communicationtraditionally considered the domain of multiprocessors. Some interesting opportunities arise from*\pqFpqpq pq ;pT@!R OOKM#9Kl(4I7$4G-DTBM@cQ>. U;039$972 sX.pJ,A*R X(4-%4,#(/sXp:BvMA3- T 9( 8' m 8 MQ] Td7+ < >]4PUP: AN INTERNETWORK ARCHITECTURE27the availability of 100 or so minicomputers interconnected by a 3-megabit per second broadcastchannel, and by 10 or so similar clusters, all interconnected by a store-and-forward network. Webelieve that the Pup architecture serves as a good foundation for such investigations.AcknowledgmentsA large systems effort such as the development of Pup reflects the efforts of many differentparticipants. Other people who have implemented parts of Pup and contributed ideas include WillCrowther, Yogen Dalal, Hal Murray, Bob Sproull, Larry Stewart, Jim White, and Graeme Williams.We also wish to thank Danny Cohen, Dave Crocker, Bob Kahn, Jon Postel, and Carl Sunshinefor their careful reading of an earlier draft of this paper.References[Cerf & Kahn, 1974]Vinton Cerf and Robert Kahn, A Protocol for Packet Network Interconnection, IEEETransactions on Communications, vol. Com-22 no. 5, May 1974.[Cerf & Kirstein, 1978]Vinton Cerf and Peter Kirstein, Issues in Packet-Network Interconnection, Proceedings of theIEEE, vol. 66 no. 11, November 1978.[Cohen, 1977]Dan Cohen, Issues in Transnet Packetized Voice Communication, 5th Data CommunicationsSymposium, Snowbird, Utah, September 1977.[Crocker et al., 1972]S. D. Crocker, J. F. Heafner, R. M. Metcalfe, and J. B. Postel, Function-oriented Protocols forthe ARPA Computer Network, AFIPS Conference Proceedings (SJCC), vol. 40, 1972.[Dalal, 1977]Yogen K. Dalal, Broadcast Protocols in Packet Switched Computer Networks, Technical Report128, Stanford University Digital Systems Laboratory, April 1977.[Dalal & Metcalfe, 1978]Yogen K. Dalal and Robert M. Metcalfe, Reverse Path Forwarding of Broadcast Packets,Communications of the ACM, vol. 21 no. 12, December 1978.[Data General, 1971]Data General Corp., Type 4038 Multiprocessor Communications Adapter, Technical Reference014-000002-01, September 1971.[Davidson et al., 1977]J. Davidson, W. Hathaway, J. Postel, N. Mimno, R. Thomas, and D. Walden, The ArpanetTelnet Protocol: Its Purpose, Principles, Implementation, and Impact on Host Operating SystemDesign, 5th Data Communications Symposium, Snowbird, Utah, September 1977.1ZpqFpqpq pq ;pRGP=$NPVG%rCp\AE?lH=7I;<3r 18p/m2s-p+)8Js'mp$ # 4s!8p!spZqpstspd s8p @/dAsp  /s/p d sp$0/]ds!p!l \=[PUP: AN INTERNETWORK ARCHITECTURE28[Feinler & Postel, 1978]E. Feinler and J. Postel, eds., Telnet Protocol Specification, Arpanet Protocol Handbook,January 1978.[Kahn et al., 1978]R. E. Kahn, S. A. Gronemeyer, J. Burchfiel, and R. C. Kunzelman, Advances in Packet RadioTechnology, Proceedings of the IEEE, vol. 66 no. 11, November 1978.[Kay, 1977]Alan C. Kay, Microelectronics and the Personal Computer, Scientific American, vol. 237 no. 3,September 1977.[McQuillan, 1974]John M. McQuillan, Adaptive Routing Algorithms for Distributed Computer Networks, HarvardPh.D. thesis, Report no. 2831, Bolt Beranek and Newman, May 1974.[McQuillan and Walden, 1977]John M. McQuillan and David C. Walden, The ARPANET Design Decisions, ComputerNetworks, vol. 1 no. 5, August 1977.[Metcalfe, 1973]Robert M. Metcalfe, Packet Communication, Harvard Ph.D. thesis, M.I.T. Project MAC TR-114,December 1973.[Metcalfe & Boggs, 1976]Robert Metcalfe and David Boggs, Ethernet: Distributed Packet Switching for Local ComputerNetworks, Communications of the ACM, vol. 19 no. 7, July 1976.[Needham & Schroeder, 1978]Roger Needham and Michael Schroeder, Using Encryption for Authentication in LargeNetworks of Computers, Communications of the ACM, vol. 21 no. 12, December 1978.[Postel, 1980]Jon Postel, Internetwork Protocols, IEEE Transactions on Communications, this issue.[Roberts, 1978]Lawrence G. Roberts, The Evolution of Packet Switching, Proceedings of the IEEE, vol. 66 no.11, November 1978.[Shoch, 1978]John F. Shoch, Internetwork Naming, Addressing, and Routing, 17th IEEE Computer SocietyInternational Conference (CompCon), September 1978.[Shoch, 1979a]John F. Shoch, Packet Fragmentation in Internetwork Protocols, Computer Networks, vol. 3 no.1, February 1979.[Shoch, 1979b]John F. Shoch, Design and Performance of Local Computer Networks, Stanford Ph.D. thesis,University Microfilms, August 1979.[Shoch & Hupp, 1979]John F. Shoch and Jon A. Hupp, Performance of an Ethernet Local Networka PreliminaryReport, Local Area Network Symposium, Boston, May 1979.1ZpqFpqpq pq ;pRQ&spOJ LspJHI spFv D9spB@A>vs4p<A: 8A,qps6vp32 spqp0A -+K*  sp'm%  D#sp!8 m$s#p 8sp 8 #s"pd ?sp   / ds1p #/Udsp 6;.[PUP: AN INTERNETWORK ARCHITECTURE29[Shoch & Stewart, 1979]John F. Shoch and Lawrence Stewart, Interconnecting Local Networks via the Packet RadioNetwork, 6th Data Communications Symposium, Pacific Grove, November 1979.[Sproull & Cohen, 1978]Robert F. Sproull and Dan Cohen, High-Level Protocols, Proceedings of the IEEE, vol. 66 no.11, November 1978.[Sproull & Thomas, 1974]Robert Sproull and Elaine Thomas, A Network Graphics Protocol, Computer Graphics, vol. 8no. 3, Fall 1974.[Sunshine, 1977a]Carl Sunshine, Interconnection of Computer Networks, Computer Networks, vol. 1, 1977.[Sunshine, 1977b]Carl Sunshine, Source Routing in Computer Networks, ACM Computer CommunicationsReview, vol. 7 no. 1, January 1977.[Sunshine & Dalal, 1978]Carl Sunshine and Yogen Dalal, Connection Management in Transport Protocols, ComputerNetworks, vol. 2, 1978.[Swinehart et al., 1979]Dan Swinehart, Gene McDaniel, and David Boggs, WFS: A Simple Shared File System for aDistributed Environment, Operating Systems Review, vol. 13 no. 5, November 1979.[Teitelman, 1977]Warren Teitelman, A Display-Oriented Programmer's Assistant, Fifth International JointConference on Artificial Intelligence, Cambridge, Mass., August 1977; also available as XeroxPARC technical report CSL-77-3.[Thacker et al., 1979]C. P. Thacker, E. M. McCreight, B. W. Lampson, R. F. Sproull, and D. R. Boggs, Alto: APersonal Computer, Computer Structures: Readings and Examples (Siewiorek, Bell, and Newell,eds.), 1979.[Zimmermann, 1980]H. Zimmermann, The ISO Reference Model, IEEE Transactions on Communications, this issue.1CpqFpqpq pq ;p;: B8As!p537s p 2 /m-?sp+)8'm5sp $#4s!8pA spd spH sp/d=s%p qp /spd.(s"p /ds#p * #?;.D HELVETICA HELVETICA  HELVETICA HELVETICA HELVETICA  HELVETICA  HELVETICALOGO TIMESROMAN   TIMESROMAN  TIMESROMAN   TIMESROMAN  TIMESROMAN  TIMESROMAN TIMESROMAN  TIMESROMAN  TIMESROMAN HELVETICA  HELVETICA  HELVETICA HELVETICA   HELVETICA   HELVETICA  TEMPLATE@e  %+3 <DLRZa jr t } $E Z =D /%iAB"9I  ^l){ ,"9R %i-B"9K !IiiG]] }%)iKEJ:iN iKB"9  %)ii'>+%T9T9R =  %)ii9Z%-i%)ii@EmX Z  j/@ٓpuppaper.pressTaftm26-Oct-79 15:32:51 PDT