Shared facility allocation system

<img file="NL8300044A_D0001.tif" />

Patent Board

<img file="NL8300044A_D0002.tif" />

The Netherlands ® ATeraslaglaidatie 0 8300044

NL

Circuit for assigning access to a shared line for polling.

Int.C!³G06F3 / 04, G06F3 / 02, G06F9 / 46, H04L11 / 00.

Applicant: Western Electric Company, Incorporated in New York.

Av .: Ir. HM Urbanus cs Vereenigde Octrooibureaux Nieuwe Parklaan 107 2587 BP The Hague.

Application no. 8300044.

Submitted January 6, 1983.

Priority from January 7, 1982.

Priority country: Ver. St. v. Am. (US).

Number of the priority application: 337868.

-0 Placed for inspection on 1 August 1983.

The print of the description with claim (s) and any drawing (s) attached to this sheet contains deviations from the documents originally submitted; the latter can be viewed at the Patent Office upon request.

........ "Ï'iillit". ", Ι / St ·

VO Uü'Sll

Bet .: Circuit for assigning access to a shared line for polling.

The invention relates to a system for allocating access to a query shared facility over a number of units, each unit having an assigned, determined n-digit priority number, which system is provided with a system controller, an arbitration line, which connects all units with each other, and an arbitration circuit in each of the units for requesting access to the query shared facility.

In systems in which a number of devices share a common resource, more particularly use is made of devices for assigning access to the resource under conditions during which a number of associated devices simultaneously. can request access. Many different allocation systems are known. In information processing and packet switching systems, it is known to use a centralized allocation device or controller for assigning access to a common information line, which connects a number of units, such as ports, which can simultaneously request access to the line. The controller can be programmed with a suitable algorithm to allocate access to the line according to a predetermined criterion that may be desired. Although centralized controller allocation systems suitably fulfill their intended function, they are not always desirable in view of the inherently complex construction of the system, which is due to the large number of interconnections between the controller, the line and the gates is needed. Furthermore, a reliability problem arises since in the event of a malfunction of the controller, the entire system can be disabled. A system with a centralized controller is found in U.S. Pat. No. 3,983,504.

It is known to use divided line allocation set 30 in which no controller is used to determine access, but instead the mutual cooperation of the requesting ports determines the line allocation in the case of simultaneous requests. Such distributed systems are often preferred since the cost and reliability problems encountered during the centralization of the controller system are avoided.

3 0 Ö 0 4 4 ............ '' '..................

.. _llÉa ί

- 2 With such a distributed allocation system, each port that can request access to a common line is assigned a constant priority number comprising a number of binary digits. In the case of simultaneous requests, access is granted on the basis of the priority number. During the line dispute period, when two or more ports request access simultaneously, each requesting port sequentially, bit by bit, the corresponding bits of its priority number, in synchronism with the supply of corresponding bits by all other currently requesting ports , to an arbitration line. When each bit is supplied, each requesting port compares the value of the bit that the port is currently supplying with the logical combination of the corresponding bits that are simultaneously supplied to the arbitration line by all simultaneously requesting ports. If a bit supplying one requesting port at a given time has a prescribed relationship to (for example, equal to or greater than) the bits supplied to the line through the other requesting ports, this operation continues and the gate applies the next bit of its assigned priority number to the arbitration line.

Each port remains in conflict as long as each bit supplying the port has the prescribed relationship to the logical combination of the corresponding bits currently being supplied by other contesting ports. A gate withdraws from the battle when the gate determines that a bit supplying this port has a relationship to the bits supplied by the other ports, (as is less than) indicating that one or more of the other ports have a higher priority number. At that time, each port with a lower priority number withdraws from the battle and does not supply any further bits to the line.

This fight continues; the remaining bits of the port priority numbers are supplied to the line by all remaining requesting ports; gates with a lower priority withdraw from the battle; and at the end of the dispute interval, when the last bit is supplied to the line, only the highest priority port remains in the battle and access to the line is provided to this port.

A device of the type described above can be found in the

V

3 U.S. Pat. No. 3,796,992 and in U.S. Pat. No. 3,818.UT.

The distributed dispute settlement system described above functions satisfactorily. However, it has the problem that the gate priority numbers are fixed and since the gate access is determined by these numbers, the gates can be considered to be functionally arranged in a fixed preference set, the most preferred gate having the highest priority number , and the least preferred port has the lowest priority number. Where this is the case, access to the line is not impartial, since ports with the higher priority numbers are always favored in the case of simultaneous requests. Although this unfair allocation of ports can be permitted in certain systems, it is a problem with those systems where more equitable access through all ports is required.

The problems are solved according to the invention with a system for allocating access to a query shared facility, wherein the arbitration circuit is provided with a number of logic devices with a number of states, a logic control circuit for the logic devices in each of the units to switch selectively and in combination from a first state to a second state under the control of certain parameters, representing the current dynamic state of the units, a buffer memory in each unit for receiving messages of different lengths, the logic control circuit being provided with a detector in each unit for determining the number of messages with a certain criterion, which are currently stored in the unit's buffer memory, a switching circuit for switching at least a first logical device of a unit from a first to a second state to indicate the presence of at least a first predetermined number of messages from the determined criterion in the buffer memory of the unit, a register circuit for forming a dynamic priority number of each of the units by applying the output signals of the logic devices of each unit as parameter digits to the more significant digit positions of the dynamic number and by adding the digits of the assigned priority number to the less significant positions of the dynamic number, the system ver8300044

