Efficient single-hop interconnection network employing merged shared directional multichannels

• US 5,278,927 A
• Filed: 05/26/1992
• Issued: 01/11/1994
• Est. Priority Date: 05/26/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Birk, Yitzhak
• Primary Examiner(s): Ullah, Akm E.
• Application Number:
  US07/888,575
• Time in Patent Office: 595 Days
• Field of Search: 385/24, 385/46, 385/39, 385/42, 359/115, 359/118, 359/127, 359/138, 359/139, 359/143
• US Class Current: 385/46
• CPC Class Codes: H04Q 11/0001 using optical switching

Abstract

A system for the scheduled transmission of signals from source stations to destination stations in a passive, static, Single-Hop Interconnection (SHI) employing a plurality of Shared Directional Multichannels (SDMs) in a power-efficient and cost-effective manner. The system provides a practical implementation of any SHI built from a plurality of smaller SDMs whose salient feature is a significant degree of parallelism at low hardware cost while retaining the simplicity and reliability of a passive interconnection. The system is a scheme for wiring a SHI to retain the useful features of a SDM design for connecting (m) Source Stations each having (a) outputs to (n) Destination Stations each having one input such that, for m=n, the power split losses are reduced to a provably optimal value of (2n/a) and component count reduced to anlog₂ (n/a), which is optimal for the optimal power split constraint. A SHI for any number of source and destination stations with any input and output count can be optimally constructed by the method of this invention. The passive efficient SHI of this invention outperforms the conventional passive bus-oriented SHI in channel concurrency with fewer components.

Claims

1. A method for interconnecting m₁ groups of m₂ first Source Stations (SSs) each said first SS having at least a₁ groups of a₂ outputs for transmitting message signals to n² groups of n₁ first Destination Stations (DSs) each said first DS having at least b₂ groups of b₁ inputs for receiving said message signals, such that each said first SS is uniquely connected to every said first DS by a single-hop directional connection whereby up to k₃ concurrent non-interfering message signal transmissions can be scheduled from said m₂ *m₁ =m₃ first SSs to said n₂ *n₁ =n₃ first DSs, wherein k₃ =k₁ *k₂, n_i >

k_i and m_i >

k_i, and wherein k_i, m_i, n_i, a_i and b_i are positive non-zero integers for i=1, 2 or 3, said method comprising the steps of;

(a) composing said interconnection of said first SSs and said first DSs by performing the steps of

(a.1) abutting a first plurality of first Shared Directional Multichannels (SDMs) to a second plurality of second SDMs, each said first SDM having a first plurality of coupling stages each having one or more couplers, said each first SDM having capacity for scheduled uniform message signal traffic of up to k₁ concurrent signals from m₁ second SSs, each said second SS having at least a₁ outputs for transmitting said signals to n₁ second DSs, each said second DS having at least b₁ inputs for receiving said signals, each said second SDM having a second plurality of coupling stages each having one or more couplers, said each second SDM having capacity for scheduled uniform message signal traffic of up to k₂ concurrent signals from m₂ third SSs, each said third SS having at least a₂ outputs for transmitting said signals to n₂ third DSs, each said third DS having at least b₂ inputs for receiving said signals, wherein said first plurality of first SDMs is at least (n₂ *b₂) in number and said second plurality of second SDMs is at least (m₁ *a₁) in number,

(a.2) assigning a second SDM index to every said second SDM in said second plurality according to the concatenation (s₁, t₁) of an index s₁ ≦

m₁ for one said first SS group and an index t₁ ≦

a₁ for one said first SS output group, where s₁ and t₁ are positive non-zero integers and said second SDM index is the concatenation (s₁,t₁),

(a.3) assigning a second output index to every output of each said second SDM having said second SDM index (s₁, t₁) according to the concatenation (d₂, r₂) of an index d₂ <

n₂ for one said third DS and an index r₂ <

b₂ for one said third DS input, where d₂ and r₂ are positive non-zero integers and said second output index is the concatenation (s₁, t₁, d₂, r₂),

(a.4) assigning a first SDM index to every said first SDM in said first plurality according to the concatenation (d₂, r₂) of an index d₂ ≦

n₂ for one said first DS group and an index r₂ ≦

b₂ for one said first DS input group, where d₂ and r₂ are positive non-zero integers and said first SDM index is the concatenation (d₂,r₂),

(a.5) assigning a first input index to every input of each first SDM having said first SDM index (d₂, r₂) according to the concatenation (s₁, t₁) of an index s₁ ≦

m₁ for one said second SS and an index t₁ ≦

