公开(公告)号：US09559985B1

公开(公告)日：2017-01-31

申请号：US14216433

申请日：2014-03-17

Applicant: GOOGLE INC.

Inventor： Fei Ye ,  Subhasree Mandal ,  Wei Sun ,  Min Zhu

IPC: H04L12/933 ,  H04L12/54

CPC classification number: H04L49/15 ,  H04L12/56 ,  H04L12/5601 ,  H04L45/12 ,  H04L49/1515 ,  H04L49/1569 ,  H04L49/256

Abstract: A technique includes determining a first set of intra-node port weights for a first switch of a first routing node, determining a set of inter-node port weights including a first inter-node port weight for routing traffic to a second routing node, determining a first inter-node weighted port group for the first switch for traffic directed to the second routing node, the first inter-node weighted port group including a first total port weight based on a first intra-node port weight and the first inter-node port weight and which is applied to a first port of the first switch, and a second total port weight based on a second intra-node port weight and the first inter-node port weight and which is applied to the second port of the first switch, and routing traffic to an output port of the first switch based on the first inter-node weighted port group.

Abstract translation: 一种技术包括确定第一路由节点的第一交换机的第一组节点内端口权重，确定一组节点间端口权重，包括用于将业务路由到第二路由节点的第一节点间端口权重，确定 第一节点间加权端口组，用于针对第二路由节点的流量的第一交换机，所述第一节点间加权端口组包括基于第一节点内端口权重的第一总端口权重和所述第一节点间节点 端口权重，并且被应用于第一交换机的第一端口，以及基于第二节点内端口权重和第一节点间端口权重的第二总端口权重，并且被应用于第一交换机的第二端口 并且基于第一节点间加权端口组将流量路由到第一交换机的输出端口。

公开(公告)号：US09736067B2

公开(公告)日：2017-08-15

申请号：US14643712

申请日：2015-03-10

Applicant: Google Inc.

Inventor： Fei Ye ,  Jiangbo Li ,  Victor Lin ,  Subhasree Mandal

IPC: H04L12/707 ,  H04L12/741 ,  H04L12/801 ,  H04L12/743 ,  H04L12/721 ,  H04L12/717

CPC classification number: H04L45/54 ,  H04L45/123 ,  H04L45/24 ,  H04L45/30 ,  H04L45/42 ,  H04L45/74 ,  H04L45/745 ,  H04L45/7453 ,  H04L47/12 ,  H04L47/17

Abstract: Methods and systems for generating a forwarding table for a packet switch. The system includes a route manager for the packet switch, configured to identify a plurality of multi-path groups each corresponding to a respective initial set of routing entries in the forwarding table and generate, for one or more multi-path groups, at least one replacement set of routing entries with fewer routing entries than the initial set corresponding to the respective multi-path group. The route manager selects, based on a traffic reduction cost metric, one or more of the replacement sets of routing entries, each corresponding to a different respective multi-path group, and updates the forwarding table with the selected replacement sets. In some implementations, the traffic reduction cost metric includes a traffic characteristic. In some implementations, the packet switch participates in a software-defined network (SDN) and the route manager is part of an SDN controller.

公开(公告)号：US09716658B1

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

申请号：US14539796

申请日：2014-11-12

Applicant: GOOGLE INC.

Inventor： Subhasree Mandal ,  Abdul Kabbani

IPC: H04L12/28 ,  H04L12/803 ,  H04L12/743

CPC classification number: H04L47/125 ,  H04L45/24 ,  H04L45/7453

Abstract: 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.

公开(公告)号：US09571400B1

公开(公告)日：2017-02-14

申请号：US14217937

申请日：2014-03-18

Applicant: GOOGLE INC.

Inventor： Subhasree Mandal ,  Abdul Kabbani

IPC: H04L12/50 ,  H04L12/803

CPC classification number: H04L47/125 ,  H04L45/24 ,  H04L45/7453

Abstract: 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.

Abstract translation: 用于数据业务的加权路由的方法可以包括基于数据分组的报头生成第一散列值，并且使用第一散列值在第一等价多路径（ECMP）表中执行查找以选择辅助ECMP表 。 第一个ECMP表可以包括至少两个辅助ECMP表的加权列表。 该方法还可以包括基于数据分组的报头生成第二哈希值，并且基于第二哈希值在所选择的辅助ECMP表中执行查找以选择数据交换机的多个出口端口的出口端口。 该方法还可以包括在选择的出口端口上转发数据分组。

公开(公告)号：US09565096B1

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

申请号：US14288972

申请日：2014-05-28

Applicant: Google Inc.

Inventor： Arjun Singh ,  Ashish Vibhakar Naik ,  Subhasree Mandal

IPC: G06F13/00 ,  H04L12/707 ,  H04L12/755

