Google Inc.

Abdul Kabbani

Amin Vahdat

Robert Edman Felderman

Dennis Charles Abts

Subhasree Mandal

Arjun Singh

Jahangir Hasan

A method for weighted data traffic routing can include receiving a data packet at data switch, where the data switch includes a plurality of egress ports. The method can also include, for each of the egress ports, generating an independent hash value based on one or more fields of the data packet and generating a weighted hash value by scaling the hash value using a scaling factor. The scaling factor can be based on at least two traffic routing weights of a plurality of respective traffic routing weights associated with the plurality of egress ports. The method can further include selecting an egress port of the plurality of egress ports based on the weighted hash value for each of the egress ports and transmitting the data packet using the selected egress port.

Weighted load balancing using scaled parallel hashing

A system includes a plurality of rate limiters and a rate limiter management module. The rate limiter management module causes a processor to analyze and compare a plurality of flows each having at least one aggregation attribute, to aggregate a first group of the plurality of flows into a first aggregate flow based on the at least one aggregation attribute, and to assign the first aggregate flow to a rate limiter having at least one membership criterion. The first aggregate flow includes flows having the at least one aggregation attribute that satisfies the at least one membership criterion.

Shared rate limiting

Aspects and implementations of the present disclosure are directed to an indirect generalized hypercube network in a computer network facility. Servers in the computer network facility 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.

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

A method for weighted routing of data traffic can include generating a first hash value based on a header of a data packet and performing a lookup in a first ECMP table using the first hash value to select a secondary ECMP table from at least two secondary un-weighted ECMP tables, the first ECMP table including a weighted listing of the at least two secondary un-weighted ECMP tables. The method can also include generating a second hash value based on the header of the data packet and performing a lookup in the selected secondary ECMP table based on the second hash value to select an egress port of a plurality of egress ports of the data switch and forwarding the data packet on the selected egress port.

Weighted load balancing in a multistage network using heirachical ECMP

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.

Systems and methods of configuring a computer network are provided. A first stage having F switches and a second stage having S switches can be provided. Each switch in the first stage of switches can form M communication links with switches in the second stage of switches. Each switch in the second stage can form N communication links with switches in the first stage of switches. Communication links between respective switch pairs can be assigned. Each switch pair can include one witch in the first stage of switches and one switch in the second stage of switches. The number of communication links assigned to at least one switch pair can differ from the number of communication links assigned to at least a second switch pair.

Achieving full bandwidth usage and max-min fairness in a computer network

A method for weighted data traffic routing can include generating an integer hash value based on a header of a data packet and encoding the integer hash value to generate a search key for a content addressable memory included in the data switch. The method can also include performing a lookup in the content addressable memory to match the search key with one of a plurality of prefixes stored in the content addressable memory, the plurality of prefixes including an encoded set of routing weights associated with a plurality of egress ports of the data switch. The method can further include forwarding the data packet on an egress port of the plurality of egress ports associated with the one of the plurality of prefixes in the content addressable memory.

Weighted load balancing in a multistage network

A method for weighted routing of data traffic can include generating a first hash value based on a header of a data packet and performing a lookup in a first equal cost multi-path (ECMP) table using the first hash value to select a secondary ECMP table. The first ECMP table can include a weighted listing of at least two secondary ECMP tables. The method can further include generating a second hash value based on the header of the data packet and performing a lookup in the selected secondary ECMP table based on the second hash value to select an egress port of a plurality of egress ports of the data switch. The method can further include forwarding the data packet on the selected egress port.

Weighted load balancing in a multistage network using hierarchical ECMP

A technique includes transmitting traffic to a destination via at least a first path of a plurality of paths to the destination, each path including one or more path segments, a plurality of ports being associated with each path segment, receiving port congestion information for each of the ports, determining whether each of the plurality of path segments is congested based on the port congestion information, making a first determination that the first path is congested and that one or more second paths are not congested, each of the paths is determined to be congested if one or more path segments of the path is congested, and re-routing at least some traffic directed to the destination from the congested first path to one or more of the uncongested second paths in response to the first determination.

Shortest first longer next routing with congestion reduction

Systems and methods of configuring a computer network are provided. N network nodes can each form M communication links with other network nodes. A number of communication links equal to the largest integer not greater than the quotient of M divided by (N&#x2212;1) can be assigned between each pair of network nodes. The remaining communication links can be assigned such that a graph represented by the network nodes and communication links is substantially geometrically symmetric.

Achieving balanced interconnectivity in a computer network

Systems and methods for managing computer network activity are disclosed. A data flow to be transmitted between a source node and a destination node can be identified. An initial graph representing the computer network can be determined. A shortest path between the source node and the destination node can be identified based on the graph. Bandwidth can be allocated to communication links along the shortest path between the source node and the destination node. It can be determined whether a bandwidth requirement associated with the data flow is satisfied by the allocated bandwidth. A residual graph can be determined. The steps of identifying a shortest path between the source node and the destination node based on the residual graph and allocating bandwidth to communication links along the shortest path between the source node and the destination node can be repeated.

Minimum latency routing

A non-transitory computer-readable storage medium may include instructions stored thereon that. When executed by at least one processor, the instructions may be configured to cause a computing system to at least determine which links connecting old super blocks to old spine blocks via a plurality of Optical Circuit Switches (OCSs) in a network to disconnect to accommodate at least one new super block and at least one new spine block being added to a switching network, the determining including determining a maximum of m links per OCS to disconnect, connect the old super blocks to the at least one new spine block via the OCSs associated with the links to be disconnected, and connect the at least one new super block to the old spine blocks via the OCSs associated with the links to be disconnected.

Distributing link cuts between switches in a network

A non-transitory computer-readable storage medium may include instructions stored thereon that, when executed by at least one processor, are configured to cause a computing system to at least cut a surplus link at a first switch between an old super block and an old spine block, add a first new link between the old super block and a new spine block, add a second new link between the old spine block and a new super block, continue to cut surplus links and add new links until determining that adding a new link at the first switch would result in an excess of links, and swap a link from the first switch with a link from a second switch.

Growing community of inventors

Los Gatos, CA, United States of America

Abdul Kabbani