a₁ for one said second SS output, where s₁ and t₁ are positive non-zero integers and said first input index is the concatenation (s₁, t₁, d₂, d₂), and

(a.6) connecting each said output from said second plurality of second SDMs having a second output index (s₁,t₁,d₂,r₂) to all said inputs of said first plurality of first SDMs having said first input index (s₁, t₁, d₂, r₂).

2. The method of claim 1 further comprising the steps of:

(b) replacing said first and said second pluralities of coupling stages with fewer coupling stages each having one or more new couplers; and

(c) connecting the inputs and outputs of said new couplers such that each said first SS is connected to every said first DS in accordance with the connections made in said composing step (a), thereby compacting said interconnection of said first SSs and said first DSs to reduce spreading loss and component count.

3. The method of claim 2 further comprising the step of:

(d) connecting said second SDM inputs to said first SS outputs such that said second SDM index (s₁, t₁) is identical to the concatenation of the index s₁ ≦

m₁ for the corresponding said first SS group number and the index t₁ ≦

a₁ for the corresponding said first SS output group number.

4. The method of claim 3 further comprising the step of:

(e) connecting said first SDM outputs to said first DS inputs such that said first SDM index (d₂, r₂) is identical to the concatenation of the index d₂ ≦

n₂ for the corresponding said first DS group number and the index r₂ ≦

b₂ for the corresponding said first DS input group number.

5. The method of claim 4 wherein:

said second SDM has no excess cumulative fan-out and said first SDM has no excess cumulative fan-in.

6. The method of claim 2 wherein a₁ =b₂ =2 and b₁ =a₂ =1.

7. The method of claim 1 wherein:

said first, second and third pluralities of coupling stages include optical star couplers; and

said interconnection includes means for conducting optical signals.

8. The method in claim 7 wherein:

said optical star couplers include a plurality of smaller optical star couplers interconnected to form larger optical star couplers.

9. The method of claim 1 further comprising the step of:

(d) connecting said second SDM inputs to said first SS outputs such that said second SDM index (s₁, t₁) is identical to the concatenation of the index s₁ ≦

m₁ for the corresponding said first SS group number and the index t₁ ≦

a₁ for the corresponding said first SS output group number.

10. The method of claim 1 further comprising the step of:

(e) connecting said first SDM outputs to said first DS inputs such that said first SDM index (d₂, r₂) is identical to the concatenation of the index d₂ ≦

n₂ for the corresponding said first DS group number and the index r₂ ≦

b₂ for the corresponding said first DS input group number.

11. The method of claim 1 wherein:

said second SDM has no excess cumulative fan-out and said first SDM has no excess cumulative fan-in.

12. A method for reducing the power spreading loss in a passive interconnection of m₁ groups of m₂ first SSs, each said first SS having at least a₁ groups of a₂ outputs for transmitting up to k₃ concurrent non-interfering message signals to n₂ groups of n₁ first DSs, each said first DS having at least b₂ groups of b₁ inputs for receiving said message signals, said passive interconnection having a first plurality of first SDMs and a second plurality of second SDMs, each said first SDM having c₁ coupling stages and a uniform scheduled concurrent non-interfering message signal capacity of k₁, each said second SDM having c₂ coupling stages and a uniform scheduled concurrent non-interfering message signal capacity of k₂, each said coupling stage having one or more couplers, where k₃ =k₁ *k₂ and k₁, k₂, c₁ and c₂ are all positive non-zero integers, said method comprising the steps of:

(a) replacing said (c₁ +c₂) coupling stages with c₃ ≦

(c₁ +c₂) new coupling stages, each said new coupling stage having a plurality of substantially balanced couplers; and

(b) connecting the inputs and outputs of said new coupling stages such that each said first SS is connected to every said first DS in accordance with the connections made by said passive interconnection, thereby compacting said passive interconnection of said first SSs and said first DSs to reduce power spreading loss and component count.

13. The method of claim 12 wherein said replacing step (a) comprises the steps of:

increasing the out-degree of each said coupler in a first said coupling stage by a first factor;

decreasing the out-degree of each said coupler in a second said coupling stage by said first factor; and

increasing the number of said couplers in said second coupling stage, where said second coupling stage is disposed on the output side of said first coupling stage.

14. The method of claim 13 wherein said replacing step (a) comprises the steps of:

decreasing the in-degree of each said coupler in a third said coupling stage by a second factor;

increasing the in-degree of each said coupler in a fourth said coupling stage by said second factor; and

increasing the number of said couplers in said third coupling stage, where said third coupling stage is disposed on the input side of said fourth coupling stage.

