Europaisches Patentamt
`
`European Patent Office
`
`Office europeen des brevets
`
`
`
`11111111 11111111 0110111111101 1111111 1100111110111101 1111
`
`
`
`
`
`
`
`
`
`CD Publication number: 0 582 537 A2
`
`EUROPEAN PATENT APPLICATION
`
`0 Application number : 93480096.2
`
`0
`
`Int. CI.5 : HO4L 29/06, HO4L 12/64
`
`0 Date of filing : 16.07.93
`
`0 Priority : 07.08.92 US 927697
`
`0 Date of publication of application :
`09.02.94 Bulletin 94/06
`
`0 Designated Contracting States :
`AT BE CH DE ES FR GB IT LI NL SE
`
`0 Applicant : International Business Machines
`Corporation
`Old Orchard Road
`Armonk, N.Y. 10504 (US)
`0 Inventor : Cidon, Israel
`Technion - I.I.T.
`Haifa 32000 (IL)
`
`Inventor: Doney, Richard M.
`5724 Fortunes Ridge Drive
`Durham, NC 27713 (US)
`Inventor : Drake, John Ellis, Jr.
`321 Fearrington
`Pittsboro, NC 27312 (US)
`Inventor: Hervatic, Elizabeth Anne
`4908 Matlock Street
`Apex, NC 27502 (US)
`Inventor : Potter, Kenneth Harvey, Jr.
`5404 Amsterdam Place
`Raleigh, NC 27606-9708 (US)
`Inventor : Tedijanto, Theodore Ernest
`106 Tasman Court
`Cary, NC 27513 (US)
`
`0 Representative : de Pena, Alain
`Compagnie IBM France Departement de
`Propriete Intellectuelle
`F-06610 La Gaude (FR)
`
`communications links.
`
`0
`
`O
`
`O
`
`.72
`0
`
`LN
`d
`
`WEli
`
`E
`
`=2 a
`a_
`
`0 0
`
`
`
`U.
`N
`
`O
`
`0
`
`0
`
`LI-
`0
`
`0
`
`0
`0
`
`0
`N
`
`0 Transmission of high-priority, real-time traffic on low-speed
`0
`A
`protocol
`is
`defined
`for mixed
`data/voice/multimedia
`communications
`sys-
`tems
`to
`transmit and
`receive high-priority,
`real-time
`traffic over low-speed digital com-
`munication
`links by embedding such high-
`priority traffic in low-priority, non-real-time traf-
`fic. High-priority, real-time packets are
`thus
`transmitted without delay by preempting low-
`priority
`packets. Low-priority,
`non-real-time
`packets are held during preemption, and low
`-priority transmission is automatically resumed
`after transmission of high-priority packets has
`been completed. A protocol is defined for corn-
`munications systems to exchange information,
`at the time that a communication link is acti-
`vated, defining their link capabilities for hand-
`ling high-priority,
`real-time packets and
`to
`agree on how this high-priority traffic will be
`transmitted on the communication link.
`
`a.
`
`03
`0
`
`Z
`
`0
`
`N
`
`O
`
`z
`
`Jouve, 18, rue Saint-Denis, 75001 PARIS
`
`EP 0 582 537 A2
`
`IPR2024-001428
`HP – EX1007, Page 1 of 15
`
`

