je vinss Al GALLIC
`{U-Ge f-cte
`
`4 io GO /
`
`Pi
`
`THE XPRESS TRANSFER PROTOCOL
`(XTP)
`A TUTORIAL
`(Short Version)
`
`:
`rot
`“al
`BO.
`35
` §8:
`
`~N
`
`ae
`rm
`QE
`=
`cal
`
`-
`
`—
`
`|
`_ Robert M. Sanders
`Alfred C. Weaver
`_
`
`Digital Technology
`
`January 1990
`
`Cooperative Agreement NCC 9-16
`Research Activity No. SE.31
`NASA Johnson Space Center
`Engineering Directorate
`Flight Data Systems Division
`.
`
`we
`=~
`
`©
`
`©
`
`ee
`
`a=
`
`-
`
`-
`
`a:
`~
`
`—
`
`a
`~
`cS
`~
`4
`s
`
`=G
`
`_
`
`_
`
`—
`
`oe
`a
`om &
`o
`pet
`Ww
`arian’
`ao
`w
`zn
`x =
`“a
`— a
`UL anal
`a <
`“<x
`ue a
`I>
`
`me
`
`rt
`
`—
`
`.
`
`—
`
`—
`
`ia
`—
`=
`Be
`:
`ft
`oe
`On
`.
`ot ee)
`On >
`bees
`Ce we
`isk
`Oe« C
`=
`ae 5
`:
`wr ~i
`Pe
`WI 3 90
`—
`Low
`=
`™ 0
`~
`.
`es
`q 5 3
`Research Institute for Computing and Information Systems
`ae
`Zest
`University of Houston - Clear Lake
`
`
`
`~~ T-EsC-H-N-I-C-A-L
`
` R-E-P-O-R-T
`
`Page 1 of 22
`
`GOOGLE EXHIBIT 1016
`
`Page 1 of 22
`
`GOOGLE EXHIBIT 1016
`
`

`

`{ td
`
`aa
`
`'
`
`Wk
`
`Ki.
`
`MuthaHt
`
`i...&
`
`Gil.
`
`Gil...
`
`Whois
`
`Mis),
`
`
`
`The
`
`dda
`
`Ria
`
`The University of Houston-Clear Lake established the Research Institute for
`Computing and Information systems in 1986 to encourage NASA Johnson Space
`Center and local
`industry to actively support research in the computing and
`information sciences. As part of this endeavor, UH-Clear Lake proposed 4
`partnership with JSCtojointly define and managean integrated program ofresearch
`in advanced data processing technology needed for JSC’s main missions, including
`
`administrative, engineering andscience responsibilities. JSC agreed andentered into
`a three-year cooperative agreement with UH-Clear Lake beginning in May,1986,to
`Concept
`jointly plan and execute such research through RICIS. Additionally, under
`Cooperative Agreement NCC 9-16, computing and educationalfacilities are shared
`
`Masai
`by thetwoinstitutions to conducttheresearch.
`:
`Themissionof RICIS istoconduct,coordinate|and disseminate research On
`
`computingand information systems among researchers, sponsors and users from
`
`
`UH-Clear Lake, NASA/JSC,and other research organizations. Within UH-Clear
`
`Lake,themission is being implementedthrough interdi
`linary involvement of
`faculty and students from each of the four schools: Business, Education, Human
`Sciences and Humanities, and Natural and Applied Sciences.
`Other research organizations are involved via the “gateway” concept. UH-Clear
`Lakeestablishes relationships with other universities and research organizations,
`having commonresearch interests, to provide additional sources of expertise to
`conduct needed research.
`A major role of RICIS is to find the best match of sponsors, researchers and
`research objectives to advance knowledge in the computing and information
`sciences. Working jointly with NASA/JSC, RICIS advises on research needs,
`recommends principals for conducting the research, provides technical and
`administrativeitivesupport to coordinate the research, and integrates technical results
`“intothe cooperative goals of UH-Clear Lake and NASA/JSC.
`
`
`
`wd
`
`hi,iihhi,4
`
`Page 2 of 22
`
`k.Hides
`
`Page 2 of 22
`
`

