US 9,288,146 B1Granted

Reducing batch completion time in a computer network with per-destination max-min fairness

AssigneeGoogle Inc.

InventorsAbdul Kabbani, Amin Vahdat

Life of this patent

Estimating the term…

Loading patent…

Abstract

The present disclosure describes a system and method for reducing total batch completion time using a per-destination max-min fairness scheme. In a distributed computer system, worker nodes often simultaneously return responses to a server node. In some distributed computer systems, multiple batches can traverse a network at any one given time. The nodes of the network are often unaware of the batches other nodes are sending through the network. Accordingly, in some implementations, the different batches encounter different effective path capacities as nodes send flows through links that are or become bottlenecked. The per-destination max-min fairness scheme described herein reduces the total batch completion time by collectively routing the batches in a way that targets providing substantially uniform transmission times without under underutilizing the network.

Claims20

Dependent claims

A system for determining routes for data flows across a network, the system comprising:

a memory to store processor-executable instructions;
and
a processing unit coupled to the memory, wherein execution of the processor-executable instructions by the processing unit causes the processing unit to:
receive a network topology of a plurality of data links that connect a plurality of source nodes to a plurality of second level nodes;
determine a proportion of data to traverse over each of the plurality of data links from each of the respective plurality of source nodes by:
maintaining, for each of the data links in the network, a corresponding virtual link;
determining a throughput allocation for each of the virtual links;
iteratively, until all of the second level nodes are fully utilized:
identify a subset of the plurality of second level nodes having additional capacity;
and
increase the bandwidth capacity of the virtual links corresponding to the identified subset of the plurality of second level nodes;
and
implement a forwarding weight between each of the plurality of source nodes and each of the plurality of second level nodes in the network topology responsive to the determined proportion of the data allocated to each of the respective virtual links, wherein implementing the forwarding weight comprises at least one of selecting a path for each of a plurality of data flows and setting a flow rate limiter for each of the plurality of source nodes.

10 more elements

A non-transitory computer readable storage medium having instructions encoded thereon which, when executed by a processor, cause the processor to perform a method for determining routes for data flows across a network, the method comprising:

receiving a network topology of a plurality of data links that connect a plurality of source nodes to a plurality of second level nodes;
determining a proportion of data to traverse over each of the plurality of data links from each of the respective plurality of source nodes by:
maintaining, for each of the data links in the network, a corresponding virtual link;
determining a throughput allocation for each of the virtual nodes/links;
iteratively, until all of the second level nodes are fully utilized:
identifying a subset of the plurality of second level nodes having additional capacity;
and
increasing the bandwidth capacity of the virtual links corresponding to the identified subset of the plurality of second level nodes;
and
implementing a forwarding weight between each of the plurality of source nodes and each of the plurality of second level nodes in the network topology responsive to the determined proportion of the data allocated to each of the respective virtual links, wherein implementing the forwarding weight comprises at least one of selecting a path for each of a plurality of data flows and setting a flow rate limiter for each of the plurality of source nodes.

7 more elements

Dependencies are inferred from the claim text.