`

`EP 0 582 537 A2
`
`Field of the Invention
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`The present invention relates to data communications networks and more particularly to a data commu-
`nications network having the capability of processing both high priority and low priority packets using a pre-
`empt-resume protocol.
`
`Background of the Invention
`
`Communications systems traditionally have used packet switching techniques for carrying bursty data traf-
`fic and have used circuit switching techniques for carrying multiplexed real-time traffic such as voice and video.
`Circuit switching techniques are typified by a time-division multiplexed voice telephone network in which the
`traffic is sent as a continuous stream of bits. Packet switching techniques, on the other hand, have been de-
`veloped to handle bursty data over digital networks in which destination and drop-off addresses are combined
`with the message data. Each packet is delimited by flags and contains address/routing headers, priority de-
`finers and error checkers. Traditional packet networks are characterized by significant per packet processing
`in the intermediate nodes of a network. This processing has limited the throughput of packet nodes and in-
`troduced high delays for packets. To achieve higher throughput and to reduce this delay, fast packet switching
`networks have been defined which minimize the amount of processing required in intermediate nodes.
`This simplified intermediate node processing now makes it feasible for packet networks to carry, in the
`form of packets, traffic traditionally carried only over circuit switched networks. In addition, this traffic in packe-
`tized form can share the same packet network including communication links with the bursty data traffic. How-
`ever since the traditional circuit switched traffic had stringent bounds on total allowable delay across the net-
`work as well as variability of delay, nodes in the packet network must ensure that this traffic receives priority
`handling. To accomplish this, packets carrying bursty data traffic can be assigned a non real-time priority while
`packets carrying the traditional circuit model traffic can be assigned a higher, real time priority. A node in a
`fast packet network contains buffers for holding packets waiting for transmission on its communication links.
`Packets waiting for transmission can be held in buffers managed differently , depending on the priority, as-
`signed to the packets.
`A communication node in a network can adopt a number of different service policies in order to transmit
`packets from the different priority buffers: priority with no preemption, preemption with retransmission, and
`preemption with resume. When do preemption is used, the packet priority is only examined to determine from
`which buffer to select the next packet for transmission. If a high-priority packet is placed in the buffer while a
`low-priority packet is being transmitted, the high-priority packet must wait until the current transmission is com-
`pleted. A preemption with retransmission service policy means that the node will abort the transmission of a
`low-priority packet upon the arrival of a high-priority packet and immediately transmit the high-priority packet.
`Once all high-priority packets have been transmitted, transmission of the preempted low-priority packet will
`be restarted from the beginning of the packet. A preemption with resume service policy is similar except the
`preempted low-priority packet is restarted from the point of interruption rather than the beginning.
`The selection of the appropriate service policy is dependent on the characteristics of the communication
`link, the delay requirements of the high-priority packets, and the size of the low-priority packets. If the trans-
`mission rate of the communication link is high enough compared to the size of the longest low-priority packets,
`then the delay incurred by a high-priority packet waiting for a low-priority one to complete may be acceptable.
`In this case, the priority with no preemption service policy is preferable since it is easier to implement and may
`have slightly lower link overhead. If the usage efficiency of the communication link is not important but the
`delay associated with waiting for completion of the low-priority packets is too high, than the preemption with
`retransmission service policy may be acceptable. However, if the usage efficiency of the communication link
`is important and the priority with no preemption service policy does not meet the delay requirements, then
`the preempt with resume service policy may be required.
`Various schemes exist for transmitting packetized information over communication links. The typical
`scheme used over low speed serial links up to T3 speeds is based ont he HDLC MAC-layer protocol. Each
`packet is delimited by starting and ending flags (X'7E'). The ending flag of one packet may also be the starting
`flag for the next packet. The packet itself consists of an integral number of bytes of data. Since the contents
`of the packet may include bit patterns that are the same as the flag pattern, a technique known as bit stuffing
`is used to differentiate the data from the flags. The transmitter inserts a '0' bit after any sequence of five con-
`tiguous '1' bits int he packet data. Likewise, the receiver removes any '0' bit immediately following a sequence
`of five '1' bits in the received bit stream. When no packets are waiting to be transmitted, flags are repeatedly
`transmitted.
`Both the priority with no preemption and the preemption with retransmission service policies can be im-
`
`2
`
`IPR2024-001428
`HP – EX1007, Page 2 of 15
`
`

`