15. The method of claim 12 wherein said replacing step (a) comprises the steps of:

decreasing the in-degree of each said coupler in a first said coupling stage by a first factor;

increasing the in-degree of each said coupler in a second said coupling stage by said first factor; and

increasing the number of said couplers in said first coupling stage, where said first coupling stage is disposed on the input side of said second coupling stage.

16. The method of claim 12 wherein:

said (c₁ +c₂) coupling stages include optical star couplers; and

said passive interconnection includes means for conducting optical signals.

17. The method of claim 12 wherein said replacing step (a) further comprises the step of:

replacing a pair of two adjacent said coupling stages with a single coupling stage, where each said coupler in one said adjacent coupling stage is connected to no more than one said coupler in the other said adjacent coupling stage.

18. A shared directional multichannel system for scheduled uniformed message signal traffic of up to (k) concurrent non-interfering message signal transmissions, wherein k, m, n, a, b and c are positive non-zero integers, c= log_a n , and m≧

k≧

(c choose (a-1))=c!/(a-1)!/(c-a+1)!, said system comprising;

a first plurality of source stations (SSs), each said SS including a second plurality (a) of transmitter outputs, wherein said first plurality is less than or equal to (m);

a third plurality (n) of destination stations (DSs), each said DS including a fourth plurality (b) of receiver inputs; and

interconnection means for passively coupling signals from each said SS to every said DS such that the power received at each said receiver input is greater than a/n² times the power transmitted from said transmitter outputs connected to said each receiver input.

19. The shared directional multichannel system of claim 18 wherein:

said power received at said each receiver input is greater than (a/n/log_a n) times the power transmitted from said transmitter outputs connected to said each receiver input.

20. The shared directional multichannel system of claim 19 wherein said interconnection means comprises:

a plurality of optical star couplers disposed to transfer optical signal transmissions forming said scheduled uniform message signal traffic.

21. The shared directional multichannel system of claim 18 wherein said interconnection means comprises:

a plurality of optical star couplers disposed to transfer optical signal transmissions forming said scheduled uniform message signal traffic.

22. A method for reducing the power spreading loss in a passive interconnection of m₁ groups of m₂ first SSs, each said first SS having at least a₁ groups of a₂ outputs for transmitting up to k₃ concurrent non-interfering message signals to n₂ groups of n₁ first DSs, each said first DS having at least b₂ groups of b₁ inputs for receiving said message signals, said passive interconnection having a first plurality of first SDMs and a second plurality of second SDMs, each said first SDM having c₁ coupling stages and a uniform scheduled concurrent non-interfering message signal capacity of k₁, each said second SDM having c₂ coupling stages and a uniform scheduled concurrent non-interfering message signal capacity of k₂, each said coupling stage having one or more couplers, where k₃ =k₁ *k₂ and k₁, k₂, c₁ and c₂ are all positive non-zero integers, said method comprising the steps of:

(a) evaluating the coupler fan-in and fan-out within each of said (c₁ +c₂) coupling stages to determine where said coupler fan-in and fan-out must be changed to make said coupler fan-in substantially equal to said coupler fan-out in said each coupling stage;

(b) responsive to the results of said evaluating step, performing at least one of the following (b.1), (b.2) or (b.3) replacing steps of;

(b.1) replacing one or more said coupling stages with one or more first new coupling stages, said first new coupling stages each having a plurality of first new couplers specified in accordance with the steps of

(b.1.1) increasing the out-degree of each said coupler in a first said coupling stage by a first factor,

(b.1.2) decreasing the out-degree of each said coupler in a second said coupling stage by said first factor, and

(b.1.3) increasing the number of said couplers in said second coupling stage, where said second coupling stage is disposed on the output side of said first coupling stage,

(b.2) replacing one or more said coupling stages with one or more second new coupling stages, said second new coupling stages each having a plurality of second new couplers specified in accordance with the steps of

(b.2.1) decreasing the in-degree of each said coupler in a third said coupling stage by a second factor

(b.2.2) increasing the in-degree of each said coupler in a fourth said coupling stage by said second factor, and

(b.2.3) increasing the number of said couplers in said third coupling stage, where said third coupling stage is disposed on the input side of said fourth coupling stage, and

(b.3) replacing a pair of two adjacent said coupling stages with a single coupling stage having a plurality of couplers with in-degree and out-degree specified in accordance with the coupler in-degree for one said adjacent coupling stage and the coupler out-degree for the other said adjacent coupling stage, where each said coupler in said one adjacent coupling stage is connected to no more than one said coupler in said other adjacent coupling stage; and