`

`|1
`
`=||oe||eei!a
`
`(‘a
`
`THE XPRESS TRANSFER PROTOCOL
`(XTP)
`A TUTORIAL
`(Short Version)
`
`Robert M. Sanders
`Alfred C. Weaver
`
`Digital Technology
`
`January 1990
`
`Cooperative Agreement NCC 9-16
`Research Activity No. SE.31
`
`NASA Johnson Space Center
`Engineering Directorate
`Flight Data Systems Division
`
`es
`
`ResearchInstitute for C.omputing and Information §ystems
`University of Houston - Clear Lake
`
`
`T-E-C-H-N-1-C-A-L
`R-E-P-O-R-T
`
`
`
`Page 3 of 22
`
`Page 3 of 22
`
`

`

`
`
`Page 4 of 22
`
`Page 4 of 22
`
`

`

`
`
`Preface
`
`This research was conducted under auspices of the Research Institute for
`Computing and Information Systems by Robert M. Sanders, Alfred C. Weaver and
`Digital Technology. Dr. George Collins, Associate Professor of Computer
`Systems Design, served as RICIS technical representative for this activity.
`
`Funding has been provided by the Engineering Directorate, NASA/JSC
`through Cooperative Agreement NCC 9-16 between NASA Johnson Space Center
`and the University of Houston-Clear Lake. The NASAtechnical monitor for this
`activity was Frank W. Miller, of the Systems Development Branch, Flight Data
`Systems Division, Engineering Directorate, NASA/JSC.
`
`The views and conclusions contained in this report are those of the authors
`and should not be interpreted as representative of the official. policies, either
`express or implied, of NASA or the United States Government.
`
`
`
`Page 5 of 22
`
`Page 5 of 22
`
`

`

`
`
`Page 6 of 22
`
`Page 6 of 22
`
`

`

`
`
`The Xpress Transfer Protocol (XTP) — A Tutorial
`
`Robert M. Sanders and Alfred C. Weaver
`
`Computer Networks Laboratory
`Department of Computer Science
`University of Virginia
`
`Introduction
`XTP is a reliable, real-time, light weight transfer’ layer protocol being developed by a group ofresearchers
`and developers coordinated by Protocol Engines Incorporated (PED).!!.23] Current transport layer protocols such
`as DoD’s Transmission Control Protocol (TCP)'4! and ISO's Transport Protocol (TP)'*! were not designed for the
`next generation of high speed, interconnected reliable networks such as FDDI and the gigabit/second wide area
`networks. Unlike all previous transport layer protocols, XTP is being designed to be implemented in hardware as
`a VLSI chip set. By streamlining the protocol, combining the transport and network layers and utilizing the
`increased speed and parallelization possible with a VLSI implementation, XTP will be able to provide the end-
`to-end data transmission rates demanded in high speed networks without compromising reliability and
`functionality. This paper describes the operation of the XTP protocol and in particular, its error, flow and rate
`control, inter-networking addressing mechanisms and multicast support features, as defined in the XTP Protocol
`Definition Revision 3.4."1)
`
`Future computer networks will be characterized by high reliability and very high data transmission rates.
`Traditional transport layer protocols, such as TCP and TP4, which were designed in an era ofrelatively slow and
`unreliable interconnected networks, may be poorly matched for the emerging environment. Although they contain
`many necessary features, such as error detection, retransmission, flow control and data resequencing, they are
`deficient in many respects — they do not provide rate control and selective retransmission, reliable multicast is
`Not supported, their packet formats are complex and require extensive parsing due to variable header lengths and
`support of complex modes. These protocols manage many timing events at both the sender and the receiver — for
`example, since the sender does notinitiate receiver data acknowledgements, both the receiver and sender require
`an additional imer. The data transmission rates assumed are no longervalid and maylimit the scalability of the
`protocols — in TCP, for example, which was designed in an era of 56Kbps data transmission rates, the flow
`window size is small, and based on.16 bit byte sequencing. Finally, the state machines for these transport
`protocols were intended for sequential rather than parallel execution. For example, the placementof the checksum
`field was considered arbitrary and so it was placed in the header.
`
`XTP provides for the reliable transmission of data in an inter-networked environment, with real-time
`processing of the XTP protocol — i.e., the processing time for incoming or outgoing packets is no greater than
`transmission time. XTP contains error, flow and rate control mechanisms similar to those found in other more
`modem transport layer protocols’ in addition to multicast capability. Timer managementis minimized — in XTP
`there is only one timer atthe receiver, used in closing the context. XTP has a 32 bit flow window. XTP’s state
`
`1. The transfer layer is formed by combining the functionalities of both the network and transport layers of the ISO
`OSI model into a single layer.
`2. Specifically,
`two other modern transport layer protocols — Versatile Message Transaction Protocol! (VMTP)
`developed at Stanford University by David Cheriton, and Network Bulk Transfer (NETBLT) developed ar MIT by
`David Clark.
`
`—
`
`Page 7 of 22
`
`Page 7 of 22
`
`

`

`
`
`machine is specifically designed for parallel execution. Address translation, context creation, flow control, error
`control, rate control and host system interfacing can all execute in parallel.
`is a fairly simple yet
`it
`The XTP protocol is considered a lightweight protocol for several reasons. First,
`flexible algorithm. Second, packet headers are offixed size and contain sufficient information to screen and steer
`the packet through the network. The core of the protocolis essentially contained in four fixed-sized fields in the
`header — KEY, ROUTE, SEQ and the command word. Additional mode bits and flags are kept to a minimum to
`simplify packet processing.
`
`Types of XTP PDUs
`XTP utilizes two frame formats, one for control packets and onefor information packets (see Figure 1).
`
`INFORMATION PACKET
`
`CONTROL PACKET
`
`
`
`(24 Bytes)
`
`(24 Bytes)
`(16 Bytes)
`(Variable Length)
`Figure 1. General Frame Formats
`
`(Variable Length)
`
`(16 Bytes)
`
`
`
`Both formats share a common header segment and a common srailer segment, each of constant length. Each
`XTP packetincludes a variable length segment between the header and trailer whose segment type determines the
`packet type. The important fields are aligned on 8 byte boundaries so that they can be quickly accessed by any
`machine with 2 byte, 4 byte or 8 byte alignment. The formats are described in greaterdetail later.
`The common header specifies the packet type and identifies what portion of the data stream, if any,
`is
`
`
`included in the information segment. Optional modes, such asdisabling error checking or multicast transmission,
`‘are indicatedin the packetheader’s controlflagsfield. The commonsailercontainstwochecksum fields,
`identifies how muchof the data stream has been delivered to the receiving client application, and also contains a
`flags field. These flags generally control state changes, for example closing the data transmission connection or
`requesting data acknowledgement. Message boundaries are also specified in the trailer by setting the end of
`message flag (EOM).
`
`The information segment contains the user data being transferred, and is also used to pass.addressesandother
`miscellaneousdata when appropriate. Each datapacketcontains a contiguoussubset ofthedatastreambeing
`transferred. In XTP, there is no protocol-imposed upperlimit on the numberof bytes included in each data packet
`— each implementation is bounded by the underlying datalink layer. For each implementationthis limitiis known
`as the maximum transmission unit (MTU)andis foundbysubtractingthe XTPheaderandtrailersizes fromthe
`datalink’s maximum data field size. XTP supports two additional modes of data transfer which allow out-of-
`oa tagged data ofconstantlength (8 bytes) to beincludediinadata packet along with the user's data, These
`
`
`beginningorat theendoftheusualuser
`data.‘Their presence is indicated by flags in the header and iriler‘ihe tag). Beginning tagged data are indicated
`by the BTAG flag in the common header. Ending raggeddata are* Specified with the ETAGflag in the:common
`The control segment contains the receiver's error, flow and rate control parameters’ values. This$ segment
`also contains fields used to resynchronizethe transmitter and receiver when necessary.
`
`trailer,”
`
`TT
`
`Multi-Packet Handshaking
`In XTP, multi--packet exchange sequencesprovide user applications withboth a transport-level virtual circuit
`capability and a transport-level datagram service. For example, in XTP a connection mayconsist of an exchange
`of three packets, as shown in Figure 2.
`
`Page 8 of 22
`
`till6)t
`
`tolilAssoiam
`
`Page 8 of 22
`
`