`EP 0 582 537 A2
`
`plemented using the existing HDLC MAC-layer protocol.
`
`Summary of the invention
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`The present invention relates to method and apparatus for effecting a modified HDLC MAC-layer protocol
`providing preemptive priority with resume over a serial communication link.
`It is, therefore, an object of this invention to provide method and apparatus for embedding high-priority
`traffic in low-priority for serial transmission though low speed communication links, without delay incurred by
`having first to complete transmission of a low-priority traffic. It is another object of this invention to preempt
`low-priority packet traffic with a high-priority packet and later resume transmission of the preempted low-pri-
`ority packet automatically, with minimal overhead on the communication link. It is another object of this inven-
`tion to detect bit transmission errors affecting packet boundaries and to recover from said errors with minimal
`loss of packets. It is another object of this invention to provide a method and apparatus for determining whether
`preemption of low-priority packets is required on a given communication link as a function of link speed, ac-
`ceptable delay and maximum packet size, and therefore whether preemption should be enabled. It is another
`object of this invention to allow a mode of operation that is compatible with HDLC MAC-layer, either priorit to
`enabling preemption or when it is determined that preemption is not required.
`According to this invention, packets of information are embedded in frames having starting and ending
`flags, control headers to designate the packet's priority, and any required routing information. The flags, in
`addition to defining the boundaries of a packet, also define byte alignment of the packet data. The flags also
`indicate when a low-priority packet has been preempted by a high-priority packet and when the transmission
`of a low-priority packet is being resumed. The control bits designate whether or not a particular packet is high-
`priority or low-priority and hence whether or not the packet is preemptable.
`Also when a communication link is activated, the two communications systems at each end of the link ex-
`change control information about their respective packet capabilities. The control information describes the
`maximum supported low-priority packet size supported in the transmit and receive direction and the ability of
`the communications system to support high-priority packets. Using the information exchanged along with the
`communication link's data rate and the maximum acceptable delay for high-priority packets, each communi-
`cations system independently determines whether the preempt/resume protocol should be enabled or whether
`a simple priority with no preemption the protocol should be used.
`
`Brief Description of the Drawings
`
`Figure 1 shows a basic packet frame used in the practice of this invention, where packet containing header
`and data is delimited by flags;
`Figure 2 shows the valid combination of formatted packet frames in which a low-priority packet is preempt-
`ed by a high-priority packet with subsequent automatic resumption;
`Figure 3 shows a combination of packet frames containing a bit error which causes a transmission abort;
`Figure 4 shows a block diagram of the transmit portion of a communication link interface of a communi-
`cations systems to which this invention is applicable;
`Figure 5 shows a block diagram of the receive portion of a communication link interface of a communica-
`tions system to which this invention is applicable;
`Figure 6 is a table used in explaining how maximum permissible packet size and the need for preempt/re-
`sume protocols is determined in each direction of a communication link; and
`Figure 7 is a finite state machine table showing preempt/resume states.
`
`Detailed Description of the Invention
`
`This invention defines a preempt/resume protocol extension to the existing HDLC MAC-layer packet fram-
`ing protocol used on serial communication links, to allow the preemption of low-priority packets so that high-
`priority packets may be transmitted with minimal delay. A link activation protocol is also defined to determine
`whether the preempt/resume protocol extension should be enabled. During the link activation , normal HDLC
`MAC-layer framing protocol is used to transmit packets across the communication link. Also if the link activation
`determines that preempt/resume should not be used, all packets are sent using the HDLC MAC-layer framing
`protocol with simple priority without preemption.
`
`3
`
`IPR2024-001428
`HP – EX1007, Page 3 of 15
`
`

`

