US 2010/0135286 A1 · 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 includes an input stage having N/d switches with each of them having d inlet links and 2×d outgoing links connecting to second stage switches, an output stage having N/d switches with each of them having d outlet links and 2×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 2 × 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 the same multi-stage network is operated in rearrangeably nonblocking manner for arbitrary fan-out multicast and each multicast connection is set up by use of at most two outgoing links from the input stage switch. A multi-stage network comprising (2×logd N)−1 stages is operated in strictly nonblocking manner for multicast includes an input stage having N/d switches with each of them having d inlet links and 3×d outgoing links connecting to second stage switches, an output stage having N/d switches with each of them having d outlet links and 3×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 3 × 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.

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

N1 inlet links and N2 outlet links, 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
;
and
an input stage comprising
N
1
d
input switches, and 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 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 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
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
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 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, d1=d and
d
1
=
N
1
×
d
N
2
=
p
×
d
and
an input stage comprising
N
2
d
input switches, and each input switch comprising d1 inlet links and 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 each output switch comprising d outlet links and 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
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 each middle switch further comprising d outgoing links (hereinafter “outgoing middle links”) connecting to switches in its immediate succeeding stage;
and
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 each middle switch further comprising d outgoing links (hereinafter “outgoing middle links”) connecting to switches in its immediate succeeding stage;
and
wherein 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

Facts

Application

12/530,207Filed 6 Mar 2008

Priority

6 Mar 2007

Published

3 Jun 2010

Term ends

Not estimatedThe source records don’t support an estimate.

Classification7 codes

H04Q 3/68
Distributing or queueing: grouping or interlacing selector groups or stages
H04Q 2213/1302
Indexing scheme relating to selecting arrangements in general and for multiplex systems: relay switches
H04Q 2213/1304
Indexing scheme relating to selecting arrangements in general and for multiplex systems: coordinate switches, crossbar, 4/2 with relays, coupling…
H04Q 2213/13242
Indexing scheme relating to selecting arrangements in general and for multiplex systems: broadcast, diffusion, multicast, point-to-multipoint

Fully connected generalized multi-stage networks

Life of this patent

Fully connected generalized multi-stage networks

Life of this patent

Abstract

Claims21