`

`DESTINATION
`
`PACKET FUNCTIONoO
`
`e Request context termination
`
`FIRST (A)
`
`FIRST (A)
`
`e Request context be established
`e Transmission ofuser data
`
`CONTROL(B)
`
`CONTROL (B)
`
`® Acknowledge contextinit request
`e Acknowledge user data reception
`e Acknowledge context termination
`request
`e Inform destination that sender
`has terminated context
`
`Figure 2. Three Packet Connection-Mode Handshake
`
`The scenario above depicts how XTP can reliably set up a connection between two user processes, transmit
`data, and close the connection with a minimum ofthree packets.
`In this scenario, the sourceinitially transmits
`packet (A). At the destination the header is examined and it is determined that the source wishes to establish a
`Send connection. If the destination wishes to comply, a contextis established. The packet's data are then queued
`for transfer to the waiting destination user process.
`
`After successfully transferring the received data to the host, the destination complies by sending control
`packet (B). This packet acknowledges the receipt of the data, and indicates that the destination is also ready to
`close the connection. On receiving packet (B), the sender emits control packet (C), and closes its side of the
`connection — thus completing the three way handshake. Any buffers still associated with the connection are
`freed, and the sender will no longer respond to control packets arriving for the context. When packet (C) is
`received by the destination, the connectionis closed.
`
`In XTP the burden of detecting lost acknowledgements is assummed by the sender. The sender requests
`acknowledgement by setting the status request bit (SREQ) in the XTP commonwailer. A timer (WTIMER)is
`used by the sender to determine if the receiver has failed to respond to a sender-generated request for current
`status and data acknowledgement. If the timer expires before an acknowledgementarrives, the sender assumesthe
`acknowledgment was lost, and sends another request for a control packet acknowledging the received data. On the
`other hand, when closing, the source acknowledges context termination, so that the receiver can be sure that the
`context is closed. If this last packet gets corrupted or lost, the receiver will eventually timeout and close the
`connection.
`a
`—
`
`Unlike TCP, where each data packet would be retransmitted after the timeout, in XTP only a CNTL packet
`containing the SREQ would be sent. The corresponding retumed CNTL packet would indicate which data
`packets, if any, to retransmit. This is a conservative procedurewhich forces a “synchronizing handshake"before
`retransmitting except when retransmissionis explicitly indicated by the receiver.
`Closing an XTP connection is coordinated using the three flags RCLOSE, WCLOSEand END.Thelocal host
`sets the RCLOSEor WCLOSEflags in an out-goingpacket to inform the remote hostthat it has completed all
`reading orwritingitintends to perform on the shared connection. Note that in a full duplex connection between
`two nodes A and B data would be transmitted in both directions (A-8 and BA). Using RCLOSE and
`WCLOSE,each direction can be shutdownindependently.
`
`The END flagis set in an outgoing packetto signal to the remote host that the local host released or closed its
`end of the connection. Thus, END is set in the final packet transmitted, and indicates that the context has been
`terminated — i.e., that it is gauranteed that no further packets can be exchanged. If, at any time, a packet is
`received with the END bit set, the context is assumed closed at the remote end, and the local host releases the
`
`q
`
`{I
`
`: e
`
`son,
`e
`7
`
`Page 9 of 22
`
`Page 9 of 22
`
`

`

`
`
`context.
`
`The "close" protocol based on END, RCLOSE and WCLOSEcan uniformly support the three packet graceful
`termination of Figure 2, an abbreviated termination, transactions, and abort situations without modification.
`
`Two-packet, transaction-like packet exchange sequencesare also allowed in XTP and are referred to as fast
`handshakes. For full duplex connections, these modes are less reliable than the three packet connection. The two
`packet fast close can be considered a transport level datagram service or the basis for simple request/response
`operations.
`
`Note that whena data acknowledgment is requested in XTP,as in the FIRST packetof Figure 2 (packet A),
`the acknowledgment
`is not necessarily provided immediately.
`In the fast close cases,
`the receiver delays
`acknowledgment until all data received prior to the SREQ have been processed. This includes the data contained
`in the packet with SREQ.
`
`XTP contains a second status request flag in the commonheader flags field which is called DREQ. DREQ
`differs from SREQ in that SREQ requests a response immediately from the receiver, and DREQ requests it after
`the currently queued data have been received at the receiver. This is useful because the acknowledgementis
`delayed until the receiver has freed the buffer space associated with the queued data andis capable cof accepting
`more data from the sender. Flow control blocking is minimized.
`-
`In closing, SREQ behaves like DREQ — if this were not so,
`the receiver might generate its final
`acknowledgement packet before the data from the last information packet has been delivered to the receiving
`client. But the sender could not close the context since unacknowledged data exists. Thus, in closing, SREQ
`responses are delayed until all data have been processed.
`
`Flow control allows the receiver to inform the sender aboutthe currentstate of its receiving buffers. In XTP,
`the receiver's flow control parameters are included in control packets sent from the receiver to the sender. These
`parameters are shown in Table 1.
`
`Flow Control
`
`
`
`LLOC 32 bit sequence number|controlsegn|controlsegment|1 +sequesequencencenumberoflastbytereceiverwillac|_|+sequencenumberoflastbytereceiverwillaccept|receiverwill accept.
`
`
`
`
`“32bilsequencenumber|common—kad+ sequencenumberoflastbyte receiverdeliveredto
`
`
`
`
`destination client process.
`
`32 bitsequence number|control segment I + sequence number of last byte receiver accepted.
`ALLOC - DSEQ
`Size of receiver's data buffer in byes.
`
`
`RSEQ - DSEQ
`Number of bytes received and waiting to be transferred to destination client process.
`TABLE 1. XTP Flow Control Parameters
`
`
`
`
`
`aA
`
`ALLOCconstrains the sender from introducing more data than the receiver's buffers can accept. The sender
`refrains from sending bytes with sequence number ALLOCorhigher. Thus, ALLOCis one gteater than the
`highest byte sequence numberthatthe receiver will accept. DSEQ is the sequence numberofthe next byte to be
`delivered to the destination applicationprocess,or client. Likewise, DSEQ can be thought of as one greater than
`the sequence numberof the last byte delivered to the destination Client. Allbytes with sequencenumberlessthan:
`DSEQ have been successfully transferredtothe destination client. DSEQisalwaysless than or equal toALLOC.
`Subtracting DSEQ from ALLOC (modulo 2%) yields the buffer size allocated in bytes to the context by the
`
`
`receiving XTP process. Thus, XTP uses a byte-oriented allocation scheme as in TCP instead of apacket-oriented
`allocation scheme as in TP4. An advantagetothis policyisthat byte-orientedallocation isnotaffected by intemet
`fragmentation.
`@ii
`The sender holds data‘thathavethavebeen,transmittediina buffer untilitknowstthedata have beendeliveredto.to.the
`destination client. As longasthedata are buffered, it can beretransmitted if necessary. When the sender notes
`
`will).
`
`ai
`
`aii
`
`l
`
`Page 10 of 22
`
`Page 10 of 22
`
`

`

`that DSEQ has been extended, it frees the buffers associated with the delivered data.
`
`RSEQ is the sequence numberofthe first byte not yet received contiguously from the network. This can be
`the first byte in the first gap, or the first byte in the next data packet expected. As with ALLOC and DSEQ,an
`alternative interpretation exists for RSEQ. All bytes associated with sequence numbers less than RSEQ have been
`buffered by the receiving XTP processat the destination, but may not have been delivered to the destination client
`process yet. Thus, RSEQ is one greater than the largest consecutively received data byte sequence number. The
`sequence numbers of all bytes associated with gaps lie between RSEQ and ALLOC.
`
`Collectively, these parameters provide the means for XTP to implement flow control whereby the receiver can
`restrict the sender from sending excessive data prematurely. Note that all sequence number parameters in XTP
`occupy 4 bytes — SEQ, RSEQ, DSEQ, ALLOCandthe sequence numberpairs contained in the SPAN field of
`CNTL packets associated with gapsin the received data stream.
`
`It should be observed that each byte still in the dit pipe,i.e., each byte currendyin transit or still subject to
`retransmission, must be uniquely identifiable, so that retransmission is possible.
`In TCP/IP sequence numbers are
`limited to 16 bit numbers with only 2!° = 64K bytes possible in the bit pipe at any given point in time. On the
`other hand, XTP’s 232 bit pattems yield over 4 billion unique sequence numbers. Thus, XTP is more naturally
`suited to networks with both high bandwidth and/or high end-to-end latency than TCP/IP.?
`Once the sender has been informed ofthe receiver’s allocation limit via the ALLOC parameter, it continues to
`transmit until the allocation has been reached, without the need for individual acknowledgements of each packet
`transmitted. Thus, XTP more efficiently utilizes the higher reliability of modem networks, such as fiber optic
`LANs, Once the allocation has been reached, the XTPsender process sets the SREQ parameterin the last data
`packet transmitted, and the receiver respondsas earlier described with a control packet that acknowledgesall data
`received, describes any gaps detected, and, if appropriate, advancesthe allocation.‘
`An alternative allocation policy exists in XTP based on the size and availability of the receiving client
`application's buffers. This mode is referred to as reservation mode. In reservation mode, the transmission is
`determined by the size of the receiving user’s buffers reserved specifically for the context (by setting ALLOC to
`the size of this reserved buffer). In this mode, the sender must pause between message transmissions until the
`receiving client has posted a new client buffer to receive the next message. This is necessary to separate adjacent
`messagesinto different client buffers, since each message may notentirely fill its buffer.
`In reservation mode,the reservation buffer size may differ greatly from the normal allocation size, and may be
`greater. This modeis similar to the the allocation control mechanisms in the VMTP"”) and NETBLT"!protocols.
`
`Rate Control
`
`“In somesituations flow control is not sufficient to ensure efficient, error-free transmission between the sender
`and receiver, even on an extremely reliable network. Imagine a network containing both hardware and software
`implementations of the XTP protocol. Since the VLSI chip set will allow much ofthe protocol to be executed in
`parallel, a sending XTP process implemented in hardware may overwhelm a receiving XTP process implemented
`in software if it sends multiple, back-to-back packets.
`,
`
`3. Wan Jacobsen has proposed extending the TCP protocol to, amongother things, include 29 bit sequence numbers to
`extend the size of the TCP flow conwol window.!4
`4. Note that other policies are possible for determining when to set the SREQ bit in XTP; in XTP, the SREQ policyis
`determined by the user application.
`
`{ U
`
`i
`
`Page 11 of 22
`
`Page 11 of 22
`
`

`

`
`
`
`
`
`|ql]1i|
`
`|{t
`
`XTP uses rate control to restrict the size and time spacing ofbursts of data from the sender. Within any small
`time period,
`the number of bytes that the sender transmits must not exceed the ability of the receiver (or
`intermediate routers) to decipher and queue the data — otherwise they will be overwhelmed and begin dropping
`packets, creating gaps in the received data stream. This problem is independent oftheflowcontrol/buffersize
`problem discussed previously. The receiver may have adequate buffer space available, but back-to-back packets
`may arrive faster than the XTP receiver process can analyze them. The XTP parameters used to implementrate
`control are shown in Table 2. Together, the two rate control parameters allow the receiver to tune the data
`transmission rate to an acceptable Islevel.
`
`[Parameter[Creation—“eriptog
`RATE-Maximum numberofbytes receiver willac‘acceptin eachonesecondtime period.|
`BURST
`controlsegment | Maxunum number of bytes receiver will accept per burst of packets. The
`
`transmitter may not transmit more than BURSTbytes between RTIMERtimeouts.
`RATE/BURST|Maximum numberof packet bursts per second.
`
`
`BURST/RATE|Seconds per Packet Burst. The rate timer (RTLMER)is set to this value.
`
`Rate control is disabled —i.2., sender transmissions are unconstrained.
`
`TABLE 2. XTP Rate Control Parameters _
`
`
`
`When a slow XTPreceiver implementedinsoftware is listening to a hardware-implemented sender, packet
`bursts must be time spaced to guarantee that the slow receiver has sufficient time between back-to-back packet
`bursts to complete protocol processing before the arrival of the next burst. With the above parameters, inter-
`packet spacing can be achieved as follows. Set the BURST parameter equal to the MTU (maximum transmission
`unit) of the underlying network. Thus, each packet “burst” may not contain more than one packet's worth of data.
`If the receiver can handle N packets per second, set RATE equal to MTU * N. In this manner, the sender is
`constrained to spacing back-to-back packets accordingly. See Figure 3 which plots bytes transmitted versus time
`during a one second time period for a hypothetical XTP transmitter.
`The RATE and BURSTparameters are adjustable, and for each implementation |of XTP, appropriate values
`could be determined experimentally. Their values would then be included in all out-going control packets from
`the receiver, Note that in this example, RATE > > BURST.
`
`In Figure 3, the BURST and RATE parameters have been adjusted suchthatan inter-burst separation occurs.
`Each burst of data is depicted by a ramped triangle. The separations between adjacent bursts are shown by
`horizontal dotted line segments in which no progress is made towards the top of the graph. During eachpause in
`the transmitter, the slower receiveris allowed to catch up.
`
`Unfortunately, the sender process does not know the appropriate RATE and BURSTvalues to use with a
`particular receiver until the first burst of data has been completed; the proper value for ALLOCis also unknown
`initially. The appropriate values only become known when the first control packet arrives at the sender. Before
`this control packetis returned, the sender must use default values for the various fow and rate control parameters.
`
`If protocol processing speeds vary widely on a network, the default values for ALLOC and rate control
`parameters affect the number of dropped packets duringthe initial data burst. A conservative approach would be
`for the senderto set the default ALLOC to a small numberof bytes (say one average sized data packet as defined
`by the maximum transmission unit) and to use the aforementioned approachto setting the default rate parameters
`such that packet spacing is sufficient for the slowest receiver on the network. After theinitial burst, which also
`establishes the context connection, the sender would block, waiting for the returned control packet generated by
`the SREQin the last data packet of the burst. This control packet would contain the more accurate flow and rate
`control parameters specifically applicable to the receiver. In this case, few packets would be lost at the cost of
`moderately more overhead in the initial burst.
`
`Consider a hardware-implemented router between an FDDI LAN and an Ethemet LANthat canabsorb back-
`to-back packets as fast as they arrive, but has limited buffer space. Rate control can be used to avoid overrunning
`
`Page 12 of 22
`
`Page 12 of 22
`
`

`

`
`
`
`
`Figure 3. Rate Control of a Hypothetical XTP Transmitter
`
`the router's buffers. To implementthis, BURSTcould be set equal to RATE, and RATE would be setto the rate
`at which the router could relay frames for the context in terms of bytes per second. In this scenario,
`the
`RTIMER’s interrupt rate would be once per second, and the number of bytes per second allowed would equal
`RATE. As more inter-network contexts become established, the router may need to restrict the burstrate for
`existing contexts with the RATE (=BURST) parameters. Later, as contexts becomeinactive or removed from the
`inter-network, the router may chose to increase theflow rate of the remaining contexts. RATE (=BURST) would
`be increased in outgoing control packets in this case. RATE and BURST allow the router to dynamically control
`the flow into the router so as to avoid overwhelmingit with requests.
`
`XTP’s rate control feature may be disabled by setting RATE equal to -1 in outgoing CNTL packets.
`
`Error Control
`
`II
`{|
`
`the errors and initiate
`like TCP and TP4, must detect
`When errors do occur in transmission, XTP,
`retransmission of the erroneous data. XTP uses two checksums over the XTP packet contents to verify the
`integrity of the data received through the network. These two checksums appear in Table 3. The XTP checksum
`algorithms were chosen for speed and VSI compatibility; details of their operation are found in Appendix A of
`the XTP Protocol Definition version 3.4."
`
`It is preferable to place the checksumsin the last few bytes of the XTP frame so that the checksum calculation
`can be concurrent with packet transmission or reception. If the checksums were placed in the front of the packet,
`the entire packet would have to be accessed to compute the checksum before packet transmission begins. Thus,
`two sweeps over the data would be necessary —~ one for the checksum, and one for copying the bytes to the
`. network. This inefficient approach is inherent to TCP and TP4, whose checksums occur before the information
`segment, and avoided in XTPwhere the checksums followthe rest ofthe packet and are foundin the common
`trailer,
`Wheneitherchecksum indicates that the packet received contains erroneous information,the receiver assumes
`the packet is garbled and discardsit. If the source were known, the receiver could immediately inform the source
`XTP sender process that the packet was garbled in transit — allowing the source to begin retransmission.
`
`Page 13 of 22
`
`Page 13 of 22
`
`

`

`
`
`wailer (4 bytes)
`
`
`
`[Parameter[eensJDescription
`DCHECK Value
`trailer (4 bytes)
`4 byte checksum over data fields.
`
`
`Includes the control segment in control packers:
`the information segment in information packets.
`
`
`4 byte checksum over headerandtrader.
`Flag used to signify that DCHECK checksum is not
`trailer flags
`
`
`present in current packet.
`field (1 BIT)
`
`
`
`Flag used to signify that checksum calculation is
`NOCHECK ~ headerflags
`
`field (t BIT)
`disabled in current packet.
`
`
`
`Calculated using exclusive-OR operations only. Represents the vertical parity of data bytes.
`XOR
`
`
`Esch intermediate resuls is left rotated before exclusive-ORingin the next word.
`:
`RXOR
`
`
` XTP’s checksum function is formed usingleft rotation and exclusive-OR operations over the 16-bit words covered.
`The 4 byte checksum is the concatenation of two 2-byte checksums XOR and RXOR. (XOR 1 RXOR).
`TABLE 3. XTP Checksum Parameters
`
`
`
`HTCHECK Value
`
`NODCHECK Flag
`
`Normally, this information is available by referencing the packet's KEY field, located in the commonheader,that
`uniquely identifies the originating client process at the node that transmitted the packet. But, the receiver cannot
`assume that the KEYfield is correct, since the error could conceivably have occurred anywhere within the packet
`including the KEY field itself (if the HTCHECK checksum is invalid). Thus, the receiver always discards packets
`Teceived with errors.
`
`Atthe sender, transmission continues as if no error had occurred. The next packetis placed onto the network.
`If this new packet arrives correctly, the receiver examines the starting sequence numberfor the packet. Like the
`context identifier KEY, the starting sequence numberis contained in the packet’s header(in the SEQ field). The
`receiver expects the SEQ valueof the incoming packet to equal the current RSEQ value for the context. Since a
`packet was dropped, the incoming SEQ is larger than RSEQ bythe size of the dropped packet. The receiver
`accepts the data packet, noting thatit arrived out of sequence, and that a gap exists in the data stream. Now the
`receiver can utilize the KEY informationof the current packet to send back a CNTL packetto announce the gap.
`Having the receiver indicate when a gap has been detected is optional in XTP; if the receiver fails to send the
`CNTL packet, the sender will eventually include a SREQ and block, or timeout,
`
`Gaps AndSelective Retransmission
`A receiver could describe a gap using a pair of sequence numbers that bound the gap. Inste