CPC classification number: H04L45/24 ,  H04L45/021 ,  H04L45/54 ,  H04L45/7453 ,  H04L47/125

Abstract: System and methods for efficiently distributing data packets in a multi-path network having a plurality of equal cost paths each having the same number of hops are provided. In one aspect, a system and method includes reordering the entries in the routing table of one or more peer routing devices, such that succeeding equal cost next hop routing devices that are interconnected in a Clos formation to the peer routing devices received unbiased traffic from each of the peer routing devices, thus enabling the succeeding next hop routing devices to distribute data traffic evenly over additional equal cost multiple hops further into the network.

Abstract translation: 提供了一种用于在具有多个具有相同跳数的等价成本路径的多路径网络中有效分配数据分组的系统和方法。 一方面，系统和方法包括重新排序一个或多个对等路由设备的路由表中的条目，使得在Clos形式中互连到对等路由设备的成功的等价成本下一跳路由设备从每个路由设备接收到无偏差业务 的对等路由设备，从而使后续的下一跳路由设备能够将数据流量均匀地分布到进一步进入网络的额外的等成本多跳中。

公开(公告)号：US20150326476A1

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

申请号：US14643712

申请日：2015-03-10

Applicant: Google Inc.

Inventor： Fei Ye ,  Jiangbo Li ,  Victor Lin ,  Subhasree Mandal

IPC: H04L12/741 ,  H04L12/801 ,  H04L12/707

CPC classification number: H04L45/54 ,  H04L45/123 ,  H04L45/24 ,  H04L45/30 ,  H04L45/42 ,  H04L45/74 ,  H04L45/745 ,  H04L45/7453 ,  H04L47/12 ,  H04L47/17

Abstract: Methods and systems for generating a forwarding table for a packet switch. The system includes a route manager for the packet switch, configured to identify a plurality of multi-path groups each corresponding to a respective initial set of routing entries in the forwarding table and generate, for one or more multi-path groups, at least one replacement set of routing entries with fewer routing entries than the initial set corresponding to the respective multi-path group. The route manager selects, based on a traffic reduction cost metric, one or more of the replacement sets of routing entries, each corresponding to a different respective multi-path group, and updates the forwarding table with the selected replacement sets. In some implementations, the traffic reduction cost metric includes a traffic characteristic. In some implementations, the packet switch participates in a software-defined network (SDN) and the route manager is part of an SDN controller.

Abstract translation: 用于生成分组交换机的转发表的方法和系统。 该系统包括用于分组交换机的路由管理器，用于识别多个多路径组，每个多路径组对应于转发表中相应的初始路由条目集合，并为一个或多个多路径组生成至少一个 具有比对应于相应多路径组的初始集更少的路由条目的路由条目的替换集合。 路由管理器基于流量降低成本度量来选择一个或多个路由条目的替换集合，每个路由条目对应于不同的相应多路径组，并且用所选择的替换集合更新转发表。 在一些实现中，流量降低成本度量包括业务特性。 在一些实现中，分组交换机参与软件定义的网络（SDN），路由管理器是SDN控制器的一部分。

公开(公告)号：US09014191B1

公开(公告)日：2015-04-21

申请号：US13630797

申请日：2012-09-28

Applicant: Google Inc.

Inventor： Subhasree Mandal ,  Amin Vahdat

IPC: H04L12/28 ,  H04L12/26

CPC classification number: H04L12/2621 ,  H04L12/4633 ,  H04L12/4641 ,  H04L45/04 ,  H04L45/46 ,  H04L45/58 ,  H04L45/74

Abstract: Systems and techniques for forwarding a data packet between network components in a virtualized network system are presented. Virtual machines in each virtual network in the virtualized network system are mapped to a unique routing table. Internet protocol (IP) addresses of virtual machines in a virtual network can overlap with IP addresses of virtual machines in another virtual network. A data packet is associated with a particular virtual network based on a tag stored in the data packet. As such, the data packet is forwarded based on a particular routing table associated with the particular virtual network. Additionally, routing domain information can be encoded into an outer source IP field of the data packet at the beginning of an IP tunnel. Furthermore, the routing domain information in the outer source IP field can be used to forward the data packet at the end of the IP tunnel.

Abstract translation: 提出了在虚拟化网络系统中的网络组件之间转发数据分组的系统和技术。 虚拟化网络系统中每个虚拟网络中的虚拟机映射到唯一的路由表。 虚拟网络中的虚拟机的互联网协议（IP）地址可能与另一个虚拟网络中的虚拟机的IP地址重叠。 基于存储在数据分组中的标签，数据分组与特定虚拟网络相关联。 因此，基于与特定虚拟网络相关联的特定路由表来转发数据分组。 另外，路由域信息可以被编码到IP隧道开始处的数据分组的外部源IP字段。 此外，外部源IP字段中的路由域信息可用于在IP隧道末端转发数据包。

