公开(公告)号：US09979648B1

公开(公告)日：2018-05-22

申请号：US14981667

申请日：2015-12-28

Applicant: Amazon Technologies, Inc.

Inventor： Bijendra Singh ,  Kari Ann O'Brien

IPC: H04L12/743

CPC classification number: H04L45/7453

Abstract: Entropy in routing tables may be increase to perform packet forwarding. Hash tables that store forwarding routes may be divided into multiple hash table segments. Forwarding routes may be stored across the hash table segments in different route segments. When looking up route segments to identify a forwarding route for a destination address of a network packet, digest values generated for previous route segments may be used to determine hash key values to identify hash table entries in a different hash table segment. The forwarding route may be identified according to the hash table entries located based on the digest values for previous route segments.

公开(公告)号：US10693790B1

公开(公告)日：2020-06-23

申请号：US16165082

申请日：2018-10-19

Applicant: Amazon Technologies, Inc.

Inventor： Bijendra Singh ,  Sravya Kusam

IPC: H04L12/803 ,  H04L12/761 ,  H04L12/18 ,  H04L12/707

Abstract: Techniques are disclosed regarding interfaces, each configured to output network packets. The techniques can include a memory storing a first multipath group associated with the interfaces and a routing table, containing a first route to the first multipath group. The techniques can also include congestion detection logic configured to determine that an interface of the first multipath group is congested. The techniques can additionally include congestion avoidance logic configured to, upon determining that the interface of the first multipath group is congested, generate a second route in the routing table to a second multipath group associated with the interfaces of the first multipath group, wherein the second route diverts a flow of network packets from the first multipath group to the second multipath group.

公开(公告)号：US10389632B1

公开(公告)日：2019-08-20

申请号：US16035508

申请日：2018-07-13

Applicant: Amazon Technologies, Inc.

Inventor： Kari Ann O'Brien ,  Thomas A. Volpe ,  Bijendra Singh

IPC: H04L12/28 ,  H04L12/741 ,  H04L12/933 ,  H04L29/08 ,  H04L29/06 ,  H04L12/723

Abstract: Disclosed herein is an apparatus for processing an Internet Protocol (IP) header and label switching (LS) headers of a packet in a pipeline. The apparatus includes an LS header processing circuit configured to select a first operation for the packet using an LS header from the packet, and an IP header processing circuit configured to perform an IP lookup to select a second operation for the packet. The apparatus further includes a tunnel initiation circuit configured to initiate an LS tunnel or IP tunnel. The LS header processing circuit, the IP header processing circuit, and the tunnel initiation circuit are operable to operate sequentially on a same packet and concurrently on different packets in a pipeline. Each of these circuits is operable to be bypassed based on an outermost header in the packet, or the selected one of the first operation or the second operation.

公开(公告)号：US20190149472A1

公开(公告)日：2019-05-16

申请号：US16194085

申请日：2018-11-16

Applicant: Amazon Technologies, Inc.

Inventor： Bijendra Singh ,  Thomas A. Volpe ,  Kari Ann O'Brien

IPC: H04L12/743 ,  H04L12/745 ,  H04L29/06 ,  H04L12/713 ,  H04L12/749

CPC classification number: H04L45/7453 ,  H04L45/586 ,  H04L45/741 ,  H04L45/748 ,  H04L69/22

Abstract: Packet processors or other devices with packet processing pipelines may implement pipelined evaluations of algorithmic forwarding route lookups. As network packets are received, a destination address for the network packets may be divided into different possible prefix lengths and corresponding entries in a routing table for the different possible prefix lengths may be determined according to a hash scheme for the routing table. The entry values may be read from the routing table and evaluated at subsequent stages to identify the entry with a longest prefix match with respect to the destination address for the network packet. The routing table may include entries for different types of network packets and may be configured to include virtual routing and forwarding for network packets.

公开(公告)号：US10069734B1

公开(公告)日：2018-09-04

申请号：US15232727

申请日：2016-08-09

Applicant: Amazon Technologies, Inc.

Inventor： Bijendra Singh

IPC: H04L1/00 ,  H04L12/801 ,  H04L12/743

Abstract: Disclosed are techniques regarding interfaces, each configured to output network packets. The techniques can regard a memory for storing multipath groups, virtual output queues, and a histogram table for storing statistical information associated with network packets to be output by interfaces. The techniques can include generating a shared-interface list including a member that represents a union of interfaces of at least some of the multipath groups, wherein the multipath groups of the member share at least one of the interfaces. The techniques can include associating the histogram table with the member. The techniques can include collecting the statistical information pertaining to network packets indicated by information stored in one of the virtual output queues, populating the histogram table with the statistical information, and determining that one of the interfaces is congested based on the statistical information.

