US 8,270,400 B2 · Fully connected generalized multi-stage networks

Abstract

A multi-stage network comprising (2×logd N)−1 stages is operated in strictly nonblocking manner for unicast, also in rearrangeably nonblocking manner for arbitrary fan-out multicast when s≧2 , and is operated in strictly nonblocking manner for arbitrary fan-out multicast when s≧3 , includes an input stage having N d switches with each of them having d inlet links and s×d outgoing links connecting to second stage switches, an output stage having N d switches with each of them having d outlet links and s×d incoming links connecting from switches in the penultimate stage. The network also has (2×logd N)−3 middle stages with each middle stage having s × N d switches, and each switch in the middle stage has d incoming links connecting from the switches in its immediate preceding stage, and d outgoing links connecting to the switches in its immediate succeeding stage. Also each multicast connection is set up by use of at most two outgoing links from the input stage switch.

A network having a plurality of multicast connections, said network comprising:

N1 inlet links and N2 outlet links, where N1>1, N2>1 and
when N2>N1 and N2=p*N1 where p>1 then N1=N, d1=d, and
d
2
=
N
2
×
d
N
1
=
p
×
d
;
where N>1, d1>1, d2>1, d>1 and
an input stage comprising
N
1
d
input switches, and said each input switch comprising d inlet links and each said input switch further comprising x×d outgoing links connecting to switches in a second stage where x>0;
and
an output stage comprising
N
1
d
output switches, and said each output switch comprising d2 outlet links and each said output switch further comprising
x
×
(
d
+
d
2
)
2
incoming links connecting from switches in a penultimate stage;
and
a plurality of y middle stages comprising
x
×
N
d
middle switches in each of said y middle stages wherein said second stage and said penultimate stage are one of said middle stages where y>3, and
said each middle switch in all said middle stages excepting said penultimate stage comprising d incoming links (hereinafter “incoming middle links”) connecting from switches in its immediate preceding stage, and each middle switch further comprising d outgoing links (hereinafter “outgoing middle links”) connecting to switches in its immediate succeeding stage;
and
said each middle switch in said penultimate stage comprising d incoming links (hereinafter “incoming middle links”) connecting from switches in its immediate preceding stage, and each middle switch in said penultimate stage further comprising
(
d
+
d
2
)
2
outgoing links (hereinafter “outgoing middle links”) connecting to switches in its immediate succeeding stage;
or
when N1>N2 and N1=p*N2 where p>1 then N2=N, d2=d and
d
1
=
N
1
×
d
N
2
=
p
×
d
and
an input stage comprising
N
2
d
input switches, and said each input switch comprising d1 inlet links and said each input switch further comprising
x
×
(
d
+
d
1
)
2
outgoing links connecting to switches in a second stage where x>0;
and
an output stage comprising
N
2
d
output switches, and said each output switch comprising d outlet links and said each output switch further comprising x×d incoming links connecting from switches in the penultimate stage;
and
a plurality of y middle stages comprising
x
×
N
d
middle switches in each of said y middle stages wherein said second stage and said penultimate stage are one of said middle stages where y>3, and
said each middle switch in said second stage comprising
(
d
+
d
1
)
2
incoming links (hereinafter “incoming middle links”) connecting from switches in its immediate preceding stage, and said each middle switch further comprising d outgoing links (hereinafter “outgoing middle links”) connecting to switches in its immediate succeeding stage;
and
said each middle switch in all said middle stages excepting said second stage comprising d incoming links (hereinafter “incoming middle links”) connecting from switches in its immediate preceding stage, and said each middle switch further comprising d outgoing links (hereinafter “outgoing middle links”) connecting to switches in its immediate succeeding stage;
and
wherein said each multicast connection from an inlet link passes through at most two outgoing links in input switch, and said multicast connection further passes through a plurality of outgoing links in a plurality switches in each said middle stage and in said output stage.

110 more elements

Fully connected generalized multi-stage networks

Life of this patent

Fully connected generalized multi-stage networks

Life of this patent

Abstract

Claims21