SCALABLE CLUSTER ROUTER

• US 20110016223A1
• Filed: 07/19/2010
• Published: 01/20/2011
• Est. Priority Date: 07/17/2009
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Baset, Salman, Dobrescu, Mihai, Ratnasamy, Sylvia, Manesh, Maziar, Iannaccone, Gianluca, Egi, Norbert, Chun, Byung-Gon, Fall, Kevin, Argyraki, Katerina, Knies, Allan
• Granted Patent: US 8,904,028 B2
• Time in Patent Office: Days
• US Class Current: 709/232
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/583 Stackable routers
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 49/45 Arrangements for providing or supporting expansion

Abstract

Generally, this disclosure describes a scalable cluster router that includes a plurality of server-class computers interconnected together to form a router. Each server may be configured to independently schedule switching of packets to reduce the switch speed requirements on a per server basis. Each server may include a scheduler that independently load balances packet flows across servers of the cluster. Router capacity may be incrementally scaled by adding more servers, and router capacity may be increased by load balancing techniques within individual servers.

Claims

1. A server, comprising:

a plurality of internal ports and at least one external port, each said internal port is configured to be coupled to and to communicate with at least one other server and included in a cluster of N interconnected servers to form a router having M router ports corresponding to the total number of external ports of all the servers in the cluster; and

each said external port is configured to couple to and to communicate with a network or a network device to receive packet flow; and

a scheduler configured to switch packets from an external port to an internal port, or from one internal port to another internal port, by load balancing a packet flow received on each said external port by selecting one of said plurality of internal ports to transmit a plurality of packets of said packet flow to a receiving interconnected server coupled to the selected internal port.

2. The server of claim 1, wherein the scheduler is configured to switch at processing rate that is independent of M.

3. The server of claim 1, wherein a line rate of each said external port is R bits per second (bps), and the scheduler is configured to switch at processing rate of c*s*R, where s represents the number of external ports of said server and c is between 2 and 3.

4. The server of claim 1, further comprising a network adapter configured to process the header of each said packet to identify an output node for the packets and to modify a MAC address of the plurality of packets with queue information to enable the receiving server to identify an the output node without further processing of the packet header.

5. The server of claim 1, further comprising:

a processor having a plurality of cores; and

a plurality of receive queues for receiving data from said external ports;

wherein each said receive queue is assigned to a specific packet flow, and wherein packet processing of said packet flow received by each said external port is distributed across said cores.

6. The server of claim 1, wherein said scheduler selects one of said plurality of said internal ports randomly.

7. The server of claim 1, wherein said selecting one of said plurality of said internal ports comprises:

determining a source of the packet flow for a given external port;

determining if a packet within the identified packet flow has been received within a predetermined time interval.

8. The server of claim 1, wherein said selecting one of said plurality of said internal ports comprises:

determining if an internal port is overloaded or has exceeded a predetermined threshold; and

randomly selecting another internal port to transmit the packet flow to another server.

9. The server of claim 1, wherein said selecting one of said plurality of said internal ports further comprises:

determining if a selected internal port has a throughput that is less than a soft limit;

determining if a selected internal port is a preferred port; and

determining if a selected internal port has a throughput less than a hard limit.

10. The server of claim 1, wherein said server is configured to interconnect with said cluster of N interconnected servers in a full mesh topology.

11. The server of claim 1, wherein said server is further configured to interconnect with a plurality of intermediate servers in a k-ary n-fly butterfly multihop topology.

12. A method, comprising:

receiving a packet flow at an external port of an input node server, wherein said input node server is one of a plurality of N node servers coupled in an interconnect topology in a cluster router, the cluster router comprising a plurality of M router ports corresponding to the total number of external ports of all the servers in the cluster,

processing said packet flow to determine a destination of the packets of the packet flow, wherein said destination comprises an output node server of said plurality of node servers;

switching packets from an external port to an internal port, or from one internal port to another internal port, by load balancing a packet flow received on each said external port by selecting one of said plurality of internal ports to transmit a plurality of packets of said packet flow to a receiving interconnected server coupled to the selected internal port.

13. The method of claim 12, wherein switching occurs at rate that is independent of M.

14. The method of claim 12, wherein a line rate of each said external port is R bits per second (bps), and the switching is configured to occur at processing rate of c*s*R, where s represents the number of external ports of said server and c is between 2 and 3.