公开(公告)号：US10009275B1

公开(公告)日：2018-06-26

申请号：US15352442

申请日：2016-11-15

Applicant: Amazon Technologies, Inc.

Inventor： Bijendra Singh

IPC: H04L12/741 ,  H04L12/721 ,  H04L12/713 ,  H04L12/947

CPC classification number: H04L45/745 ,  H04L45/14 ,  H04L45/586 ,  H04L49/252

Abstract: Disclosed are techniques for determining lookup value(s) for each of a plurality of network packets. The lookup value can be used to locate a forwarding table storage location(s) for populating or retrieving forwarding information from forwarding table(s). An entropy value of the lookup values can indicate a greater degree of disorder than an entropy value for addresses of the network packets.

公开(公告)号：US09898069B1

公开(公告)日：2018-02-20

申请号：US15087291

申请日：2016-03-31

Applicant: Amazon Technologies, Inc.

Inventor： Kari Ann O'Brien ,  Bijendra Singh ,  Thomas A. Volpe

IPC: G06F1/32 ,  H04L12/743

CPC classification number: G06F1/3275 ,  H04L45/7453

Abstract: Disclosed are devices, systems, and methods for the use of memory including a data table configured to store a plurality of elements, wherein the plurality of elements are arranged into a plurality of buckets and each of the plurality of buckets comprising a plurality of entries. A first power domain can be associated with an entry of each bucket or with a first bucket. A second power domain can be associated with a second entry of each bucket or a second bucket. Processing logic can be configured to search for a particular value stored in an element of the plurality of elements by selecting buckets of the plurality of buckets and selecting at least one entry of each of the buckets. A programmable register can be used to select a powered state of the second power domain based on a configuration of the programmable register.

公开(公告)号：US11126249B1

公开(公告)日：2021-09-21

申请号：US15932244

申请日：2018-02-16

Applicant: Amazon Technologies, Inc.

Inventor： Kari Ann O'Brien ,  Bijendra Singh ,  Thomas A. Volpe

IPC: G06F1/32 ,  G06F1/3234 ,  H04L12/743

Abstract: Disclosed are devices, systems, and methods for the use of memory including a data table configured to store a plurality of elements, wherein the plurality of elements are arranged into a plurality of buckets and each of the plurality of buckets comprising a plurality of entries. A first power domain can be associated with an entry of each bucket or with a first bucket. A second power domain can be associated with a second entry of each bucket or a second bucket. Processing logic can be configured to search for a particular value stored in an element of the plurality of elements by selecting buckets of the plurality of buckets and selecting at least one entry of each of the buckets. A programmable register can be used to select a powered state of the second power domain based on a configuration of the programmable register.

公开(公告)号：US10735325B1

公开(公告)日：2020-08-04

申请号：US16024139

申请日：2018-06-29

Applicant: Amazon Technologies, Inc.

Inventor： Bijendra Singh

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

Abstract: Techniques are disclosed regarding receiving a plurality of flows of network packets and determining, by processing logic of a device, a hash value for each of the network packets of the flows, wherein the hash value indicates the flow of network packets that a network packet belongs to. Based on the hash value, one of a plurality of interface ports of a multipath group of the device can be selected for output of network packets from two of the flows of network packets. Network packets from the two flows of network packets to be output by the interface port can be stored. Upon determining that a number of packets stored from the one of the two flows of network packets meets a first threshold, one of the two flows of network packets can be identified as a congestion contributing flow.

公开(公告)号：US10666564B2

公开(公告)日：2020-05-26

申请号：US15983856

申请日：2018-05-18

Applicant: Amazon Technologies, Inc.

Inventor： Bijendra Singh ,  Kari Ann O'Brien

IPC: H04W72/04 ,  H04L12/743

Abstract: Entropy in routing tables may be increase to perform packet forwarding. Hash tables that store forwarding routes may be divided into multiple hash table segments. Forwarding routes may be stored across the hash table segments in different route segments. When looking up route segments to identify a forwarding route for a destination address of a network packet, digest values generated for previous route segments may be used to determine hash key values to identify hash table entries in a different hash table segment. The forwarding route may be identified according to the hash table entries located based on the digest values for previous route segments.