- 4 of them is provided with a superposition circuit in each of the units, which at that moment requests access to the sharing facility for querying the corresponding digits of the associated dynamic priority number simultaneously, successively, digit by digit, on the arbitration line superimpose a comparison circuit in each of the requesting units for the numerical value on the arbitration line thereto with the corresponding numerical value, supplied by the requesting unit. The invention provides a method and system for assigning a query shared line to one or more requesting units or ports, each having a certain assigned priority number with a number of binary coded digits, and a second circuit for a requesting unit from. remove the units from the facility access battle upon detecting a prescribed comparison result between a line digit value and the corresponding digit value supplied by the unit.

According to the invention, each port includes facilities to dynamically check the current state of different operational port parameters and generate corresponding port priority bits representing these parameters. These generated bits are used together with the assigned port priority number albums to determine the line access.

The gate parameter bits generated by the facilities according to the invention are fed into the more significant bit positions of a gate 25 shift register. The assigned port priority number albums are applied to the rest of the shift register to be of less significance than the parameter bits. During the line dispute times, the bits in the shift register of each requesting gate are read sequentially, one-by-one, starting with the most significant bit, and applied to the arbitration line.

In circumstances where no gate parameter bits are generated by the facilities according to the invention, the shift register contains zeros in the corresponding, more significant bit positions and the regularly assigned gate priority number has bits in the less significant bit positions thereof. Under these circumstances, the port priority is determined using only the assigned port priority number. During operational states of ports in which a 1

0 0 0 4 4: ~

-5-.

however, before one or more of the parameter bits is generated, these parameter bits are read from the shift register for the gate priority number albums and will therefore control the line access. If two or more ports have identical parameter bits that are set to one, and there are no other ports with parameter bits that indicate a higher priority, the port priority number albums are used to cut the node.

According to the invention, facilities are provided which control the information packets present at any given time in each packet buffer of a port and identify the number of such packets having a predetermined length, such as short packets. More specifically, short packets represent information which, in time, is more urgent for the operation of the system than the information in longer packets. For example, short packages contain more in particular information regarding job creation and management of the system; longer packages contain more in particular word processing or text information. It is often desirable for ports containing short packets to be operated under otherwise equal conditions rather than ports containing long packets. Therefore, the facilities according to the invention identify and count the number of short packets that are introduced into and read out from each packet buffer of a port. These facilities together control an up / down threshold counter, the current state of which represents the number of short packets present in the buffer at a given time. This counter drives a circuit that generates gate parameter bits specifying that the gate buffer 1) contains fewer than m short packets or 2) at least mⁿ short packets or 3) contains at least n "short packets, where n&gt; m. Typical values ​​for m" and n "are 2 and 5, respectively. These bits are applied to a control circuit which introduces these bits into the gate parameter portions of the shift register .

Furthermore, according to the invention, facilities are provided in each port for the length of time during which the port waits for a line access, after the port has assumed a certain operational state, such as that in which one of the short packet identification bits is set to a 1 , to count. This facility includes a threshold counter,

......... 8 3 0 0 0 4 4 ...

- 6 which is periodically advanced by the system clock when the gate is waiting for access. After the counter has advanced to a predetermined level, the counter generates a bit which is introduced into the parameter portion of the shift register as an indication that the gate has waited a predetermined time for gate access after a packet length identification bit has been generated .

As before, the corresponding shift register bits from each requesting gate are simultaneously applied to the arbitration line during the dispute time, sequentially, bit by bit. Both 10 port parameter bits and the assigned port priority number albums are present.

The bit values ​​of each disputing port are compared in a prescribed order with the corresponding line digit value. A unit is removed from the line battle if a predefined result is obtained in a figure comparison, which indicates that another gate with higher priority requests access. In the described embodiment of the invention, the priority for line access is based on the value of the number determined by the parameter bits and the priority number bits in each gate shift register. In the described embodiment, a wired OR-TTL line is used, in which a 1 represents the dominant low voltage state.

With a packet switch, packets are stored in a buffer memory in the ports; the logic gate dispute circuit contends for access to the common resources of the switch, including more particularly a common packet transfer line, which is referred to herein as an information line. A packet will be lost if it is transferred to a port which already has one or more packets in the associated buffer memory and does not have sufficient space to store another packet. The amount of packet loss can be made low by providing sufficient memory space in each port, so that on a statistical basis the packet loss rate is acceptable at the switch traffic limit. The invention makes it possible to design the packet switch so that smaller memories are required to provide the same amount of packet loss with a certain amount of network traffic; or with a constant amount of memory, the loss of packets will be smaller with a certain amount of traffic.

- Since the largest amount of costs and complexity of the switch

