Copyright Xerox Corporation 1979Inter-Office MemorandumToCommunication ProtocolsDateJune 30, 1978FromEd Taft and Bob MetcalfeLocationPalo AltoSubjectPup SpecificationsOrganizationPARC/CSLXEROX Filed on: [Maxc1]PupSpec.pressThe purpose of this memo is to specify a standard with which to interconnect Parc's various packet-switching networks.This memo updates Pup Specifications of October 20, 1975. A number of corrections and editorialchanges have been incorporated. The primary motivation for this update has been to produce aversion of the specifications in Bravo and Press format.We have designed a protocol, based on Pups (Parc Universal Packets), to allow processes on any ofour interconnected computers to exchange packets through any of our interconnected networks. Ofcourse, not all communications need use Pups. However, nearly all resources presently accessible viathe Xerox research network communicate using Pups and Pup-based protocols, and, in particular,the Gateway hosts that interconnect our networks will forward Pups only.At the most basic level, this standard introduces three fundamental principles.1.All Pup-based communication makes use of a standard inter-network packet format(the Pup), specified in this document. All transporting networks are assumed to beable to carry Pups transparently.2.Pup communication is end-to-end at the packet level. The inter-network is requiredonly to be able to transport independently-addressed Pups from source todestination. Use of higher levels of protocol is entirely the responsibility of thecommunicating end processes.3.When Pups are handed to the packet transport mechanism, they may be expected toarrive only with high probability and not necessarily in the order they weretransmitted. It is the responsibility of the communicating end processes to agreeupon higher-level protocols that provide reliable communication of the quality theythemselves require.Also included in this memo are:how a Pup should be encapsulated for transport through various existing networks;a Pup Echo Protocol for test and diagnosis;a Rendezvous/Termination Protocol for connection establishment and synchronization; anda Pup Byte Stream Protocol for carrying error- and flow-controlled byte streams between &pX]g~qi cr]pX-r7Bp \r]p-r7Bp Vr]p-r 7BpOsp I# C&= BD ?_tp< =]  G>/d Pup Specifications2cooperating processes.It should be noted that all of these protocols have remained essentially unchanged since 1975.Experience has demonstrated the strengths and weaknesses of these protocols, and a number ofother higher-level Pup-based protocols have been designed and implemented. However, this bulk ofall traffic is still carried by the protocols described in this document, and these protocols are unlikelyto undergo any further change.A word of caution is in order to anyone contemplating a new implementation of the Pup protocols.While these specifications are reasonably complete in describing the syntax and semantics of theprotocols, they contain very little discussion of strategies for implementing them. Carefully-chosenstrategies turn out to be crucial to good performance. Unfortunately, very little documentation onimplementation strategies presently exists.All numbers are decimal unless followed by 'B'.The PupThe standard Pup format is illustrated in Figure 1.The Pup Length is the number of 8-bit bytes in the Pup, including header, contents, and checksum.There may be from 0 to 532 content bytes in a Pup so that the length will range between 22 and554 bytes. The Pup specification does not expressly prohibit Pups longer than 554 bytes, but by convention hosts arenot expected to be able to transport Pups larger than this. A Pup is always carried in an integral number of16-bit words. The number of 16-bit words is calculated by adding 1 to the length and dividing by 2.The number of content bytes is calculated by subtracting 22 from the length. When there are anodd number of content bytes in a Pup, the extra garbage byte required to fill the Pup out to anintegral number of 16-bit words precedes the checksum word.The Transport Control byte is for use by Gateways; it should normally be zeroed at the Pup'ssource. Setting bit 0, the most significant bit, indicates that the Pup should be traced for debugging.Tracing might involve a Gateway's recording a packet's passage or perhaps even a trace message sentto some monitoring process, perhaps the originating process itself. To date, no such tracing mechanismshave been implemented. Bits 0-3 are used to count the number of Gateways encountered during thePup's transport. A Pup which reaches its 16th Gateway will be discarded. Bits 4-7 currently haveno use and should be zero.The Pup Type is assigned by the source process for interpretation by the destination process; it iscarried in the header for possible use by Gateways. A type of 0 is illegal. Types 1 through 127 areregistered types, such as the ones defined in this document. They may receive optional type-specifichandling by intermediate agents such as Gateways. Registered types are assigned a singleinterpretation that is either used in only one protocol or that is applicable in all protocols; they maynot have different interpretations in different protocols.Types of 128 through 255 are unregistered and their interpretation is strictly a matter of agreementbetween the source and destination processes. A given type may be assigned independent meaningsin different protocols so long as such protocols need not be compatible (in the sense of being usedsimultaneously between a given pair of ports).In practice, the distinction between registered and unregistered Pup Types has not turned out to be particularly useful,except in one case. Pups of type Error may be generated by the packet transport mechanisms without knowledge of thehigher-level protocols being used by the end processes.The 32 bits of the Pup Identifier are assigned by the source process for interpretation, relative to thePup type, by the destination process. Pup IDs identify Pups and their contents to distinguish themfrom others, for purposes such as duplicate suppression and ordering. The specific interpretation ofthe Pup ID is not defined at the Pup level but is rather a matter of convention established at higherlevels of protocol (e.g., the Byte Stream Protocol presented later in this document). fpGb _9X ]\ \/E Z _ Y% V@L TF S6.7 QM P,+ MG,rp Hu Ep3 Bt p; Ak-1 ? r=, >a;p <); ;WD 9D 8M; 5htp' 3Y 2^^ 03r% /TpJ -S ,J )etp8 'L &[B# $R  #Q72 !: Z bK <t p X. r$T YvrM 7 [pt p : 7, QG 14 GU ?/\ iTwo 8-bit bytes<>DestinationPortSourcePortPupHeader(20 bytes)Figure 1. The Format of a PupPup LengthTransport ControlPup TypePup IdentifierDestination NetworkDestination HostDestination SocketSource NetworkSource HostSource SocketContentsPossibleGarbage BytePup Checksum(0 to 532 bytes)e #G7`Gr`#G`G\Gr\<#G7\<GSGSX#G7SXG +F#G7FG 8#G78G G*:r#G7rG*#G%\GrW9$5WW9$O #$%O-$rJ9$5WJ9$8GA#$%A$r=B9$5W=B9$%$@%A$@%z$(z$*:z$,sz$.z$0z$3z$5Wz$eC]$8$,s89$9S|9$<FI$ V9F&]$<8$ V98]$ |;6t;>;pN >;K>;@>;> TR9PJ r ] $,s ] $!qb V^.+W^.!VW:P)PJ-C*:C < #%+W)H d +$%9$Up%UkB_Pup Specifications3All Pups originate at a Source Port and are routed to a Destination Port. Pup ports extend theaddressing normally found in networks both for communication with distinct processes in a singlehost and for communication with hosts on networks other than the local one. A Port identifies oneof 255 possible networks, one of 255 hosts in that network, and one of 232-1 sockets in that host.The Destination Port is specified by the source process. The Source Port is verified enroute. Thesource socket is provided and/or verified by the source host's process interface. The source host andsource network bytes are specified and/or verified by the first authority. Careful enroute assignmentand verification of Pup source ports is the basis for (inter)network access control.A source network of zero indicates that the source process does not know the identity of thenetwork to which its host is connected. A destination network of zero indicates that the Pup isaddressed to a host in the current network, i.e., the one over which the Pup is physically transmittedby the source process. This convention is for use by processes which know that they want tocommunicate with a known host on their own network, but can't find out which network they're on.We wish to avoid the situation in which processes on the same network can't communicate with oneanother because there is not an operating Gateway at the moment.If the destination host is zero, the process intends the Pup to be broadcast in the destination network(if such a broadcast capability is implemented in that network). The Pup is received by active portsat the given destination socket in all hosts on the specified network. By convention, we do not presentlypermit a Pup source to broadcast to any except a directly connected network; that is, broadcasts never propagate throughGateways.These conventions permit convenient communication among machines known to be on the sameunidentified network and provide a mechanism for finding Gateways. Processes will not be allowedto send Pups outside of their local network unless they know its identity. A process must be able tofind out the identity of its local network from its local network control program which in turn mustfind out from a directly connected Gateway. See the memo Naming and Addressing Conventions forPup for an elaboration on these topics.There may be from 0 to 532 Content Bytes in a Pup. Content bytes are carried in an integralnumber of 16-bit words. If the number of content bytes is odd, the last word is filled out with agarbage byte, not counted in the Pup's length.The Pup Checksum is an optional 16-bit, one's complement, add-and-cycle checksum computed overthe 16-bit words in the Pup's header and contents. It is intended as an end-to-end reassurance ofcorrect transport by intermediate hardware and software components, and is not associated with or areplacement for any network's existing error checking mechanisms (which are usually specialized todetect the specific sorts of errors commonly encountered on that network).The checksum is initialized to 0 and computed by repeated one's complement addition and leftcycle, starting with the Pup's Length word and ending with the last content word. Note that thechecksum includes the garbage data byte if there is one. If the result is the ones-complement value"minus zero" (177777B), it should be converted to "plus zero". 177777B is specifically defined tomean that the Pup carries no checksum.The Pup's checksum is carried with it from source to destination. If and when a Pup is alteredenroute, say when the hop count in the transport control field is incremented, its checksum must berecomputed. Our choice of the 1's complement add-and-cycle is intended to permit incrementalchecksum updating. The algorithm for updating the checksum after changing a single word of thePup is as follows (one's complement arithmetic used throughout):1.If the Pup Checksum is 177777B, do nothing.2.Subtract the old contents of the changed word from the new.3.Left-cycle this difference (n mod 16) bits, where n is the distance (in words) fromthe changed word to the Pup Checksum word. fpG bt ptp `A _C ]I9]r]Ip Zdtp't p X,: WZf UT R:" Qk*6 OZ Na'5 LT KWW I@ F=tp Eh [ C&r$ B9@ AE >pX <C ;zU 9_ 8p:t% 6p$ 4t p( 211 0. .t p@ ,R + R )_ (J %? #C "N rp1rp  & %M R ;" [ @,rp G; btptp *b ?/\tPup Specifications44.Add the result to the existing Pup Checksum.The foregoing procedure produces a correct Pup Checksum if and only if the original PupChecksum was correct.It may be assumed that the packet transport system will give its best efforts to the delivery of a Pup.It must be assumed, however, that Pups will sometimes be lost (even when they are "known" totraverse only networks that are believed to be "perfect"). If a Pup's checksum is checked enrouteand found to be in error, the Pup may be thrown away without even so much as a trouble report.Pups may also be discarded in the event of a buffer shortage or other resource limitation at any ofthe places through which it may pass. An optional Pup Error Protocol exists by means of which a Pup's sourcemay be notified of the packet's demise, but no process should depend on receiving such negative acknowledgments for all(or indeed any) lost packets. Many precautions will be taken to improve the chances of a Pup in gettingto its destination, but no amount of machinery can assure trouble-free transport.Pup EncapsulationPups are to be encapsulated to conform to the conventions and formats of a transporting network. Itis unlikely but in the spirit of Pup encapsulation to rearrange various portions of a Pup forconvenient handling; however, Pups must be seen by user processes and Gateways as definedpreviously.Pup encapsulation consists of two steps (sometimes accomplished in a single operation). First, thePup is transformed in whatever fashion is necessary to permit the entire Pup (including Header andChecksum) to pass through the transporting network as "data". This generally involves simplyadding network-dependent headers and/or trailers, but could also include encoding of data invarious ways (for transmission over phone lines, for example). Second, an immediate destination hostis derived from the Pup Destination Port. This will be either the final destination host (if that hostis directly connected to the network over which the Pup is about to be transported) or a Gatewayhost through which it is believed (by some sort of routing function) the final destination may bereached.When a Pup is received at its final destination port, it is decapsulated (by applying the inverse of theencapsulation transformation for that network) before being passed to the destination process.When a Pup is received by a Gateway, it is (1) decapsulated, (2) routed to another network, and (3)re-encapsulated according to the conventions of this new network.Ethernet EncapsulationRefer to Figure 2. The Destination byte (Immediate Ethernet Destination Host) is derived from thedestination port; it will be either the destination host itself, or a Gateway host through which thedestination can be reached.The Source byte (Immediate Ethernet Source Host) is the hardware address of the host transmittingthe encapsulated Pup through the Ethernet.The Type word identifies the packet as being a Pup so that it can be given Pup processing when itarrives at the immediate destination host. The Type of a Pup is 512.The Ethernet CRC (Cyclic Redundancy Check) is shown to distinguish it from the Pup's checksum.Pups will get the Ethernet's kind of error checking while exposed to the Ethernet's kind of errors.The CRC is computed and checked totally in the bit-serial portion of the local source anddestination Ethernet interfaces. fpGb, _9"5 ] Z<+ YJtp tp W.4 V@ R T\ S6'r7 Qe Ptp4 NQ Jbu G}pt pE E2+ DsA B @ X >6, <] ;z5' 9Kt 8pp7 tp 6/*t 5fp U 3 08t p /wU -[ ,mA (t %pt pt#p $J` " tpt p2 [* vtpE E  t pF H D } F 6?/ULEncapsulatedPupEthernet EncapsulationArpanet EncapsulationDestinationSourceType = "Pup"Ethernet CRCTypeHostLink0Figure 2. Pup Encapsulation0UGKQfGr0QG0QG0O $0L$0J$>;J$90H_9$0F&$IXH_9$0C$>;D$90?{$0A9$IXA9$0=B$08$>;=f$90; 9$IX; 9$0'$0$G9$G"sG.9"sG9"G.9'$; 9$9; 9$=f$998$9=B$A9$9A9$9?{$D$99C$H_9$9F&$9H_9$J$99J$9L$9O $9QG9QGQfGr9UGQC$$$,s$@$.QC@$.$$,s.$$"s@- %>9S|$S$90S|$>;Qf$r9rH5HqT- rT- Q #H 0$G,sK$G,s5T-BT-6tQCQVr9I?Pup Specifications5Arpanet EncapsulationAt present, Pups are encapsulated within Arpanet packets using the "old" Imp-Host leader format.The Type byte is zero, to denote that the packet is an Arpanet "Regular message".The Host byte (Immediate Arpanet Destination Host) is derived from the Pup Destination Port asdescribed previously. Note that when the message arrives at its immediate destination, this byte will have beenchanged by the Imps to identify the message's sender.The Link identifies the message as being a Pup. It should be 152.BiSync EncapsulationPups are encapsulated for transmission on low-speed synchronous lines using a data frame formatthat is a subset of the BiSync protocol. Synchronous line drivers also implement a network-dependent (non-Pup) line control protocol that enables maintenance of sub-network connectivity androuting information. That protocol is not described in this document.Echo ProtocolFor test and diagnosis purposes, a process receiving an EchoMe Pup may echo it (Figure 3). Beforedoing so, the receiving process should check the packet's checksum and the validity of the sourceport. If the packet checks out, it should be returned to its source as an ImAnEcho Pup withrecomputed checksum. If it fails to check out, but there is evidence that its source is correctlyidentified, then the packet should be returned as an ImABadEcho Pup. Note that the source anddestination ports must be exchanged, the Gateway hop count zeroed, and the type changed; thus,the checksum must be recomputed. If the receiving process accepts broadcast Pups, it (or the host's Pup handlingsoftware) must substitute the local host's actual address for the (zero) Pup Destination Host.The process controlling any port may choose to respond to EchoMe Pups according to the Echoprotocol; it is expected that most hosts will have a process prepared to echo and that perhaps acertain socket on each host will be reserved for this purpose. Well-known socket 5 is presently assigned toEcho servers.Rendezvous/Termination ProtocolSome terminology. Packets (including Pups) have a source and destination. A Rendezvous has alistener and initiator. Services have a server and user. Data, specifically byte streams, have a senderand receiver. These are independent descriptors. Usually the listener is also the server. The servermay be either the sender or the receiver of a byte stream depending on the service being offered.The Rendezvous/Termination Protocol is a convention by means of which a connection between twoports may be established and later broken. The manner in which the the processes communicateover an existing connection is the subject of other protocols (for example, the Byte Stream Protocol,to be described later).RendezvousA Rendezvous is accomplished with an exchange of packets, each called an RFC, a Request ForConnection (Figure 4).RFCs may be exchanged to establish a connection between a user process and a server process. Theports between which the RFCs are sent we call Rendezvous Ports. A user initiates by transmittingan RFC to a listening (server) rendezvous port. The listener confirms by returning an RFC withmatching Pup ID. In addition to the rendezvous ports carried in the Pup header, each RFC carriesthe address of a Connection Port through which the RFC's source intends to maintain the newly fpG bt _9pH \TtpI Yotptp- WrY V5 Sptp: Pt M*pX K:" J b HF Du A)p*8 ?&; >= tp <b ;5t p 9O 8 "rI 6^ 3p P 2dQ 05r. /~ +u (0p3tpt p &tptptptp+t %&ptp[ #J (t p 7/. [ - tt p:tpt  p %I tp#  T Y tp5 " >/]@RFigure 3. Echo Protocol Pup FormatFigure 4. Rendezvous/Termination Protocol Pup FormatsPup HeaderPup HeaderPup HeaderPup HeaderPup ChecksumPup ChecksumPup ChecksumPup ChecksumType is EchoMe, ImAnEcho, ImABadEchoType is RFCRequestor's Connection PortAbort CodeAbort TextArbitrary Content BytesType is End, EndReplyType is Aborts`G7LGsLeGsLGHs\<GsNGr+WGr2Gr)G r)eG#)eG Vr6tG,s6tGK0G,s/eG,s/G,s2GsGsGsG seG7+G Vs :Gr/9$r-9$0$9/]$/9$s$rGf# 6$q_J 5 85 $ #M ) 70 # ]$!V/9$!V-9$2 p.e$d $ :UJ4q2# Hr GfUmPup Specifications6established connection.The Connection Port is separately specified so that, for example, a server can handle requests forservice at a single, widely advertised rendezvous port and provide the service concurrently to anumber of users via a number of connection ports. The connection port may be the same as therendezvous port, and we expect this will be the case for most user processes and for servers notcapable of spawning multiple instances of themselves.The Pup ID of the initiating RFC also defines the Connection ID for the resulting connection. Itshould be chosen in such a way as to reduce the probability of confusion among connectionsestablished near in time; the identifier in the complementing and confirming RFC must match. Ifconnection IDs are generated from an appropriate real-time clock, for example, the probability ofPups from an extinct connection being mistaken for Pups in a new connection between the samepair of ports may be made vanishingly small.If an initiator's RFC is lost, it should be retransmitted by the initiator after enough time has passedfor a normal answer, say something like 1 or 5 seconds. Duplicate RFC's can, at best, be discardedon the basis of state information kept in the normal course of providing service. Upon detecting aduplicate RFC, the receiver must, of course, retransmit the appropriate answering RFC before discarding the duplicate.At worst, multiple servers will be generated to which no packets are ever sent; these servers shouldeventually time out and destroy themselves.Normal TerminatonA connection is normally terminated by a three-way handshake consisting of an End Pup and twoEndReply Pups. The end of a connection may be initiated from either of its ports by transmissionof an End Pup whose ID matches the Connection ID. The End Pup must be retransmitted until amatching EndReply Pup is received. Upon receiving an EndReply, the initiator of the End shouldthen send an EndReply in response and promptly self destruct.The receiver of the End Pup responds by returning an EndReply Pup with matching ID and thendallying up to some reasonably long timeout interval (say, 10 seconds) in order to respond to aretransmitted End Pup should its initial EndReply be lost. If and when the dallying end of thestream connection receives its EndReply, it may immediately self destruct.In the normal case, an End Pup and two EndReply Pups will be required to promptly close aconnection. The receiver of an End Pup must dally after sending its EndReply just in case theEndReply is lost and the End is retransmitted. The longer the dallying period, the higher theprobability that both ends of a stream connection will be able to agree on its normal termination.The purpose of the second EndReply, the one sent by the end initiator, is to attempt to notify thedallying end that it need not dally longer. Thus, in the normal case, three Pups and it's over; in aslightly less normal case (the End initiator's final EndReply is lost), the dallying end will dally for itstimeout wasting resources; in the arbitrarily unlikely case that the dallying end self destructs beforean EndReply has been successfully received by the end-initiating port, the initiator will feel that thestream was terminated abnormally while the dallying end will feel everything went AOK.It may happen that both processes choose to send End Pups simultaneously. Upon receiving anEnd Pup in seeming answer to an End Pup of its own, a port should at once send an EndReply andbegin dallying in the normal fashion (i.e., it should abandon sending Ends).Abnormal TerminationThe Abort Pup should be used to terminate a connection (or a connection attempt) in the event of adetected catastrophe. An Abort can be sent to reject an RFC or to terminate a connection in theevent of a catastrophe, say storage overflow or continuing checksum errors. A listener wishing toreject a rendezvous should try to send an Abort Pup with an explanation (e.g., "disk full" or "paperjam" or "tape busy"). Either end of a connection in progress, with its back against the wall, shouldtry to send an Abort before self destructing, though its demise will eventually be detected anyway fpG b _9U ]B \/M Z+5 Y%5 V@2t p T@ S6] QO P,< N, K@' J=^ HQr G3U! EpV D)+ @pt =pNtp <tp#6 :C 8? 7w= 4D 3 tpQ 11. 0J -C +R *Z (C ' ;' %e $"I "{M S qV I Q L t ptpF _N L U\ >' K[v ?/]pPup Specifications7(by timeout).The Abort Pup carries a program interpretable code and a human readable explanation of someabnormal condition. An Abort must carry as its Pup ID the ID of the connection being aborted--the ID of the connection's initiating RFC. Abort Pups need not be acknowledged because it ispresumed that there would be nobody to receive the acknowledgment. Of course, receiving anAbort is itself something of a catastrophe and an Abort might be sent in seeming answer, just forcompleteness--it would most likely arrive at an inactive port and be discarded.The Abort code is for program interpretation and the Abort text is for human consumption. Thecodes should be registered and the text printable.Byte Stream ProtocolThe error- and flow-controlled transfer of bytes between two processes may be accomplished using abidirectional byte stream maintained using the Byte Stream Protocol (BSP). A byte-streamconnection between two ports is generally established and destroyed by means of theRendezvous/Termination protocol described previously.Byte Stream MaintenanceBytes in a stream are numbered consecutively by a 32-bit number referred to as the Byte ID, whichis initialized to the Connection ID (i.e., the Pup ID used for the rendezvous) when the connection iscreated. A byte stream is carried from one port to another by Data Pups, each containing zero to532 consecutive bytes starting with the one identified by the Pup's ID. In return for these aretransmitted Acknowledgment packets with matching identifiers (though not necessarily on a one-to-one basis) which verify correct receipt and control flow. The streams of data flowing in eachdirection, while starting with the same initial byte ID, are independent.Data packets should not be sent unless space has been allocated for them at the stream receiver.The sender is informed about receiver allocations in the Acknowledgment Pups returned by thestream receiver. These allocations are not additive; each one reflects the current state of thereceiver's space allocation at the time of departure of its transporting Acknowledgment. Acks andtherefore allocations travel in both directions, independently for each direction of data flow.There are two kinds of data Pup under the BSP, one which demands an immediateacknowledgment, called the AData Pup, and one which doesn't, called the Data Pup. All data mustbe positively acknowledged, but not on a strict packet-for-packet basis. It is intended that data willbe transmitted in a number of Data Pups followed by an AData Pup asking for acknowledgment ofreceipt of all.Data which have been transmitted but not acknowledged must be retransmitted after some timeout.If there are too many retransmissions, a stream connection may be aborted.We expect that null AData Pups (containing no data bytes) will be used to probe a receiver for anupdate of the allocation block and receiver byte ID. This will probably happen when a byte streamis first established and the sender has no allocation information or when the sender has been heldup for some time with a zero allocation and wants to verify that the receiver is still alive.The Ack Pup indicates to the sender that all bytes previous to that identified by its Pup ID havebeen received correctly. A received Ack whose Pup ID is less than the previous one should be considered a delayedduplicate and discarded. Also, it carries a 3-word allocation block indicating the receiver's state as of thetime the Ack was sent. The stream sender should update its state to reflect the cumulativeacknowledgment denoted by the Pup ID (e.g., discard Data packets being held for possibleretransmission) before considering the updated allocations.The most recent allocation block indicates the maximum number of bytes per Pup that the receiveris willing to accept. Similarly, the number of Pups and number of bytes total which can safely be fpG b _9< ]@ \/W Z? Y%=$ WO TB S62 Nu Kp02 J?: HQCR G55 C|t @pH ?B# =?tp  <K :a 8 T 7yI 4` 34t p 1+5 0R .0/ +D%E( *tp tp (H ' 0- % ":% !J 8I J .J M U ?r(0 p,* 5@ ; +; FX _H z?/]_Pup HeaderPup HeaderPup HeaderPup ChecksumPup ChecksumPup ChecksumPup ChecksumPup HeaderFigure 5. Byte Stream Protocol Pup FormatsType is Data or ADataType is AcknowledgmentData BytesMaximum Bytes per PupNumber of PupsNumber of BytesOptional PosAck/NegAck BlocksType is Mark or AMarkType is InterruptInterrupt CodeInterrupt TextMark Byter`G#LGrLeGrLGHr\<GrNGr:Gr=Gr8G +r8eG#8GrAG,s2G,s=G,s/G,s/eGK0G,sAG,s; $q_J @- 8@- M 9 70 7M 8_J ,sNG,s\<G,sLGH,sLeGKLG,s`Gr%* Vq]4;]pUJ ,sZ&$,sW$,sU$4;Z6tX6tVf1sQ q>6t>7p;76,;-$9V; Qr%Gf;Pup Specifications8sent are limited. The maximum number of bytes per Pup and the number of bytes total are bothexpressed in terms of the number of data bytes, exclusive of the fixed-length Pup headers involved.The "Number of Pups" allocation indicates the maximum number of additional Data Pups thestream receiver is prepared to handle, over and above any Data Pups it has already received andmay be holding in its buffers. In making use of this allocation, the stream sender should assumethat any Data Pups that it has transmitted but which have not been acknowledged have in fact not(yet) reached the receiver. Hence, the "Number of Pups" allocation should be compared to thenumber of unacknowledged output Data packets in order to determine whether or not it is OK togenerate additional Data packets.The "Number of Bytes" allocation should be interpreted relative to the Ack's ID, i.e., the byte ID ofthe first byte yet to be acknowledged. Adding the allocation to the Pup ID of the Ack in which itcame yields the ID of the last byte in the stream which the receiver is prepared to accept. This byteID implied in Acks should be monotonically increasing so that stream senders need not hold backexisting data Pups they had previously committed to transmit. In general, this means that a stream receivershould not decrease the total amount of storage allocated for buffering received Data Pups during the life of a connection.However, strict adherence to this policy may be difficult to implement; hence, small, short-term decreases in allocationshould be tolerated by stream senders. Similarly, the maximum number of bytes per Pup should not bedecreased during the life of a BSP connection, so that stream senders need not take existing dataPups and break them apart.Optionally, an Ack Pup may carry up to 85 specific acknowledgments, described by Pos/NegAckBlocks. Each is a 3-word item indicating that a specified interval of bytes in the unacknowledgedpart of the byte stream is known by the receiver to be either received or lost. The purpose of theseindications is to hasten the retransmission of bytes known to be missing and to avoid theretransmission of bytes already received. Once a receiver indicates with a PosAck Block that aninterval of bytes has been received, the sender may discard the packets which contain them knowingthat they will not require retransmission.Each 3-word Pos/NegAck Block begins with a bit indicating whether the interval is known to bemissing or received: a one indicates that the bytes in the interval have been received. The next 15bits hold the number of bytes in the interval. And the next 2 words hold the byte ID of the firstbyte in the interval. To simplify processing of Pos/NegAck Blocks by the stream sender, theintervals denoted by successive blocks in the same Ack should start at monotonically increasing ByteIDs and should not overlap.The transfer of bytes from stream sender to stream receiver should not depend on thesePos/NegAck Blocks being used by either end, except that bytes might flow with less efficiencywithout them. A receiver may choose not to include Pos/NegAck Blocks in its Ack Pups and asender may choose to ignore them if present.Experience has shown that when communicating over high-bandwidth, low-loss networks such as the Ethernet, thesoftware overhead required to generate and interpret specific acknowledgments is not rewarded by any noticeableimprovement in performance. No software presently implements specific acknowledgments.Marks and InterruptsThe Mark is a distinguished byte in the byte stream. It is analogous to the file mark found onmagnetic tapes. The length of a Mark Pup is always 23. It carries exactly one content byte whichindicates which of a possible 256 types of mark is being signalled.While reading the data from a stream, a process reads up to a Mark and is then signalled in muchthe same way as when reading up to an end-of-file. The type of Mark should then be accessible.After clearing mark status, the user should be able to read on in the stream.For purposes of transmission and flow control, Marks are treated exactly the same as Data Pups.They occupy one position in the Byte ID sequence, and are acknowledged in the same manner asany other byte in the stream. An AMark Pup is simply a Mark that demands an immediateacknowledgment (in the same manner as an AData). fpG bL `$tp* ]< \/D ZZ Y%\ WC VQ T! QB# P,D N7/ M"D K 2r- J<$W H(Q Gp> FH D Atpt @*p=t >pe = : ;O : W 8* 5./ 4'I 2b 1\ /S . +.2$ )R ($3( &, #r_ "` !cW t ptp@ d\ C =# uD M  4+ 1+ "tp+ |0* 5?/]Pup Specifications9An Interrupt Pup is used to signal some asynchronous event requiring immediate action by the otherend of a stream. The Interrupt Pup is not subject to BSP flow control allocations and jumps overany and all buffered data. We envision using the Interrupt Pup in conjunction with the Mark Pupfor flushing buffered data from a stream in response to some abnormal condition.An Interrupt Pup should not be sent until the previous Interrupt Pup has been acknowledged withan InterruptReply Pup. Interrupt Pup IDs are generated from the stream's send Interrupt ID, whichis initially the Connection ID. Successive interrupts advance the Interrupt ID. An Interrupt shouldbe retransmitted until acknowledged.Upon receipt of an Interrupt Pup, it should be acknowledged with an InterruptReply Pup only if itsID is equal to or one less than the current Interrupt ID. If its ID matches the current Interrupt ID,the using process should be signalled and the Interrupt ID advanced. If its ID is one less than thecurrent Interrupt ID, it is a duplicate and should therefore be acknowledged without giving rise to anew signal to the process.Interaction with Rendezvous/Termination ProtocolThe Byte Stream Protocol interacts with the Rendezvous/Termination Protocol in two importantways. First, the Connection ID (i.e., the Pup ID of the initiating RFC) is used to initialize thestream's Byte IDs and Interrupt IDs for both directions, as has already been explained.Second, to ensure clean and unambiguous termination of the byte stream, it is required that astream sender delay transmitting either an End or an EndReply until all outstanding Data andInterrupt Pups have been acknowledged. For the same reason, it is forbidden to transmit (or evenretransmit) Data Pups once an End or EndReply has been sent.In the typical scenario for terminating a BSP connection, one of the processes decides that theconnection should be closed. It first waits until no unacknowledged Data or Interrupt packetsremain, then transmits an End.At the other end of the connection, the process eventually exhausts the incoming byte stream and isnotified that an End has been received, thereby terminating the stream. It now proceeds in turn totransmit any remaining data, wait until no unacknowleged Data or Interrupt packets remain,transmits an End Reply, and begins dallying.In the meantime, the first process (the one that originally requested termination) reads the remainderof the incoming byte stream. When the stream is exhausted and the End Reply has been received,the process is notified of termination of the incoming stream. It now sends the answering EndReply(to terminate the other, dallying process) and is free to destroy the port.Registered Pup TypesThe Pup Types for the protocols described in this document are assigned the following values:TypeAssignmentEchoMe1ImAnEcho2ImABadEcho3Error4RFC8Abort9End10EndReply11Data16AData17Ack18 fpG btp J `B _'9 ]P ZH Y%t pK WL V$ S6[ QP P,E Nc M" Iit0 Fp\ DF CzW @V ?4( =B <t p2 9!N 7D 6 32 W 1H 0(Z ., +\ *9B (Z '/K "u p:#t# p( n(  ( d( ( Z( ( P(  (  F(  (  | z>/]BPup Specifications10Mark19Interrupt20InterruptReply21AMark22 fpG?b( `( _ ( ]( < ]H * TIMESROMAN  TIMESROMAN  TIMESROMANLOGO TIMESROMAN  TIMESROMAN  TIMESROMAN HELVETICA  HELVETICA  HELVETICA  TEMPLATE@  ~ ((* 3Z5 @ JSL }W_a%')Fi'9AZ%!*i>%)*%T9T9R =  %)ii9Z%-i%)ii@EmY Z  %+9+9)   Z  TWZ :Z"*i?B"Pj/db' PupSpec.pressTaftP 3-Sep-79 18:48:01 PDTb