Systems and methods for routing data through data centers using an indirect generalized hypercube network

{
  "publication_number": "US9705798B1",
  "country": "US",
  "kind": "B1",
  "title": "Systems and methods for routing data through data centers using an indirect generalized hypercube network",
  "abstract": "Aspects and implementations of the present disclosure are directed to an indirect generalized hypercube network in a data center. Servers in the data center participate in both an over-subscribed fat tree network hierarchy culminating in a gateway connection to external networks and in an indirect hypercube network interconnecting a plurality of servers in the fat tree. The participant servers have multiple network interface ports, including at least one port for a link to an edge layer network device of the fat tree and at least one port for a link to a peer server in the indirect hypercube network. Servers are grouped by edge layer network device to form virtual switches in the indirect hypercube network and data packets are routed between servers using routes through the virtual switches. Routes leverage properties of the hypercube topology. Participant servers function as destination points and as virtual interfaces for the virtual switches.",
  "claims": [
    "1. A system comprising: a first rack in a data center equipped with a first rack switch and a first server with at least a first network interface on the first server having a first network address and a second network interface on the first server having a second network address, the second network address comprising a virtual switch identifier identifying the first rack switch and a dimension identifier identifying a position of the first server in the first rack, the first server storing the second network address; a second rack in the data center equipped with a second rack switch and a second server with at least a first network interface on the second server and a second network interface on the second server; a first bi-directional network link directly connecting the first network interface on the first server in the first rack to the first rack switch; a second bi-directional network link directly connecting the first network interface on the second server in the second rack to the second rack switch; and a third bi-directional network link directly connecting the second network interface on the first server in the first rack to the second network interface on the second server in the second rack.",
    "2. The system of claim 1, wherein the first rack in the data center is equipped with a fourth server with at least a first network interface on the fourth server and a second network interface on the fourth server, the system further comprising: a third rack in the data center equipped with a third rack switch and a third server with at least a first network interface on the third server and a second network interface on the third server; a fourth network link directly connecting the first network interface on the fourth server in the first rack to the first rack switch; a fifth network link connecting the first network interface on the third server in the third rack to the third rack switch; and a sixth network link directly connecting the second network interface on the fourth server in the first rack to the second network interface on the third server in the third rack.",
    "3. The system of claim 1, wherein each respective server is configured to determine if a data packet received at the server is addressed to a server other than the respective server and in response to determining that the received data packet is not addressed to the respective server, forward the data packet over one of the network interfaces of the server other than a network interface over which the data packet was received.",
    "4. The system of claim 1, wherein the first server is equipped with a network interface controller controlling the first network interface on the first server and the second network interface on the first server.",
    "5. The system of claim 1, wherein the first server is configured to: monitor congestion data for a first route that uses the third bi-directional network link directly connecting the second network interface on the first server in the first rack to the second network interface on the second server in the second rack; and determine whether to use the first route to transmit a data packet based on the congestion data.",
    "6. The system of claim 1, wherein the first rack switch is configured to maintain a routing table for routing data packets addressed to servers within the data center, wherein the routing table includes at least one entry for forwarding a data packet via a bi-directional network link between a server in the first rack and a server in another rack.",
    "7. The system of claim 1, wherein: the second network interface on the second server has a third network address, the third network address comprising a virtual switch identifier for the second rack and the dimension identifier.",
    "8. The system of claim 5, wherein the first server is configured to: use the first route for the data packet when the congestion data indicates that the first route is not congested, and use a second route for the data packet when the congestion data indicates that the first route is congested.",
    "9. The system of claim 6, wherein the routing table stores an indirect generalized hypercube network routing topology for the data center.",
    "10. A method of configuring multiple server racks in a data center, the method comprising: configuring a first rack in a data center with a first rack switch and a first server with at least a first network interface on the first server having a first network address and a second network interface on the first server having a second network address, the second network address comprising a virtual switch identifier identifying the first rack switch and a dimension identifier identifying a position of the first server in the first rack, the first server storing the second network address; configuring a second rack in the data center with a second rack switch and a second server with at least a first network interface on the second server and a second network interface on the second server; configuring a first bi-directional network link connecting the first network interface on the first server in the first rack to the first rack switch; configuring a second bi-directional network link directly connecting the first network interface on the second server in the second rack to the second rack switch; and configuring a third bi-directional network link directly connecting the second network interface on the first server in the first rack to the second network interface on the second server in the second rack.",
    "11. The method of claim 10 comprising: configuring a third rack in the data center with a third rack switch and a third server with at least a first network interface on the third server and a second network interface on the third server; configuring the first rack in the data center with a fourth server with at least a first network interface on the fourth server and a second network interface on the fourth server; configuring a fourth bi-directional network link directly connecting the first network interface on the fourth server in the first rack to the first rack switch; configuring a fifth bi-directional network link directly connecting the first network interface on the third server in the third rack to the third rack switch; and configuring a sixth bi-directional network link directly connecting the second network interface on the fourth server in the first rack to the second network interface on the third server in the third rack.",
    "12. The method of claim 10, wherein each respective server is configured to determine if a data packet received at the server is addressed to a server other than the respective server and in response to determining that the received data packet is not addressed to the respective server, forward the data packet over one of the network interfaces of the server other than a network interface over which the data packet was received.",
    "13. The method of claim 10, wherein the first server is equipped with a network interface controller controlling the first network interface on the first server and the second network interface on the first server.",
    "14. The method of claim 10, comprising configuring the first server to: monitor congestion data for a first route that uses the third bi-directional network link directly connecting the second network interface on the first server in the first rack to the second network interface on the second server in the second rack; and determine whether to use the first route to transmit a data packet based on the congestion data.",
    "15. The method of claim 10, wherein the first rack switch is configured to maintain a routing table for routing data packets addressed to servers within the data center, wherein the routing table includes at least one entry for forwarding a data packet via a bi-directional network link between a server in the first rack and a server in another rack.",
    "16. The method of claim 10, wherein: the second network interface on the second server has a third network address, the third network address comprising a virtual switch identifier for the second rack and the dimension identifier.",
    "17. The method of claim 14, comprising configuring the first server to: use the first route for the data packet when the congestion data indicates that the first route is not congested, and use a second route for the data packet when the congestion data indicates that the first route is congested.",
    "18. The method of claim 15, wherein the routing table stores an indirect generalized hypercube network routing topology for the data center."
  ],
  "description_excerpt": "Servers in a data center are frequently arranged as leaf nodes in a “fat tree” of network devices that connect the servers to external networks. A fat tree can be generalized into three layers: an edge layer connecting to servers, an intermediary aggregation layer, and a root gateway layer connecting the tree to external networks. Each layer includes one or more network devices each bi-directionally linked to multiple devices in a lower layer. The bandwidth of each link is generally greater than (or “fatter” than) the bandwidth for a link at a lower layer. However, the aggregate bandwidth of the multiple links is generally reduced. As a result, in some cases, the upper layers of the fat tree are unable to accommodate the bandwidth demands of lower devices were they all to maximize their use of the provisioned bandwidth. That is, in many cases, the upper layers are over-subscribed and/or the lower layers are over-provisioned.\n\nIn one aspect, the disclosure relates to a system. The system includes at least a first rack in a data center equipped with a first rack switch and a first server with at least a first network interface on the first server and a second network interface on the first server and a second rack in the data center equipped with a second rack switch and a second server with at least a first network interface on the second server and a second network interface on the second server.",
  "cpc": [
    "H04L 47/122",
    "H04L 43/0888",
    "H04L 45/22"
  ],
  "ipc": [
    "H04L 45/24"
  ],
  "assignees": [
    "Google LLC"
  ],
  "inventors": [
    "Dennis Charles Abts",
    "Abdul Kabbani",
    "Robert Felderman"
  ],
  "filing_date": "2014-01-07",
  "publication_date": "2017-07-11",
  "grant_date": "2017-07-11",
  "priority_date": "2014-01-07",
  "application_number": "US-201414149469-A",
  "family_id": "59257594",
  "cited_by_count": 19,
  "citations": [
    "US6456588B1",
    "US6151297A",
    "US6696917B1",
    "US20120230182A1",
    "US8065433B2",
    "US20120026917A1",
    "US20110258340A1",
    "US8412919B2",
    "US20130111070A1",
    "US20140298113A1",
    "US20130250802A1",
    "US20140122560A1",
    "US9288101B1"
  ]
}