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

• US 7,436,775 B2
• Filed: 07/24/2003
• Issued: 10/14/2008
• Est. Priority Date: 07/24/2003
• Status: Expired due to Fees

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Rabinovitch, Peter, Jordan, John Lawrence
• Primary Examiner(s): Chan, Wing F.
• Assistant Examiner(s): Mais, Mark A.
• Application Number:
  US10/625,667
• Publication Number:
  US 20050018665A1
• Time in Patent Office: 1,909 Days
• Field of Search: 370235-238, 370/238.1, 370/389, 370/390, 370/392, 370/395.1, 370/396, 370/395.21, 370/395.31, 370/411, 370/432, 370/431, 370/474, 370/475, 370/476, 370/235.1, 370/236.1, 370/236.2, 370/395.2
• US Class Current: 370/238
• 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 software configurable cluster-based router (400) for a packet-switched communication network, said cluster-based router including N cluster nodes (402) connected by a plurality of internal links (404), characterized by:

a plurality of external links for enabling said cluster-based router to exchange traffic with a plurality of nodes of said packet-switched communication network;

each cluster node of said N cluster nodes (402) being adapted to operate as a core router cluster node and as an edge router cluster node;

the internal links (404) connect said cluster nodes in an intra-connection network adapted to provide a high path diversity for a plurality of packet processing flows routed over said intra-connection network between edge router nodes; and

the cluster nodes connected to external links being adapted to operate as edge router cluster nodes,

whereby a specified routing capacity is obtained for said cluster-based router by selecting N and selecting a configuration of said intra-connection network, said configuration having n dimensions, said cluster nodes being interconnected by said internal links in such a way that each of said cluster nodes is connected to two other cluster nodes in each of said dimensions, each of said cluster nodes thereby being connected to 2*n said internal links.

2. A software-configurable cluster-based router as claimed in claim 1, wherein each cluster node (402) is a personal computer.

3. A software-configurable cluster-based router as claimed in claim 1, wherein said specified configuration comprises an n dimensional topology, each cluster node being connected to 2*n neighboring cluster nodes (402).

4. A software-configurable cluster-based router as claimed in claim 1, further comprising:

an additional cluster node (410) adapted to operate as a management node for managing operation of said cluster nodes of said intra-connection network; and

dedicated management links (412) for enabling said additional cluster node to communicate with said cluster nodes.

5. A software-configurable cluster-based router as claimed in claim 4, wherein said management links (412) form a star or a bus topology.

6. A software-configurable cluster-based router as claimed in claim 1, wherein each cluster node comprises a plurality of routing, functional blocks, all said cluster nodes comprising the same routing functional blocks.

7. A software-configurable cluster-based router as claimed in claim 1, wherein each cluster node uses an internal addressing process for dynamically determining a node address of each cluster node (402) on said intra-connection network.

8. A software-configurable cluster-based router as claimed in claim 1, wherein said cluster nodes use an external addressing process for dynamically determining a router address for said cluster-based router (400) on said communication network.

9. A software-configurable cluster-based router as claimed in claim 6, wherein said routing functional blocks comprise:

entry packet processing and routing response processing blocks, adapted to route an untagged packet to an output port of the output ports of said cluster node;

exit packet processing blocks adapted to route a tagged packet to an output port of the output ports of said cluster node;

a packet classification unit connected to input port of said cluster node adapted to route said untagged packet received on said input port over an external link to said entry packet processing and routing response processing blocks, and to route said tagged packet received on said input port over an internal link to said exit packet processing blocks.

10. A software-configurable cluster-based router as claimed in claim 9, wherein said entry packet processing and routing response processing blocks includes:

a decision block (506, 510, 520, 533) for determining if said untagged packet needs to be processed at said cluster node; and

a routing response processing block (570) for performing a route lookup on said untagged packet and routing said untagged packet into an output queue corresponding to said output port.

11. A software-configurable cluster-based router as claimed in claim 9, wherein said entry packet processing and routing response processing blocks include a tag packet block (540) for attaching a tag to said untagged packet.

12. A software-configurable cluster-based router as claimed in claim 11, wherein said exit packet processing blocks include a decision block (580) for determining whether said cluster node is an exit edge cluster node.

13. A software-configurable cluster-based router as claimed in claim 11, wherein said exit packet processing blocks include a remove tag block (582) for removing said tag from said tagged packet if said cluster node is an exit edge cluster node.

14. software-configurable cluster-based router as claimed in claim 9, further comprising a decision block (510) for determining if said untagged packet is a router management packet and routing said untagged packet to a management node (410) of said cluster based router.

15. A software-configurable cluster-based router as claimed in claim 11, wherein said tag is provided as an optional packet header, a packet trailer, or an additional header.

16. A method of routing packets over a cluster-based router (400) with a configurable routing capacity and port count, comprising the steps of:

i) selecting a number N and a configuration for said cluster-based router for obtaining a specified routing capacity and port count for said cluster-based router, said configuration having n dimensions, said cluster nodes being interconnected by said internal links in such a way that each of said cluster nodes is connected to two other cluster nodes in each of said dimensions, each of said cluster nodes thereby being connected to 2*n said internal links,

ii) connecting N cluster nodes (402) via internal links in an intra-connection network according to said configuration;

iii) connecting a selected number of cluster nodes designated to operate as edge router cluster nodes over a plurality of external links for enabling connection of said cluster-based router in a communication network; and

iv) routing packets along packet processing flows established between two edge router cluster node over a plurality of core router cluster nodes.

17. A method as in claim 16, wherein whenever one of said cluster nodes is affected by a failure, the remaining cluster nodes take over the functionality of said failed cluster node.

18. A method as claimed in claim 16, wherein step iv) comprises providing each cluster node with a node MAC address on said intra-connection network, and providing each port of said cluster node with a unique port MAC address.

19. A method as claimed in claim 18, wherein said node MAC address is set to the lowest MAC address of all ports of said respective cluster node.

20. method as claimed in claim 16 further comprising using a dynamic internal cluster router MAC address determination process for establishing a router MAC address for said cluster-based router.

21. A method as claimed in claim 16, wherein step iv) comprises:

attaching a tag to each new packet received on an input port of an edge router cluster node; and

differentially processing packets at each cluster node according to the presence or absence of said tag, whereby;

said packet is routed towards another cluster node if it is addresses to said another cluster node, or said tag is removed and said packet is routed to an edge node for transmission over said communication network.