Self-routing permutation networks based on de Bruijn digraphs
AssigneeColorado Seminary
InventorsAzman Samsudin, Kyungsook Y. Lee
Life of this patent
Estimating the term…
Abstract
Permutation networks based on de Bruijn digraphs exhibit constant control complexity (wide sense non-blocking) and constant control complexity (self-routing). The cost in terms of the cross-points used for such networks is an optimal O(N log N). This non-blocking network uses fast algorithms to control in the Terabit bandwidth while providing for cost-effective switching. The network has expandable (i.e., scalable) architecture, i.e., the network can be built by interconnecting smaller non-blocking networks (e.g., small crossbars).
Claims19
A network stage comprising:
- a first number of cross-bar switches,
- a second number of a group of switches, each group of switches providing an input to the network stage,
- a third number of multiplexers, each multiplexer providing an output for the network stage,
- said cross-bar switches, said switches, and said multiplexers interconnected as an (N×N) one dimensional de Bruijn permutation network single stage network, wherein N=(d2)2 of a d-ary number system and wherein each crossbar switch has d inputs, and wherein the first number, the second number, and the third number equal d2.
A scalable permutation network comprising:
- a plurality of (N×N) 1D-de Bruijn permutation network elements, where N=(d2)2, and nD=the number n of dimensions D of a d-ary number system, each of said plurality of de Bruijn permutation network elements having a cross-bar switch and an associated set of routing switches, each of said plurality of cross-bar switches having directed edge outputs connected to sets of routing switches of other de Bruijn permutation elements and having directed edge inputs from the sets of routing switches of other de Bruijn permutation elements, one of said directed edge inputs coming from one of the routing switches in said associated set of switches.
A pipeline network comprising:
- a first stage of demultiplexers, each said demultiplexer having one input and d outputs,
- a second stage of crossbar switches, each crossbar switch having d inputs and d outputs,
- a third stage of multiplexers, each said multiplexer having d inputs and one output, said demultiplexers, crossbar switches, and multiplexers interconnected as a pipelined single dimension de Bruijn permutation network of a d-ary number system,
- said first, second, and third stages each having d data packets.
A pipelined network comprising:
- a first stage having a set number of demultiplexers,
- a second stage having the set number of crossbar switches,
- a third stage having the set number of multiplexers,
- said set number of demultiplexers, crossbar switches, and multiplexers connected as a pipelined nD-dBPN(d) de Bruijn permutation network where nD=the number of dimensions of a d-ary number system so that the set number of data packets occupy each of said first, second, and third stages at any given time.
A network comprising:
- an array of single dimension networks, each single dimension network having cross-point switches interconnected as an (N×N) nD−de Bruijn permutation network, where N=d2 and nD=the number dimensions of a d-ary number system, each single dimension network having inputs and outputs,
- data packets, said data packets at the outputs from a lower dimension network self-route synchronously during a single network cycle to inputs of the next higher dimension network.
A network comprising:
- a plurality of row de Bruijn permutation networks,
- a plurality of column Banyan networks, each output of each column of said plurality of Banyan networks connected to input one of each of the plurality of row de Bruijn permutation networks.
Dependencies are inferred from the claim text.