公开(公告)号：US09806993B1

公开(公告)日：2017-10-31

申请号：US14449871

申请日：2014-08-01

Applicant: Google, Inc.

Inventor： Subhasree Mandal ,  James Wanderer

IPC: H04L12/28 ,  H04L12/707 ,  H04L12/741

CPC classification number: H04L45/24 ,  H04L45/54 ,  H04L45/745

Abstract: Techniques for multi-path routing of packets to a destination node based on multiple routing tables of a router device. In an embodiment, a router device includes port groups which each correspond to a different respective network path to the same destination node. In another embodiment, each routing engine of multiple routing engines in a router device routes packets to the destination node based on a different respective one of multiple routing tables. The routing tables may include respective entry sets which, at least with respect to routing packets to the destination node, dedicate each routing engine to a respective one of the port groups.

公开(公告)号：US09369408B1

公开(公告)日：2016-06-14

申请号：US14176625

申请日：2014-02-10

Applicant: Google Inc.

Inventor： Barath Raghavan ,  Subhasree Mandal ,  Mohammad Alfares ,  John Mccullough ,  Fei Ye ,  Min Zhu ,  Aravind Ravisankar

IPC: G01R31/08 ,  H04L12/939 ,  H04L12/26

CPC classification number: H04L49/557 ,  H04L43/08 ,  H04L43/0888

Abstract: Aspects and implementations of the present disclosure generally relate to use of a multi-chassis link aggregation for high performance and resilience in wide-area networking. In one aspect, the disclosure relates to a system that includes a switch fabric. The fabric includes at least a plurality of edge network devices, a set of internal switch devices, and a plurality of internal network links coupling each edge network device to at least a subset of the set of internal switch devices. The system includes a network controller coupled to the switch fabric, configured to maintain at least one link aggregation comprising a logical grouping of externally facing network interfaces of at least two of the plurality of edge devices. The network controller is configured to monitor internal link performance characteristics and determine throughput characteristics for each link aggregation over time based at least in part on current internal link performance characteristics.

Abstract translation: 本公开的方面和实施方式一般涉及在多区域网络中使用多机箱链路聚合以实现高性能和弹性。 一方面，本发明涉及一种包括交换结构的系统。 该结构包括至少多个边缘网络设备，一组内部交换设备和将每个边缘网络设备耦合到该组内部交换机设备的至少一个子集的多个内部网络链路。 该系统包括耦合到交换结构的网络控制器，被配置为维持至少一个链路聚合，其包括多个边缘设备中的至少两个的外部面向的网络接口的逻辑分组。 网络控制器被配置为至少部分地基于当前的内部链路性能特征来监视内部链路性能特征并且确定每个链路聚合随时间的吞吐量特性。

公开(公告)号：US20140355415A1

公开(公告)日：2014-12-04

申请号：US14459670

申请日：2014-08-14

Applicant: Google Inc.

Inventor： Subhasree Mandal ,  Subbaiah Venkata ,  Leon Poutievski ,  Amit Gupta ,  Min Zhu ,  Rajiv Ramanathan ,  James M. Wanderer ,  Joon Ong

IPC: H04L12/24 ,  H04L12/703

CPC classification number: H04L41/0668 ,  H04L41/12 ,  H04L45/28 ,  H04L45/38 ,  H04L45/42 ,  H04L45/64

Abstract: Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for semi-centralized routing. In one aspect, a computer-implemented method receives a network protocol packet at a router adapted for routing data packets to one or more additional routers. The network protocol packet conforms to a routing protocol that provides distributed routing computation. The method also sends the network protocol packet, through a controller, to a selected one of a plurality of route control servers. The method also processes the network control packet at the selected route control server to generate a routing computation result that conforms to the routing protocol. The method also generates routing information based on the routing computation. The routing information conforms to a control protocol that provides centralized routing computation. The method also sends the routing information to the router for routing of data packets based on the control protocol.

Abstract translation: 方法，系统和装置，包括在计算机存储介质上编码的计算机程序，用于半集中式路由。 在一个方面，计算机实现的方法在适于将数据分组路由到一个或多个附加路由器的路由器处接收网络协议分组。 网络协议分组符合提供分布式路由计算的路由协议。 该方法还通过控制器将网络协议分组发送到多个路由控制服务器中的所选择的一个。 该方法还处理所选择的路由控制服务器上的网络控制分组，以生成符合路由协议的路由计算结果。 该方法还基于路由计算生成路由信息。 路由信息符合提供集中式路由计算的控制协议。 该方法还根据控制协议将路由信息发送给路由器进行路由数据包路由。