7 is more particularly present in the memory or queue of the gates, the logic gate disputing circuit can be extended in a substantial manner, while still reducing the cost and complex construction of the system since the power according to the invention allow significant cost and complexity reductions in memory. The invention provides means for dynamic state of the gates and also means for modifying the parameters to which the algorithm is sensitive on a frame-by-frame basis. This is done by fault-tolerant bodies without sacrificing anything, to the divided nature of the arbitration bodies.

The device described above solves the problems of the prior art in that a greater flexibility and a more optimal allocation of ports for access to the facility or line in systems are provided, with a fixed priority number assigned to each port, the value would determine the line access priority.

The invention will be explained in more detail below with reference to the drawing. It shows:

Fig. 1 is a simplified block diagram illustrating the components of a typical system in which the invention can be applied; Fig. 2 further details of the gate circuit according to fig. 1;

Fig. 3 is a time diagram;

4, 5 and 6 show the circuit details of the logic arbitration circuit of the gate of FIG. 2; and FIG. 7, which is found in FIG. 3, the manner in which the figures

U, 5 and 6 must be placed in relation to each other.

FIG. 1 shows a packet switching system according to the invention. Fig. 1 shows a controller 100 with a polarity generator 122, gates 110-1 to 110-n, a switch 107, and a number of lines connecting the controller 100 to the gates 110. These lines include a packet line 105 which receives the information from the output

111. from each port to a different port. The packet line 106 receives this information after it has passed over the switch 107 and supplies this information to the input 112 of each port. A clock line

103 supplies the signals indicated in FIG. 3 from the controller to the gates. The arbitration line 102 simultaneously receives the corresponding priority bits, which are sequentially supplied through each requesting port during the line dispute time. The polarity conductor. . 101 applies a potential from the controller 100 to the gates 110 at selected times to cause these gates to supply the line 102 with the reverse of each digit of their assigned priority number.

The enable / disable line 108 includes a conductor that is unique to each port and extends from the controller 100 to each port 110. This line is effective when the line is activated to cause the associated port out of the service. The operation is removed and access to the arbitration line and the package lines 105 and 106 at this port is denied. The mask line 104 comprises a conductor which is common to all ports and extends from the controller 100 to the ports. This line is effective when the line is activated to cause a combination of the gate parameter bits during the dispute time to be disregarded, so that the line access is allocated based on the remaining parameter bits, if any, and the priority number assigned to each port ..

The information processor 120-1 and the mail controller 120-n together with the stations 121 are illustrative of the type of facilities that can be operated by the gates. As is typical with packet circuitry, a transmitting port, which gains access to the packet line 105, carries information that is desired over the packet line 105, via the switch 107, sa via the packet line 106 to the input 112 of the port to which the information is directed.

FIG. 2 shows further details of the gates 110 of FIG. 1. Each port comprises an I / O interface device 200, an input line interface device 210, and an output line interface device 220. The input line interface device 210 includes a logic arbitration circuit 218 and a buffer 30 circuit 213, which provides information to the package line 105. The packet length detector includes counters and the like for checking the length of. each package, provided by FIFO 21Γ. is received and read. The detector 205 checks the number of packets that are smaller or larger than a predetermined length present in the FIFO at that moment and, by means of conductors 208 and 209, supplies this information to the logic arbitration circuit 218, which in turn this information is used as port ..... parameter bits. The coupling device 210 further comprises a FIFO

9 211, a packet length detector 205 and a FIFO controller 214. The FIFO 211 receives packet information from the coupling device 200 and stores it temporarily until the information is read out and fed to the packet line 105 via the buffer. The FIFO controller 214 receives information on the path 212 from the FIFO 211, this information including both packet length information and bits specifying whether the FIFO is currently at least half-full or full. The FIFO controller carries this information about lanes 206 and 20? to the logical arbitration circuit 218, which uses this information as additional parameter bits for dispute purposes.

The output line capping device 220 includes the circuit through which the port receives information from the packet line 106. This circuit includes a buffer 221, a FIFO 227, a FIFO controller 225, and a packet recognition device 223. More specifically, the information processor 120 passes through the gate of FIG. 2 is operated, a packet of information to be sent to another port, via the lane 116-1, via the I / O interface device 200 and via the lane 201 to the FIFO 211. The FIFO controller 214 detects the receipt of a complete package by the

FIFO 211, and sends a request for line access to the logical arbitration circuit 218, which then operates during the next dispute interval and attempts to gain access for the gate to the line 105. Upon obtaining such access, the FIFO controller 214 causes the FIFO 211 to send the packet information it contains through the buffer 213

2-5 to the package line 105. This information includes introductory information, which identifies the port to which the packet is sent.

After passing the switch 107 of FIG. 1, the information on the packet line 106 is supplied to the path 112 of the receiving port and via its buffer 221 to the associated FIFO 227 and the associated packet recognition device 223. The element 223 detects that the information currently contained in the FIFO 227 is indeed directed to this port and then causes by means of the FIFO controller 225 that the FIFO 227 the information via the path 202, the O-coupling device 200 and directs via the path 117 to the device which is operated by the receiving gate.