`EP 0 582 537 A2
`
`Enabling Preempt/Resume Protocol Extension
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`Determination of when to use the preempt/resume protocol extension is based on the support of high pri-
`ority traffic, low-priority packet sizes supported, communication link speed, and maximum acceptable delay
`of high-priority packets. The two communications systems on each end of the communication link can deter-
`mine the need for the preempt/resume protocol independently for their direction of the link. During link-
`activation, each communications system sends a control message to its neighbor at the other end over the
`communication link using the normal HDLC MAC-layer framing. The control message contains the following
`fields
`. A High-priority Traffic Supported filed indicates whether the sending system supports high-priority traf-
`fic on its link.
`. A Maximum Received Low-Priority Packet Size Supported field defines the maximum packet size that
`the sender can receive.
`. A Maximum Transmitted Low Priority Packet Size Supported field defines the maximum packet size that
`the sender can transmit .
`If high-priority traffic is not supported, the receiver must verify that each packet received is a low-priority
`packet. If a packet identified as high-priority packet is received, it is discarded by the receiver.
`The following example, described with reference to Figure 6, shows how communications systems A and
`B each determine the maximum low-priority packet size supported in each direction and whether preempt/re-
`sume protocol extension should be enabled.
`Transmission of a high-priority packet may not be delayed by a low-priority packet for more than T, where
`in the following example T = 0.5 msecs. A sender that supports high-priority traffic must either transmit :
`. without preempt/resume protocol, which constrains the low-priority packet size to satisfy the equation
`packet size <T
`link speed
`
`. or with preempt/resume.
`For link direction A to B, the maximum low-priority packet size is 8KB. Assuming a link speed of
`18.432Mbps, the above inequality is not satisfied since
`8 Kbytes
`18.432 kbits per msec
`Therefore, to satisfy the delay requirements, the preempt/resume protocol is required. This means that
`communications system A will transmit preempted packets and that communications system B must support
`receipt of preempted packets.
`For link direction B to A, the maximum low-priority packet size is 1KB. The above inequality is satisfied
`
`- 3.56 msecs > 0.5 msecs
`
`35
`
`as
`
`- 0.44 msecs < 0.5 msecs
`
`Kbytes
`18.432 kbits per msec
`and the preempt/resume protocol is not be used. This means that communications system B will not transmit
`preempted packets and that communications system A will interpret preempt flags as error conditions.
`If a particular communications system has not implemented the preempt/resume protocol extension but
`supports high-priority packets, it will select a maximum low-priority packet size to greater than the value of
`link speed x T. Using this value, the communications system on the other end of the communication link will
`correctly determine that the preempt/resume protocol is not to be used.
`
`40
`
`45 Preempt/resume Protocol Extension
`
`50
`
`55
`
`In the following description, bit sequences may be described using either conventional binary represen-
`tation or, for the sake of convenience, hexadecimal representation.
`The protocol for allowing high-priority packets to temporarily preempt low-priority packets uses three types
`of flags to delimit packets : a normal flag which can be a starting, endingor idle flag, a start-preempt flag and
`an end-preempt flag. The normal flag is defined as the 8-bit sequence B'01111110'(X'7e'). The star-preempt
`flag is defined as the 9-bit sequence 6'011111110' and the end-preempt flag is defined as the ten-bit sequence
`6'0111111110'. All flags are on byte boundaries with respect to the packet data that they delineate. To differ-
`entiate flag bit sequences from bit sequences within the packets, zero bit stuffing is used in the packet data.
`An extra '0' bit is inserted in the transmitted bit stream after each occurrence of five consecutive '1' bits in a
`packet. A sequence of more than eight '1' bits indicates an error condition aborting the current packet being
`transmitted and received. Also a sequence of more than six '1' bits indicates an abort condition if the pre-
`empt/resume protocol is not enabled.
`
`4
`
`IPR2024-001428
`HP – EX1007, Page 4 of 15
`
`

`

