Software configurable cluster-based router using stock personal computers as cluster nodes

• US 20050018665A1
• Filed: 07/24/2003
• Published: 01/27/2005
• Est. Priority Date: 07/24/2003
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Rabinovitch, Peter, Jordan, John Lawrence
• Granted Patent: US 7,436,775 B2
• Time in Patent Office: Days
• US Class Current: 370/388
• CPC Class Codes: H04L 45/06 Deflection routing, e.g. hot-potato routing
• CPC Class Codes: H04L 45/42 Centralised routing

Abstract

A cluster router architecture and methods for performing distributed routing is presented. Implementations include off-the shelf Personal Computer (PC) hardware. The cluster router architecture includes PC-based router cluster nodes toroidally interconnected in an intra-connection network in multiple dimensions. The cluster router may further make use of a management node. Each router cluster node is provided with the same routing functionality and a node centric configuration enabling each router cluster node by itself or multiple router cluster nodes in the cluster router to provide routing responses for packets pending processing. The method divides packet processing into entry packet processing and routing response processing; and exit processing. Entry packet processing and routing response processing is performed by router cluster nodes receiving packets from communication networks in which the cluster router participates. Exit packet processing is performed by router cluster nodes transmitting packets into communication networks in which the cluster router participates. Advantages are derived from: a configurable, and scalable cluster router design providing a high routing capacity using cost effective stock PC hardware; from the toroidal topology of the intra-connection network which provides a high degree of diversity ensuring resilience to equipment failure, and from the use of the star topology of the management links which reduces management overheads in the intra-connection network.

Claims

1. A cluster-based router comprising:

a. a plurality of equivalent interconnected router cluster nodes, the routing capacity of the cluster router increasing substantially O(N) with the number N of router cluster nodes in the cluster router;

b. a plurality of cluster router internal links interconnecting router cluster nodes forming an intra-connection network ensuring a high path diversity in providing resiliency to failures;

c. each router cluster node having a group of cluster router external links enabling packet exchange with a plurality of external communication network nodes; and

d. each router cluster node operating in accordance with a provisioned router-cluster-node-centric configuration to effect distributed routing of the conveyed packets,

the equivalency between the router cluster nodes providing a scalable cluster router.

2. The cluster router claimed in claim 1, wherein the router-cluster-node-centric configuration further comprises routing functional blocks and specifies packet processing flows between the routing functional blocks effecting packet routing employing one of:

a single router cluster node, and a sequence of router cluster nodes.

3. The cluster router claimed in claim 1, wherein each router cluster node comprises a personal computer platform providing flexibility and cost savings in the development, deployment, maintenance, and expandability of the cluster router.

4. The cluster router claimed in claim 1, wherein the intra-connection network further comprises an n dimensional toroidal topology, wherein 2*n internal links interconnect each router cluster node with 2*n adjacent neighboring router cluster nodes;

the routing capacity of the cluster router being increased substantially linearly by adding an n-1 dimensional slice of router cluster nodes to the cluster router.

5. The cluster router claimed in claim 4, wherein the intra-connection network comprises a three dimensional toroidal topology, wherein six internal links interconnect each router cluster node with six adjacent neighboring router cluster nodes.

6. The cluster router claimed in claim 1, wherein the intra-connection network further comprises one of unidirectional and bi-directional internal interconnecting links.

7. The cluster router claimed in claim 1, further comprising:

a router cluster node designated as a management node, should a management node designated router cluster node fail, designating another router cluster node as a management node without making changes to the cluster router infrastructure.

8. The cluster router claimed in claim 1, further comprising:

a. at least one management node; and

b. a plurality of management links interconnecting the at least one management node with the plurality of router cluster nodes and enabling one of out-of-band;

configuration deployment to each router cluster node, router cluster node initialization, and reporting functionality;

employing the plurality of management links reducing an in-band cluster router management overhead.

9. The cluster router claimed in claim 8, wherein the plurality of management links from one of a star and a bus topology.

10. The cluster router claimed in claim 1, further comprising an cluster router internal addressing process dynamically determining router cluster node addressing.

11. The cluster router claimed in claim 1, further comprising a cluster router external addressing process dynamically determining a cluster router address.

12. A router cluster node of a plurality of router cluster nodes interconnected in a cluster router, the router cluster node comprising:

a. a plurality of cluster router internal interconnecting links connected thereto, the internal interconnecting links enabling the exchange of packets with adjacent router cluster nodes in the cluster router;

b. at least one cluster router external link connected thereto, the at least one external link enabling exchange of packets between external communications network nodes and the cluster router; and

c. a router-cluster-node-centric configuration to effect distributed routing of the conveyed packets,

the equivalency between router cluster nodes in the cluster router providing a scalable router.

13. The router cluster node claimed in claim 12, wherein the router-cluster-node-centric configuration further comprises routing functional blocks and specifies packet processing flows between the routing functional blocks effecting packet routing employing one of:

a single router cluster node, and a sequence of router cluster nodes.

14. The router cluster node claimed in claim 12, wherein each router cluster node comprises a personal computer platform providing flexibility and cost savings in the development, deployment, maintenance, and expandability of the cluster router.

15. The router cluster node claimed in claim 12, wherein 2*n cluster router internal links interconnect the router cluster node with 2*n adjacent neighboring router cluster nodes in accordance with an n dimensional toroidal topology, the routing capacity of the cluster router being increased substantially linearly by adding an n-1 dimensional slice of router cluster nodes to the cluster router.

16. The router cluster node claimed in claim 12, further comprising:

a management link interconnecting the router cluster node to a management node.

17. The router cluster node claimed in claim 12, further providing management functionality.

18. A router-cluster-node-centric configuration enabling the provision of a distributed packet routing response in a cluster router having a plurality of router cluster nodes, the configuration comprising:

a. a plurality of routing functional blocks; and

b. at least one cluster-node-centric packet processing flow, via the plurality of routing functional blocks, to effect routing of packets received at the cluster router employing one of a single router cluster node and a group of router cluster nodes.

19. The router-cluster-node-centric configuration claimed in claim 18, further comprising:

a. an entry-and-routing processing packet processing flow specification;

b. a transit packet processing flow specification; and

c. an exit packet processing packet processing flow specification,

the packet processing flow specifications enabling a received packet to undergo entry and routing processing at an entry router cluster node, optionally transit via at least one intermediary router cluster node, and undergo exit processing at an exit router cluster node.

20. The router-cluster-node-centric configuration claimed in claim 18, wherein the router cluster node configuration further employs a tag conveyed with each packet within the cluster router infrastructure, the tag holding specifiers for tracking packet processing within the cluster router.

21. The router-cluster-node-centric configuration claimed in claim 20, wherein each tag identifies an associated packet as one having received a routing response and propagating through the cluster router towards a specified exit router cluster node.

22. The router-cluster-node-centric configuration claimed in claim 20, wherein each tag comprises a combination of:

an optional packet header, a packet trailer, and an additional header encapsulating the associated packet having cluster router relevance only.

23. The router-cluster-node-centric configuration claimed in claim 20, wherein each tag holds a tag time-to-live specification decremented while the associated packet propagates via router cluster nodes in the cluster, the packet being discarded when the time-to-live specification is zero and the packet has not reached a corresponding exit router cluster node thereby reducing transport overheads.