Priority broadcast and multi-cast for unbuffered multi-stage networks

A dual priority switching apparatus for making input port to output port connections on a requested basis quickly and dynamically, in a standard mode from any one of the input ports to a fixed number of subsets of multiple output ports simultaneously, or in a broadcast mode from any one of the input ports to all output ports simultaneously. The apparatus permits multiple broadcasts to be queued at the individual switching apparatus which resolves the broadcast contention on a synchronous priority driven basis that permits one broadcast to follow the other at the earliest possible moment and the quickest possible speed. The apparatus permits multiple multi-cast operations to occur simultaneously within the network. The multi-cast function permits subsets of nodes assigned to the same tasks to communicate among themselves without involving other nodes that are not in its own subset. Hardware circuitry detects and corrects deadlock conditions in the multi-stage network. The hardware circuitry detects all the different types of deadlock conditions automatically and issues correction indications to the network paths involved. The network deadlock is thereby eliminated, and the two broadcasts or multi-casts involved continue their operation in a rearranged sequence that will not cause deadlock.

FIELD OF THE INVENTIONS 
This invention relates to unbufferd multi-stage switching networks, and 
particularly to byte-wide parallel hardware using parallel crossbar 
switches for a byte parallel multi-sized interface switch for broadcasting 
and multi-casting over multi-staged switching networks using a special 
high priority implementation that allows broadcast and multi-cast 
functions to be transmitted over the same simplex network used for normal 
message transmission. 
BACKGROUND OF THE INVENTIONS 
In the patent literature, there are many patents which deal with broadcast 
mechanisms. Some broadcast mechanisms are not implemented by hardware. For 
instance, U.S. Pat. No. 4,818,984 to S. J. Chang et al. issued on Apr. 4, 
1989 describes a broadcast mechanism implemented in software. 
Switching networks are different from busses and local area networks 
(LANs). For instance, it would be recognized that U.S. Pat. No. 4,926,375 
to F. L. Mercer et al. issued on May 15, 1990 relates to a broadcast 
mechanism implemented over a multi-drop bus. U.S. Pat. No. 4,706,080 to W. 
D. Sincoskie issued on Nov. 10, 1987 describes a broadcast mechanism 
implemented over several multi-drop busses; as does U.S. Pat. No. 
4,855,899 to S. D. Presant issued on Aug. 8, 1989; as also does the 
publication by IBM in the TECHNICAL DISCLOSURE BULLETIN, IBM TDB Vol. 30, 
No. 1, 6/87 pg 72-78, POLL ACTUATED MULTIPLE ACCESS TECHNIQUE FOR 
BROADGATHERING SYSTEMS. 
There are several patents which describe broadcast mechanisms for LANs. 
U.S. Pat. No. 4,754,395 to B. P. Weisshaar et al. issued on Jun. 28, 1988 
describes a broadcast mechanism implemented over a serial, loop-connected 
LAN. U.S. Pat. No. 4,835,674 to R. M. Collins et al. issued on May 30, 
1989 describes a broadcast mechanism implemented over multi-drop busses 
tied to LANs and broadcasting over the entire set-up. 
Some broadcast mechanisms are designed for synchronized multiplexed time 
slot, bit oriented networks, as represented by U.S. Pat. No. 4,897,834 to 
J. R. Peterson et al. issued on Jan. 30, 1990 and others, such as U.S. 
Pat. No. 4,766,592 to E. Baral et al. issued on Aug. 23, 1988 describe a 
broadcast mechanism implemented over a synchronized, multiplexed time 
slot, telephone line hook-up. IBM TDB Vol. 22, No. 12, 5/80 pg 5450-52, 
DISTRIBUTED STAR NETWORK WITH UNROOTED TREE TOPOLOGY describes a broadcast 
mechanism implemented over an unrooted tree network which uses synchronous 
transmissions and packet switching. 
Other mechanisms are designed for transmission lines. U.S. Pat. No. 
4,935,866 to R. Sauvajol et al. issued on Jun. 19, 1990 describes a 
broadcast mechanism implemented over a synchronous, transmission line, 
communication link. U.S. Pat. No. 4,941,084 to M. Terada et al. issued on 
Jul. 10, 1990 describes a broadcast mechanism implemented over a 
transmission line, loop interconnect arrangement. U.S. Pat. No. 4,815,105 
to S. Bottoms et al. issued on Mar. 21, 1989 describes a broadcast 
mechanism implemented over a transmission line, telephone line type 
interconnect arrangement. While telephone switches have employed crossbar 
switches, generally they do not use parallel connect crossbar switches. 
Some prior work related to multi-stage switching networks has also been 
developed. U.S. Pat. No. 4,956,772 to P. M. Neches issued on Sep. 11, 1990 
provided a buffered packet synchronous switch. This complex single serial 
interface line switch requires data recovery capabilities. It needs a 
complex priority determination built into each switch stage, and brings 
the broadcast command bits into the switch serially. Another packet switch 
which relates to a multistage switching network is U.S. Pat. No. 4,701,906 
to M. N. Ransom et al. issued on Oct. 20, 1987. It also is a buffered 
synchronous packet switch, and provides for a handshaking interface. It 
brings the broadcast command bits into the switch serially, and the 
complex switch also requires data recovery capabilities. It is a single 
serial interface, and appears not to have considered the need for an 
asynchronous byte-wide parallel interface for broadcast applications. 
Broadcasting a message from one device to N devices through a multi-stage 
network composed of BUFFERED switching devices is a relatively simple 
task: at each switch the message is fanned-out to all the switch outputs 
by inserting it into a queue (ordered buffer) associated with each output. 
The transmitter of the broadcast message does not have to concern itself 
with contention at each switch output (i.e., the output being busy 
transmitting previously initiated messages). If the output is busy, the 
broadcast message merely goes into a queue of messages waiting to use the 
output and eventually will get its turn and the broadcast message will 
propagate slowly through the network. However, there are 3 drawbacks to 
using buffered networks: they are usually relatively slow; there is the 
problem of not knowing when the broadcast will arrive and certainly it 
will arrive at vastly different times at the various receiving devices; 
and buffered networks usually require synchronization across all 
transmitting and receiving devices as well as the network switches 
themselves. Synchronous systems are finding it more and more difficult to 
meet the ever-increasing communication demands of modern parallel 
processing systems; they are just not fast enough to keep pace with the 
rapidly increasing computer clock rates and thus they are becoming a high 
risk problem. 
On the contrary, UNBUFFERED asynchronous networks can provide greatly 
improved speed at a much lower complexity, risk and cost. However, one of 
the problems usually inherent with unbuffered networks is that they cannot 
BROADCAST messages (i.e. send messages over the switching network from one 
device to all the devices attached to the network). 
SUMMARY OF THE INVENTION. 
The present invention provides a solution applicable to performing both 
broadcast and multi-cast transfers over switching networks, in addition 
and inter-mixed with the single transfers normally supported by the said 
networks. In particular, the disclosure applies to byte-wide parallel 
hardware using parallel crossbar switches for a byte parallel multi-sized 
interface switch for communicating over multi-staged switching networks. 
This solution provides the usual advantages of broadcast and multi-cast 
operations through an unbuffered network, and gives a far superior 
broadcast capability in comparison to buffered networks in that the 
broadcast message propagates quickly and arrives simultaneously at all 
receiving devices. In addition, the present invention permits multiple 
broadcasts to be queued at the switching apparatus and resolves the 
broadcast contention on a synchronous priority driven basis that permits 
one broadcast to follow the other at the earliest possible moment and the 
quickest possible speed. In addition, the present invention permits 
multiple multi-cast operations to occur simultaneously within the network.