(c) repeating said evaluating step (a) and said replacing step (b) successively until said coupler in-degree and out-degree are substantially balanced in each remaining said coupling stage.

23. A method for reducing the power spreading loss in a passive interconnection for transmitting a plurality of concurrent non-interfering message signals from a set of Source Stations (SSs) to a set of Destination Stations (DSs), said passive interconnection having a first plurality of coupling stages each having one or more couplers, each said coupler having one or more inputs and one or more outputs, wherein said coupler inputs of the i^th said coupling stage are connected passively to said coupler outputs of the (i-1)th said coupling stage and said coupler outputs of said i^th coupling stage are connected passively to said coupler inputs of the (i+1)th said coupling stage, where i<

j are non-zero positive integers less than or equal to said first plurality, said method comprising the steps of;

(a) replacing said first plurality of coupling stages with a second plurality of new coupling stages, said second plurality being less than or equal to said first plurality, each said new coupling stage having a plurality of substantially balanced couplers; and

(b) connecting said inputs and said outputs of each said new coupling stage such that said set of SSs is interconnected with said set of DSs in accordance with said passive interconnection, thereby compacting said passive interconnection of said set of SSs and said set of DSs to reduce power spreading loss and component count.

24. The method of claim 23 wherein said replacing step (a) comprises the steps of:

increasing the out-degree of each said coupler in said i^th coupling stage by a first factor;

decreasing the out-degree of each said coupler in said j^th coupling stage by said first factor; and

increasing the number of said couplers in said j^th coupling stage.

25. The method of claim 24 wherein said replacing step (a) comprises the steps of:

decreasing the in-degree of each said coupler in said i^th coupling stage by a second factor;

increasing the in-degree of each said coupler in said j^th coupling stage by said second factor; and

increasing the number of said couplers in said i^th coupling stage.

26. The method of claim 23 wherein said replacing step (a) comprises the steps of:

decreasing the in-degree of each said coupler in said i^th coupling stage by a first factor;

increasing the in-degree of each said coupler in said j^th coupling stage by said first factor; and

increasing the number of said couplers in said i^th coupling stage.

27. The method of claim 23 wherein:

said plurality of coupling stages includes optical star couplers; and

said passive interconnection includes means for conducting optical signals.

28. The method of claim 23 wherein said replacing step (a) further comprises the step of:

replacing a pair of two adjacent said coupling stages with a single coupling stage, where each said coupler in one said adjacent coupling stage is connected to no more than one said coupler in the other said adjacent coupling stage.

29. A method for reducing the power spreading loss in a passive interconnection for transmitting a plurality of concurrent non-interfering message signals from a set of Source Stations (SSs) to a set of Destination Stations (DSs), said passive interconnection having a first plurality of coupling stages each having one or more couplers, each said coupler having one or more inputs and one or more outputs, wherein said coupler inputs of the i^th said coupling stage are connected passively to said coupler

outputs of the (i-1)th said coupling stage and said coupler outputs of said i^th coupling stage are connected passively to said coupler inputs of the (i+1)th said coupling stage, where i<

j are non-zero positive integers less than or equal to said first plurality, said method comprising the steps of;

(a) evaluating the coupler fan-in and fan-out within each of said first plurality of coupling stages to determine where said coupler fan-in and fan-out must be changed to make said coupler fan-in substantially equal to said coupler fan-out in said each coupling stage;

(b) responsive to the results of said evaluating step, performing at least one of the following (b.1), (b.2) or (b.3) replacing steps of;

(b.1) replacing one or more said coupling stages with one or more first new coupling stages, said first new coupling stages each having a plurality of first new couplers specified in accordance with the steps of

(b.1.1) increasing the out-degree of each said coupler in said i^th coupling stage by a first factor,

(b.1.2) decreasing the out-degree of each said coupler in said j^th coupling stage by said first factor, and

(b.1.3) increasing the number of said couplers in said j^th coupling stage,

(b.2) replacing one or more said coupling stages with one or more second new coupling stages, said second new coupling stages each having a plurality of second new couplers specified in accordance with the steps of

(b.2.1) decreasing the in-degree of each said coupler in said i^th coupling stage by a second factor

(b.2.2) increasing the in-degree of each said coupler in said j^th coupling stage by said second factor, and

(b.2.3) increasing the number of said couplers in said i^th coupling stage, and

(b.3) replacing a pair of two adjacent said coupling stages with a single coupling stage having a plurality of couplers with in-degree and out-degree specified in accordance with the coupler in-degree for one said adjacent coupling stage and the coupler out-degree for the other said adjacent coupling stage, where each said coupler in said one adjacent coupling stage is connected to no more than one said coupler in said other adjacent coupling stage; and

