Switching element for self-routing multistage packet-switching interconnection networks
First Claim
1. A packet-switching element for a selfrouting multistage interconnection network comprising a multiplicity of said elements in respective stages of said network and allowing broadcasting of packets forwarded through the network, each of said elements comprising:
- a plurality of element inputs (IDA, IDB) and a plurality of element outputs (UD0, UD1);
an input unit composed of the same number of sections as there are said element inputs for the respective element and having for each of said sections a respective FIFO memory (FIFA, FIFB) for packet buffering before forwarding a packet received at the respective element input toward at least one of said element outputs;
a switch (SW) having a switch control unit (SCU) between said input unit and said element outputs for establishing a connection between one of said element inputs (IDA, IDB) and at least one of said element outputs (UD0, UD1) as determined by information contained in a routing tag associated with each packet and having a first routing tag portion (TAG) and a second routing tag portion (BRD) signalling a normal nonbroadcast routing and broadcasting to different one of said network stages, respectively, and including means for solving possible routing conflicts between packets simultaneously arriving at different element inputs; and
an output unit (RU0, RU1) having as many sections as there are element outputs and each provided with a respective one of said element outputs and being connected to said switch (SW),said switch control unit (SCU) comprising;
broadcasting-request-responsive means (SCUBRD, MANET) for detecting a broadcasting request carried by a respective packet for;
evaluating a possibility of accepting a broadcast request carried by a respective packet by comparing a first parameter representing a number of destination ones of said elements to which the respective packet is to be broadcast with a second parameter representing a position of the stage to which the respective element belongs among all stages where broadcasting is requested and indicating a maximum number of outputs of said network which may be potentially seized for broadcasting of a particular message,accepting said broadcasting request if said first parameter is greater than or equal to said second parameter,generating, if said request is accepted, a signal (DEFOISA, DEFOISB) for communicating an accepted-request condition to the memory (FIFA, FIFB) storing the packet to be broadcast, and generating at least one modified routing tag for the packet to be broadcast and sending the modified routing tag over a respective one of said element outputs selected for broadcasting, the broadcasting request being processed in one of said elements in a respective one of said stages independently of the processing of other broadcasting requests in others of said elements in the same stage; and
each of said memories (FIFA, FIFB) being provided with means (CTD, CT) responsive to said signal (DEFOISA, DEFOISB) for communicating an accepted-request condition to the memory (FIFA, FIFB) storing the packet to be broadcast and generated by the switch control unit (SCU) of the switch (SW), for effecting actual broadcasting of the respective packet by a plurality of successive readings of the same packet.
1 Assignment
0 Petitions
Accused Products
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).
-
Citations
14 Claims
-
1. A packet-switching element for a selfrouting multistage interconnection network comprising a multiplicity of said elements in respective stages of said network and allowing broadcasting of packets forwarded through the network, each of said elements comprising:
-
a plurality of element inputs (IDA, IDB) and a plurality of element outputs (UD0, UD1); an input unit composed of the same number of sections as there are said element inputs for the respective element and having for each of said sections a respective FIFO memory (FIFA, FIFB) for packet buffering before forwarding a packet received at the respective element input toward at least one of said element outputs; a switch (SW) having a switch control unit (SCU) between said input unit and said element outputs for establishing a connection between one of said element inputs (IDA, IDB) and at least one of said element outputs (UD0, UD1) as determined by information contained in a routing tag associated with each packet and having a first routing tag portion (TAG) and a second routing tag portion (BRD) signalling a normal nonbroadcast routing and broadcasting to different one of said network stages, respectively, and including means for solving possible routing conflicts between packets simultaneously arriving at different element inputs; and an output unit (RU0, RU1) having as many sections as there are element outputs and each provided with a respective one of said element outputs and being connected to said switch (SW), said switch control unit (SCU) comprising;
broadcasting-request-responsive means (SCUBRD, MANET) for detecting a broadcasting request carried by a respective packet for;evaluating a possibility of accepting a broadcast request carried by a respective packet by comparing a first parameter representing a number of destination ones of said elements to which the respective packet is to be broadcast with a second parameter representing a position of the stage to which the respective element belongs among all stages where broadcasting is requested and indicating a maximum number of outputs of said network which may be potentially seized for broadcasting of a particular message, accepting said broadcasting request if said first parameter is greater than or equal to said second parameter, generating, if said request is accepted, a signal (DEFOISA, DEFOISB) for communicating an accepted-request condition to the memory (FIFA, FIFB) storing the packet to be broadcast, and generating at least one modified routing tag for the packet to be broadcast and sending the modified routing tag over a respective one of said element outputs selected for broadcasting, the broadcasting request being processed in one of said elements in a respective one of said stages independently of the processing of other broadcasting requests in others of said elements in the same stage; and each of said memories (FIFA, FIFB) being provided with means (CTD, CT) responsive to said signal (DEFOISA, DEFOISB) for communicating an accepted-request condition to the memory (FIFA, FIFB) storing the packet to be broadcast and generated by the switch control unit (SCU) of the switch (SW), for effecting actual broadcasting of the respective packet by a plurality of successive readings of the same packet. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
Specification