×

Switching element for self-routing multistage packet-switching interconnection networks

  • US 4,890,281 A
  • Filed: 11/06/1987
  • Issued: 12/26/1989
  • Est. Priority Date: 11/18/1986
  • Status: Expired due to Fees
First Claim
Patent Images

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 all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×