公开(公告)号：US09544226B1

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

申请号：US14142162

申请日：2013-12-27

Applicant: Google Inc.

Inventor： Peter Michael Klausler

IPC: H04L12/741 ,  G06F9/30 ,  H04L12/743 ,  H04L12/701 ,  H04L12/745

CPC classification number: H04L45/74 ,  G06F9/30 ,  G06F9/30185 ,  H04L45/00 ,  H04L45/745 ,  H04L45/7457 ,  H04L45/748

Abstract: Aspects and implementations of the present disclosure are directed to a network device. The network device includes memory for storing a first dataset comprising first data structures, a second dataset comprising second data structures, and a set of Boolean values. Each first data structure includes an address and a corresponding instruction parameter. Each second data structure includes an address prefix and at least one intermediary value. Each Boolean value corresponds to a respective address prefix and indicates whether the second dataset includes a second data structure with the respective address prefix. The network device is configured to identify a first address and a first address prefix for a first data packet, identify one or more intermediary values for the first address prefix using the set of Boolean values, and identify a packet processing instruction parameter using the one or more identified intermediary values.

Abstract translation: 本公开的方面和实现涉及网络设备。 网络设备包括用于存储包括第一数据结构的第一数据集的存储器，包括第二数据结构的第二数据集和一组布尔值。 每个第一数据结构包括地址和对应的指令参数。 每个第二数据结构包括地址前缀和至少一个中间值。 每个布尔值对应于相应的地址前缀，并且指示第二数据集是否包括具有相应地址前缀的第二数据结构。 所述网络设备被配置为识别第一数据分组的第一地址和第一地址前缀，使用所述一组布尔值来识别所述第一地址前缀的一个或多个中间值，并且使用所述一个或多个 更多的中介价值。

公开(公告)号：US08806244B1

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

申请号：US14084054

申请日：2013-11-19

Applicant: Google Inc.

Inventor： Dennis Charles Abts ,  Peter Michael Klausler ,  Hong Liu ,  Michael Marty ,  Philip Michael Wells

IPC: G06F1/32

CPC classification number: G06F1/3253 ,  H04L41/0833 ,  H04L43/0882 ,  H04L69/14 ,  Y02D10/151 ,  Y02D50/30

Abstract: Energy proportional solutions are provided for computer networks such as datacenters. Congestion sensing heuristics are used to adaptively route traffic across links. Traffic intensity is sensed and links are dynamically activated as they are needed. As the offered load is decreased, the lower channel utilization is sensed and the link speed is reduced to save power. Flattened butterfly topologies can be used in a further power saving approach. Switch mechanisms are exploit the topology's capabilities by reconfiguring link speeds on-the-fly to match bandwidth and power with the traffic demand. For instance, the system may estimate the future bandwidth needs of each link and reconfigure its data rate to meet those requirements while consuming less power. In one configuration, a mechanism is provided where the switch tracks the utilization of each of its links over an epoch, and then makes an adjustment at the end of the epoch.

Abstract translation: 为诸如数据中心的计算机网络提供能量比例解决方案。 拥塞感知启发式用于自适应地跨链路路由流量。 检测到交通强度，并根据需要动态激活链路。 随着提供的负载减小，感测到较低的信道利用率，并且减少链路速度以节省功率。 扁平蝶形拓扑可以用于进一步节能方法。 交换机制通过重新配置链路速度来快速利用拓扑的功能，以匹配带宽和功率与流量需求。 例如，系统可以估计每个链路的未来带宽需求，并重新配置其数据速率以满足这些要求，同时消耗更少的功率。 在一种配置中，提供了一种机制，其中开关在历元上跟踪其每个链接的利用率，然后在时代结束时进行调整。

公开(公告)号：US08964559B2

公开(公告)日：2015-02-24

申请号：US13872450

申请日：2013-04-29

Applicant: Google Inc.

Inventor： Peter Michael Klausler

IPC: H04L1/00 ,  H04L12/26 ,  H04L12/28 ,  H04L12/56

CPC classification number: H04L47/12 ,  G06F15/17312 ,  G06F15/17381 ,  H04L45/06 ,  H04L45/18 ,  H04L45/60 ,  H04L49/253

Abstract: Aspects of the invention pertain to routing packets in a computer system while avoiding deadlock. A turn rule is set according to unique identifiers associated with switches in the system. Numeric values of switches in possible turns are compared to determine whether a turn is permissible. The rule applies to all nodes in the system. The rule may be violated when using virtual channels. Here, a violation is permissible when using monotonically increasing virtual channel numbers or monotonically decreasing virtual channel numbers. Alternatively, the violations of the turn rule may be allowed if they force a packet to change to a later virtual channel in some fixed ordering of virtual channels. Deadlock can thus be avoided in many different types of architectures, including mesh, torus, butterfly and flattened butterfly configurations.

Abstract translation: 本发明的方面涉及在计算机系统中路由分组，同时避免死锁。 根据与系统中的开关相关联的唯一标识符设置转弯规则。 比较可能转弯中开关的数值，以确定转弯是否允许。 该规则适用于系统中的所有节点。 使用虚拟通道时可能会违反规则。 这里，当使用单调递增的虚拟通道号或单调递减虚拟通道号时，允许违规。 或者，如果在某些固定的虚拟通道排序中强制分组改变为稍后的虚拟通道，则可能允许违反转弯规则。 因此，可以在许多不同类型的架构中避免死锁，包括网格，环面，蝴蝶和扁平蝶形配置。

公开(公告)号：US20130242731A1

公开(公告)日：2013-09-19

申请号：US13872450

申请日：2013-04-29

Applicant: GOOGLE INC.

Inventor： Peter Michael Klausler

IPC: H04L12/70

CPC classification number: H04L47/12 ,  G06F15/17312 ,  G06F15/17381 ,  H04L45/06 ,  H04L45/18 ,  H04L45/60 ,  H04L49/253

Abstract: Aspects of the invention pertain to routing packets in a computer system while avoiding deadlock. A turn rule is set according to unique identifiers associated with switches in the system. Numeric values of switches in possible turns are compared to determine whether a turn is permissible. The rule applies to all nodes in the system. The rule may be violated when using virtual channels. Here, a violation is permissible when using monotonically increasing virtual channel numbers or monotonically decreasing virtual channel numbers. Alternatively, the violations of the turn rule may be allowed if they force a packet to change to a later virtual channel in some fixed ordering of virtual channels. Deadlock can thus be avoided in many different types of architectures, including mesh, torus, butterfly and flattened butterfly configurations.

Abstract translation: 本发明的方面涉及在计算机系统中路由分组，同时避免死锁。 根据与系统中的开关相关联的唯一标识符设置转弯规则。 比较可能转弯中开关的数值，以确定转弯是否允许。 该规则适用于系统中的所有节点。 使用虚拟通道时可能会违反规则。 这里，当使用单调递增的虚拟通道号或单调递减虚拟通道号时，允许违规。 或者，如果在某些固定的虚拟通道排序中强制分组改变为稍后的虚拟通道，则可能允许违反转弯规则。 因此，可以在许多不同类型的架构中避免死锁，包括网格，环面，蝴蝶和扁平蝶形配置。