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

• US 7,483,998 B2
• Filed: 11/14/2003
• Issued: 01/27/2009
• Est. Priority Date: 11/14/2003
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Rabinovitch, Peter
• Primary Examiner(s): Cardone, Jason D
• Assistant Examiner(s): Pollack, Melvin H
• Application Number:
  US10/712,104
• Publication Number:
  US 20050108425A1
• Time in Patent Office: 1,901 Days
• Field of Search: 709/221, 709232-235, 709238-241, 709/246, 709/252, 709/253, 370216-220, 370/229, 370/230, 370/230.1, 370/237, 370/238, 370/240, 370/244, 370/257, 370/389, 713/1, 713/2, 713/100, 714/4
• 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 to provide routing responses for packets pending processing. Packet processing is divided into entry packet processing and routing response processing; special processing; and exit processing. Exit packet processing is performed by router cluster nodes transmitting packets into communication networks in which the cluster router participates. Packet processing 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.

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, wherein said plurality of interconnected router cluster nodes appears to external communications networks and nodes as a single communications network attached router;

b. at least one special purpose cluster node providing special packet processing functionality that is not provided by any other of said router cluster nodes in the cluster router, wherein said at least one special purpose cluster is interconnected in a lattice of the cluster router but cannot be counted on to perform routing functions performed by said others of said router cluster nodes;

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, wherein said provisioned router-cluster-node-centric configuration takes into account that said at least one special purpose router cluster node cannot be counted on to be aware of, or be configured via, said distributed cluster-node-centric router cluster node configuration.

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, each 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 to each of the cluster router nodes interconnected in the cluster router, the at least one external link enabling exchange of packets between communications network nodes external to said cluster router and the cluster router;

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

wherein the inclusion of said at least one external link in each of the router cluster nodes in the cluster router provides 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 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.

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

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

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

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

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

25. 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, each including at least one external link enabling packet exchange with communication network nodes external to said cluster router, the configuration comprising:

a. a plurality of routing functional blocks;

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;

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

d. a transit packet processing flow specification; and

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

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

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

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

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

30. The router-cluster-node-centric configuration claimed in claim 26, wherein each tag holds a tag time-to-live specification decremented while the associated packet propagates via muter 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.

31. 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 25, 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 water-cluster-node-centric packet processing flow effecting forwarding of the packet to a special purpose cluster node for processing.

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

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

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