FIG. 3 shows the waveforms of the timing and control signals,

- which are supplied to the gates via the clock line 103. The upper signal is a positive frame pulse and identifies the start of each frame. A line dispute interval starts with each field pulse. This grid is as long as required for a completely transferable package. The logical line dispute and the packet transfer can occur simultaneously during each frame, with the port, which wins a dispute period, the packet line 10? during the next grid. The lower signal is the bit clock signal and this signal is used for a number of control purposes during the dispute or arbitration interval.

.10 The details of the logic arbitration circuit 218 of FIG. 2 is shown in FIGS. 4, 5 and 6 when placed as indicated in FIG. T.

The parallel-in, series-out-shift register 500 receives the bits that are fed to the arbitration line 102 during the dispute time and stores them. The shift register receives the assigned port priority number albums from the element 52 ?, which is hard-wired 'for storing these bits. The different gate parameter bits are provided by the. shift register from the flip-flops and other circuits shown immediately below the shift register in FIG.

. The lane .524 applies a '1 as a FIFO buffer full signal to the most significant bit position of the shift register. The lane 522 applies a 1 as an at least half-full signal to the second most significant bit position 2SB. The lanes 531 and 536 apply packet length information to the third and fourth most significant bit positions of the register. The lane 546 applies a signal to the fifth most significant bit position (5SB), which signal indicates that the gate has waited at least a predetermined time for line access after certain qualifying gate events have occurred. The lane 423 applies a signal representing a snapshot bit to the sixth most significant bit position.

₍ The FIFO 211, as shown in FIG. 2, is shown in more detail in FIG. 6 and includes an input buffer 600. a FIFO buffer 602 and an output buffer 604. The packet length detector 205 is also shown in more detail in FIG. As will be described later, this circuit recognizes the receipt by the buffer 600 and the delivery by the buffer 6θ4 of packages equal to or smaller than predetermined lengths, this information being supplied to the up / down

- 11 counter 620. The setting of the counter at a given moment specifies the number of packets with the predetermined length or smaller that are present at that moment in the buffer 602. The status of the counter 620 is checked by the interpreting device 625 to control the setting of the flip-flops 628 and 629. Information, what the condition. of these flip-flops, is passed over paths 208 and 209 for controlling the flip-flops 530 and 535. The output of these flip-flops in turn supplies corresponding gate parameter information to the shift register.

Information packets received by a gate from the device 120, which is operated by it, are supplied to the input buffer 600 of the FIFO 211 from the I / O coupling device 200 over the path 201. The FIFO controller 21U sends a signal the lane 215 for gating an information packet from the input buffer 600 to the

FIFO buffer 602 over the path 601, and from the input buffer 600 to the tail and end detector 61O over the path 203. The start and end detector 610 detects the packet boundaries by decoding the special packet-encoding codes associated with each packet. The packet boundary information is supplied over the path 611 to the threshold counter20 Irish 612. The threshold counter 612 receives clock pulses and determines whether each packet is a short or long packet by counting the number of clock periods present within the packet limits determined by the start and end detectors 610 and by comparing this count with a predetermined package is extended by parameter. When the up-threshold counter 612 detects a packet of a predetermined length, such as a short packet, a pulse is applied to the up-down counter 620 over the path 613. This pulse increments the up / down counter 620, which in combination with the counter 61T maintains a count of short packets in the FIFO buffer 602. The P / down counter 620 carries the short packet information on the track

621 to the qualifying packet interpreting device 625. The qualifying packet interpreting device 625 decodes the short packet information to determine how many short packets are present in the FIFO buffer 602 at that time. For example, if the FIFO buffer 602 contains two or more short packets, the qualifying packet interpreter 3525 sends a positive pulse along the path 626 around the SR flip-flop

628 in settings. If the FIFO buffer 602 contains five or more short packets, the qualifying packet interpreter 625 sends a position

12 pulse over the paths 626 and 627 for adjusting the SR flip-flops 628 and 629. These flip-flops in turn adjust the flip-flops 530 and 535.

When line access is allowed at the port, the FIFO5 controller 214 sends a signal over the lane 215 for an information packet from the FIFO buffer 602 to the output buffer 6θ4 over the lane 603, and to the start and end detector 615 'over the lane 204. The start and end detector 615 determines the packet boundaries by decoding the special packet encoding codes associated with each packet. The package is ...

boundary information is applied to the up-threshold counter 617 via the path 616. The up-down counter 617 determines whether the packet has a predetermined length, such as a short packet, by the number of clock periods in the packet limits found by the start and end detector 615 »By counting and comparing this count with a predetermined package length para15 meter. For example, when the up-down counter 617 detects a short packet, a pulse is applied across the path 618 to the up-down counter 620. This pulse decrements the up / down counter 620 to maintain a count of short packets in the FIFO buffer 602. The up / down counter 620 feeds the short packet information on the lane 621 to the qualifying packet interpreter 625 which, as already discussed, decodes the short packet information to determine how many short packets are currently in the FIFO buffer 602. have been saved. If the FIFO buffer 602 contains fewer than two short packages, the qualifying packet translation device 25 sends a positive pulse along the path 630 for resetting the SR flip-flop 628. If the FIFO buffer 602 contains fewer than five short packages , the qualifying packet interpreter 625 sends a positive pulse over the lane 631 to reset the SR flip-flop 629.

