Data center interconnect and traffic engineering

• US 8,160,063 B2
• Filed: 03/25/2009
• Issued: 04/17/2012
• Est. Priority Date: 06/09/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Maltz, David A., Greenberg, Albert G., Patel, Parveen K., Sengupta, Sudipta, Lahiri, Parantap
• Primary Examiner(s): Pezzlo, John
• Application Number:
  US12/410,745
• Publication Number:
  US 20090303880A1
• Time in Patent Office: 1,119 Days
• Field of Search: 370/389, 370/386, 370/401, 370/254
• US Class Current: 370/389
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

A system for commoditizing data center networking is disclosed. The system includes an interconnection topology for a data center having a plurality of servers and a plurality of nodes of a network in the data center through which data packets may be routed. The system uses a routing scheme where the routing is oblivious to the traffic pattern between nodes in the network, and wherein the interconnection topology contains a plurality of paths between one or more servers. The multipath routing may be Valiant load balancing. It disaggregates the function of load balancing into a group of regular servers, with the result that load balancing server hardware can be distributed amongst racks in the data center leading to greater agility and less fragmentation. The architecture creates a huge, flexible switching domain, supporting any server/any service, full mesh agility, and unregimented server capacity at low cost.

Claims

1. An interconnection topology system for a data center, comprising:

a plurality of servers in the data center;

a plurality of nodes of a network in the data center through which data packets may be routed; and

a routing scheme used in the data center where the routing is oblivious to the traffic pattern between nodes in the network;

wherein the interconnection topology contains a plurality of paths between one or more servers;

wherein a route between a node i to a node j is chosen by first determining an intermediate node k and then routing i to k followed by k to j, the node k being randomly chosen; and

wherein a packet is modified using encapsulation to direct the packet to the selected intermediate node.

2. An interconnection topology system of claim 1, further comprising a component on one of a server or a node that contributes to the routing scheme by the component limiting traffic traversing the component so as to prevent sustained overload on any link of the paths taken by the traffic.

3. An interconnection topology system of claim 2, wherein the traffic limiting component is TCP.

4. An interconnection topology system of claim 1, further comprising a directory service, wherein packets sent by a server without specific routing instructions are directed to an intermediate node k, the node k consulting the directory service to determine a destination server for the packet and a routing from k to j.

5. An interconnection topology system of claim 1, wherein k is chosen through a random or pseudo-random hash of non-volatile components of a TCP/IP header of the data packet.

6. An interconnection topology system of claim 1, wherein the routing scheme used is Valiant load balancing.

7. An interconnection topology system of claim 1, wherein the fraction of traffic sent to each intermediate node k is not the same for all nodes k.

8. An interconnection topology system of claim 1, wherein packets can go from i to j without passing through k if node k does not lie on the shortest path between i and j.

9. An interconnection topology system for a data center, comprising:

a plurality of servers;

a plurality of nodes through which data packets may be routed;

a topology of switches providing a plurality of paths between the plurality of servers; and

a routing scheme employing Valiant load balancing to allow data packet transfers to take place from any node to any other node, the routing scheme dividing traffic among the plurality of paths, the routing scheme selecting a route between first and second nodes by first determining an intermediate node and routing through the intermediate node.

10. An interconnection topology system of claim 9, the routing scheme being an adaptive routing scheme that chooses routes by considering at least one of a traffic matrix, congested links, the network topology and put together with an optimization procedure, so as to split traffic between intermediate nodes in unequal ratios.

11. An interconnection topology system of claim 9, further comprising at least one of a control plane and a directory service that adaptively adjust the routing scheme in the event of node or link failure by causing data packets to avoid switches or links that have failed.

12. An interconnection topology system of claim 9, further comprising a directory service wherein the source of the packet or a switch on the path of the packet uses the directory service to identify one or more addresses of servers appropriate to receive the packet.

13. An interconnection topology system of claim 12, wherein the directory service provides addresses used in constructing a data packet, the addresses specifying at least one of an intermediate or destination node, switch, or server.

14. An interconnection topology system for a data center, comprising:

a plurality of servers in the data center;

a plurality of nodes through which data packets may be routed; and

a routing scheme allowing data packet transfers to take place from any node to any other node, the routing scheme including;

a directory service for providing routing information to reach a destination server,

an agent for looking up at least one of a destination address or switch address for each data packet using the directory service, and

an encapsulator that modifies data packets so that they pass through at least one of a destination server or an intermediate switch.

15. An interconnection topology system of claim 14, the encapsulator selecting different intermediate nodes to spread load without causing packet reordering.

16. An interconnection topology system of claim 14, the routing scheme using Valiant load balancing wherein no node is asked to send or receive more traffic than its network interface can support at a given time.

17. An interconnection topology system of claim 16, wherein the intermediate node through which a data packet is routed is chosen through a random or pseudo-random hash of non-volatile components of a TCP/IP header of a data packet.

18. An interconnection topology system of claim 14, the routing scheme between source and destination nodes following a shortest path between the source and destination nodes under a given metric associated with the links between the plurality of nodes.