Multi-dimensional lattice network

• US 20050068946A1
• Filed: 10/20/2004
• Published: 03/31/2005
• Est. Priority Date: 07/24/2000
• Status: Active Grant

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Maged E. Beshai
• Inventors: Beshai, Maged E.
• Granted Patent: US 7,684,389 B2
• Time in Patent Office: Days
• US Class Current: 370/368
• 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. An N-dimensional lattice network comprising

a plurality of sub-nets and a plurality of independent core stages, each sub-net including at least two edge modules and being associated with one of said core stages and one of N dimensions wherein:

each edge module belongs to N sub-nets associated with N different dimensions; and

said each edge module is connected to the core stage associated with each of said N sub-nets.

2. An N-dimensional lattice network as claimed in claim 1 wherein the number of edge modules in each sub-net has an upper-bound Q_d, 0≦

d≦

N.

3. An N-dimensional lattice network as claimed in claim 1 wherein the capacity of the network is limited by:

C=R×

m₀×

(Q₁×

Q₂×

. . . ×

Q_N),

C being total capacity of the N-dimensional network, m₀ being a number of input/output links per edge module, R being the capacity of each of said links, and Qn being a number of edge modules in each sub-net associated with dimension n;

wherein

a target capacity for the N-dimensional network is achieved by selecting an appropriate number of edge modules for each of said sub-nets.

4. An N-dimensional lattice network as claimed in claim 1 wherein the core stage comprises at least one data packet switch.

5. An N-dimensional lattice network as claimed in claim 1 wherein the core stage of at least one of said sub-nets comprises at least one cross connector.

6. An N-dimensional lattice network as claimed in claim 1 wherein the core stage of at least one of said sub-nets comprises a plurality of core switch modules.

7. An N-dimensional lattice network as claimed in claim 6 wherein said core switch modules are geographically distributed.

8. An N-dimensional lattice network as claimed in claim 6 wherein at least one of said core switch modules is a time-division-multiplexed space switch.

9. An N-dimensional lattice network as claimed in claim 6 wherein at least one of said core switch modules is an optical switch.

10. An N-dimensional lattice network for high speed data transport over a large geographical area, comprising:

a) a plurality of edge modules connected to local data sources/sinks, each edge module being identified by N coordinates that define a relative position of the edge modules in the N-dimensional lattice network, wherein each edge module is a member of a plurality of sets of edge modules associated with a number of predefined dimensions of the N-dimensional lattice network; and

b) a plurality of core stages for switching data packets between the plurality of edge modules, each edge module being connected to N core stages.

11. An N-dimensional lattice network as claimed in claim 10 wherein the edge modules are switching nodes each having a plurality of input/output ports and the input/output ports of each of the edge modules are divided into N+1 port groups, a one of the port groups being connected to the local sources/sinks, and a remainder of the port groups being connected to the respective N core stages.

12. An N-dimensional lattice network as claimed in claim 11 wherein the N+1 port groups are substantially equal in size.

13. An N-dimensional lattice network as claimed in claim 10 wherein edge modules having N−

1 common coordinates form a sub-net, each of the edge modules in the sub-net being connected to a same one of the core stages.

14. An N-dimensional lattice network as claimed in claim 10 wherein the core stages are modular switching core stages.

15. An N-dimensional lattice network as claimed in claim 14 wherein the modular switching core stages are geographically distributed.

16. An N-dimensional lattice network as claimed in claim 10 wherein the core stages are switching core stages that are agile and are adapted to reconfigure in response to fluctuations in traffic loads.

17. A method of routing from a first edge module to a second edge module in an N-dimensional lattice network comprising a plurality of edge modules and a plurality of core stages, each edge module being connected to N core stages, comprising steps of:

c) identifying each edge module with N coordinates associated with N dimension identifiers arranged in a predetermined order; and

d) using the coordinates of said second edge module to define a path from the first edge module to the second edge module said path traversing at most N of said core stages.

18. The method as claimed in claim 17 further comprising a step of storing the respective coordinates and the dimension identifiers in a routing array that is forwarded in a connection request message sent towards the second edge module as a connection is routed through the network.