The Q output signals of these SR flip-flops are traversed

208 and 209. applied to the logical arbitration circuit 218. An HI on the Q1. ...

output of the SR flip-flop 629 indicates to the logic arbitration circuit 218 that at least five short packets are stored in the FIFO buffer 602. An HI at the Q output of the SR flip-flop 628 indicates to the logic arbitration circuit 218 that two or more short packets are stored in the FIFO buffer 602. If the Q outputs of the SR --- flip-flops 628 and 629 are both low, there are fewer than two short ones

- 13 packages, 602 in the FIFO buffer.

The information sent over the path 212 to the FIFO controller 214 includes occupation information, which indicates whether the buffer 602 is full, at least half-full, or less than half-full.

The clock line 103 supplies the bit clock and RASTER CLOCK signals across the lane 115-1 to the logic gate arbitration circuit 218. The bit clock signal is fed across the logic gate arbitration circuit 218 to the lane 425 and the RASTER CLOCK signal is fed across the lane 426. The relationships between these two clock signals are indicated in the time diagrams of FIG. 3.

When the FIFO buffer 602 is full, the VOL signal becomes high and this signal is applied across the path 207 from the FIFO controller 214 to the D input of the D flip-flop 523. The high transition of the next RASTER CLOCK at the CLK input of the D-flip-flop 523 sets the flip-15 flop and causes its Q output to become high. This Q output signal is applied across the path 524 to the MSB input of the shift register 500.

When the FIFO buffer 602 is at least half-full, the 1/2 VOL signal from the FIFO controller 214 becomes high and the signal is applied across the path 206 to the D input of the D flip-flop 521 and at the lower input of the OR gate 540. This high signal at the input of the OR gate 540 causes the output thereof to become high. The high output of the OR gate 540 partially actuates the AND gate 542 via the path 541. The high transition from the next RASTER CLOCK to the CLK input of the D flip-flop 521 sets the flip-flop and causes its Q output to become high. The Q output signal of the D flip-flop 521 is applied across the path 522 to the 2SB input of the shift Register 500.

When more than five short packages through the package length detec30. 205 are detected, a high signal is applied to the D input of the D flip-flop 530 over the path 208. At the next high transition of the RASTSRKLOK pulse on the CLK input of the D flip-flop 530, the flip-flop is set to cause its Q output to become high. The Q output signal of the D flip-flop 530 is applied across the path 531 to the 3SB input of the shift register 500. When at least two short packets are detected by the packet length detector 205, a high signal is applied to the D input of the D flip-flop

8300044 .....

535 The OR gate 540 is supplied over the path 209. This signal is applied through the gate 54θ to one input of the AND gate 542. At the next high transition of the RASTER CLOCK pulse on. the CLK input of the Dflip-flop 535 sets the flip-flop and the Q output thereof becomes high. The Q output signal of the D-flip-flop 535 is traversed

536 applied to the 4SB input of the shift register 500.

The positive transition from the first RASTER CLOCK received after the output of the OR gate 540 goes high sets the EH gate 542 in operation. to supply a high signal to the CLK input of the threshold counter 542. The threshold counter 5 ^ 3 counts each received frame pulse after either the cock 206 or the web 209 becomes high. The threshold counter 543 is advanced by the high output signal from the AND gate 542 by one count. When the count reaches a pre-set threshold value, its associated CI&gt; UT output becomes high. This exit signal is applied via line 544 to the D input of the Dflip-flop 545. The D-flip-flop 545 is then set by the high transition of the next GRID CLOCK at its CLK input. This causes the Q output thereof to become high. The Q output signal of the flipflop 5 ^ 5 is applied via the path 546 to the 5SB input of the shift register 500.

The AND gate 550 receives one of its two input signals over the path 541 from the gate 540. The other input signal is the RASTER CLOCK pulse over the path 426. The gate 550 serves to release the threshold counter 543 over the path 551 when the following raster pulse occurs after the output of gate 540 becomes low. The gate 540 becomes low when there is neither a high state representing an at least half-full bit on the path 209 nor a high short packet bit on the path 209. Since the input signal of the gate 550 »is present. that the signal received from the gate 540 is inverted, a low signal on the path 541 causes the field pulse to be gated via the gate 550 to the threshold counter 543, which causes the counter to be released (ie, the outputs become low). When the exit. from the threshold counter 543 becomes low, this low state is clocked to the flip-flop 545 at the next field pulse after that which the threshold counter 543 has released. This causes the SB signal as applied to the shift register 500 to become low. The threshold counter 543 and the flip-flop 545 remain both in the low starting state until

3 0 0 0 4 4 '

• at least one of the two states occurs, in which the gate 5 ^ 0 can provide a high signal.

