Multi-dimensional lattice network

• US 7,684,389 B2
• Filed: 10/20/2004
• Issued: 03/23/2010
• Est. Priority Date: 07/24/2000
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Beshai, Maged E.
• Primary Examiner(s): Moore, Ian N
• Application Number:
  US10/969,748
• Publication Number:
  US 20050068946A1
• Time in Patent Office: 1,980 Days
• Field of Search: 370/254, 370/255, 370352-359, 370387-389, 370/360, 370/361, 370/395.1, 370/395.32, 370/395.52, 370/400, 385/17, 398 41- 58, 712 11- 15, 709238-244
• US Class Current: 370/387
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus

Abstract

An N-dimensional lattice network that scales to capacities of the order of a Yotta bits per second (10²⁴ bits per second) includes a plurality of sub-nets of edge module switches interconnected by an agile switching core. The agile core may be distributed. In the N-dimensional lattice network, each edge module 408 is connected to N core stages, each core stage having an associated dimensional indicator. The input/output ports of each edge module are divided into (N+1) port groups. One of the port groups serves local sources/sinks while the remaining port groups are respectively connected to core stages in each of the N dimensions. This structure permits virtually unlimited capacity growth and significantly simplifies the routing and forwarding functions. The edge modules are addressed using logical coordinates, one coordinate being assigned for each of the N dimensions. This simplifies routing and permits each edge module to compute its own routing tables.

Claims

1. A lattice network comprising:

a plurality of edge modules arranged into;

a group of non-intersecting primary sub-nets, each primary subnet having a first number of edge modules;

a group of non-intersecting secondary sub-nets, each secondary sub-net having a second number of edge modules; and

a group of non-intersecting ternary sub-nets, each ternary-subnet having a third number of edge modules;

and

a plurality of core modules arranged into;

a group of primary core stages, each primary core stage exclusively assigned to a respective primary sub-net and having a number of primary core modules, each said primary core module connecting to each edge module of said respective primary sub-net;

a group of secondary core stages, each secondary core stage exclusively assigned to a respective secondary sub-net and having a number of secondary core modules, each said secondary core module connecting to each edge module of said respective secondary sub-net; and

a group of ternary core stages, each ternary core stage exclusively assigned to a respective ternary sub-net and having a number of ternary core modules, each said ternary core module connecting to each edge module of said respective ternary sub-net;

wherein each edge module belongs to only one of said primary sub-nets, only one of said secondary sub-nets, and only one of said ternary sub-nets.

2. The lattice network of claim 1 wherein each of said first number of edge modules, said second number of edge modules, and said third number of edge modules is within the range of 8 to 256.

3. The lattice network of claim 1 wherein a target capacity C, expressed in bits per second, is realized by selecting said first number of edge modules, said second number of edge modules, and said third number of edge modules, denoted Q₁, Q₂, and Q₃, respectively, so that:

C=R×

m₀×

(Q₁×

Q₂×

Q₃),

m₀ being a number of dual links per edge module where a dual link comprises an input link and an output link, and R being a capacity, in bits per second, of each of said links.

4. The lattice network of claim 1 wherein at least one core stage comprises at least one data packet switch.

5. The lattice network of claim 1 wherein the core stage of at least one of said sub-nets comprises at least one cross connector.

6. The lattice network of claim 1 wherein the core stage of at least one of said sub-nets comprises a plurality of core switch modules.

7. The lattice network of claim 6 wherein said core switch modules are geographically distributed.

8. The lattice network of claim 6 wherein at least one of said core switch modules is a time-division-multiplexed space switch.

9. The lattice network of claim 6 wherein at least one of said core switch modules is an optical switch.

10. A network comprising:

a plurality of core modules arranged into core stages, each core stage comprising a number of core modules;

a plurality of edge modules arranged into a plurality of sub-nets, each sub-net having an integer number, Q, of edge modules, the sub-nets having a one-to-one correspondence to the core stages so that each sub-net is coupled to a corresponding core stage, and all edge modules of a sub-net coupled to a given core stage are interconnected through each core module of the given core stage;

wherein any two sub-nets from among the plurality of sub-nets have at most one edge module in common;

wherein each edge module of the plurality of edge modules is common in a predefined number, N, of corresponding sub-nets from among the plurality of sub-nets;

wherein the predefined number, N, is specific to the network and is selected to be an integer between two and five;

wherein each edge module has a plurality of dual ports, and the plurality of dual ports of a specific edge module common to N specific sub-nets are divided into N port groups each connecting to a respective core stage corresponding to one of the N specific sub-nets and a port group connecting to local sources and sinks wherein the plurality of sub-net are arranged into N groups of sub-nets;

wherein any two sub-nets within any group of sub-nets from among the N groups of sub-nets are non-intersecting having no edge module in common; and

wherein each sub-net within any group of sub-nets from among the N groups of sub-nets intersects a number of sub-nets belonging to each other group of sub-nets.

11. The network of claim 10 wherein said each edge module is identified by coordinates, each coordinate associated with one of the N groups of sub-nets.

12. The network of claim 11 wherein said each edge module determines its routes to each destination edge module, from among the plurality of edge modules, solely from coordinates of said each destination edge module.

13. The network of claim 10 wherein at least one core module, from among the plurality of core modules, is an optical switch.

14. The network of claim 10 wherein a route from any edge module belonging to a given sub-net to any other edge module belonging to the given sub-net traverses only one core module belonging to a core stage corresponding to the given sub-net.

