Software configurable cluster-based router using heterogeneous nodes as cluster nodes

• US 20050108425A1
• Filed: 11/14/2003
• Published: 05/19/2005
• Est. Priority Date: 11/14/2003
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Rabinovitch, Peter
• Granted Patent: US 7,483,998 B2
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing

Abstract

A cluster router architecture and methods for performing distributed routing are presented. The cluster router architecture includes off-the shelf Personal Computer (PC) hardware-based router cluster nodes interconnected in an intra-connection network in multiple dimensions. Each PC-based router cluster node is provided with the same routing functionality and a router-cluster-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. Optimized packet processing in respect of specific functionality is provided via special purpose router cluster nodes not necessarily PC-based taking part as cluster nodes in the cluster router lattice. The method divides packet processing into entry packet processing and routing response processing; special 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. Packet processing in accordance with the router-cluster-node-centric specification is interrupted on determining that special processing is required in respect of a packet, and the packet is handed over to a corresponding special purpose router cluster node. Advantages are derived from: a configurable, and scalable cluster router design providing a re-configurable high routing capacity using cost effective stock PC hardware; from the intra-connection network which provides a high degree of diversity ensuring resilience to equipment failure; from the use of a star topology with respect to management links which reduces management overheads in the intra-connection network; and from the ability to forward packets to designated special purpose router cluster nodes optimized to provide specific packet processing functionality.

Claims

1. A cluster-based router comprising:

a. a plurality of 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, each router cluster node having a group of cluster router external links enabling packet exchange with a plurality of external communication network nodes;

b. at least one special purpose cluster node providing special packet processing functionality in the cluster router;

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

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

employing the at least one special purpose router cluster node providing a reduction in the development, validation, deployment and re-configuration of the 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 processing employing one of:

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

3. The cluster router claimed in claim 1, wherein each router cluster node further 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 at least one special purpose cluster node providing special packet processing functionality further comprises one of:

a specially coded personal computer platform, a personal computer platform having designed hardware characteristics in providing specific functionality, dedicated hardware implemented equipment designed to provide an enhancement in providing special packet processing functionality, and a router cluster node further coded to provide special packet processing functionality.

5. 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.

6. The cluster router claimed in claim 5, 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.

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

8. 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, another router cluster node being designated as a management node without making changes to the cluster router infrastructure.

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

a router cluster node designated as a special purpose cluster node, should a special purpose cluster node designated router cluster node fail, another router cluster node being designated as a special purpose cluster node without making changes to the cluster router infrastructure.

10. 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.

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

12. The cluster router claimed in claim 11, wherein the at least one special purpose cluster node is associated with the management node, special functionality being available one-hop-away from each router cluster node.

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

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

15. The cluster router claimed in claim 1, further comprising means for distributing to each router cluster node information regarding availability and addressing information regarding special purpose cluster nodes.

16. The cluster router claimed in claim 15, further employing methods of detecting special purpose cluster nodes providing special packet processing functionality.

17. 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 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.

18. The router cluster node claimed in claim 17, 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 group of router cluster nodes.

19. The router cluster node claimed in claim 18, wherein the router-cluster-node-centric configuration further comprises routing functional blocks determining a need for special packet processing and specifies packet processing flows forwarding packets to at least one special purpose cluster node associated with the router cluster.

20. The router cluster node claimed in claim 17, 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.

21. The router cluster node claimed in claim 17, 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.

22. The router cluster node claimed in claim 17, further comprising:

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

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

24. The router cluster node claimed in claim 17, further providing special packet processing functionality as a special purpose cluster node.

25. The router cluster node claimed in claim 24, wherein the special purpose cluster node provides packet processing in respect one of:

authentication, decryption, encryption, decoding, encoding, billing, directory access, and video stream processing.

26. 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 router-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.

27. The router-cluster-node-centric configuration claimed in claim 26, 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.

28. The router-cluster-node-centric configuration claimed in claim 26, 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.

29. The router-cluster-node-centric configuration claimed in claim 28, 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.

30. The router-cluster-node-centric configuration claimed in claim 28, wherein each tag identifies an associated packet as one requiring special processing and propagating through the cluster router towards one of:

a special purpose cluster node, and the router cluster node which determined that the packet required special processing.

31. The router-cluster-node-centric configuration claimed in claim 28, 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.

32. The router-cluster-node-centric configuration claimed in claim 28, 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.

33. 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 and at least one special purpose cluster node as claimed in claim 26, the configuration further comprising:

a. at least one routing functional block determining a need for special functionality in respect of processing a packet; and

b. at least one router-cluster-node-centric packet processing flow effecting forwarding of the packet to a special purpose cluster node for processing.

34. The router-cluster-node-centric configuration claimed in claim 33, wherein the at least one router-cluster-node-centric packet processing flow further specifies one of:

storing a copy of the packet header and a corresponding tag in an optional header of the packet; and

storing information about the packet in a storage structure for the purposes of continuing packet processing in accordance with the router-cluster-node-centric configuration.

35. The router-cluster-node-centric configuration claimed in claim 33, wherein the at least one cluster-node-centric packet processing flow further specifies at least one packet processing flow for further processing a packet having undergone packet processing at a special purpose cluster node.

36. The router-cluster-node-centric configuration claimed in claim 33, wherein the at least one cluster-node-centric packet processing flow further specifies employing addressing information stored in the packet header in forwarding the packet requiring special processing towards a special purpose cluster node.