In the following, the circuit of FIG. U will be described which allows a port to set its snapshot bit to have a snapshot time. determine when no other port supplies a 1 as a snapshot bit (SSB) to the arbitration line 102. When a port is switched on for the first time, the flip-flops become Mo, U12, 118, U21 and Λ22. all reset by the MAIN RELEASE signal, which is applied to their respective CLR inputs via the path U6. When these flip-flops are in the reset state, their respective Q outputs are all low.

A . high REQUEST-HANGING signal is applied over the path 216 from the FIFO controller 21U to one input of the NAND gate U30 and one input of the AND gate U17 when the gate requests line access. The high transition of the next GRID CLOCK is applied to the other input of the NEN gate ^ -30. This makes the associated output low. The low output signal of the NEN gate U30 is applied to the bias input of the D-flip-flop if-10 and the bias input of the SR-flip-flop U12 via the path U31. This sets the flip-flops and makes their Q outputs high. This makes it possible for the gate to start supplying the bits in the shift register 500 to the arbitration line 102.

The six-part counter 51U counts bit clock pulses which are applied across the path U28 to their CLK input after each field pulse is applied to its R input. After five bit clock pulses have been counted, the dividing counter 51U supplies the sixth bit clock pulse from its Q output via path 519 to the CLK input of the Dflip-flop ^ 18. The bits supplied by the gate U0 to the arbitration line 102 are supplied from the line 102 via the path 11 ^ -1 to the input of the gate ^ 17. Since the D-flip-flop U18 is only clocked by the sixth bit clock pulse from the by-dividing counter 51, the Q output of the flip-flop is only set high if the output of the AND-gate U17 is currently is high. The output of the AND gate 417 is only high at the time of the bit clock 6 if no 1s (wired OR los) are supplied to the arbitration line 102 as a snapshot bit at that time by requesting gate circuits. The Q output signal of the setting flip-flop U18 is applied to the setting input of the SR flip-flop

<img file="NL8300044A_D0003.tif" />

16 422 is fed across the track 419 to set its Q output high. This high output signal is applied to the SSB input via the lane 423. from the shift register 500. The snapshot bit. is then applied to the shift register 500 by the layer transition of the next RASTER CLOCK.

In order for the leading edge of the pulse generated by the six-part counter 514 to correctly clock the snapshot bit to the flip-flop 418, it must be ensured for the particular combination of selected components that the snapshot bit is on the D input of the flip-flop 418 is still stable when the clock pulse arrives from the counter 514. A potential race condition occurs here, because the same rising edge of the bit clock, which causes the logical arbitration chains to pass the SSB bit to the arbitration line 102, also includes the counter 514. clocks. For most applications, a time analysis for the worst case shows that the delay caused by the combination of the delay from the shift register 5θθ, the gate 4θ4, the line drive port 4θ6, the capacity of the arbitration line 102 and the gate

417. is much greater than the delay over the counter 514 and therefore no race condition will occur. If a race problem occurs with a certain choice of the logic components, a delay element between the gate 417 'and the D input of the flip-flop may occur.

418. be included to eliminate the problem.

The gate 409 detects incorrect adjustments between the bit that each gate supplies to the line and the logical combination of the bit value of the line when each bit is supplied. An incorrect adjustment is detected when a port on the line 102 supplies a 0 at a time that a 1 is applied by another port.

A gate gains access to the packet line 105 when the exclusive OR gate 409 does not detect an incorrect adjustment state when the contents of the shift register 500 are read out and applied to the line 102. The Q outputs of the flip-flops 410 and 412 remain high at this time and the high Q-output signal of the SR flip-flop 412 'is applied to the D input of the via the path 413. the D-fliplfop 421. The high transition of the next RASTER CLOCK pulse sets the Q output of the D flip-flop 421 high. The Q-output signal from the D-flip-flop 421 is selected as a GATE SELECT signal across the path 217

....... lined. The PORT SELECTED signal is applied to the reset input of the

Ó0 04 4 ......

17 SR flip-flop 422 is applied to set the Q output thereof low. This Q output signal from the SR flip-flop 422 is applied as 0 to the SSB input of the shift register 500. The GRID CLOCK is applied via the path k26 to the LOAD INPUT of the shift register 500.

When the RASTER CLOCK becomes low, the different bits occurring on the input lines of the shift register 500 are applied in parallel to the shift register. These bits represent the Q output signals of the flip-flops 523, 521, 530, 535, 545, the snapshot bit, on the lane 423 and the assigned gate number from the hard-wired gate number element 527. The bits are then serially shifted out of the shift register by the bit clock which is applied over the path 425 to the SLID input of the shift register. One bit is shifted from the shift register 500 at each positive transition of the bit clock. The MSB is first followed by the bits 2SB, 3SB, .... ISB, in this order, from the.

shift register 500 via the lane 501 to the exclusive OR gate 4θ4. The bits which are read from the shift register 500 are influenced by the exclusive OR-gate 4o4 and applied to a NEN-gate 4θ6 with three inputs, as will be explained later.

The six-dividing counter 433 and the SR flip-flop 435 make it