(c) repeating said evaluating step (a) and said replacing step (b) successively until said coupler in-degree and out-degree are substantially balanced in each remaining said coupling stage.

30. A method for reducing the number of switching elements in a switched interconnection for transmitting a plurality of non-interfering message signals from a set of Source Stations (SSs) to a set of Destination Stations (DSs), said switched interconnection having a first plurality of switching stages each having one or more switches, each said switch having one or more inputs and one or more outputs, wherein the inputs of the i^th said switching stage are connected passively to the outputs of (i-1)th said switching stage and the outputs of said i^th switching stage are connected passively to the inputs of the (i+1)th said switching stage, where i<

j are non-zero positive integers less than or equal to said first plurality, said method comprising the steps of;

(a) replacing said first plurality of switching stages with a second plurality of new switching stages, said second plurality being less than or equal to said first plurality, each said new switching stage having a plurality of substantially balanced switches; and

(b) connecting said inputs and said outputs of each said new switching stage such that said set of SSs is interconnected with said set of DSs in accordance with said passive interconnection, thereby compacting said passive interconnection of said set of SSs and said set of DSs to reduce component count.

31. The method of claim 30 wherein said replacing step (a) comprises the steps of:

increasing the out-degree of each said switch in said i^th switching stage by first factor;

decreasing the out-degree of each said switch in said j^th switching stage by said first factor;

increasing the number of said switches in said j^th switching stage.

32. The method of claim 31 wherein said replacing step (a) comprises the steps of:

decreasing the in-degree of each said switch in said i^th switching stage by a second factor;

increasing the in-degree of each said switch in said j^th switching stage by said second factor; and

increasing the number of said switches in said i^th switching stage.

33. The method of claim 30 wherein said replacing step (a) comprises the steps of:

decreasing the in-degree of each said switch in said i^th switching stage by a first factor;

increasing the in-degree of each said switch in said j^th switching stage by said first factor; and

increasing the number of said switches in said i^th switching stage.

34. The method of claim 30 wherein:

said plurality of switching stages includes optical switches; and

said passive interconnection includes means for conducting optical signals.

35. The method of claim 30 wherein said replacing step (a) further comprises the step of:

replacing a pair of two adjacent said switching stages with a single switching stage, where each said switch in one said adjacent switching stage is connected to no more than one said switch in the other said adjacent switching stage.

36. A method for reducing the number of switching elements in a switched interconnection for transmitting a plurality of non-interfering message signals from a set of Source Stations (SSs) to a set of Destination Stations (DSs), said switched interconnection having a first plurality of switching stages each having one or more switches, each said switch having one or more inputs and one or more outputs, wherein the inputs of the i^th said switching stage are connected passively to the outputs of (i-1)th said switching stage and the outputs of said i^th switching stage are connected passively to the inputs of the (i+1)th said switching stage, where i<

j are non-zero positive integers less than or equal to said first plurality, said method comprising the steps of;

(a) evaluating the switch fan-in and fan-out within each said switching stage to determine which of said switch fan-in and fan-out must be increased to make said switch fan-in substantially equal to said switch fan-out for said each switching stage;

(b) responsive to the results of said evaluating step, performing at least one of the following (b.1), (b.2) or (b.3) replacing steps of;

(b.1) replacing one or more said switching stages with one or more first new switching stages, said first new switching stages each having a plurality of switches specified in accordance with the steps of

(b.1.1) increasing the out-degree of each said switch in said i^th switching stage by a first factor,

(b.1.2) decreasing the out-degree of each said switch in said j^th switching stage by said first factor, and

(b.1.3) increasing the number of said switches in said j^th switching stage,

(b.2) replacing one or more said switching stages with one or more second new switching stages, said second new switching stages each having a plurality of switches specified in accordance with the steps of

(b.2.1) decreasing the in-degree of each said switch in said i^th switching stage by a second factor,

(b.2.2) increasing the in-degree of each said switch in said j^th switching stage by said second factor, and

(b.2.3) increasing the number of said switches in said i^th switching stage, and

(b.3) replacing a pair of two adjacent said switching stages with a single switching stage having a plurality of switches with in-degree and out-degree specified in accordance with the switch in-degree for one said adjacent switching stage and the switch out-degree for the other said adjacent switching stage, where each said switch in said one adjacent switching stage is connected to no more than one said switch in said other adjacent switching stage; and

(c) repeating said evaluating step (a) and said replacing step (b) successively until said switch in-degree and out-degree are substantially balanced in each remaining said switching stage.