`EP 0 582 537 A2
`
`The following is a set of rules adopted for a practical preempt/resume protocol.
`. The bit sequence 6'01111110' (X'7E') always defines byte alignment and may occur any number of times
`before and after complete packets.
`. Sic '1' bits preceded by a '0' bit that is not byte aligned with received packet data is an invalid code.
`. Nine '1' bits preceded by a '0' bit that is byte aligned is also an invalid code.
`. Receipt of an invalid code aborts the current packet and all subsequent packets are aborted until
`X'7E' occurs.
`. Verification that the preempted packet is a low priority packet is performed.
`. Verification that packets received during preemption are high-priority packets is also performed.
`. A low-priority packet cannot be preempted until the first byte is transmitted.
`. Receipt of the start-preempt flag (6'011111110') immediately followed by the end-preempt flag
`(6'0111111110') aborts the preempted packet and ends preempt mode.
`Under the foregoing rules, the following is a valid combination of packets and flags when preempt/resume
`is not enabled.
`
`7E [ 7E][ RTP 7E][ 7E][ NRTP 7E ] }
`Under the foregoing rules, the following is a valid combination of packets and flags when preempt/resume
`is enabled :
`
`7E { [ 7E ] [ RTP 7E ] [ 7E
`
`[ NRTP 7E )
`
`preempted packet
`4
`[ pNRTP { [ SP [ 7E ] RTP [ 7E RTP ] [ 7E ] EP ] pNRTP } ] 1
`
`
`
`preemption
`
`4
`
`where
`. [] denotes optional and repeatable fields
`. {} denotes required, repeatable fields
`. 7E represents the byte-aligned flag (6'01111110', X'7E')
`. RTP represents a high-priority packet
`. NRTP represents a low-priority packet
`. pNRTP represents portions of a preempted low-priority packet
`. SP represents a start-preempt flag (6'011111110')
`. EP represents an end-preempt flag (6'0111111110')
`Figure 1 shows a conventional frame 10 delimited by normal (starting and ending) 7E flags 10a and con-
`taining both a control header 10b field and a data 10c field.
`Figure 2 illustrates in frame sequence 20 a preempt valid operation in more detail with the case of a low
`priority packet being preempted by two consecutive high-priority packets. The first field 20a shows the normal
`byte-aligned starting flag X'7E'. The second field 20b is an ongoing low-priority packet NRTP1. The third field
`20c shows a start-preempt or SP flag bit by bit. This SP flag interrupts the low-priority packet and indicates
`the transmission of the remainder of the low-priority packet NRTP1 is suspended. The fourth field 20d repre-
`sents the first high-priority packet RTP1. the fifth field 20c shows the recurrence of a normal flag indicating
`the completion of the RTP1 packet. The transmission of the second high-priority packet RTP2 begins imme-
`diately in the sixth field 20f, without reversion to NRTP1. the seventh field 20g contains an end-preempt flag
`EP.
`
`Thereafter the remainder of the preempted low-priority packet NRTP1 is completed, as shown in the eighth
`field 20h. Finally, in the ninth field 20i, the normal flag X'7E' indicates the end of NRTP1 and returns the system
`to the ready state.
`Figure 3 illustrates in frame sequence 30 the case of a bit error corrupting the start-preempt flag SP in
`the third field 30c. The bit error would typically be caused by a transmission error on the communication link.
`The first and second fields 30a and 30b are identical with the same fields in Figure 2. The third field 30c shows
`a double '0' at the beginning of what otherwise would be a normal flag. Since the flag does not occur on a
`byte-aligned boundary with respect to the low-priority packet NRTP1 in the second field 30b, then NRTP1 is
`invalid and discarded. The high-priority packet RTP1 in the fourth field 30d is saved because it is surrounded
`by valid flags in the third and fifth fields 30c and 30c. The second high-priority packet RTP2 in the sixth field
`30f is discarded, however, because it is followed by an end-preempt flag EP in the seventh field 3g, when no
`
`5
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`IPR2024-001428
`HP – EX1007, Page 5 of 15
`
`

`

`EP 0 582 537 A2
`
`valid start-preempt flag SP was detected due to the bit error. All packets thereafter are discarded until the nor-
`mal flag X'7E' appears, as in the ninth field 30i.
`The preempt/resume states of this invention can be summarized by a Finite State Machine (FSM) Table
`shown in Figure 7. Since this preempt/resume protocol is a "bit-oriented" protocol, the complete FSM describ-
`ing the protocol machine (the sender or the receiver) is also at the bit level. However, for the sake of clarity,
`the following describes only the FSM in terms of detected "sequences of bits", which captures those state tran-
`sitions which are associated with preemption. Furthermore, for the purpose of describing the protocol, is be-
`lieved to suffice to show the FSM for a receiver only.
`The following is a list of the FSM states, inputs and outputs (actions) along with their description.
`
`STATE
`
`DESCRIPTION
`
`idl
`
`rdy
`
`Idle, expecting '7E'.
`
`Just received '7E' or non-byte-aligned '7E*', ready to
`
`receive either high-priority packet or low priority
`
`packet
`
`5
`
`10
`
`15
`
`20
`
`rtp
`
`Receiving high-priority packet
`
`25
`
`rnrtp
`
`Receiving low-priority packet
`
`p_rdyl
`
`Just entered preemption mode (just received start-
`
`preempt flag SP), ready to receive high-priority
`
`packet
`
`or '7E'
`
`p_rdy2
`
`'7E*',
`
`In preemption mode, just received either '7E' or
`no high-priority packet has been received yet during
`
`current preemption
`
`30
`
`35
`
`p_rdy3
`
`40
`
`'7E*I ,
`
`In preemption mode, just received either '7E' or
`ready to receive a high-priority packet, at least one
`
`high-priority packet has already been received during
`
`current preemption
`
`45
`
`50
`
`55
`
`p_rrtp
`
`Receiving high-priority packet in preemption mode
`
`p_id12
`
`Idle in preemption mode, expecting '7E', no high-
`priority packet has been received yet during the
`
`current
`
`preemption
`
`p_id13
`
`Idle in preemption mode, expecting '7E', at least one
`high-priority packet has already been received during
`the current preemption
`
`6
`
`IPR2024-001428
`HP – EX1007, Page 6 of 15
`
`

`

`EP 0 582 537 A2
`
`p_end
`
`5
`
`Just exited preemption mode (just received end-preempt
`flag EP), expecting data (the continuation of the
`preempted low-priority packet)
`
`INPUT
`
`DESCRIPTION
`
`10
`
`'7E' share
`
`Normal starting/ending/idle flag, X'7E' (does not bit with prior flag)
`
`'7E*'
`
`X'7E' flag not byte-aligned with received data bytes
`
`RTP
`
`NRTP
`
`SP
`
`EP
`
`IC
`
`or
`
`Data (non-flag) byte from a high-priority packet, distinguished from NRTP by a control bit
`in the first byte of a string, indicating packet priority. Zero bit stuffing is performed on se-
`quences of these bytes.
`
`Data (non-flag) byte from a low-priority packet, distinguished from RTP by a control bit in
`the first byte of a string indicating packet priority. Zero bit stuffing is performed on se-
`quences of these bytes.
`
`Start-preempt flag 13'011111110' (seven l's)
`
`End-preempt flag 6'0111111110' (eight l's)
`
`Invalid codes, include non-byte-aligned SP, non-byte-aligned EP, a run of six '1' bits right
`after a flag
`
`B'0111111111 (nine l's), or 6'01111111 (seven l's)
`
`when
`
`preempt/resume is not enabled
`
`OUTPUT
`
`DESCRIPTION
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`7
`
`IPR2024-001428
`HP – EX1007, Page 7 of 15
`
`