2Q, a low signal on the mask line 104 may only be the parameter bits, ie the port busy bits, packet length bits, the bit from the counter 543, and snapshot bits (bits MSB ... SSB), so that line access can then be controlled by one of these bits, which is not masked, and the bits from the element 52. The counter 433 prevents one of the gate number albums from the element 527 from being masked. so that the assigned port number is always available during an arbitration period. The counter 4-433 also makes it possible for a high signal on the polarity only 101 to invert 30 the assigned gate number bits read from the shift register 500 to the arbitration line 102. This prevents the bits MSB. .. SSB are inverted.

; The six-divide counter 433 and the SR flip-flop 435 are reset when the RASTER CLOCK is applied to the corresponding reset inputs when the path 426 becomes high and causes its (outputs) to become low. When SSB are read out of the shift 35 register 500, the low Q output signal of the SR flip-flop 435 is applied to the NOF gate 437. As a result, the gate - 437 is partially actuated so that it receives a low signal that passes through

- 18 the web 118-1 is received from the line 104 mask, can reverse. A received low mask line signal is then applied as a high signal from the HOF gate 437 over the path 438 to the OR gate 440. This high signal prevents the flip-flop 4Ίθ. is reset during the reception of the parameter bits (MSB ... SSB) as will be described later. A high mask line signal is inverted and applied as a low signal from the HOF gate 437 via the path 438 to the OR gate 440. This low signal makes it possible for the flip-flop 410 to be reset by an incorrect adjustment detected by the gate 409. This makes it possible for a combination of parameter bits during the dispute period to be disregarded, but still on the arbitration line 102. so that a facility for collecting statistical network data (e.g., how often at least one port is full) only needs to check the arbitration line 102.

The low Q output signal of the SR flip-flop 435 is also via a. lane 436 applied to one input of the AND gate 402. This low signal turns off the E1 gate 402 and makes the output thereof low. This prevents the polarity line 101 from reversing the parameter bits. The low output signal of the E1 gate 402 is applied via the path 403 to one input of the exclusive OR gate 4θ4. .-&gt; -. · .. ·

The parameter bits which are read out from the shift register 500 are applied via the path 501 to the other input of the exclusive OR-gate 4θ4. If the bit from the shift register 500 is high, the output from the exclusive OR gate 4o4 is high and, if the bit from the shift register 500 is low, the output from the exclusive OR gate 4o4 is low. Therefore, when the upper input of the exclusive OR gate 4θ4 is kept low, the bits supplied from the shift register 500 are not reversed and are supplied by the exclusive 30. OR gate 4θ4 applied to the center entrance of the NEII gate 4o6 with. three inputs and on. the lower entrance of the exclusive OR gate 409.

via the lane 405.

When each parameter bit is read out of the shift register 500 by the bit clock, the bit clock also increments the counter dividing 433 'by six. After five bit clock pulses are counted, the first five bits (MSB ... 5SB) from the shift register 500 are shifted and the - by six dividing counter sets the output thereof high when the next

-19-.

CIK pulse corresponding to the SSB bit is received. This high signal is applied via the path 434 to the S input of the SR flip-flop 435 to set the Q output of the flip-flop high. The Q output signal of the SR flip-flop 435 is applied to the NOF gate 437 and the AND gate

402 added. The high input signal from the NOF gate 437 makes the output low. The low output signal of the NOF gate 437 is applied to the OR gate 440 via the path 438. This prevents a low mask line signal from being able to mask the assigned gate priority bits since a low signal on the input of the gate

437 the gate output cannot float high. The high signal from the SR flip-flop 435 to the AND gate 402 partially triggers the AND gate. This makes it possible for a polarity reversal signal (a high signal) to be supplied from the polarity line 101 via the AND gate 402 to the exclusive OR gate 404. . .

The polarity reversal signal from the polarity line 101 on the lane 113-1 is used to selectively reverse the assigned gate number bits which are read from the gate to the arbitration line 102 via the lane 114-1. A low polarity signal does not pass the gate number bit to the arbitration line 102; a high polarity 20 signal passes an inverted gate number bit to the arbitration line 102. The gate number bits are selectively controlled by the polarity signal which is applied to the exclusive OR gate 404 over the path 113-1, as will be explained below.

If the polarity signal and the gate number bit supplied to the ex25 inclusive OR gate 4θ4 are both high or both low, the output of the exclusive OR gate 4θ4 is low. If the polarity signal and the gate number bit applied to the exclusive OR gate 4o4 are different (one high and one low), the output of the exclusive OR gate 4θ4 is high. In other words, a low polarity signal causes an assigned gate number bit to pass through the exclusive OR gate 4θ4 unchanged, while a high polarity signal causes a reverse gate number bit through the exclusive OR gate 4θ4. These bits at the output of the exclusive OR gate 4θ4 are inverted by the switched-on NEN gate 4θ6 with three inputs and applied to the arbitration line 102. The bits from the exclusive OR gate 4θ4 are also supplied to the exclusive OR gate 409.

