Copyright Xerox Corporation 1979Inter-Office MemorandumToCommunication ProtocolsDateJuly 3, 1978FromEd TaftLocationPalo AltoSubjectSynchronous Line Transport ProtocolOrganizationPARC/CSLXEROX Filed on: [Maxc1]SyncTransport.pressLow-speed synchronous lines used to transport Pups are controlled by means of the SynchronousLine Transport Protocol (sometimes referred to as the SLA protocol because synchronous lines werefirst interfaced to Novas using a Synchronous Line Adapter). In addition to Pup encapsulation, thisprotocol entails some network-specific, non-Pup communication that enables hosts to maintaindynamic information about line status and sub-network connectivity.The Synchronous Line Transport Protocol is used by Nova and Alto Gateways. We presentlyconsider it to be a private'' protocol among Gateways, and it is subject to change at any time.All numbers are decimal unless suffixed with B', in which case they are octal.Packet FramingAll packets (whether or not they are Pups) are transmitted as transparent BiSync data frames. Weare using only a subset of the full BiSync line control protocol, namely the part dealing withtransparent transmission of data frames.Frame FormatA frame consists of the following sequence of 8-bit bytes:SYN SYN ... SYN DLE STX ... transparent data ... DLE ETX CRC1 CRC2The frame begins with at least two SYN bytes, which the receiver searches for in order to establishbyte synchronization. The sequence DLE STX signals the start of the data portion of the frame.Within the data portion, all bytes are treated as literal data except DLE, which is an escape character.A literal data byte whose code corresponds to DLE is transmitted by doubling it, i.e., by sending DLEDLE. If the sequence DLE SYN appears, both bytes are ignored. Some synchronous interfaces automaticallytransmit DLE SYN when a transmit data-late condition occurs.The end of the transparent data is indicated by the sequence DLE ETX. Following this are two bytescontaining the 16-bit CRC (Cyclical Redundancy Check), transmitted low-order byte first. The CRCalgorithm is given below. The CRC is computed over the transparent data bytes and the ETX. Whenthe sequence DLE DLE appears, only one of the DLEs contributes to the CRC. When DLE SYNappears, neither byte is included.Byte synchronization is not necessarily maintained from one frame to the next, so after each frame &pX]g~qi cr]pX-r7Bp \r]p-r7Bp Vr]p#-r 7BpOsp I) CM BD6rp @=' ?:B =C :7! 9KN 6f.rp 1t .pF -oY +( (1u %Lp:"grpXrprprprprprprpr p#rp 0 $rprp, >rp rp1r prprp r) < p=rprp grp(r prprp ] rprprprprpr p" b j?/d 5Synchronous Line Transport Protocol2the receiver should restart its bit-at-a-time search for a SYN byte. The data transmitted betweenframes is not specified, but it should not be a pattern that could be mistaken for SYN or DLE. All-zeroes or all-ones are good choices for inter-frame data.All bytes are transmitted low-order bit first. When the transparent data is treated as 16-bit words,the order of bytes in each word is high-order, then low-order.Character CodesWe use the ASCII codes for the special characters. These are:SYN026BDLE020BSTX002BETX203BCRC AlgorithmThe CRC algorithm used is the industry-standard CRC-16. The CRC is a 16-bit number which is theremainder from dividing the data bit stream by the polynomial x16+x15+x2+x0. Hardwareimplementations of CRC-16 are available in the form of integrated circuits such as the Fairchild 9401.The manner in which the CRC is generated and checked is as follows. The transmitter initializes theCRC to zero. Then, for every bit in the data stream, it updates the CRC using a simple XOR-feedbacktechnique. At the end of the data, the transmitter appends the CRC, low-order bit first.The receiver computes the CRC in a similar manner except that the 16 bits of CRC at the end of thedata are included in the CRC computation. The CRC algorithm has the property that if no errorshave occurred, the result of applying the algorithm to the data and the received CRC will be zero.The CRC may be computed in software or microcode by any of several methods. One that is easy tounderstand works a single bit at a time, but this is relatively expensive since it must be executed 8times for every data byte. The following BCPL procedure, given a partial CRC and a new data byte(right-justified), returns the updated CRC:let UpdateCRC(crc, data) = valof[for i = 1 to 8 do[let xorFeedback = (crc xor data) & 1crc = crc rshift 1data = data rshift 1if xorFeedback ne 0 then crc = crc xor 120001B]resultis crc]The idea is to right-shift the partial CRC and the data byte by one bit and to compare the bits thatare shifted out. If they are the same, the CRC is not modified further; if they are different, the(shifted) CRC is XORed with the constant 120001B. fp#G b;rp `&-rprp _9 \/L Z> Vu T p rp.Q'rprOprNprLpr Hvu Eprprp rp D/2 DrD/pDrD/pDrD/pDrD/p Brp0 ?rpI >@rpBrprp <@rp 9rp0rp 8Quprprp  6@up rp 3rp; 2bW 0*rp rp /X'rp,swX*)iS'S&_$S$S#US!-xS Kw A \pK rp5 R rprprp  >/PESynchronous Line Transport Protocol3A faster technique updates the CRC a full byte at a time, using a 256-word table, CRCTAB, which isinitialized as follows:for i = 0 to 255 do[let crc = 0let val = ifor power = 0 to 7 dotest (val & 1) eq 0ifso val = val rshift 1ifnot[crc = crc xor (120001B rshift (7 - power))val = (val rshift 1) xor 120001B]CRCTAB ! i = crc]The procedure for updating the CRC is then simply:let UpdateCRC(crc, data) =(crc rshift 8) xor CRCTAB ! ((crc xor data) & 377B)Packet FormatsTwo types of packets are presently transported over synchronous lines: encapsulated Pups and sub-network routing tables. Refer to Figure 1. The two types are distinguished by the first word of thepacket. An encapsulated Pup is type 512 and a routing table is type 513. 16 bits are reserved for theType word because we contemplate subdividing it to include other information such as that required for sub-networkfragmentation of large packets.Note that what is shown in the figure is the transparent data only; all packets are carried withinframes as described in the preceding section. This should be assumed for the remainder of thisdocument.Pup EncapsulationA Pup is encapsulated simply by prefixing the appropriate Type word. Note that the packet doesnot carry immediate source and destination host numbers, though the immediate destination isderived and used by the sub-network routing algorithm to determine on which outgoing line totransmit the packet. A consequence of the packet's not carrying the immediate destination host number is that thePup must undergo inter-network Pup routing at every sub-network node through which it passes. This in turn impliesthat all sub-network nodes must be Pup Gateways.Sub-Network Routing TableA Routing Table is a non-Pup packet carrying sub-network routing information. This should not beconfused with a Gateway Information Pup, which is network-independent and carries inter-networkrouting information.The packet consists of an identifying Type word, the sub-network host number of the packet'ssender, the number of routing entries, and the routing entries themselves. The first routing entryrefers to sub-network host 1, the second to host 2, etc. This arrangement implies that there can't be verymany hosts in the sub-network, and the host number space must be fairly dense.Each routing table entry contains a hop count and a line number. The hop count is the estimatedminimum number of point-to-point lines between the host generating the routing table and the hostto which the routing table entry refers. The entry corresponding to the sending host itself must fp#G brp0rp `]wX\/Z Y% WSVTSQPxwNxLwKxxw I GprpD)wXBxwxw >t ;2p?upu 9p= 8( >r 6r 5 2p(up% 1DL / ,u )!p_ 'upY &E $r[ #1c !0 _u zpupE _ p E .5 /r3  N _p-3 P UP D >/\.EncapsulatedPupType = "Pup"Type = "Routing Table"Source HostNumber of EntriesHost 1 Hop CountLine NumberHost 2 Hop CountLine NumberLine NumberHost n Hop CountSynchronous Line Transmission Protocol Packet FormatsPup EncapsulationSub-Network Routing TableFigure 1.0SXGKQfG90QG0QG9'$; 9$9; 9$=f$998$9=B$A9$9A9$9?{$D$99C$H_9$9F&$9H_9$J$99J$9L$9O $9QG9QG9SXGQC$$$,s$@$ :@- :> qQ 0=fG9$G,s5Q>;O-$9>;L$90L$0J$>;J$9>;H$90H_$0F&$>;FI$9>;D$90C$0A$>;A$9>;?$90?{$>;=f$93pO ?WO0NG1sMAM 1sKJAKJ A= 1s= z5r 4;8#z QfG9$G,s9$G0=GK=GH9I=mSynchronous Line Transport Protocol4contain a hop count of zero. Entries corresponding to hosts that are believed to be inaccessiblecontain a hop count of 255.The line number identifies the line over which the sending host believes it can achieve the minimumpath claimed by the hop count. This information is useless to a host receiving the routing table. It is included sothat the body of a Routing Table packet may be generated simply by copying the internal representation of the sender'srouting table.Sub-Network Organization and AlgorithmsA collection of hosts interconnected by synchronous lines is treated as a single network within thePup inter-network. This network is assigned a unique network number, and the hosts are assignedunique host numbers within that network. To avoid any confusion between the Pup inter-networkand a specific network composed of nodes interconnected by synchronous lines, we refer to thelatter as the sub-network.Each host in the sub-network maintains a local routing table containing an entry for every otherhost. Each entry contains a hop count and a line number, as described in the preceding section.Additionally, for each synchronous line connected to the host there is a line state with values down,up, and looped back, and a timer used to time out dead lines.Every 5 seconds, the host sends a Routing Table packet on every line.Upon receiving a routing table from some line l, the host updates its local state as follows:The timer for line l is reset.The local routing table is enumerated. For each entry whose line number field is equal to l,the hop count is set to 255. The effect of this is to purge obsolete information about line l, since newinformation is about to be incorporated.If the Source Host is equal to the local host number, the line state for line l is set to loopedback and no further processing is performed on the Routing Table packet.The line state for line l is set to up.The local routing table and the entries in the packet are enumerated in parallel. For eachhost, if the hop count in the local routing table is greater than the corresponding hop countin the packet, the local routing table entry's hop count is replaced by the packets hop countplus one and the line number is replaced by l. If the resulting hop count is greater than theconstant MaxHops (presently 15), it is replaced by 255 (thereby marking the hostinaccessible).If no routing tables are received over some line l during a period of 20 seconds, the line's state ischanged to down. Then all entries in the local routing table are enumerated. For each entry whoseline number field is equal to l, the hop count is set to 255.Outgoing Pups are routed to lines by computing the immediate destination host (an operationperformed at the Pup inter-network level) and simply using it as an index into the local routingtable. If the routing table entry's hop count is 255, the host is inaccessible and the packet isdiscarded.This is an extremely simplified version of the routing algorithm used in the Arpanet. Its major defects are that (a) it usesan imperfect metric (hop count) for making routing decisions, (b) it is unable to make effective use of multiple paths to agiven destination, and (c) it does not extend well to large sub-networks. fp#G bE ` ]K \/r'0 ZN( Y U(t' RCpG PM O9P M7& L/ u p IJ&: G<$ F@"'u p up Dupu p* AE >(up.< up 9'Wup7r 5vr 6A(3pu p6up u1pD/up up,1R*U)'./'(up1&up/$ !+up3 . upA up 3up ?L .3 5 sr'V 6p I ?/V4R TIMESROMAN  TIMESROMAN  TIMESROMANLOGO TIMESROMAN  TIMESROMAN  TIMESROMAN HELVETICA  HELVETICA HELVETICA  HELVETICA  HELVETICA   HELVETICA  ! "=M##=I#B"*iG "*iA !OiO%1)Mi19KZ%+*iH%')Fi'9AZ%!*i>%)*%T9T9R =  %)ii9Z%-i%)ii@EmY Z  %+9+9)   Z  TWZ :Z"*i?B"Pj/$"*SyncTransport.pressTaft  3-Sep-79 19:01:13 PDT"