公开(公告)号：US09876705B1

公开(公告)日：2018-01-23

申请号：US15377645

申请日：2016-12-13

申请人： Google Inc.

发明人： Leon Poutievski ,  Amin Vahdat ,  Ashish Naik

IPC分类号： H04L12/28 ,  H04L12/751 ,  H04L12/24 ,  H04L12/931

CPC分类号： H04L45/02 ,  H04L41/0816 ,  H04L41/12 ,  H04L49/35

摘要： A system and method are provided for updating a network including at least one optical circuit switch (OCS) to transition from an existing network topology to a new network topology. One or more intermediate topologies between the existing topology and the new topology are created. Creating the intermediate topologies includes selecting first links to be added to the existing topology without removing links, selecting additional links to be added to the existing topology upon removal of one or more existing links, and adding one or more of the selected first and additional links to the existing topology to create a first intermediate topology. It is determined whether any of the selected first and additional links are still to be added, and if no selected first and additional links are to be added, remaining links are removed. The transition from the existing topology to the first intermediate topology is then effected.

公开(公告)号：US09307013B1

公开(公告)日：2016-04-05

申请号：US13905353

申请日：2013-05-30

申请人： Google Inc.

发明人： Abdul Kabbani ,  Amin Vahdat

IPC分类号： G06F15/16 ,  H04L29/08 ,  G06F3/12 ,  G06F9/48

CPC分类号： G06F9/4843 ,  G06F3/1262 ,  H04L67/1002

摘要： The present disclosure describes a system and method for reducing total batch completion time using a max-min fairness process. In some implementations, the max-min fairness process described herein reduces the batch completion time by collectively routing the batches in a way that targets providing the same effective path capacity across all requests. More particularly, given a network shared by batches of flows, total throughput is increased with max-min fairness (and therefore batch completion time decreased) if the nth percentile fastest flow of a batch cannot increase its throughput without decreasing the nth percentile fastest flow of another batch whose throughput is not greater than the throughput of the first batch.

摘要翻译： 本公开描述了使用最大 - 最小公平过程来减少总批量完成时间的系统和方法。 在一些实施方案中，本文描述的最大 - 最小公平性过程通过以指向在所有请求之间提供相同有效路径容量的方式集体路由批次来减少批次完成时间。 更具体地说，给定由批量流量共享的网络，如果批次的第n百分位数最快的流量不能增加其吞吐量而不减少第n百分位数最快的流量，则总吞吐量以最大 - 最小公平性（并且因此批次完成时间减少）增加 另一批的吞吐量不大于第一批的吞吐量。

公开(公告)号：US09288146B1

公开(公告)日：2016-03-15

申请号：US13903676

申请日：2013-05-28

申请人： Google Inc.

发明人： Abdul Kabbani ,  Amin Vahdat

IPC分类号： G06F15/16 ,  H04L12/801

CPC分类号： H04L47/10 ,  H04L45/125

摘要： 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.

摘要翻译： 本公开描述了使用每目的地最大 - 最小公平方案来减少总批量完成时间的系统和方法。 在分布式计算机系统中，工作者节点通常同时向服务器节点返回响应。 在一些分布式计算机系统中，多个批次可以在任何一个给定时间穿过网络。 网络的节点通常不知道其他节点通过网络发送的批次。 因此，在一些实现中，当节点通过正在或已经成为瓶颈的链路发送流时，不同批次遇到不同的有效路径容量。 本文描述的每目的地最大 - 最小公平性方案通过以不提供基本上均匀的传输时间的方式集体路由批次来减少总批次完成时间，而不在网络不充分利用的情况下。

公开(公告)号：US09247326B2

公开(公告)日：2016-01-26

申请号：US14169734

申请日：2014-01-31

申请人： Google Inc.

发明人： Ryohei Urata ,  Hong Liu ,  Amin Vahdat ,  Christopher Lyle Johnson ,  Junlan Zhou ,  Alexander Shraer

IPC分类号： H04Q11/00 ,  G06F13/40

CPC分类号： H04Q11/0005 ,  G06F13/4022 ,  H04Q11/0062 ,  H04Q2011/0015 ,  H04Q2011/0052 ,  Y02D10/14 ,  Y02D10/151

摘要： Systems and methods for increasing bandwidth in a computer network are provided. A computer network can include a first lower level switch having a first port and a second port. The computer network can include a second lower level switch having a first port and a second port. The computer network can include an upper level switch having respective ports directly coupled to ports of the first and second lower level switches. A third port of the upper level switch can couple to a first port of a passive optical splitter. The passive optical splitter can have second and third ports coupled to respective ports of the first and second lower level switches. The passive optical splitter can be configured to transmit signals received at its first port as output signals on both of its second and third ports.

摘要翻译： 提供了一种用于增加计算机网络带宽的系统和方法。 计算机网络可以包括具有第一端口和第二端口的第一下级开关。 计算机网络可以包括具有第一端口和第二端口的第二下层开关。 计算机网络可以包括具有直接耦合到第一和第二下级交换机的端口的相应端口的上级交换机。 上级开关的第三端口可以耦合到无源分光器的第一端口。 无源光分路器可以具有耦合到第一和第二下层开关的相应端口的第二和第三端口。 无源光分路器可以被配置为将在其第一端口处接收的信号作为其第二和第三端口两端的输出信号进行发送。

公开(公告)号：US09184999B1

公开(公告)日：2015-11-10

申请号：US13872626

申请日：2013-04-29

申请人： Google Inc.

发明人： Abdul Kabbani ,  Amin Vahdat

IPC分类号： H04L1/00 ,  H04L12/24

CPC分类号： H04L41/0823 ,  H04L41/12 ,  H04L41/145