15. The network of claim 10 wherein the core modules of the plurality of core modules are not connected to each other.

16. The network of claim 10 wherein each of the edge modules receives a request for a connection to a destination edge module belonging to said plurality of edge modules and generates a plurality of routes to said destination edge module.

17. The network of claim 16 wherein said plurality of routes includes mutually exclusive routes traversing different core modules.

18. In a network comprising a plurality of edge modules and a plurality of core modules, the core modules arranged into a predefined number N, 2≦

N≦

5, of core groups, each core module in core group j, 1≦

j≦

N, connecting to a number Q_j of edge modules, the number Q_j being specific to core group j, 2<

Q_j≦

256, and each edge module connecting to one core module in each of the N core groups and uniquely identified by N coordinates associated with the N core groups where a j_th coordinate, 1≦

j≦

N, takes a value between 0 and (Q_j−

1), a method of setting-up a connection from a first edge module to a second edge module, the method comprising steps of;

formulating at the first edge module a first path identified by a first routing array having N records, each record corresponding to an edge module along the first path and storing a coordinate identifier and a coordinate value, the coordinate identifier indicating a subsequent core group and the coordinate value indicating a subsequent edge module connecting to a core module of the subsequent core group;

setting the first edge module as a current edge module;

determining coordinates of a subsequent edge module according to a coordinate identifier and a coordinate value indicated in a first record of the first routing array;

deleting the first record of the first routing array;

forwarding the first routing array from the current edge module to the subsequent edge module; and

setting the subsequent edge module as the current edge module with current coordinates equal to coordinates of the subsequent edge module.

19. The method of claim 18 further comprising repeating the steps of determining, deleting, and forwarding until a last record of the first routing array is deleted.

20. The method of claim 19 further comprising:

specifying a bit-rate requirement for the connection; and

abandoning the first path subject to unavailability of sufficient free capacity on a link of the first path to support the bit-rate requirement.

21. The method of claim 20 further comprising steps of:

formulating at the first edge module a second path identified by a second routing array having N entries, each entry corresponding to an edge module along the second path and storing a coordinate identifier and a coordinate value, the coordinate identifier indicating a subsequent core group and the coordinate value indicating a subsequent edge module connecting to a core module of the subsequent core group;

setting the first edge module as a current edge module;

determining coordinates of a subsequent edge module according to a coordinate identifier and a coordinate value indicated in a first entry in the second routing array;

deleting the first entry of the second routing array;

forwarding the second routing array from the current edge module to the subsequent edge module; and

setting the subsequent edge module as the current edge module with current coordinates equal to coordinates of the subsequent edge module.

22. The method of claim 21 wherein the first path and the second path are mutually exclusive traversing different core modules.

23. In a network comprising a plurality of edge modules and a plurality of core modules, the core modules arranged into a predefined number N, N=4, of core groups, each core module in core group j, 1≦

j≦

N, connecting to a number Q_j of edge modules, the number Q_j being specific to core group j, 2<

Q_j≦

256, and each edge module uniquely identified by N coordinates where a j^th coordinate, 1≦

j≦

N, takes a value between 0 and (Q_j−

1), a first edge module, from among the plurality of edge modules, the first edge module;

identifies the core groups by N identifiers A, B, C, and D;

permutes (N−

1) identifiers B, C, D, to produce factorial (N−

1) route-set generating permutations ABCD, ABDC, ACBD, ACDB, ADBC, and ADCB;

generates N rotations of each route-set generating permutation, each rotation defining N mutually-exclusive routes traversing different core modules, the N rotations of permutations of ABCD, ABDC, ACBD, ACDB, ADBC, and ADCB, respectively, being;

ABCD, BCDA, CDAB, and DABC,

ABDC, BDCA, DCAB, and CABD,

ACBD, CBDA, BDAC, and DACB,

ACDB, CDBA, DBAC, and BACD,

ADBC, DBCA, BCAD, and CADB, and

ADCB, DCBA, CBAD, and BADC;

and

selects N rotations of one of the factorial (N−

1) route-set generating permutations to define N mutually exclusive routes from the first edge module to a destination edge module from among the plurality of edge modules according to N coordinates of the destination edge module.

24. A network comprising:

a plurality of edge modules arranged into a number Q₁ of columns and a number Q₂ of rows, each column having Q₂ edge modules and each row having Q₁ edge modules;

a number Q₂ of primary core modules having a one-to-one correspondence to the Q₂ rows, each primary core module interconnecting Q₁ edge modules of one of the Q₂ rows; and

a number Q₁ of secondary core modules having a one-to-one correspondence to the Q₁ columns, each secondary core module interconnecting Q₂ edge modules of one of the Q₁ columns;

wherein the number Q₁ is between 8 and 256 and the number Q₂ is between 8 and 256 wherein each edge module has at least one link from data sources and at least one link to data sinks;

wherein a path from an edge module in a specific row to another edge module in the specific row traverses a primary core module corresponding to the specific row;

wherein a path from an edge module in a specific column to another edge module in the specific column traverses a secondary core module corresponding to the specific column;

wherein a first path from a first edge module, in a first row and a first column, to a second edge module, in a different row and a different column, traverses a primary core module corresponding to the first row and a secondary core module corresponding to the second column; and

wherein a second path from the first edge module to the second edge module traverses a secondary core module corresponding to the first column and a primary core module corresponding to the second row.

25. The network of claim 24 wherein each of the primary core modules is a switching module.