`

`EP 0 582 537 A2
`
`strt_R
`
`Indicate start of received high-priority packet and
`
`forward first byte
`
`strt_N
`
`Indicate start of received low-priority packet and
`
`forward first byte
`
`more_R
`
`Forward another byte of high-priority packet
`
`more_N
`
`Forward another byte of low-priority packet
`
`end_R
`
`Indicate end of received high-priority packet
`
`end_N
`
`Indicate end of received low-priority packet
`
`5
`
`10
`
`15
`
`20
`
`abrt_R
`
`Abord/discard current received high-priority packet
`
`25
`
`abrt_RN
`
`abord/discard both preempting high-priority packet and
`the preempted low-priority packet
`
`30
`
`Note that states p_rdy1, p_rdy2 and p_rdy3 are similar in that the receiver is in the preempt mode and
`expecting a high-priority packet in all these states. However, it is necessary to have p_rdy1 and p_rdy2 to en-
`sure that all packets are recovered when surrounded by normal flags. Likewise, p_rdy2 and p_rdy3 are needed
`to tell whether or not it is legal to receive the end-preempt (EP) flag.
`
`35 Embodiment of Communication Link Interfaces
`
`40
`
`45
`
`50
`
`55
`
`Figure 4 shows a block diagram of the transmitter 40 portion of the communication link interface of that
`communications system. Packets arrive from the communications system's packet source 41 for transmission
`on communication link 48. The packets may have been generated locally by this system or may have been
`received from another communication link on this system (e.g. an intermediate node in a packet network). The
`communications system places the high-priority packets into a high priority buffer42 and places the low-priority
`packets into a low priority buffer 43. If no packets are stored in either high priority buffer 42 or low priority buffer
`43, a flag generator 46 is connected to the communication link 48 via a bit multiplexer 47. The flag generator
`46 repeatedly generates an idle flag X'7E', when no packets are stored for transmission.
`When a low-priority packet arrives in the low priority buffer 43 and a packet is currently being transmitted,
`the transmitter 40 waits until all earlier packets in the low priority buffer 43 have been transmitted and the high
`priority buffer 42 is empty. When a low-priority packet is at the head of the low priority buffer 43 and no other
`packet is being transmitted on the communication link 48, bytes from the low priority buffer 43 are transferred
`one at a time through a byte multiplexer 44 to a parallel serial converter 45. The parallel serial converter 45
`serializes the data and monitors the outgoing data for sequences of five consecutive '1' bits. It also inserts a
`single '0' bit immediately after each set of five '1' bits. The resulting bit stream is routed through the bit to the
`communication link 48. When the transmission of the low-priority packet is complete, the bit multiplexer 47
`selects the flag generator 46 for transmission to send at least one or more normal flags until the next packet
`is ready to be transmitted. Note that each time a flag is sent, the parallel serial converter 45 resets its internal
`count of the number of consecutive '1' bits.
`If a low-priority packet is being transmitted from low priority buffer 43 and a high-priority packet arrives in
`the high priority buffer 42, then the transmission of the low-priority packet is preempted. The remaining bits
`int he parallel serial converter 45 along with any stuffed zero bits are transmitted guaranteeing a data byte
`
`8
`
`IPR2024-001428
`HP – EX1007, Page 8 of 15
`
`

