US 5,541,914 AGranted

Packet-switched self-routing multistage interconnection network having contention-free fanout, low-loss routing, and fanin buffering to efficiently realize arbitrarily low packet loss

OwnerAshok V. Krishnamoorthy, Fouad Kiamilevinventors

Life of this patent

Estimating the term…

Loading patent…

Abstract

A new class of packet-switched extended generalized-shuffle self-routing multistage interconnection networks provides a continuous performance-cost tradeoff between, on the one hand, the knockout switch or buffered crossbar and, on the other hand, the tandem banyan network. Multiple copies of the new networks may be serially cascaded back-to-back, and connected in parallel. A particular concentrator circuit in the network concentrates active communications packets randomly distributed on many lines onto selected lines. Another, second, network communicates synchronization information communicable point-to-point and multipoint while performing arithmetic and logical operations on the synchronization information so communicated. A hybrid parallel combination of both the first and second networks serves to efficiently communicate information point-to-point while simultaneously communicating synchronization information both point-to-point and multipoint.

Claims25

Dependent claims

An [N,M,F] multistage interconnection network where N is the number of logical input channels to the network, M is the number of output channels, and F is the fanning parameter, the multistage interconnection network comprising:

a fanout stage having N fanout modules with fanout of F.sub.o each, F.sub.o greater than one and F.sub.o less than M, each fanout module routing a packet received on a corresponding one of the N input channels to a one of its F.sub.o output channels;
log.sub.K [N/F] switching stages, log.sub.K [N/F] being an integer, with each stage having NF/K K.times.K switches, each switch of a first switching stage routing packets received on its K input lines from K of the fanout modules, and each switch of stages subsequent to the first routing packets received on its K input lines from K of the switches of the previous switching stage, to its K output lines based on log.sub.K bits of routing information contained in each packet;
and
a fanin stage having M fanin modules with fanin of F.sub.i each, F.sub.i greater than one and F.sub.i less than N, each fanin module concentrating packets received on its F.sub.i input lines from F.sub.i switches of the final switching stage into P packets output on a corresponding one of the M output channels;
wherein F is the maximum of F.sub.o and F.sub.i ;
and
wherein 2.ltoreq.F.sub.i .ltoreq.N-1.

4 more elements

An R series-replicated [N,M,F] multistage interconnection network for connecting N input channels to M output channels, the [N,M,F,R] network comprising:

a fanout stage for routing live, meaning carrying useful information to be routed, and also dead, meaning carrying no presently useful information, input packets received on N input channels according to routing information contained in each packet;
a first network switching stage for routing as is best possible all live packets received from the fanout stage towards their intended destinations while changing the code identification of packets that are unroutable due to contention to be zombie, meaning unsuccessfully-routed, packets;
a first minor fanin stage, receiving all packets from the first network switching stage, for concentrating and passing on all successfully routed live packets while ignoring dead and zombie packets;
at least one repetition of plural stages consisting of
a judgement stage, also receiving in parallel with the first minor fanin stage all packets from the first network switching stage, for re-identifying zombie packets to be live packets, for re-identifying live packets to be dead packets, and for maintaining dead packets as dead packets;
a successive next network switching stage for routing as is best possible all live packets received from the judgement stage towards their intended destinations while changing the code identification of packets that are unroutable due to contention to be zombie, meaning unsuccessfully-routed, packets;
and
a minor fanin stage associated with each successive network switching stage, receiving all packets from the associated network switching stage, for concentrating and passing on all successfully routed live packets while ignoring dead and zombie packets;
and
a major fanin stage for concentrating live packets received from all minor fanin stages onto the M output channels.

7 more elements

R series-replications of a [N,M,F] multistage interconnection network, the [N,M,F,R] network comprising:

