Abstract

The switching element for self-routing multistage packet-switching interconnection networks comprises: an input unit, composed of as many sections (IMA, IMB) as the element inputs are, each section comprising a FIFO memory (FIFA, FIFB) for packet buffering; a switch (SW) associated with a control unit (SCU) which, for each packet to be forwarded, sets up the connection requested for that packet between one input and one or more outputs of the element (ECP), on the ground of a routing tag associated with each packet and comprising a first and a second portion relative to normal routing and to broadcasting in the different stages of the network (RC), and solves possible routing conflicts between packets simultaneously arriving at different inputs; and an output unit, composed of as many sections (RU0, RU1) as the element outputs are and performing the whole of the functions necessary for the correct packet forwarding towards a destination. The control unit (SCU) of the switch (SW) is arranged to handle broadcasting of a packet independently of all other elements (EDP) in the same stage, so as to allow broadcasting also to a number of destinations different from a power of 2 (for an element with two inputs and two outputs) and cooperates with the memory (FIF) storing the packet to be broadcast in such a way that broadcasting does not give rise to internal blocking in the network (RC). Said control unit (SCU) moreover solves routing conflicts so as to set an upper bound to packet permanence time within the network (FIG. 2).

Other References

• H. J. Siegel et al., article "The Multistage Cube: A Versatile Interconnection Network", IEEE Computer, Dec. 1981, pp. 65-76
• Carver Mead et al., Introduction to VLSI Systems, (Addison-Wesley Publishing Co.), pp. 78,79; 157,158
• F. F. Sellers Jr. et al., Error Detecting Logic for Digital Computers, (McGraw-Hill Book Company), p. 25