15. The method of claim 12, further comprising:

processing a header of each said packet to identify an output node for the packets; and

modifying a MAC address of the plurality of packets with queue information to enable the receiving server to identify an the output node without further processing of the packet header.

16. The method of claim 12, wherein:

said input node server further comprises a processor having a plurality of cores, and a plurality of receive queues for receiving data from said external ports;

said method further comprises;

assigning a packet flow to a receive queue; and

distributing packet processing of said packet flow received by each said external port across said cores.

17. The method of claim 12, wherein said selecting one of said plurality of said internal ports is performed randomly.

18. The method of claim 12, wherein said selecting one of said plurality of said internal ports comprises:

determining a source of the packet flow for a given external port;

determining if a packet within the identified packet flow has been received within a predetermined time interval.

19. The method of claim 12, wherein said selecting one of said plurality of said internal ports comprises:

determining if the internal port is overloaded or has exceeded a predetermined threshold; and

randomly selecting another internal port to transmit the packet flow to another server.

20. The method of claim 12, wherein said selecting one of said plurality of said internal ports comprises:

determining if a selected internal port has a throughput that is less than a soft limit;

determining if a selected internal port is a preferred port; and

determining if a selected internal port has a throughput less than a hard limit.

21. The method of claim 12, wherein said server is configured to interconnect with said cluster of N interconnected servers in a full mesh topology.

22. The method of claim 12, wherein said server is further configured to interconnect with a plurality of intermediate servers in a k-ary n-fly butterfly multihop topology.

23. An apparatus comprising a computer-readable storage medium having stored thereon computer readable instructions that when executed by one or more processors result in the following operations, comprising:

processing a packet flow received at an external port of an input node server to determine a destination of the packets of the packet flow, wherein said destination comprises an output node server;

switching packets from said external port to one of a plurality of internal ports of the input node server, or from one internal port of the input node server to another internal port of the input node server, by load balancing a packet flow received at said external port by selecting one of said plurality of internal ports to transmit a plurality of packets of said packet flow to another server coupled to the selected internal port;

wherein said input node server is one of a plurality of N node servers coupled in an interconnect topology in a cluster router, the cluster router comprising a plurality of M router ports corresponding to the total number of external ports of all the servers in the cluster.

24. The apparatus of claim 23, wherein switching occurs at rate that is independent of M.

25. The apparatus of claim 23, wherein a line rate of each said external port is R bits per second (bps), and the switching is configured to occur at processing rate of c*s*R, where s represents the number of external ports of said server and c is between 2 and 3.

26. The apparatus of claim 23, wherein the instructions that when executed by one or more of the processors result in the following additional operations comprising:

processing a header of each said packet to identify an output node for the packets; and

modifying a MAC address of the plurality of packets with queue information to enable the receiving server to identify an the output node without further processing of the packet header.

27. The apparatus of claim 23, wherein said input node server further comprises:

a processor having a plurality of cores; and

a plurality of receive queues for receiving data from said external ports;

wherein each said receive queue is assigned to a specific packet flow, and wherein packet processing of said packet flow received by each said external port is distributed across said cores.

28. The apparatus of claim 23, wherein the instructions that when executed by one or more of the processors result in the following additional operations comprising:

randomly selecting one of said plurality of said internal ports.

29. The apparatus of claim 23, wherein, for the selecting operation, the instructions that when executed by one or more of the processors result in the following additional operations comprising:

determining a source of the packet flow for a given external port;

determining if a packet within the identified packet flow has been received within a predetermined time interval.

30. The apparatus of claim 23, wherein, for the selecting operation, the instructions that when executed by one or more of the processors result in the following additional operations comprising:

determining if the internal port is overloaded or has exceeded a predetermined threshold; and

randomly selecting another internal port to transmit the packet flow to another server.

31. The apparatus of claim 23, wherein, for the selecting operation, the instructions that when executed by one or more of the processors result in the following additional operations comprising:

determining if a selected internal port has a throughput that is less than a soft limit;

determining if a selected internal port is a preferred port; and

determining if a selected internal port has a throughput less than a hard limit.

32. The apparatus of claim 23, wherein said server is configured to interconnect with said cluster of N interconnected servers in a full mesh topology.

33. The apparatus of claim 23, wherein said server is further configured to interconnect with a plurality of intermediate servers in a k-ary n-fly butterfly multihop topology.