Google Inc.

X Development LLC

Fei Ye

Subhasree Mandal

Victor Lin

Jun Gong

Jiangbo Li

Min Zhu

Zhifeng Sun

Jeff Gilbert

Amin Vahdat

Yifang Liu

Joon Suan Ong

Shidong Zhang

Clemens Buehling

Qingxi Li

Wei Sun

Aravind Ravisankar

John Mccullough

Mohammad Alfares

Barath Raghavan

Hongyi Zeng

Mickey Ju

A method for matching a ground station to an aerial vehicle for establishment of a backhaul link to an airborne network involves: (i) determining location information for a ground station that is configured to provide a backhaul link to an airborne mesh network, (ii) determining flight data for one or more of the aerial vehicles in the airborne mesh network, (iii) based at least in part on the combination of (a) the location information for the ground station and (b) the flight data for the one or more of the aerial vehicles, selecting a flight with which the ground station should establish a backhaul link to the airborne network, and (iv) generating a link-assignment message that comprises instructions for the ground station to establish a backhaul link between the ground station and an aerial vehicle carrying out the selected flight.

Coordinating backhaul links between ground stations and airborne backhaul network

A system and method for social-aware clustering of user data replicas in a large-scale distributed computing system is disclosed. An exemplary system finds at least one user's connected users based on communications between the user and other users. The datacenters that contain the user replicas of the user's connected users are found. Connections and connection weights between the user and the user's connected users' datacenters are computed. The preferred datacenters for the user's current user data replica is computed based on the location of the connected datacenters and the weights of the connections. An optimization model minimizes the distance between the user's current datacenter and the user's preferred datacenter to reduce network traffic and central processing unit usage and determines the user's datacenter. The user's current datacenter is updated to the datacenter determined by running the optimization model.

Social-aware resource allocation for large-scale distributed systems

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.

Prefix-aware weighted cost multi-path group reduction

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.

Scalable network route analysis

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.

Weighted cost multipath routing with intra-node port weights and inter-node port weights

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.

High performance and resilience in wide area networking

This disclosure provides systems, methods, and apparatus for providing a network switch for implementing weighted cost multi-pathing (WCMP). In some implementations, the switch can implement equal cost multi-pathing (ECMP) using ECMP forwarding tables. The ECMP forwarding table may include more than one output port associated with a destination address of an incoming packet. The ECMP forwarding table may become undesirably large if unequal weights were assigned to the output ports. A multi-level ECMP table can be implemented that can allow assigning weights to the output ports while being relatively small. The multi-level ECMP table can include a first level where each entry includes at most a single output port. A second level can include entries having one or more output ports.

Systems and methods for implementing weighted cost multi-path using two-level equal cost multi-path tables

Growing community of inventors

Mountain View, CA, United States of America

Fei Ye