The left and right inputs of the NEN gate 406 with three inputs are operated in a manner as will now be described. The D input of the D flip-flop 442 is high when the control ace carries a high GATE ENABLE signal across lane 119-1. The high5 transition of the next RASTER CLOCK sets the flip-flop, so that its Q output becomes high. The Q output signal of the D flip-flop 442 is applied via the path 443 to the left input of the AND gate 406. The D-flip-flop 442 remains set (with the Q output thereof being kept high) unless a low PORT-OFF signal .10 is applied from the controller to the D-input of the flip-flop to disable this port. and prevent it from seeking line access.

• When this port requests line access, the FIFO controller 214 sets the REQUEST PENDING signal 216 high. This REQUEST PENDING15 signal is applied to the lower input of the AND gate 417 and the right input of the NAND gate 430 over the path 216. This activates both of these ports. When the next GRID CLOCK becomes high, the output of the NEN gate 430 becomes low. The low output signal of the NEN gate 430 is applied to the low bias input of the D-flop flop 410 and to the low bias input of the SRflip-flop 412 via the lane 431. This low input signal sets the two flip-flops , making its Q outputs high. The Quit output signal from the SR flip-flop 412 is applied to the right input of the NEN gate 4o6 and to the D input of the D flip-flop 421 across the track.

25. 413 added.

The bits which are applied through the gate 4θ4 to the central input of the switched-on NEN gate 4θ6 with three inputs over the path 405. are reversed by the NEN gate and applied to the arbitration line 102 as priority bits via the lane 407.

When the priority bits are supplied from the exclusive OR-gate 4o4 to the NEN-gate 4o6 with three inputs, they are also supplied via the path 405 to the exclusive OR-gate 409. The logical combination of priority bits brought to the arbitration line 102 becomes the request of all ports (including this port).

from the arbitration line 102 to the exclusive OR gate 409. Since any priority bits that are supplied from this gate to the arithmetic line "through NEN gate 407 with drisliagangencworêTöOTi"⁷ ~:

- 21 and vice versa, the input signals from the exclusive OR gate

409 are not adjusted if the numerical value of the priority bit from the arbitration line 102 is the same as the priority bit which is supplied from the NEN gate 4θ6 with three inputs to the arbitration line 102. If the input signals from the exclusive OR gate

409 are not matched, the output of the exclusive OR gate 409 remains high. This high output signal is applied across the path 439 to the OR gate 440 to cause the output thereof to become high. The high output signal from the OR gate 440 is applied to the D input of the D flip-flop 410. The high input of the D flip-flop 410 allows the Q output thereof to remain high. This Q output signal is applied from the D flip-flop 410 over the path 411 to the low reset input of the SR flip-flop 412. The high signal on the low reset input of the SR flip-flop 412 sets the flip do not flop back and its Q output remains high. The high Q output signal of the SR flip-flop 412 is supplied to the NEN gate 4θ6 with three inputs. This allows the NEN gate to continue to pass through subsequent priority bits to the arbitration line 102.

The only way in which the input signals from the exclusive OF gate 409 can be matched to each other is that, when a "0" bit is applied to the line through the gate and a ⁿ1-bit is already present on the line (indicating that another port has a higher priority) or when a "1-bit is applied to the line and a" 0 is returned (indicating a defective NEN-gate) with three inputs). In both cases, the gate withdraws itself from the battle if there is no low mask line signal on the line 104.

The mask line signal can only have an influence during the first six bit times (MSB ... SSB). The output of the NOF gate 437 is kept low at all other times by the high Q output of the SR flip-flop 435. A low signal from the mask line 104 during the time of the first six bits makes the output of the NOF port 437 high. The high output signal from the IIOF gate 437 is applied to the NOF gate 440 over the path 438, thereby making the output thereof high and preventing a low signal from being output from the exclusive OR gate 409 when the port an incorrect to8300044

- 22 passing detects. If through the NOF gate 437 from the mask line

104 When a high signal is received, the output from the HOF gate 437 becomes low. This allows the OR gate to transmit 440 hits from the exclusive OR gate 409.

After the first five bits (MSB ... SSB) have been applied to the arbitration line, the SR flip-flop 435 is set by the sixth CLK pulse. This makes the Q output thereof high. This Q signal is applied to the NOF gate 437 to make its output low. This prevents a mask line signal from being fed via the path 438 to the OR gate 44-0. If the input signals from the exclusive OR gate

409 matched to each other, the gate output becomes low. This output signal is applied to the OR gate 440 via the path 439. The low input signal of the OR gate 440 makes its output low (since the other input of the gate is kept low by the NOF gate 437). The low output signal from the OR gate 440 is applied to the D input of the D flip-flop 4-10. When the next bit clock on the CLK input of the D flip-flop 410 becomes high, its Q output is set low. The Q output signal of the D flip-flop 410 is applied via the path 4-1.1 to the low reset input of the SR flip-flop 412 to make the Q output thereof low. The Q output signal of the SR flip-flop 4-12 is applied to the D input of the D flip-flop 421 and to one input of the NEN gate 4θ6 with three inputs. The low signal on the input of the gate 4θ6 switches the gate off and removes the gate from the battle.

This port will not send any further bits to the arbitration line 102 before the next RASTER CLOCK becomes high and the REQUEST HANGING signal from the FIFO controller 214 is high.

3 0 Ö 0 4 4