DETAILED DESCRIPTION OF THE INVENTIONS 
The "Broadcast/Switching Apparatus For Executing Broadcast/Multi-Cast" 
Transfers over Unbuffered Asyncgronous Switching Networks by H. T. 
Olnowich et al U.S. Ser. No. 07/748,316, filed Aug. 21, 1991 now U.S. Pat. 
No. 5,409,461 and "Multi-Sender/Switching Apparatus For Status Reporting 
Over Unbuffered Asynchronous Multi-Stage Networks" by H. W. Olnowich et al 
U.S. Ser. No. 07/748,302, filed Aug. 21, 1991 (IBM Docket EN991030B) meet 
a need for improved switching network approaches using parallel connect 
crossbar switches (a non-loop or transmission line approach) for circuit 
switching networks for asynchronous, dedicated path (not time slotted), 
byte wide parallel direct connect switching, which is applicable to 
multi-stage networks. The way for executing broadcast/multi-cast transfers 
over unbuffered, asynchronous, switching networks solved the broadcast 
problem for simple low priority broadcast in an unbuffered multi-stage 
network capable of supporting only one broadcast at a time in the network 
and consuming all of the network facilities. This concept meets the needs 
of many low end systems and provides an inexpensive and easy solution that 
doesn't required any clock signals whatever to execute. 
The present invention expands on the simple asynchronous broadcast 
disclosed in an earlier device and provides a more complex, yet faster and 
higher powered broadcast and multi-cast function that works synchronously 
and requires a clocking control signal to execute. The disclosed invention 
permits multiple broadcasts to be queued at the switching apparatus and 
resolves the broadcast contention on a synchronous priority driven basis 
that permits one broadcast to follow the other at the earliest possible 
moment and the quickest possible speed. In addition, the present invention 
permits multiple multi-cast operations to occur simultaneously within in 
the network. This is becoming an increasingly important function for 
future massively parallel processors consisting of many nodes that can be 
subdivided into many tasks. With this type of environment it is recognized 
that multi-cast becomes a very important function, more so than broadcast, 
because not all processors need to communicate through broadcast. Rather 
the needs lies in having the subsets of nodes assigned to the same tasks 
communicate to only the other nodes in its own subset. For this type of 
communication, multi-cast provides the solution. The present invention 
provides a network capable of sustaining many multi-casts simultaneously, 
thus, providing a very powerful tool for future parallel applications. The 
broadcast method described in the invention is understood to be related to 
the contemporaneously filed U.S. Ser. No. 07/800,652, filed Nov. 27, 1994 
now U.S. Pat. No. 5,444,705 entitled "DUAL PRIORITY SWITCHING APATUS 
FOR SIMPLEX NETWORKS" which discloses a way for giving certain network 
operations a higher priority than others, which is incorporated by 
reference which in turn is predicated on U.S. Ser. No. 07/677,543, filed 
Mar. 29, 1991 now abandoned entitled "ALL-NODE Switch - an unclocked, 
unbuffered, asynchronous, switching apparatus", which performs the basic 
point-to-point transfers over the said network. The present invention uses 
the high priority mode of transfer to implement a better performing and 
more capable mode of broadcast and multi-cast functions. 
According to the objects of this invention, functions, interface lines, and 
hardware are added to the said ALL-NODE Switch to enhance it to 
additionally perform the priority broadcast and multi-cast functions from 
any element connected to the said network. 
In accordance with the preferred embodiment the dual priority switching 
apparatus described in U.S. Ser. No. 07/800,652, Filed Nov. 27, 1991 now 
U.S. Pat. No. 5,444,705 entitled "DUAL PRIORITY SWITCHING APATUS FOR 
SIMPLEX, provides an unbuffered multi-stage network for interconnecting 
several or many system elements. The invention apparatus as modified with 
additional hardware provides a means for providing the priority 
broadcasting or multi-casting functions amongst these elements in 
accordance with this preferred embodiment 
It is a feature of this embodiment that a unique interface line to and from 
each element is provided to define the activation of priority broadcast or 
multi-cast mode. The System has the ability to process one broadcast or 
multiple multi-cast operations at a time. In addition, it will not 
normally reject other subsequent attempts to broadcast or multi-cast when 
contention or blockage exists, but will hold them pending to be executed 
in priority order at the earliest moment after the contention subsides. 
In accordance with our inventions, we provide a hardware circuit for a 
common priority broadcast/multi-cast design function which works equally 
well at any stage whatsoever of the network. 
In accordance with our inventions, we provide hardware circuitry for the 
detection and correction of deadlock conditions in the multi-stage 
network. Deadlock conditions are not expected to be usual conditions in 
the network, but there is a possibility of their occurrence resulting from 
multiple simultaneous broadcasts or multi-casts colliding within the 
network in a manner which is not resolvable. The hardware circuitry 
detects all the different types of deadlock conditions automatically and 
issues reject or retry indications to the network paths involved. The 
network deadlock is thereby eliminated, and the two broadcasts or 
multi-casts involved continue their operation in a rearranged sequence 
that will not cause deadlock. 
In addition, the invention apparatus has the capability of providing a 
positive feedback acknowledgment that it has made connections to all the 
commanded paths. This is provided uniquely for each stage of the network. 
Turning now to the drawings in greater detail, as illustrated by FIG. 1, 
showing the preferred switch, the preferred switch shall be a 4.times.4 
crossbar which operates asynchronously to transmit 4 bits of data in 
parallel FROM any of 4 input ports TO any of 4 output ports. Such a switch 
as shown in FIG. 1 is capable of supporting up to 4 simultaneous 
connections at any instant of time. The assumed switch shall be capable of 
operating in either of 2 modes--a low-priority mode or a high-priority 
mode. The description of the individual modes are given below. 
It is here understood that the FIG. 1, FIG. 2, FIG. 3, and FIG. 4 are 
illustrations which are common to U.S. Pat. No. 07/677,543, now abandoned 
the parent application which is incorporated herein by reference as to all 
of its contents. The disclosure made therein has been modified by the 
logic and timing of control signals which are illustrated by FIGS. 5 to 
14. 
As illustrated by FIG. 1 the preferred switching apparatus would be 
provided for a node having a plurality of input and output ports, and 
would comprise the connection control circuit for each input port, and a 
multiplexer control circuit for each output port for connecting any of I 
inputs to any of Z outputs, where I and Z can assume any unique value 
greater or equal to two, as in the parent application. 
However, by the modifications made and illustrated herein, a dual priority 
switch will be provided for consistent operation in a multi-stage network. 
The switch would allow for two priorities, and assign a different priority 
level to each function, and allow each function to be transmitted over the 
same physical single network path. 
The preferred embodiment is a 4.times.4 crossbar switching apparatus, where 
the function of the present invention is to provide a means of connecting 
any of four input pods on a mutually exclusive basis to any one of the 
unused four output pods on a priority basis. 
Referring to FIG. 1, the 4.times.4 crossbar switching apparatus can support 
up to four simultaneous connections at any given time. For instance, Input 
1 could be connected to Output 3, Input 2 to Output 4, Input 3 to Output 
2, and Input 4 to Output 1. 
The invention switching apparatus 10 is unidirectional, which means that 
data flows in only one direction across the said switching apparatus 10, 
that being from input to output. Although the said switch apparatus 10 is 
unidirectional, it supports bidirectional communication amongst four nodes 
(20, 22, 24, and 26) by connecting the 4.times.4 ALL NODE switching 
apparatus 10 as shown in FIG. 1. Each node 20, 22, 24, and 26 has two sets 
of unidirectional interconnecting wires, one going to the switch 10 and 
one coming from the switch 10. The dashed lines internal to the switching 
apparatus 10 indicate that the function of the said switching apparatus is 
to connect an input port such as INPUT PORT 1 to one of four possible 
output pods. The switching apparatus 10 provides exactly the same function 
for each input port, allowing it to be connected to any unused output 
port. As illustrated by FIG. 2 the switch 12 has four data bit inputs and 
four control inputs. A new high priority (HI-PRI) interface control line 
is added to the basic ALLNODE switch design to implement the new dual 
priority function. In addition, the VALID and REJECT control signals 
remain, as well as the ACCEPT line which becomes mandatory line. 
Referring thus to FIG. 2, block 12 shows an expanded drawing of switching 
apparatus 10 and defines in detail the interface lines connecting to 
switching apparatus 10. The set of lines 31, 32, 33, and 34 at each 
in-port to the switching apparatus 12 are identical in number and function 
to the set of lines 41, 42, 43, and 44 at each out-port. The sets of 
interface lines to each input and output port contain eight unique 
signals: four data lines and four control lines (VALID, REJECT, ACCEPT, 
and HI-PRI (High Priority) which are differentiated by a prefix of INX- or 
OUTX- indicating the direction and number of the port (X) that they are 
associated with. The four data and VALID and HI PRI lines have a signal 
flow in the direction going from input to output across switching 
apparatus 12, while the REJECT and ACCEPT control lines have a signal flow 
in the opposite direction. 
The sets of input port interface lines 31, 32, 33, and 34 transfer control 
information to switching apparatus 12 for the purpose of commanding and 
establishing input port to output port connections internal to the said 
switching apparatus. In addition, the said port interface lines also carry 
data information to be transferred from input port to output port across 
the switching apparatus 12. The four data interface lines contained in 
interfaces 31, 32, 33, and 34 do not restrict the transfer of data across 
switching apparatus 12 to only four bits of information, but rather the 
said four data lines can each contain a string of serial data making the 
transmission of any size data possible. For example, the said four data 
lines could transfer data at a 160 Mbits/sec rate, if all four data lines 
were transmitting serial data at a 40 MHZ rate. 
The Switch Interface requires only 8 signals, as shown in FIG. 3, to 
transmit and control dual priority data through the network--the data 
transfer width is 1/2 byte (4 bits) at a time. The signals required are: 
DATA: 4 parallel signals used to command switch connections and transmit 
data messages. 
VALID: When active, indicates that a message is in the process of being 
transmitted. When inactive, indicates a RESET command and causes all 
switches to reset to the IDLE state. All switch functions are reset, 
except the high priority latches. 
HI-PRI: When active, indicates the message in process is in high priority 
mode. When inactive, issues a TERMINATE high priority command and causes 
all associated high priority latches to reset. This line must be active 
during the duration of priority broadcast and multi-cast operations. 
REJECT: This signal is the only bi-directional interface signal. Signal 
flow is in the opposite direction from the other 6 signals for low 
priority transfers. When active for a low priority transfer, it indicates 
that a REJECT condition has been detected. For a high priority operation 
when performing either broadcast or multi-cast operations, the signal flow 
is in the same direction as the data flow across the switch and the signal 
is used to correct deadlock conditions occurring between different stages 
in the switching network (deadlock type 2 conditions). 
ACCEPT: Signal flow is always opposite to that of the other 6 signals. When 
in the zero state, it indicates that a WAIT condition has been detected 
and a high priority connection cannot be made at this time. When in the 
high state, it indicates that the WAIT condition has ended and the 
commanded high priority connection has been established. 
Referring to FIG. 3, blocks 56, 52, and 54 illustrate a typical method for 
generating serial data in the form of a message which can be transmitted 
to and across switching apparatus 14, which is a partial drawing of the 
switching apparatus 12. Similar serial data generation logic as provided 
by 56, 52, and 54 can be used at each of the other input ports to 
switching apparatus 12. Each set of input data lines provides serial data 
to a given input port which is synchronized to the same clock by the four 
shift registers 54 which create serial data by shifting four synchronized 
lines of data 31 as controlled by the same identical clocking signal (40 
MHZ in FIG.3). However, the four different input port sources (31, 32, 33, 
and 34) to switching apparatus 14 can be asynchronous to each other, being 
based on different, non-synchronized, 40 MHZ clocking signals. 
The process for sending serial messages through switching apparatus 14 
involves FIFO 56, which accumulates data messages to be transmitted. The 
next entire message to be transmitted is moved to buffer 52. The message 
stored in buffer 52 is moved to shift registers 54 in preparation for 
transmittal and the data is dispersed across the four shift registers 54 
by placing data bit 0 into the first bit of shift register 1, data bit 1 
into the first bit of shift register 2, data bit 2 into the first bit of 
shift register 3, data bit 3 into the first bit of shift register 4, data 
bit 4 into the second bit of shift register 1, etc. Shift registers 54 
then begin to send serial data to switching apparatus 14 over four 
synchronized data lines, in such a manner that the serial data flows 
continuously until the entire message has been transmitted. The switch 
apparatus 14 uses the first eight bits transmitted (in the first two clock 
cycles of serial data over interface 31 from serial registers 54 to 
switching apparatus 14) to select and establish a connection path through 
the switching apparatus 14. The example in FIG. 3 illustrates via dashed 
lines, the switching apparatus establishing a temporary connection between 
input port 1 (31) and output port 2 (42), such that each of the seven 
individual lines in interface 31 are uniquely and directly connected to 
each of the corresponding lines in interface 42. 
Referring to FIG. 4, a method is illustrated for increasing the number of 
nodes in a system by cascading eight switching apparatus 10 blocks. The 
eight cascaded switches are denoted as 10A through 10H to indicate that 
they are identical copies of switching apparatus 10, varying only in 
regards to the wiring of their input and output ports. It can be noted 
that any of sixteen nodes can communicate to any other node over a 
connection that passes through exactly two of the switching apparatus 10 
blocks. For instance, Node 5 can send messages to Node 15 by traversing 
switch 10B and switch 10H. Since all connections are made through two 
switching apparatus 10 blocks, the network comprised of the eight 
switching apparatus 10 blocks is referred to as a two stage switching 
network. Other multi-stage networks can be configured from switching 
apparatus 10 blocks by using three stages, four stages, etc. in a similar 
manner. The number of nodes possible to interconnect with this type of 
network can become very large; however, for simplicity the network in FIG. 
4 will be assumed throughout this disclosure, since it typifies the 
characteristics of larger networks. 
In the low-priority mode the switch will be capable of receiving commands 
from each input port, commands that can arrive asynchronously and request 
connection to a specific output port. If the requested output port is 
available (NOT BUSY; i.e., not being used to support a previously 
commanded connection), the command shall be executed and the connection 
established. If the output port is BUSY, the command shall be rejected and 
the input port will return to the IDLE state (i.e., ready to accept any 
subsequent command it receives). This rejected connection in the low 
priority mode is referred to as a KILL operation because the entire path 
in the network is broken down or KILLED, if any pad of the complete path 
cannot be established. 
Switches can be cascaded together to form networks larger than the 
4.times.4 interconnection scheme supported by an individual switch. FIG. 4 
shows how this is done by connecting an output port from one switch to the 
input port of a second switch. A possible occurrence in this larger 
network is that the initial switches establish valid connections and a 
subsequent switch is BUSY and thus issues a REJECT. The REJECT indication 
then gets sent in the reverse direction back to the previous switch's 
output port--which has already established a valid connection. In this 
case, the switch shall dissolve its valid connection and indicate this 
action by sending a REJECT signal to the input port to which it was 
previously connected. In turn, the input port will issue a REJECT to its 
source and then return to the IDLE state. This approach is called KILL, 
because a REJECT sequence causes all previously established connections to 
be broken or KILLed and everything in the KILL path to be returned to the 
idle state. Also, any portion of the message whose transmission has been 
initiated is completely lost or KILLed and any retransmission of the 
message must be reinitiated from the very beginning. 
If 2 or more of the input ports receive commands simultaneously and contend 
with each other to establish connection to the same NOT BUSY output port, 
the lower numbered input port shall win the contention, make the 
connection desired, and the other contenders shall be rejected and their 
connections KILLED. Accordingly, it will be seen that the low-priority 
path through the simplex network uses the KILL function. If rejection 
occurs in any part of the path, the entire path is broken down immediately 
and the message must be retransmitted from scratch. 
Single destination messages, priority broadcasts, and priority multi-casts 
are all capable of being transmitted over the high priority path through 
the network. The high priority mode performs differently than the low 
priority mode in that it sets a special high priority pending latch, which 
inhibits the issuing of REJECT in response to a blocked connection, but 
instead holds that connection or connections (broadcasts or multi-casts 
require more than 1 connection) pending at the switch until the blocked 
connection or connections becomes available. Then, it immediately makes 
the pending connection(s) and issues a positive feedback to the requester. 
The pending connection cannot be lost or lose its priority unless it is 
terminated by the message source or reprioritized by the deadlock 
correction function. 
Instead of a REJECT response, the high priority mode issues a WAIT 
response, if a connection cannot be made. The WAIT response consists of 
driving the ACCEPT signal to zero and holding it at a zero for the 
duration of the WAIT condition. When the pending connection is made, the 
ACCEPT signal is driven to a logical 1 as a positive indication that the 
WAIT state is over. When the node requesting a connection senses a WAIT 
response, it temporarily pauses its message transmission and continues 
from where it left off when the WAIT condition subsides. Thus, in the high 
priority mode, the transmitting node doesn't retransmit a blocked message 
from the beginning, like it does in the low priority mode, but instead 
just pauses and continues when ACCEPT rises. The timing is such that the 
transmitting node receives the ACCEPT indication to continue at the 
earliest possible moment, thus allowing the high priority message to be 
transmitted at the earliest possible time. In addition, all stages 
previous to the blockage (in which connections were previously won) are 
held for the duration of the WAIT period and never have to be 
re-established again for the high priority message, broadcast, or 
multi-cast in progress. Thus, it provides for the guaranteed delivery of a 
high priority single destination message and for delivery of broadcast and 
multi-cast messages at the quickest possible time. 
If more than one high priority message is waiting for the same output port 
to become available, the message associated with the lowest numbered input 
port gets connected first--while the others continue to WAIT in a snapshot 
register. After all requests waiting in the snapshot register have been 
serviced, the register is allowed to load again if more high priority 
requests are pending. The snapshot register gives all requesters an equal 
chance to make a connection to an output port, before any given requester 
can be serviced a second time. Thus, it provides a method via the high 
priority path through a network to prevent any given requestor from being 
completely blocked from the network and experiencing starvation. 
It is possible for larger networks that the initial switches establish 
valid connections, while a subsequent switch detects a WAIT condition. In 
this case, the WAIT indication is transmitted in the reverse direction to 
the previous switch--which doesn't break its connection, but merely 
propagates the WAIT indication in the reverse direction. This recurs at 
all previously connected switches until the WAIT gets propagated all the 
way back to the message source. 
It is possible for the source to reset all the high priority path at any 
time by returning the HI-PRI to the zero state. The source does have the 
ultimate control over the network. 
Referring to FIG. 5, an example is shown of a two stage network comprised 
of dual priority switches 10 supporting a broadcast connection from node 3 
to all sixteen nodes. Switching apparatus 10A in the first stage of the 
network forms a connection from its input port attached to node 3 to all 
four of its output ports. Fixed (non-switchable) wiring provides 
connection paths between the switching apparatuses 10 of the first and 
second stages of the network. Switches 10E, 10F, 10G, and 10H in the 
second stage of the network each connect their input port 1 to all four of 
their output ports. Thus, the broadcast connection from node 3 to all 
nodes is achieved. Likewise, any input node to the first stage of the 
network could be connected to broadcast to all nodes. The switching 
apparatus 10 services broadcast connections one at a time; although the 
high priority function does permit other broadcast commands to be sent to 
the switch. These are held pending at the switch and the subsequent 
broadcast connections established at the earliest possible time as soon as 
the previous connections are relinquished. 
Referring to FIG. 6, a typical priority multi-cast example showing how 2 
different multi-casts can exist simultaneously in the same simplex 
network. A multi-cast from node 7 to nodes 2, 4, 10, and 12 through two 
stages of dual priority switches is shown simultaneously with a second 
multi-cast from node 1 to nodes 5, 6, 13, and 14. Switching apparatus 10B 
in the first stage of the network forms a connection from its input port 
attached to node 7 to its first and third output ports. Fixed 
(non-switchable) wiring provides connection paths between the switches 10 
of the first and second stages of the network. Switches 10E and 10G in the 
second stage of the network each connect their input port 2 to their 
second and fourth output ports. Thus, the desired multi-cast connection is 
accomplished. Likewise, input node 1 to the first stage of the network 
makes connections to output ports 2 and 4 and is then connected to nodes 
5, 6, 13, and 14 in the second stage to perform a second multi-cast 
operation simultaneously or overlapped in any manner with the multi-cast 
shown from node 7. In general, multiple multi-casts can be performed 
simultaneously, as long as there are no shared connection paths amongst 
the different multi-cast operations. For instance, node 1 multi-cast could 
not have existed simultaneously if it wanted to multi-cast to node 5, 
because node 5 is connected to node 7 multi-cast and could not share its 
connections simultaneously to two different operations. If a shared path 
exists, the high priority mode resolves the contention on a priority 
driven basis and establishes a new connections to the shared path as soon 
as the path becomes available. 
Referring to FIG. 7, the detailed logic implementation is shown for a 
portion of the dual priority switch 10, the said portion being the typical 
circuitry required to establish a single low priority or high priority 
data transfer connection between one input port (such as input port 1) and 
one output port (such as output port 1) of the preferred 4.times.4 dual 
priority switching apparatus 10 embodiment. Latches 70, 72, 74, and 74 
control the normal low priority path and their operation is explained in 
detail as to how they implement the low priority path and how a connection 
in the switch is broken (KILLED) when a REJECT is encountered as described 
in, "All-Node Switch-Asynchronous Low Latency Approach to Switching 
Networks" by H. T. Olnowich, et al; U.S. Ser. No. 07/677,54307 now 
abandoned. 
The high priority path implementation used for the priority broadcast and 
multi-cast operations is an addition to the basic ALLNODE Switch logic. 
The high priority logic is comprised of latches 172, 174, block 140, delay 
block 84, gates 178, 182, 78, 95, and 115, plus a new interface control 
signal at every port--such as IN1-HI-PRI at Input Pod 1 and OUT1-HI-PRI at 
Output Port 1 as shown in FIG. 7. In addition, this disclosure adds some 
new circuitry specifically required for implementing the priority 
broadcast and multi-cast operations; these are gates 542, 544, and logic 
functions 546 and 548. The functional operation of all the high priority 
logic components, including the priority broadcast and multi-cast 
operations, will be described in detail in this present disclosure. 
Referring to FIG. 8, the timing sequences generated by the node attached to 
Input Port 1 for the purpose of transmitting a priority broadcast 
operation are shown. FIG. 8 defines the signal sequences that Input Port 1 
uses to command the priority broadcast connection of Input Port 1 to 
Output Ports 1 to 4 through the dual priority switching apparatus. The 
operation starts by Input Port 1 activating the IN1-HI-PRI and IN1-VALID 
interface control lines simultaneously to a logical one. The IN1-HI-PRI 
signal turns on the high priority logic path in FIG. 7, and its activation 
to a logical one removes the reset from latches 172 and 174 and enables 
them. Gates 542 and 544 are used to turn off the low priority path 
completely during a priority broadcast and multi-cast operation. This 
occurs when the IN1-HI-PRI interface signal is activated to command the 
execution of a high priority mode transfer. The IN1 HI-PRI signal is 
inverted by gate 544 to send a zero to AND gate 542, which in turn sends a 
reset to latches 74 and 76 since the zero dominates AND gate 542. 
The next occurrence, as shown in FIG. 8, is concurrent set of 4 command 
pulses 81A, 81B, 81C, and 81D are sent to Input port I on IN1-DATA 1, 
IN1-DATA 2, IN1-DATA 3, and IN1-DATA 4 interface lines, respectively. 
These 4 pulses command Input Port 1 to make a high priority connections to 
Output Ports 1 to 4; the command is specified by the IN1-HI-PRI being 
active to define that it is a high priority connection and by the pulse 
81A being on IN1-DATA 1 line which defines that a connection is to be to 
Output Port 1, by the pulse 81B being on IN1-DATA 2 line which defines 
that a connection is to be to Output Port 2, by the pulse 81C being on 
IN1-DATA 3 line which defines that a connection is to be to Output Port 3, 
and by the pulse 81D being on IN1-DATA 4 line which defines that a 
connection is to be to Output Port 4. Broadcast is the maximum connection 
mode as defined by all 4 pulses 81; single destination and multi-cast 
connections are defined by not transmitting all 4 pulses 81, but 
eliminating any 1, 2, or 3 of the pulses 81 as a means a defining a subset 
of the maximum broadcast connection configuration. 
A typical example of the logic interpretation of pulses 81 by the switch is 
shown in FIG. 7 in regards to Pulse 81A on IN1-DATA 1 in causing latch 172 
to set on the rise of pulse 81A and latch 174 to set on the fall of pulse 
81A. Latch 174 being set causes the dual priority switch to latch the fact 
that is has received a COMmand to make a HI-PRIority connection from Input 
Port 1 to Output Port 1 as defined by the COM HI-PRI 11 signal from latch 
174. Latch 172 being set causes the PREHI-PRI 11 signal to activate, which 
in turn causes AND gate 95 to go active creating the WAIT 11 signal. 
Similar logic to that shown in FIG. 7 for Output Port 1, is used to 
generate similar functions and signals in relation to each of the other 3 
Output Ports. The typical timing for the WAIT signals from each of these 
other 3 (not shown) sets of logic are shown in FIG. 8. The 4 WAIT signals 
generate pulses 401 to 404, respectively, based on the occurrence of 
pulses 81A to 81D, respectively. The four WAIT signals are sent through 
NOR gate 115 where they are OR'ed and the result is inverted). The 
function of gate 115 is to cause the priority broadcast to remain in the 
WAIT State if anyone of the four individual WAIT signals is a logical one 
to gate 115. The composite WAIT signal (NOT IN1-WAIT from gate 115 goes to 
AND gate 182, where it is driven back to node 1 over the IN1-ACCEPT line 
causing pulse 71 as shown in FIG. 8. 
Pulse 71 gives a positive acknowledgement to Input Port 1 indicating when 
the commanded connection has been established. As long as any one of the 4 
WAIT signals is active, the dual priority switch is waiting to make the 
connection: i.e., it has not been successful yet at making the connection 
to all 4 of the output ports. When the connection is made successfully to 
all 4 ports, the 4 WAIT signals go inactive, causing gate 115 to go 
active, and causes a logical one to be passed through gate 182 to cause 
the IN1-ACCEPT signal to rise, thus completing pulse 71 and giving a 
positive feedback to Input Port 1 that the connection has been made. Pulse 
71 shows the fastest possible connection time where the connection is made 
quickly (within the duration of the pulses 81) such that pulses 81 and 71 
are of the same duration with pulse 71 being delayed by the path it takes 
through the logic shown in FIG. 7. In order to get this quickest response, 
all 4 output ports have to be available and accept the newly commanded 
broadcast connections immediately with only a very shod WAIT period as 
shown by pulses 401 to 404 occurring at the same time. 
The COM HI-PRI 11 signal also goes to NOR gate 182, where it is NOR'ed with 
other similar signals from the other input ports, any of which will 
propagate through gate 180 and delay block 85 to cause Output Port 1 to 
appear BUSY. Likewise, all the other output ports immediately go busy 
during a broadcast operation. This will cause all subsequent low priority 
requests for be rejected for the duration of the broadcast. 
The making of high priority connections to Output Port 1 are controlled 
through logic block 140, which receives commands from latch 174 and 
similar latches related to the other Input Ports and determines the 
priority in which these connections are to be established. When it decides 
that Input 1 is the highest priority requester for Output 1, block 140 
will activate the "Enable HI-PRI 11" signal--thus informing the dual 
priority switch to make the connection at this time. The detailed 
operation of block 140 is described later in relation to FIGS. 9 and 10. 
The "Enable HI-PRI 11" signal being activated as shown by 207 goes to AND 
gate 178 where it will be inhibited from propagating any further if a low 
priority connection is presently active to Output Port 1 as detectable by 
a latch like 74 being active through NOR gate 80. However, the normal case 
is that NOR gate 80 does not block the "Enable HI-PRI 11" signal at gate 
178 and allows it to pass through and activate the "HI-PRI 11" signal 
immediately or as soon as the low priority connection is broken. Note that 
a high priority operation will not permit any subsequent low priority 
connections to be made until the high priority operations are all 
completed. However, the high priority operation will not break any low 
priority connections previously established, it will merely hold the high 
priority operation pending until the low priority operation releases the 
connection. The "HI-PRI 11" signal is OR'ed with the low priority signal 
(LCONNECT 11) in gate 190 to generate a composite signal CONNECT 11 
defining to the dual priority switch to make the high priority connection 
of Input Port 1 to Output Port 1. The Connect 11 signal is inverted in 
gate 192 and goes to gate 95 where it causes the WAIT 11 signal to go 
inactive once the connection is made. 
The CONNECT 11 signal is also used to establish the direct connection of 
six interface lines between input port 1 and output port 1. The four data 
lines of input port 1 become connected to the four data lines of output 
port 1. The details of a typical connection are shown by AND gate 122 and 
OR gate 130. CONNECT 11 going active to AND gate 122 causes the output of 
AND gate 122 to follow directly the values on IN1-DATA1, which is gated 
through 0R gate 130 to OUT1-DATA1. The other AND gates 124, 126, and 128 
feeding 0R gate 130 will all be held to logical 0's and have no effect on 
gate 130; this is because normally only one CONNECT signal can be active 
at any given time, thus enabling a single connection to a specified output 
port. Therefore, if CONNECT 11 is active to gate 122, CONNECT 21, CONNECT 
31, and CONNECT 41 to gates 124, 126, and 128, respectively, must all be 
inactive. In similar fashion the IN1-HI-PRI and IN1-VALID lines are also 
connected from Input Port 1 to Output Port 1 based on the CONNECT 11 
signal. A typical connection is shown for the IN1-HI-PRI line through 
gates 154 and 162. The result being that all 6 input signals present on 
Input Port 1 get connected directly to the same signals at Output Port 1, 
going directly through the dual priority switch through only 2 gates, such 
as 154 and 162, and without being buffered, such that the pulse forms 
appearing on Input Port 1 appear instantaneously on Output Port 1 
experiencing only a slight delay caused by the 2 logic gates (like 154 and 
162) that they pass through. There is one slight exception where the Input 
PORT 1 waveforms shown in FIG. 8 differ from the output waveforms; that is 
pulse 81A is stripped from the input waveform and stored in latch 174 and 
it is not passed to the Output Port 1. There are 2 reasons for this: 1) By 
the time the CONNECT 11 signal goes active, pulse 81A is gone and cannot 
be passed to the Output Port 1.2) Pulse 81A defines the first stage switch 
connection to be made and has not other meaning, therefore it is not 
desirable to pass pulse 81A any further into the network. 
For the priority broadcast operation, similar CONNECT signals (CONNECT 12, 
CONNECT 13, and CONNECT 14) are used to simultaneously connect the same 
input port 1 interlace signals (IN1-VALID, IN1 HI-PRI, IN1 -DATA1 to 4) to 
output ports 2, 3, and 4 as soon as they become available to affect the 
broadcast connection of input port 1 to all 4 output ports through the 
dual priority switch. 
Two feedback signals from the 4 Output Ports to Input Port 1 also have 
connections established at the time the CONNECT 11 signal becomes active. 
AND gate 94 shows CONNECT 11 selecting OUT1-REJECT as the source of the 
IN1-REJECT signal through NOR gate 92 and OR gate 90. The ACCEPT signals 
from all four output ports come into gates 104, 106, 108, and 110, 
respectively, and are ANDed together by gate 102. The individual 
monitoring of the four OUTx-ACCEPT signals is enabled by the inverse of 
their corresponding CONNECT signals, shown typically by gate 192 
generating NOT CONNECT 11 going to gate 104. Likewise, the REJECT signals 
from each output port are combined in gate 90 to provide a single 
composite IN1-REJECT signal to input port 1. 
In a multi-stage network, pulse 71 going away indicates that the first 
stage switch in the network has made its broadcast connections. The next 
step is to command the second stage network switch to make its broadcast 
connections by issuing pulses 73A to D on IN1-DATA 1 as shown in FIG. 7. 
The example assumes a two stage network shown in FIG. 4 and that the 
second stage switch logic, like the first, is identical to the logic shown 
in FIG. 7. The second stage is commanded to make the exact same high 
priority connection as the first stage of Input Port I to all 4 output 
ports by the presence of pulses 73 on all 4 of the IN1-DATA lines. Note 
that switch stage two does not see pulses 81 that have been stripped of by 
stage 1 switch. 
The events which take place at the stage 2 switch are similar the events 
which previously took place at the stage 1 switch. The operation starts at 
stage 2 by Input Port 1 activating the IN1-HI-PRI and IN1-VALID interface 
control lines simultaneously to logical ones as they get connected through 
from stage 1. The IN1-HI-PRI signal controls the high priority logic path 
and disables further use of the low priority path as it did in stage 1. 
Likewise, the activation of IN1-HI-PRI at the second stage to a logical 
one removes the reset from latches 172 and 174 and enables them. 
The next occurrence, as shown in FIG. 8, is command pulse 73A on IN1-DATA 1 
interface line that commands Input Port 1 to make a high priority 
connection to Output Port 1. Pulse 73A being on IN1-DATA 1 causes latch 
172 at the second stage switch to set on the rise of pulse 73A and latch 
174 to set on the fall of pulse 73A. Latch 174 being set causes the dual 
priority switch to latch the fact that is has received a COMmand to make a 
HI-PRIority connection from Input Port I to Output Port 1 as defined by 
the COM HI-PRI 11 signal from latch 174. Latch 172 being set causes the 
PREHI-PRI 11 signal to activate, which in turn causes AND gate 95 to go 
active creating the WAIT 11 signal. Similar logic to that shown in FIG. 7 
for Output Port 1, is used to generate similar functions and signals in 
relation to each of the other 3 Output Ports. The typical timing for the 
WAIT signals from each of these other 3 (not shown) sets of logic are 
shown in FIG. 8. The 4 WAIT signals generate pulses 405 to 408, 
respectively, based on the occurrence of pulses 73A to 73D, respectively. 
Pulses 405 to 408 being of different pulse sizes show an example of the 
WAIT period being of different durations for establishing a connection to 
each of the 4 output ports; i.e., some of the output ports are assumed to 
have previous connections so that they cannot respond at the quickest 
possible instant as shown in stage 1 by pulses 401 to 404, but instead 
they have to wait until the connection becomes available. The four WAIT 
signals are sent through NOR gate 115 where they are OR'ed and the result 
is inverted). The function of gate 115 is to cause the priority broadcast 
to remain in the WAIT state if any one of the four individual WAIT signals 
is a logical one to gate 115. The composite WAIT signal (NOT IN1-WAIT from 
gate 115 goes to AND gate 182, where it is driven back to node 1 over the 
IN1-ACCEPT line causing pulse 75 as shown in FIG. 8. In the stage two 
case, the WAIT 11 signal (pulse 405) is the last WAIT signal to go away 
and causes the composite IN1-ACCEPT signal pulse 75 to be elongated until 
the WAIT 11 goes to a 0, even though the other 3 connections were 
established sooner. 
At pulse 209 time the "Enable Hi-PRI 11" signal is issued by block 140, 
which assigns the next connection to be made to Output Port 1 as coming 
from Input Port 1. The "Enable HI-PRI 11" signal being activated goes to 
AND gate 178 to be OR'ed with the low priority signal (LCONNECT 11) in 
gate 190 and generate a composite signal CONNECT 11 defining to the dual 
priority switch to make the connection of Input Port 1 to Output Port 1. 
The Connect 11 signal is inverted in gate 192 and goes to gate 95 where it 
causes the WAIT 11 signal to go inactive (as shown by the termination of 
pulse 405). 
Note from FIG. 5, that to establish a broadcast connection to all 16 nodes 
that there are 4 stage 2 switches (10E to 10H) that must all establish 
broadcast connections similar to the stage two switch described above. All 
4 stage 2 switches function identically to the typical stage 2 switch 
described above, and all receive the exact same interface signals as they 
are fanned out in broadcast mode by the first stage switch. However, each 
of the 4 second stage switches (10E to 10H) can experience different WAIT 
times for establishing their broadcast connections. The individual wait 
times are reported back to the first stage switch over individual ACCEPT 
lines, one to each output port as shown in FIG. 2 by signals OUT1-ACCEPT, 
OUT2-ACCEPT, OUT3-ACCEPT, and OUT4-ACCEPT. Each OUTX-ACCEPT from the first 
stage is connected to a different IN1-ACCEPT signal coming from the second 
stage switches 10E to 10H. The 4 second stage switches pass the ACCEPT 
indication back to switch 10A in the first stage, which in turn sends an 
indication immediately on its IN1-ACCEPT signal to Node 1. Switch 10A 
logically "ANDs" all the ACCEPT signals it receives from its four output 
ports as shown by AND gate 102 of FIG. 8 after gating the signals 
individually in OR gates 104, 106, 108, and 110. Gates 104 to 110 are used 
in relation to single destination or multi-cast operations to prevent the 
second stage switches which are not effected by the transfer from having 
any affect on the composite ACCEPT signal generated by gate 102. However, 
for the broadcast operation, all the OR gates 104, 106, 108, and 110 are 
preconditioned so as to pass the four ACCEPT signals directly to gate 102. 
Thus, gate 102 collects WAIT signals from all 4 second stage switch ANDS 
them together. Note that the wait period inside of the switch is indicated 
by the WAIT signal being a logical 1; however, this indication is 
signalled outside the switch over the interface line INX-ACCEPT being a 
zero to indicate wait and a one to indicate that all connections have been 
made. Gate 102 in stage 1 forms a composite ACCEPT signal based on the 
value of all 4 OUTX-ACCEPT signals it receives (the 4 OUTX-ACCEPT signals 
are are connected directly to the INX-ACCEPT signal from all 4 second 
stage switches). The result being that gate 102 will not go active until 
all 4 second stage switches report that they have successfully made 
connection to all 4 of their associated output ports. If any one of the 
four inputs to gate 102 is a zero (indicating wait), the output of gate 
102 will be a zero and return a zero to node 1 over the IN1-ACCEPT line 
from stage 1--keeping pulse 75 in the zero state. However, when all 4 
inputs to gate 102 return to the one state, indicating that all 16 
broadcast connections have been made, the output of gate 102 goes to a one 
causing IN1-ACCEPT to go to a one and pulse 75 to terminate. Pulse 75 
gives a positive acknowledgement that all 16 of the stage 2 connections 
have been established. ANDing of the ACCEPT signals requires that an 
active ACCEPT signal is sent from all receiving nodes attached to the 
output ports of each broadcast/switch before an ACCEPT signal is forwarded 
to the previous broadcast/switch stage or to Node 3. When Node 3 sees the 
ACCEPT signal go active, it gets a positive feedback indication that the 
transfer completed successfully to all sixteen nodes. Node 3 then resets 
its IN3-BRDCAST, IN3-VALID, and four IN3-DATA lines to broadcast/switch 
10A to zeroes, thus completing the broadcast and returning its interface 
to the IDLE state. The IN3-BRDCAST and IN3-VALID input lines going to a 
zero at clock time n+3 causes broadcast/switch 10A input port 3 to break 
its connection to all four output ports, returning them to the IDLE state. 
Immediately, broadcast/switches 10E, 10F, 10G, and 10H see their 
respective IN1-BRDCAST and IN1-VALID input lines go to zero, breaking 
their connections to all their four output ports and returning them to the 
IDLE state. Thus, the connections can be broken and the broadcast/switches 
returned to IDLE in as little as one clock time. If Node 3 has another 
broadcast or non-broadcast message to transmit, it can load the next 
message into buffer 52 and shift registers 54 (FIG. 7) and begin 
transmission as soon as clock time n+4. The only restriction is that the 
VALID signal generated by Node 3 must return to zero for a minimum of one 
clock time (time n+3) to signify the end of one transfer before beginning 
another. 
This completes the establishment of the high priority broadcast connections 
through both stages of a two stage network. The path connections are now 
established and MESSAGE DATA can be broadcast from node 1 to all 16 nodes 
simultaneously, as shown in FIG. 8. The result of this implementation is 
that a high priority path is established at the quickest possible speed 
because the high priority command is stored at the switch stage involved 
and made on a priority basis as soon as output ports required become 
available. In addition, a positive feedback is given to the node 
establishing the connection immediately upon the making of the connection, 
so that it may proceed at the earliest possible moment. 
After the MESSAGE DATA has been broadcast to all nodes, all the receiving 
nodes can check the message for accuracy using the selected error 
detection method (parity, CRC, etc. ). If the message has been received 
correctly, each receiving node responds by activating its ACCEPT signal 
back to the second stage switches 10E to 10H in the network shown in FIG. 
5. The second stage switches pass the ACCEPT indication back to the first 
stage switch 10A, which in turn returns it immediately to Node 1. Each 
switch (10A and 10E to 10H) logically "ANDS" all the ACCEPT signals it 
receives from its four output ports as shown by AND gate 102 of FIG. 7. 
This ANDing of the ACCEPT signals requires that an active ACCEPT signal is 
sent from all receiving nodes attached to the output ports of each switch 
(10E to 10H) before an ACCEPT signal is forwarded to the the first switch 
stage 10A or to Node 1. In order for the ACCEPT function to operate 
accurately in multi-cast mode, the switch must cause the ACCEPT interface 
lines from all output ports NOT involved in the transmission to go to a 
logical 1, so they will not prevent the propagation of an accurate ACCEPT 
indication from the nodes that are involved. This is accomplished 
internally to switch 10 by gates 104, 106, 108, and 110 for output ports 1 
to 4, respectively. Thus, the AND gates 102 in each switch 10 (10A and 10E 
to 10H) are primed to pass accurate ACCEPT feedback indications for any 
type of command--broadcast, multi-cast, or single destination. When Node 1 
sees the ACCEPT signal go active (Pulse 79 terminates), it gets a positive 
feedback indication that the transfer completed successfully to all 
selected nodes. Node 1 then resets its IN1 HI-PRI, IN1-VALID, and four 
IN1-DATA lines to switch 10A to zeroes, thus completing the broadcast and 
returning its interface to the IDLE state. 
Two new functional blocks 546 and 548 have been added to FIG. 7 as part of 
the present invention to deal specifically with two different types (TYPE 
1 and TYPE 2) of deadlock conditions that can occur while attempting to 
execute 2 or more simultaneous priority broadcast or multi-cast operations 
in the simplex network. The detail of blocks 546 and 548 are described 
later in relation to FIGS. 11 to 14. 
Key to the high priority implementation and the prioritizing of broadcast 
and multi-cast operations is the function provided by block 140, which is 
shown in detail in FIG. 9. Typical logic is shown for establishing a high 
priority connection from Input Port 1 to Output Port I by latches 252 and 
254 as they function in relation to gates 250 and 258, and delay block 
257. Identical logic is shown for establishing a high priority connection 
from Input Port 2 to Output Port 1 by latches 262 and 264 as they function 
in relation to gates 260, 266, and 268, and delay block 267. Identical 
logic is shown for establishing a high priority connection from Input Port 
3 to Output Port 1 by latches 272 and 274 as they function in relation to 
gates 270, 276, and 278, and delay block 277. Identical logic is shown for 
establishing a high priority connection from Input Port 4 to Output Port 1 
by latches 282 and 284 as they function in relation to gates 280, 286, and 
288, and delay block 287. 
Block 140 requires sequential logic operations and decisions which require 
a clock signal to implement. This is the first time that a clock has been 
necessary to implement any of the ALLNODE Switch concepts. The clock used 
in FIG. 9 has been selected to be 40 MHZ for the purpose of example, but 
the clock frequency in general is dependent upon the technology of 
implementation. 
The functions performed by block 140 and shown in FIG. 9 shall be described 
here by continuing the previous example of Input Port 1 commanding a high 
priority connection to Output Port 1, and adding to it a simultaneous 
request of Input Port 2 commanding a high priority connection to Output 
Port 1, to demonstrate the priority function. The "COM HI-PRI 11" and "COM 
HI-PRI 21" signals convey this information to the block 140 by going 
active to latch 252, where is resynchronized in relation to the 40 MHZ 
clock. Latch 252 is enabled by the IN1-HI-PRI signal on its reset line to 
function whenever Input Port 1 is operating in high priority mode. Latch 
252 will set and generate the IN1-HI PENDING signal when the "COM HI-PRI 
11" signal is active in synchronization with the rise of the 40 MHZ clock 
signal as shown in the timing of FIG. 10. Latch 252 being set indicates 
that Input Port 1 has a pending high priority connection that it wishes to 
make to Output Port 1. The purpose of the block 140 logic is to record 
this pending command and to make the desired connection on a priority 
basis at the very earliest moment. The Latch 252 -Q output is fed back 
into the SET input of the same latch to cause it to remain set after 
initially being set until the IN1-HI-PRI signal goes inactive on the reset 
input to the latch and causes it to reset. The latches 254, 264, 274, and 
284 comprise the 4-bit SNAP SHOT REGISTER, which allows all pending 
connections to be made on a rotating priority basis and prevents any 
individual user from hogging an Output Port connection and causing the 
starvation of some other user who is unable to make the required 
connection. The SNAP SHOT REGISTER is allowed to take "snap shots" only at 
specified intervals for the purpose of determining what connections are 
pending. The "snap shot" intervals are defined by AND gate 300 which 
provides the clock signal that causes the SNAP SHOT REGISTER to sample the 
pending connection requests coming from registers 252, 262, 272, and 282, 
respectively. The clocking of the SNAP SHOT REGISTER occurs as determined 
by gate 300 at a 40 MHZ rate when none of the SNAP SHOT REGISTER bits are 
set and when the Output Port 1 is not busy as determined by the OUT1-NOT 
CONNECTED signal from gate 320. Basically the SNAP SHOT REGISTER will be 
clocked at a 40 MHZ rate as long as Output Port 1 has no present 
connections to it and there are no active bits in the SNAP SHOT REGISTER. 
FIG. 10 shows the timing of the SNAP SHOT REGISTER when both Input Ports 1 
and 2 issue pending high priority commands to connect to Output Port 1, 
and Output Port 1 is previously busy with a previous low priority 
connection as defined by the OUT1-NOT CONNECTED signal 302 being a zero. 
FIG. 10 shows that in this case, both the IN1-HI PENDING and IN2-HI 
PENDING latches 254 and 264 get set and both wait for Output Port 1 to 
become available. At pulse time 301, Output Port 1 terminates its previous 
connection and becomes available. Assuming that the SNAP SHOT REGISTER has 
no bits set previously, the CLOCK SNAP SHOT REGISTER signal goes active 
producing pulse 303 during coincidence with the next 40 MHZ clock signal 
after pulse 301. Pulse 303 goes to all 4 bits of the SNAP SHOT REGISTER 
and causes them to set to the state corresponding to the state of latches 
252,262, 272, and 282, respectively. In the example, both the SNAP SHOT 
REGISTER latches 254 and 264 will set at this time. This will cause the 
"Enable HI-PRI 11" signal to go active after a delay of 10 ns through 
block 257 and gate 258. This selects Input Port 1 to connect to Output 
Port 1 next by issuing pulse 305. Note, that even thought latch 264 gets 
set by pulse 303, "Enable HI-PRI 21 signal doesn't go active at the same 
time as pulse 305 because it is prevented by gate 266, since the "NOT 
Enable HI-PRI 11" signal is a zero at this time. 
After Input Port 1 sends its message to Output Port 1, it breaks its 
connection to Output Port 1 by deactivating its IN1-HI-PRI signal as shown 
in FIG. 10 which in turn resets COM HI-PRI 11, IN1-HI PENDING and ENABLE 
HI-PRI 11 (a bit in the SNAP SHOT REGISTER). At this time only Latch 264 
remains set in the SNAP SHOT REGISTER, gate 266 is enabled to pass the 
indication to delay block 267 which causes the "ENABLE HI-PRI 21" signal 
268 to go active 10 ns later to produce pulse 307 in FIG. 10 and select 
Input Port 2 to connect to Output Port 1 next. After Input Port 2 sends 
its message to Output Port 1, it breaks its connection to Output Port 1 by 
deactivating its IN2-HI-PRI signal as shown in FIG. 10, which in turn 
resets COM HI-PRI 21, IN2-HI PENDING and ENABLE HI-PRI 21 (based on 
resetting a bit in the SNAP SHOT REGISTER). Then Output Port 1 has 
serviced all of its pending connections, the CLOCK SNAP SHOT REGISTER 
signal 300 begins clocking the SNAP SHOT latches again by issuing pulses 
like 309 and 311 and which continue until Output Port 1 becomes connected 
again or until another high priority operation gets latched into the SNAP 
SHOT REGISTER. 
The purpose of delay blocks 257,267,277 and 287 is to prevent one 
connection from following too closely behind another and causing erroneous 
operation prior to the time the interface signals settle out. 
Gates 250, 260, 270, and 280 permit latches in the SNAP SHOT REGISTER to be 
individually reset by the NOT RESET IN1 HI-PRI, NOT RESET IN2 HI-PRI, NOT 
RESET IN3 HI-PRI, and NOT RESET IN4 HI-PRI signals, respectively. These 
signals are unique to the broadcast and multi-cast operations and are used 
to correct deadlock conditions. Deadlock can occur in the network in two 
different types of circumstances, as shown in FIG. 11. The first deadlock 
condition, referred to as Type 1, occurs entirely within one switch as 
illustrated internal to switch 10A in FIG. 11. One example of deadlock 
type 1 is shown which assumes that node 1 and 4 are trying to multi-cast 
simultaneously. Node 1 is multi-casting to switch 10A output ports 2, 3, 
and 4 and is successful in winning output ports 2 and 4 immediately as 
shown by the connecting lines from input port 1 internal to switch 10A. 
However, node 1 is unable to successfully complete the multi-cast 
connection because it can not get a connection to output port 3. Node 4 is 
multi-casting to switch 10A output ports 1, 2, and 3 and is successful in 
winning output ports 1 and 3 immediately as shown by the connecting lines 
from input port 4 internal to switch 10A. However, node 4 is unable to 
successfully complete the multi-cast connection because it can not get a 
connection to output port 2. Nodes 1 and 4 have become deadlocked in the 
example and can never resolve the problem on their own. Node 1 has a 
connection to output port 2 that it will never release until it gets a 
connection to output port 3. However, node 4 has a connection to output 
port 3 that it will never release until it gets a connection to output 
port 2. The problem is due to a race condition between the two multi-cast 
operations coming from different nodes at about the same time. This can 
cause two sets of the SNAP SHOT REGISTERS (FIG. 9), one associated with 
input port 4 and one with input port 1, to get out of synchronization with 
each other, such that the priority decision as to which input port gets 
output ports 2 and 3 are not consistent; i.e., it was decided to give the 
highest priority for connecting to output port 2 to node 1 and the the 
highest priority for connecting to output port 3 to node 4. If these 
decisions were consistent, for instance, if the highest priority for both 
output ports 2 and 3 were given to node 1 first, there would be no problem 
because node 1 would go first and then node 4 would go next and deadlock 
would be avoided. Therefore, the solution is to detect the deadlock 
condition and cause the SNAP SHOT registers involved to reprioritize to be 
consistent; then the operations will flow sequentially, rather than 
causing deadlock. The correctioninvolves removing the inconsistent 
priorities from the SNAP SHOT REGISTERS and letting the priority be 
recalculated so that it will be consistent across the various SNAP SHOT 
REGISTERS. Thus gates 250, 260, 270, and 280 are used in FIG. 9 to reset 
individual latches 254, 264, 274, 284, respectively, in the SNAP SHOT 
REGISTER based on individual resets from the deadlock detection and 
correction logic. The detection is based on a priority decision that is 
detected to be inconsistent and has caused deadlock. This inconsistent 
priority decision is reset individually from a latch in the SNAP SHOT 
register. Note that the reset does not go to latches 252,262, 272, and 
282, which do not get reset but continue to hold the connection pending at 
the switch. Only the priority is changed by resetting a bit in the SNAP 
SHOT REGISTER, the operation is not lost or affected in any other way. For 
instance, the highest priority initially in our example for connection to 
output port 3 is input port 4. When deadlock is detected the latch 284 
which gives input port the highest priority is reset. Then priority to 
output port 3 is recalculated and input port 1 wins the connection to 
output port 3. This enables input port 1 to successfully establish all of 
its multi-cast connections and the operation proceeds to completion. After 
the input port 1 multi-cast is complete, input port 4 wins its required 
connections and its operation proceeds to completion. 
Deadlock type 1 cannot occur for single destination high priority 
connections; however, it can occur for broadcast or multi-cast operations 
where an input port must win connections to 2, 3, or 4 output ports within 
the same switch. For two destination multi-casts, deadlock can only occur 
if another multi-cast is going to the exact same two output ports, and 
only then if one multi-cast wins one of the two ports and the other 
multi-cast wins the other. For simultaneous multi-casts to 3 or 4 output 
ports within a given switch, the example above in FIG. 11 of switch 10A 
shows how deadlock can typically occur. For all of the type I cases the 
deadlock can be detect immediately and corrected immediately without 
causing any noticeable delay in the transmission. 
The logic required to detect and correct type 1 deadlock conditions is 
shown in FIG. 12. AND gate 600 shows the combinational logic to detect the 
example deadlock case shown in switch 10A in FIG. 11. The detection is 
based on the outputs of the SNAP SHOT REGISTER such as the signals ENABLE 
HI-PRI 12, etc. which define the multi-cast connections which have been 
made, and the WAIT signals which define the multi-cast connections which 
are trying to be made. In this case, gate 600 says that connections have 
been made from input port 1 to output port 2 and 4, and connections have 
been made from input port 4 to output port 1 and 3, but that deadlocked 
connections 1 to 3 and 4 to 2 are waiting to be made. The combinational 
logic in block 604 is composed of gates similar to gate 600 which detect 
all the other various combinations of 2, 3, and 4 connection multi-casts 
that can cause similar deadlock conditions between input ports 1 and 4. OR 
gate 602 performs a logical OR of all the possible type 1 deadlock 
conditions and generates a RESET IN1 & 4 signal that indicates that a type 
1 deadlock has been detected between input ports 1 and 4. Logic similar to 
gates 600, 602, and 604 is used to detect deadlock conditions between 
every possible combination of the 4 input ports taken two at a time. The 
results are NOR'ed in gates like 606 and 608 which combine all the resets 
to the SNAP SHOT REGISTER associated with a given port. For instance, gate 
606 combines the resets to all the SNAP SHOT REGISTER latches associated 
with input port 4; i.e., it controls the reset of a deadlock between input 
ports 1 and 4, 2 and 4, and 3 and 4. One additional input to gate 606 is 
included (IN4-REJECT) which is the correction reset for type 2 deadlock 
conditions. Thus the type 2 deadlock conditions cause the exact same 
correction algorithm to be implemented as is used for type 1 deadlock 
conditions. A correction signal like the output of gate 606 (NOT RESET IN4 
HI-PRI) goes to AND gate 280 in the SNAP SHOT REGISTER logic of FIG. 9 and 
causes latch 284 to be reset. Latch 284 going to a zero causes signal 
ENABLE HI-PRI 41 and ENABLE HI-PRI 43 (not shown) to go to zero removing 
those conditions from gate 600. Thus, the deadlock condition is removed 
which causes gates 600 and 602 to go to zero and remove the deadlock 
correction signal (NOT RESET IN4 HI-PRI). Then normal operation may 
continue. Note that the type I deadlock detection and correction occurs 
completely within a single switch 10 apparatus and does not affect the 
other switches in the network in any manner or cause any change in the 
propagation of the multi-cast or broadcast operation across the network. 
The second deadlock condition, referred to as Type 2, occurs between two 
adjacent stages of a multi-stage network as illustrated in FIG. 11. One 
example of deadlock type 2 is shown which assumes that node 7 and 15 are 
trying to multi-cast simultaneously. Node 7 is multi-casting to switches 
10E, 10F, and 10G, and is successful in winning the required connections 
in switches 10F, and 10G immediately as shown by the connecting lines in 
FIG. 11. However, node 7 is unable to successfully complete the multi-cast 
connection because it can not get a connections required in switch 10E. 
Node 15 is multi-casting to switches 10E, 10G, and 10H, and is successful 
in winning the required connections in switches 10E, and 10H immediately 
as shown by the connecting lines in FIG. 11. However, node 15 is unable to 
successfully complete the multi-cast connection because it can not get a 
connections required in switch 10G. Nodes 7 and 15 have become deadlocked 
and can never resolve the problem on their own. Node 7 has a connection to 
switch 10G that it will never release until it gets a connection to switch 
10E, and node 15 has a connection to 10E that it will never release until 
it gets a connection to switch 10G. This problem is harder to solve than 
the type 1 deadlock, because it can span several or many switch chips in 
two adjacent network stages. The correction involves removing the 
inconsistent priorities that have been established in the stage 2 
switches. Unfortunately, it is difficult to detect at the stage two 
switches because each individual switch has made what it thinks is a 
consistent priority decision, and it cannot detect that deadlock has 
occurred. The problem must therefore be detected by the stage 1 switch, 
which can detect that the multi-cast operation is not progressing the way 
it should be in the following stage. After stage 1 detects the problem it 
must issue a correction signal to the stage 2 switches that will cause 
them to reprioritize and eliminate the deadlock condition. Like the type 1 
deadlock solution, the correction occurs without terminating or causing 
any change in the propagation of the multi-cast or broadcast operation 
across the network. The logic required to detect and correct type 2 
deadlock conditions is shown in FIG. 13, and by way of example it can be 
assumed to be the logic contained entirely within the first stage switch 
10D. However, the same logic is resident in every switch 10, regardless of 
the stage of the network, because for larger networks the stage 2 switches 
would be required to perform the same deadlock detection and correction 
functions in relation to the third stage switches. 
The switch 10 D uses indications it receives back from the second stage 
switches over the OUTX-ACCEPT lines to detect the possible occurrence of 
deadlock type 2 conditions. FIG. 14 shows the timing for the multi-cast 
operation from node 15 shown in FIG. 11 that has experienced a type 2 
deadlock. The timing shows that the stage 1 connections in switch 10D are 
made easily and without any contention via the commands received on the 
pulses 81. Node 15 then receives pulse 71 on the INX-ACCEPT line from 
switch 10D informing it that all 3 stage 1 connections have been 
successfully established and cannot be broken for any reason, except a 
termination of the operation commanded by node 15. Node 15 then issues the 
73 pulses to command connections to the second stage switches and pulse 75 
goes to zero in response, which is a composite of the OUTX-ACCEPT pulses 
arriving from the 4 second stage switches and going to gate 102 of. FIG. 
7. As each second stage switch makes its commanded connections it 
signifies success to the first stage switch 10D by raising it associated 
signal INX-ACCEPT signal, which is connected directly to the OUTX-ACCEPT 
signals of switch 10D. A zero on an OUTX-ACCEPT to switch 10D informs the 
first stage switch 10D that the commanded connections to be made in stage 
2 via that stage 1 output port are pending and not successfully 
established. A one on an OUTX-ACCEPT to switch 10D informs the first stage 
switch 10D that the commanded connections to be made in stage 2 via that 
stage 1 output port have been successfully established. 
Referring to FIG. 14, The OUT2-ACCEPT signal from stage 2 switch 10F stays 
at a logical one because there are no commanded connections to be made in 
switch 10F, and it therefore has completed making its commanded 
connections (none) as signified by OUT2-ACCEPT being a logical one. 
OUT3-ACCEPT completes its connection and specifies so by terminating pulse 
407. OUT4-ACCEPT is shown to be slower, but it completes its connection 
and specifies so by terminating pulse 408. OUT1-ACCEPT can not make its 
connections in switch 10E because of deadlock type 2 conditions, and 
therefore pulse 405 is driven to zero and held there to indicate the 
required connections have not been made. Switch 10D implements a time-out 
detection of the type 2 deadlock. It begins a time-out count down after at 
least one output ports reports a successful connect and at least one 
output port reports an unsuccessful attempt. 
FIG. 13 shows the typical logic used to detect the type 2 deadlock by 
monitoring the OUTX-ACCEPT lines; this logic is represented by block 546 
in FIG. 7. Each OUTX-ACCEPT line is monitored by identical sets of logic 
shown typically by gates 104, 500, 506, and 508, and latches 502 and 504 
for the purpose of monitoring OUT1-ACCEPT. 104 type gates (also shown in 
FIG. 7) enables only the monitoring of OUTX-ACCEPT signals which are 
presently involved in supporting valid connections. If there is a valid 
connection from input port 1 to output port 1, gate 1 will reproduce the 
waveform presented on OUT1-ACCEPT. When an OUTX-ACCEPT signal falls to 
indicate that a connection is pending in the following stage, latch 502 
will be set to record the first such occurrence. Latch 502 is only 
permitted to set in the high priority mode of operation as specified by 
the ENABLE HI-PRI 11 signal into gate 500, which will hold latches 502 and 
504 reset when there is no high priority operation being executed. Gate 
506 detects the rise of the OUT1-ACCEPT signal indicating that the 
commanded connections have been made in the stage 2 switch 10E connected 
to output port 1 of the first stage switch. The first occurrence of the 
fall of OUT1-ACCEPT followed by the first rise causes latch 504 to set and 
to indicate that one switch in the next stage is done with the task of 
making its commanded connections. Note that this logic only functions for 
the first pulse on the OUT1-ACCEPT signal and that latches 502 and 504 
will remain set in the normal case, so that the switch will only activate 
these latches once to detect deadlock in the very next stage. This logic 
is not active for subsequent stages of larger networks; i.e., a similar 
function in the stage 2 switch will detect type 2 deadlock conditions in 
stage 3, while the stage 1 deadlock detection logic remains dormant. 
Gate 522 detects conditions where the one of the next stage switches has 
successfully established its connections as indicated by an active NEXT 
DONE 11 signal from latch 504, and some second stage switch has not yet 
established its connections successfully. This is detected by the OR of 
signals like NOT DONE 14 coming from gate 518, which indicates that a 
connection has been commanded between input port 1 and output port 4, but 
OUT4-ACCEPT has indicated that the connection has been made. OR gate 536 
is the OR of all similar conditions to that detected by gate 522, but 
giving the status of the other output ports. Thus the output of OR gate 
536 will go active during a high priority operation, if some of the 
connections in stage 2 of the network have been made and some haven't. The 
output of OR gate going active is delayed by block 540 and then used to 
start and enable the time-out counter 538. 
Referring to FIG. 14 to relate the time-out counter to the deadlock timing 
diagram, in the example shown OUT3-ACCEPT goes away first by indicating 
successful connection to its second stage switch by the rise of pulse 407. 
At the rise of pulse 407, pulse 405 is still a zero; this meets the 
criteria that some second stage connections have been made and some are 
still pending. This detection starts the time-out counter 538 (as shown by 
pulse 409) through OR gate 536 and delay block 540. If the possible 
deadlock indication detected by gate 536 remains active for a specified 
length of time (as defined by the time-out counter), the suspicion is 
confirmed and the event is classified and detected to be a deadlock type 2 
condition. This occurs in FIG. 13 when the TIME-OUT IN1 signal goes active 
indicating that the specified time interval has elapsed. The output from 
counter 538 is gated by the appropriate high priority enable signals in 
gates 541 to 544 to direct a correction signal to the output ports that 
are involved in the multi-cast or broadcast operation. The correction 
signal is send to all the second stage switches involved in the multi-cast 
or broadcast, whether they have successfully made connections or not. The 
correction signal is a pulse like 420 send over the OUTX-REJECT lines from 
the first stage 10D switch to the second stage switches which are 
presently connected to switch 10D. Pulse 420 is driven on to the 
OUTX-REJECT lines, which are otherwise unused during high priority set-up 
time. The path from gate 541 to the OUT1-REJECT signal coming from the 
Deadlock Type 2 Logic Block 546 is shown in FIG. 7. The reject pulse 420 
to each second stage switch is received over the INx-REJECT line and 
routed to the Deadlock Type I Logic Block 548 as shown in FIG. 7. At the 
deadlock type I logic in the second stage, the INX-REJECT signals are 
NOR'ed with the deadlock type 1 cases in gates like 608. Thus, a deadlock 
type 2 indication is transmitted from the previous stage over the REJECT 
interface line connecting the two stages, and causes the second stage 
switch to reprioritize its high priority operations, just like a deadlock 
type 1 condition detected within its own switch would do. An internal 
deadlock correction signal, the output of gate 606 (NOT RESET IN4 HI-PRI) 
goes to AND gate 280 in the SNAP SHOT REGISTER logic of FIG. 9 and causes 
latch 284 to be reset. Thus, the deadlock condition is removed by 
reprioritizing the high priority operations, so that the priority will be 
consistent across the stage 2 switches. 
The size of the 420 pulse issued on the OUTX-REJECT lines is controlled by 
the logic which generates the pulse. In FIG. 13 the output of gate 541 
which generates and transmits pulse 420 is inverted by gate 550 and sent 
to AND gate 500, where it is used to reset latches 502 and 504 under the 
unusual condition of detecting a type 2 deadlock. Latch 504 being reset 
takes away the conditions from gates 522, 526, 530, and 534 which 
initially caused gate 536 to go active and enable the time-out. This 
disables the time-out counter 538 after the delay experienced by block 
540, and causes pulse 420 to terminate. Thus, the delay block time is 
controls the pulse width for pulse 420. After the deadlock correction, 
latches 502 and 504 again look for the first occurrence of the 
corresponding OUT-ACCEPT pulses and begin to check again whether the 
connections will now be made correctly in the second stage. FIG. 14 shows 
via pulses 425, 427, and 428 that now the stage 2 connections are all 
established correctly and the MESSAGE DATA can be transferred in 
multi-cast fashion. Note that the conditions are present to to cause OR 
gate 536 to go active a second time and again start the time-out counter 
538 to begin counting. However, this time the required connections are 
made before the counter 538 times out. The connections being made causes 
OR gate 536 to go to zero and to reset counter 538 before it times out. 
FIGS. 7, 9, 12, and 13 show the typical circuit implementations required 
within the dual priority switch. Further replications of these functions 
are required to totally define all input ports as they each connect to all 
output ports. However, these implementations are an obvious extension of 
the figures shown and are not shown here. 
Clearly, the inventions we have described by way of example of our 
preferred embodiments and in illustration of the best mode for practicing 
them provide a basis for much potential growth in the performance of 
switching networks for high speed data processing. Accordingly, it will be 
understood that those skilled in the art after reviewing our presently 
contemplated mode of practicing our inventions, both now and in the 
future, will envision further improvement and make enhancements and 
inventions without departing from the scope of the following claims which 
should be construed to protect and maintain the rights of the inventors in 
light of other developments.