19. The method as claimed in claim 18 further comprising a step of shortening the routing array at each intervening edge module in the path to the second edge module by deleting a coordinate and a dimension identifier from the array at the intervening edge module, the coordinate and the dimension identifier deleted defining the next edge module to which the connection request message is to be sent.

20. A network comprising a plurality of edge modules arranged into a plurality of sets of edge modules wherein:

each of said sets is associated with one of a predefined number of dimensions;

each edge module in said plurality of edge modules belongs to a selected number of sets associated with different dimensions; and

the edge modules of each of said sets are interconnected by a core stage, said core stage including at least one core module.

21. The network of claim 20 wherein said selected number of sets equals said predefined number of dimensions and only one set of said selected number of sets is associated with any dimension of said predefined number of dimensions.

22. The network of claim 21 wherein said each edge module is identified by coordinates each coordinate associated with one of said predefined number of dimensions.

23. The network of claim 22 wherein said each edge module determines its routes to each destination edge module solely from coordinates of said each destination edge module.

24. The network of claim 20 wherein at least one of said at least one core module is an optical switch.

25. The network of claim 20 wherein each of said at least one core module connects exclusively to a respective one of said sets of edge modules.

26. The network of claim 20 wherein each route from each edge module belonging to one of said sets to each other edge module belonging to the same said one of said sets traverses only one core module.

27. The network of claim 20 wherein said at least one core module comprises independent core modules.

28. The network of claim 20 wherein each of said edge modules is operable to receive a request for a connection to a destination edge module belonging to said plurality of edge modules and generate a plurality of routes to said other edge module.

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

30. A method of setting-up a connection from a first edge module to a second edge module in a multi-dimensional network comprising a plurality of edge modules arranged into sets of edge modules, each of said sets further associated with one of a predefined number of dimensions, and each edge module belonging to one of said sets in each of said dimensions, the method comprising steps of:

formulating at said first edge module a first routing array having a number of records equal to said predefined number of dimensions, each record indicating a dimension identifier and a corresponding edge-module coordinate; and

determining at a current edge module, said current edge module initially being said first edge module, a dimension identifier and a coordinate of a subsequent edge module from a first record of said first routing array;

deleting at said current edge module said first record; and

forwarding from said current edge module to said subsequent edge module a remaining portion of said routing array using said dimension identifier and coordinate of said subsequent edge module.

31. The method of claim 30 wherein said determining, deleting, and forwarding are repeated until a last record of said routing array is deleted.

32. The method of claim 31 wherein said routing array further includes a specified bit-rate requirement and said connection set-up is abandoned if said path cannot accommodate said specified bit rate.

33. The method of claim 32 further including a step of identifying a second routing array and repeating said formulating, determining, deleting, and forwarding.

34. The method of claim 33 wherein said first routing array and said second routing array are mutually exclusive having different corresponding records.

35. In a multi-dimensional network said network comprising a plurality of edge modules arranged in sets of edge modules each of said sets associated with one of a number of predefined dimensions and each edge module is identified by coordinates associated with said predefined dimensions, a first edge module operable to:

permute selected dimensions of said predefined dimensions to determine route-set generating permutations;

associate the coordinates of a second edge module, selected from among said edge modules, with each one of said route-set generating permutations to determine a sequence of coordinates; and

rotate said sequence of coordinates to generate a set of mutually-exclusive routes to said second edge module.

36. The edge module of claim 35 further operable to:

receive a request for a connection to a destination edge module selected from among said edge modules; and

determine a set of routes to said destination edge module based solely on coordinates of said destination edge module.

37. A network comprising:

a plurality of edge modules wherein each edge module is a member of a plurality of sets of edge modules associated with a number of predefined dimensions of the network; and

the edge modules of each of said plurality of sets are interconnected by a core stage, said core stage including at least one core module.

38. The network of claim 37 wherein each set in said plurality of sets is associated with only one of said predefined dimensions.

39. The network of claim 38 wherein said at least one core module comprises at least two independent core modules.

40. The network of claim 38 wherein at least one of said at least one core module connects to each edge module of said edge modules of each of said plurality of sets.

41. The network of claim 37 wherein said at least one core module is a switching module.