摘要： A system for configuring a network topology in a data center is disclosed. The data center includes nodes having ports capable of supporting data links that can be connected to other nodes. The system includes a memory and a processing unit coupled to the memory. The processing unit receives demand information indicative of demands between nodes. The processing unit determines a set of constraints on the network topology based on the nodes, feasible data links between the nodes, and the demand information. The processing unit determines an objective function based on a sum of data throughput across data links satisfying demands. The processing unit performs an optimization of the objective function subject to the set of constraints using a linear program. The processing unit configures the network topology by establishing data links between the nodes according to results of the optimization.

摘要翻译： 公开了一种用于在数据中心中配置网络拓扑的系统。 数据中心包括具有能够支持可连接到其他节点的数据链路的端口的节点。 该系统包括耦合到存储器的存储器和处理单元。 处理单元接收指示节点之间的需求的需求信息。 处理单元基于节点，节点之间的可行数据链路和需求信息来确定网络拓扑上的一组约束。 处理单元基于满足需求的数据链路之间的数据吞吐量的总和来确定目标函数。 处理单元使用线性程序来执行受约束集合的目标函数的优化。 处理单元通过根据优化结果在节点之间建立数据链路来配置网络拓扑。

公开(公告)号：US20150180778A1

公开(公告)日：2015-06-25

申请号：US14139150

申请日：2013-12-23

申请人： Google Inc.

发明人： Alexander Shraer ,  Junlan Zhou ,  Amin Vahdat

IPC分类号： H04L12/801

CPC分类号： H04L49/205 ,  H04L45/125 ,  H04L47/10 ,  H04L47/125 ,  H04L49/356

摘要： The present disclosure provides for the determination of bandwidth allocation of inter-block traffic in a data center network. It employs a number of optimization objectives and a heuristic water-filling strategy to avoid producing unnecessary paths and to avoid determining paths that would be unavailable when actually needed. Allocation may be adjusted incrementally upon node and link failure, for instance to perform only the minimal allocation changes necessary. If demand between a source and a destination cannot be satisfied, a decomposition process may be used to allocate remaining demand. One aspect constructs a graph for route computation based on inter-block topology. Here, the graph initially starts with a highest level of abstraction with each node representing a middle block, and gradually reduces the abstraction level to identify paths of mixed abstraction level to satisfy additional demand.

摘要翻译： 本公开提供了确定数据中心网络中的块间业务的带宽分配。 它采用了一些优化目标和启发式注水策略，以避免产生不必要的路径，并避免确定在实际需要时不可用的路径。 在节点和链路故障时，分配可以逐渐调整，例如仅执行必要的最小分配更改。 如果源和目的地之间的需求不能满足，则可以使用分解处理来分配剩余的需求。 一方面构建了基于块间拓扑的路由计算图。 这里，图形最初以最高级别的抽象开始，每个节点表示一个中间块，并逐渐降低抽象级别，以识别混合抽象级别的路径以满足额外的需求。

公开(公告)号：US09705740B2

公开(公告)日：2017-07-11

申请号：US14276399

申请日：2014-05-13

申请人： Google Inc.

发明人： Leon Poutievski ,  Amin Vahdat

IPC分类号： G06F15/16 ,  H04L12/24 ,  G06F13/38 ,  H04L12/717 ,  H04L12/70

CPC分类号： H04L41/0813 ,  G06F13/385 ,  G06F2213/3808 ,  H04L45/42 ,  H04L47/00

摘要： As an overview, the present disclosure presents a system for increasing network optimization. In particular, the disclosure discusses a unified system for control of data routing in a dynamic network. In some implementations, edge devices (i.e., hosts or exterior switches) are interconnected through a network fabric (i.e., a plurality of interior switches). The hosts and switches include forwarding engines, which determine the next destination of incoming traffic. The disclosure discusses a network controller that collects application requirements and programs the forwarding engines of the edge devices and the network fabric responsive to the application requirements.

公开(公告)号：US09692639B1

公开(公告)日：2017-06-27

申请号：US13932703

申请日：2013-07-01

申请人： Google Inc.

发明人： Abdul Kabbani ,  Amin Vahdat

IPC分类号： G06F15/177 ,  H04L12/24

CPC分类号： H04L41/12

摘要： 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.

公开(公告)号：US09660886B1

公开(公告)日：2017-05-23

申请号：US14444156

申请日：2014-07-28

申请人： Google Inc.

发明人： Fei Ye ,  Shidong Zhang ,  Mickey Ju ,  Joon Ong ,  Amin Vahdat ,  Hongyi Zeng

IPC分类号： H04L12/26 ,  H04L12/939 ,  H04L12/58 ,  H04L12/751 ,  H04L12/24

CPC分类号： H04L43/0823 ,  H04L41/065 ,  H04L41/0677 ,  H04L41/12 ,  H04L43/0876 ,  H04L45/02 ,  H04L49/55 ,  H04L51/30

摘要： This disclosure provides systems, methods and apparatus for providing a network verification system (NVS) to analyze and detect anomalies and errors within a network. The NVS requests forwarding tables from each of the switches within the network being analyzed, and generates directed forwarding graphs for each subnet within the network. Certain graph properties of the directed forwarding graphs are analyzed to detect anomalies or errors in the subnets represented by the directed forwarding graphs. In some implementations, the NVS can execute the generation of the directed forwarding graphs in parallel. In some implementations, the NVS can be implemented on a MapReduce system.

公开(公告)号：US09608913B1

公开(公告)日：2017-03-28

申请号：US14223645

申请日：2014-03-24

申请人： GOOGLE INC.

发明人： Abdul Kabbani ,  Jahangir Hasan ,  Amin Vahdat

IPC分类号： H04L12/803 ,  H04L12/743

CPC分类号： H04L47/125 ,  H04L45/7457

摘要： 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.