`

`EP 0 582 537 A2
`
`5
`
`10
`
`boundary for the preempted packet, and then the flag generator 46 sends special start-preempt flag described
`earlier. Bytes from the high priority buffer 42 are then transferred through the byte multiplexer 44 to the parallel
`serial converter 45 which performs serialization and zero bit stuffing. The resulting high-priority packet is then
`transferred to the communication link 48. If, during the transmission of the high-priority packet, another high-
`priority packet arrives in the high-priority buffer 42, then the flag generator 46 sends a normal flag when the
`first high-priority packet is completed and transmitter 40 begins transmission of the next high-priority packets
`without exiting the preempt mode. When the last of the series of high-priority packets has been sent (there
`are not more packets waiting in the high priority buffer 42), the flag generator 46 sends the end-preempt flag
`described earlier. The remaining bytes from the preempted low-priority packet in the low priority buffer 43 are
`the released to the parallel serial converter 45 and the communication link 48. If a subsequent high-priority
`packet arrives at the high-priority buffer 42 prior to the completion of the preempted low-priority packet, the
`preemption and resume sequence is repeated. When the transmission of the low-priority packet is completed,
`the flag generator 46 transmits a normal ending flag.
`Figure 5 shows a block diagram of the receiver 50 portion of the communication link interface of the corn-
`15 munications system up to a point at which received whole packets are passed to a packet target 56 within the
`communications system. The packet target 56 could be the final destination for the received packets or could
`be a packet switch used to route packets to other communication links for transmission to other nodes in a
`packet network. Any buffering associated with the packet target 56 is outside the receiver 50 and is not in-
`cluded in Figure 5.
`A flag detector 52 continuously monitors the bit stream received from a communication link 51 for normal,
`start-preempt and end-preempt flags. If a sequence of bits other than a flag is detected immediately following
`a normal flag, it indicates the beginning of a new frame. A serial parallel converter 53 receives the bit stream,
`discard any '0' bit if it immediately follows five consecutive '1' bits, and converts the remaining bits into byte-
`parallel form. If the received packet is a high-priority , packet, the parallel byte data is passed directly through
`a multiplexer 59 to a multiplexer 55 connected to the packet target 56 until a normal ending flag is detected
`by the flag detector 52. The receiver 50 indicates the end of the packet to the packet target 56.
`If the received packet can be preempted (i.e. low-priority, non-real-time packet), then the parallel byte data
`is instead passed through byte multiplexer 59 to the preemptable packet buffer 54 in order to permit the entire
`packet to be accumulated before passing it to the packet target 56. If flag detector 52 detects a start-preempt
`flag and there is no partial byte in the serial parallel converter 53, then it indicates the beginning of a high-
`priority preempting packet and therefore the beginning of preempt mode. The bit stream is passed through
`the serial parallel converter 53 as before but this time the parallel byte data is passed directly through the mul-
`tiplexers 59 and 55 to the packet target 56 within the communications system.
`When the flag detector 52 detects either an normal ending flag or an end-preempt flag, then the receiver
`50 indicates the end of the packet to the packet target 56. If a normal ending flag is detected, then the serial
`parallel converter 53 will continue to route the parallel byte data from subsequent packets directly to the mul-
`tiplexer 55. Kan end-preempt flag is detected, the receiver 50 will end preempt mode. The received bit stream
`will be routed through the serial parallel converter 53 and multiplexer 59 to the preemptable packet buffer 54
`thus resuming reception of the preempted low-priority packet . If the flag detector 52 detects a normal ending
`flag indicating the end of the low-priority packet, the receiver 50 transfers the entire low-priority packet stored
`in the preemptable packet buffer 54 through the multiplexer 55 to the packet target 56.
`Figure 5 assumes that the transfer of a whole packet from the preemptable packet buffer 54 to the packet
`target 56 is