a fanout stage
having N fanout modules with fanout of F.sub.o each, F.sub.o greater than one and F.sub.o less than M, each fanout module routing a packet received on a corresponding one of the N input channels to a one of its F.sub.o output channels
each fanout module routing an input packet received on its input channel to one of F.sub.o output lines according to log.sub.2 F.sub.o bits of routing information contained in the packet regardless of whether the packet is also code-identified either as live or as dead, meaning inactive and carrying no useful information,
wherein the fanout stage receives in total up to N packets code-identified as live, meaning carrying useful information, and receives all remaining packets code-identified as dead, and routes all packets;
R sub-networks each having
log.sub.K [N/F] switching stages, F being the maximum of F.sub.o and F.sub.i, log.sub.K [N/F] being an integer, with each stage having NF/K K.times.K switches, each switch of a first switching stage routing packets received on its K input lines from K of the fanout modules, and each switch of stages subsequent to the first routing packets received on its K input lines from K of the switches of the previous switching stage, to its K output lines based on log.sub.K bits of routing information contained in each packet,
the first switching stage of a first of the R sub-networks receiving the live and dead packets of the fanout stage,
the first switching stages of subsequent ones of the R sub-networks other than the first sub-network receiving re-identified packets of the previous sub-network,
each switching stage
for routing as is best possible all live packets to their intended destinations while changing the code identification of packets that are unroutable due to contention at the K.times.K switches to be zombie, meaning unsuccessfully-routed, packets,
for sending zombie packets to arbitrary outputs other than those used by the live packets, and
for passing dead packets to any available output,
wherein all live packets are routed, all zombie packets are sent, and all dead packets are passed,
a splitting stage, receiving all output packets from a final switching stage, for transferring all received packets to two destinations, and, in all sub-networks other than the first,
a judgement stage, receiving all packets from the splitting stage of the previous sub-network as a first destination thereof, for re-identifying zombie packets to be live packets, for re-identifying live packets to be dead packets, and for maintaining dead packets as dead packets, and for transferring all packets as the re-identified packets:
a minor fanin stage
having M minor-fanin modules with fanin of F.sub.i each, 1<F.sub.i <N, 2.ltoreq.F.sub.i .ltoreq.N-1,
receiving all packets from the splitting stage of the previous sub-network as a second destination thereof,
wherein N times F.sub.o equals M times F.sub.i,
each minor-fanin module concentrating live ones of all packets received into up to P live output packets, 0.ltoreq.P.ltoreq.F.sub.i ;
each minor-fanin module outputting F.sub.i packets of which up to P packets are live:
a major fanin stage
having M major-fanin modules with fanin of R each,
each major-fanin module receiving all F.sub.i output packets from each associated minor-fanin module of the fanin stages of all R sub-networks,
each major-fanin module concentrating live ones of the R.times.F.sub.i received packets into up to R.times.P live output packets, 0.ltoreq.R.times.P.ltoreq.N, output on a corresponding one of the M output channels.

22 more elements

A concentrator usable in a packet-switched communications network for concentrating F input packets, of which at most P packets are live meaning carrying useful information to be routed and of which (F-P) packets are dead meaning carrying no presently useful information, received on F input channels, P.ltoreq.N.ltoreq.F, to P output channels so that the P live packets as are distributed anywhere among the F input channels are distributed to an uppermost P among N output channels, the concentrator comprising:

a plurality of hierarchically-series-connected concentrating stages each of which functions to
operate on all F input packets received on F input channels
to concentrate all F packets onto P output channels so that P live ones of said packets are distributed to a upper P of N total output channels,
wherein said ordered distribution is called concentrating,
the plurality of hierarchically-series-connected concentrating stages comprising:
an integer F/2 of first-stage 2.times.2 concentrator switches each receiving packets on an associated two of the N input lines and concentrating these packets onto two output lines;
an integer F/4 of second-stage 4.times.4 concentrator switches, each of which comprises
two, an upper and a lower, 2.times.2 concentrator switches connected in parallel, for receiving, in order from uppermost to lowermost, the (i) the upper, first, output line of a first, relatively more uppermost, previous 2.times.2 concentrator switch, (ii) the upper, first, output line of a second, relatively more lowermost, previous 2.times.2 concentrator switch, (iii) the lower, second, output line of said first previous 2.times.2 concentrator switch, and (iv) the lower, second, output line of said second previous 2.times.2 concentrator switch, plus
an additional, final, 2.times.2 concentrator switch connected for concentrating packets received from the lower output line of the upper 2.times.2 concentrator switch and the upper output line of the upper 2.times.2 concentrator switch;
wherein four signal lines communicating concentrated packets from the second-stage 4.times.4 concentrator switch are ordered from uppermost to lowermost as (i) the upper, first, output line of the upper 2.times.2 concentrator switch, (ii) the upper and the lower, the first and the second, output lines of the final 2.times.2 switch, and (iii) the lower, second, output line of the lower 2.times.2 concentrator switch;
an integer F/8 of third-stage 8.times.8 concentrator switches each of which comprises
two, an upper and a lower, 4.times.4 concentrator switches connected in parallel, for receiving, in order from uppermost to lowermost, the (i) the upper, first, output line of a first, relatively more uppermost, previous 4.times.4 concentrator switch, (ii) the upper, first, output line of a second, relatively more lowermost, previous 4.times.4 concentrator switch, (iii) the second output line of said first previous 4.times.4 concentrator switch, (iv) the second output line of said second previous 4.times.4 concentrator switch, (v) the third output line of said first previous 4.times.4 concentrator switch, (vi) the third output line of said second previous 4.times.4 concentrator switch, (vii) the lower, fourth, output line of said first previous 4.times.4 concentrator switch, and (viii) the lower, fourth, output line of said second previous 4.times.4 concentrator switch, plus
two additional, final, 2.times.2 concentrator switches connected for parallel, for concentrating, in uppermost to lowermost order of their combined four input lines, packets received from (i) the third output line of the upper 4.times.4 concentrator switch, (ii) the upper, first, output line of the lower 4.times.4 concentrator switch, (iii) the lower, fourth, output line of the upper 4.times.4 concentrator switch, and, finally, (iv) the second output line of the lower 4.times.4 concentrator switch;
and further stages of identical organization until the output lines of a final-stage concentrator switch equal in number the F output channels;
wherein the P active packets as are distributed anywhere among the F input channels are distributed to uppermost P of N output channels.

12 more elements

Dependencies are inferred from the claim text.