Load-balanced forwarding of network packets generated by a networking device

• US 10,454,831 B1
• Filed: 06/30/2016
• Issued: 10/22/2019
• Est. Priority Date: 06/30/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Volpe, Thomas A., Kahn, Asif, Bshara, Nafea
• Primary Examiner(s): Mills, Donald L
• Application Number:
  US15/199,501
• Time in Patent Office: 1,209 Days
• Field of Search: None
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

Forwarding of network packets generated by a networking device may be load-balanced. Network packets may be generated by a networking device, such as a packet processor, that also processes and forwards received network packets. Forwarding decisions for the generated network packets may be made according to a load balancing scheme among possible forwarding routes from the networking device. In at least some embodiments, a destination resolution pipeline for determining forwarding decisions for generated network packets may be implemented separate from a destination resolution pipeline for determining forwarding decisions for received network packets in order to determine different forwarding decisions for the generated network packets. The generated network packets may then be forwarded according to the determined forwarding decisions.

Claims

1. A networking device, comprising:

a plurality of physical network interfaces; and

a packet processor, comprising a destination resolution pipeline for processing received network packets and a different destination resolution pipeline for processing generated network packets;

wherein the packet processor is configured to;

receive different network packets via the physical network interfaces from different sources;

process, by the destination resolution pipeline, the different network packets to determine respective forwarding decisions for the different network packets;

based on the different network packets, generate a plurality of additional network packets that originate from the packet processor instead of being received via the physical network interfaces;

process, by the different destination resolution pipeline, the additional network packets to determine respective forwarding decisions for the additional network packets; and

forward the different network packets and the additional network packets via the physical network interfaces according to the respective forwarding decisions.

2. The networking device of claim 1, wherein to process the additional network packets via the different destination resolution pipeline, the packet processor is configured to apply a load balancing scheme amongst a plurality of possible forwarding routes from the network packet processor to determine the respective forwarding decisions for the additional network packets.

3. The networking device of claim 2, wherein to apply the load balancing scheme, the packet processor is configured to:

for individual ones of the additional network packets;

identifying a group of elements in a group table for a destination resolution stage of the different destination resolution pipeline according to a pointer obtained at a prior stage of the packet processor for the additional network packet;

select one element of the group of elements according to a hash value generated for the additional network packet and the destination resolution stage; and

read an entry in a pointer table for the destination resolution stage mapped to the selected element, wherein the respective forwarding decision for the additional network packet is based on the entry read from the pointer table.

4. The networking device of claim 1, wherein the additional network packets comprise:

a mirrored version of one of the different network packets received at the packet processor;

a sampled version of one of the different network packets received at the packet processor;

or

a network statistics packet based on an analysis of the different network packets received at the packet processor that is performed by the packet processor.

5. A method, comprising:

generating, by a packet processor, a plurality of network packets that originate from the packet processor instead of being received at the packet processor, wherein the plurality of network packets are generated in addition to different network packets received via respective network connections from different sources at the packet processor for processing;

determining, by the packet processor, respective forwarding decisions for the plurality of network packets according to a load balancing scheme amongst a plurality of possible forwarding routes from the packet processor; and

forwarding, by the packet processor, the plurality of network packets via different ones of the possible forwarding routes according to the respective forwarding decisions.

6. The method of claim 5,

wherein the method further comprises identifying, by the packet processor, one of the different network packets for mirroring;

and

wherein generating the plurality of network packets comprises generating a mirrored version of the identified network packet.

7. The method of claim 6,

wherein the method further comprises identifying, by the packet processor, another one of the different network packets for mirroring, wherein the other network packet is received as part of a same traffic flow as the one network packet identified for mirroring;

wherein generating the plurality of network packets comprises generating a mirrored version of the identified other network packet; and

wherein the mirrored version of the other network packet is forwarded via one of the possible forwarding routes that is different than the mirrored version of the one network packet.

8. The method of claim 5,

wherein the method further comprises analyzing, by the packet processor, the different network packets received at the packet processor for processing;

and

wherein generating the plurality of network packets comprises generating one or more network statistic packets based on the analysis of the different network packets.

9. The method of claim 5, wherein determining respective forwarding decisions for the plurality of network packets according to the load balancing scheme comprises:

applying a hash function to respective data in the plurality of network packets to generate respective hash values; and

selecting the different ones of the possible forwarding routes as the respective forwarding decisions based on the respective hash values for the plurality of network packets.

10. The method of claim 9, further comprising modifying the respective data of one of the plurality of network packets prior to applying the hash function.

11. The method of claim 5,

wherein the method further comprises processing the different network packets received at the packet processor via a destination resolution pipeline;

and

wherein determining the respective forwarding decisions for the plurality of network packets comprises processing the plurality of network packets via a different destination resolution pipeline than the destination resolution pipeline.

12. The method of claim 5, wherein processing the plurality of network packets via the different destination resolution pipeline comprises:

for individual ones of the plurality of network packets;

identifying a group of elements in a group table for a destination resolution stage of the different destination resolution pipeline according to a pointer obtained at a prior stage of the packet processor for the network packet;

selecting one element of the group of elements according to a hash value generated for the network packet and the destination resolution stage; and

reading an entry in a pointer table for the destination resolution stage mapped to the selected element, wherein the respective forwarding decision for the network packet is based on the entry read from the pointer table.

13. The method of claim 12, further comprising:

for one of the individual network packets;

identifying a group of elements in another group table for a different destination resolution stage of the different destination resolution pipeline according to another pointer;

selecting one element of the group of elements in the other group table according to another hash value generated for the one network packet and the other destination resolution stage; and

reading an entry in another pointer table for the other destination resolution stage mapped to the selected element, wherein the respective forwarding decision for the one network packet is based on the entry read from the other pointer table.

14. A system, comprising:

a device configured to perform packet processing, the device comprising;

a plurality of network interfaces configured to transmit and receive packets via a network connection to the device; and

a packet processing pipeline that processes different network packets received from different sources via the network interfaces and forwards the different network packets according to forwarding decisions determined for the different network packets by the packet processing pipeline, wherein the packet processing pipeline is configured to;

generate a plurality of network packets that originate from the device instead of being received at the device via the plurality of network interfaces in addition to the different network packets;

apply a load balancing scheme amongst a plurality of possible forwarding routes via the network interfaces from the device to determine respective forwarding decisions for the generated network packets; and

send the generated network packets via different ones of the possible forwarding routes according to the respective forwarding decisions.

15. The system of claim 14,

wherein the packet processing pipeline is further configured to identify one of the different network packets for mirroring;

and

wherein to generate the plurality of network packets, the packet processing pipeline is configured to generate a mirrored version of the identified network packet.

16. The system of claim 14,

wherein the packet processing pipeline is further configured to identify one of the different network packets for sampling;

and

wherein to generate the plurality of network packets, the packet processing pipeline is configured to include a sampled version of the identified network packet in a sample network packet.

17. The system of claim 14, wherein to apply the load balancing scheme amongst the plurality of possible forwarding routes, the packet processing pipeline is configured to:

generate respective hash values according to a hash function applied to respective data in the plurality of network packets; and

select the different ones of the possible forwarding routes as the respective forwarding decisions based on the respective hash values for the plurality of network packets.

18. The system of claim 14,

wherein the forwarding decisions determined for the different network packets received by the packet processing pipeline are determined by one or more destination resolution stages of the packet processing pipeline;

and

wherein to apply the load balancing scheme to determine the respective forwarding decisions for the plurality of network packets, the packet processing pipeline is configured to process the plurality of network packets via one or more different destination resolution stages than the one or more destination resolution stages.

19. The system of claim 18, wherein to process the plurality of network packets via the one or more different destination resolution stages, the packet processing pipeline is configured to:

for individual ones of the plurality of network packets;

identify a group of elements in a group table for one of the one or more different destination resolution stages according to a pointer obtained at a prior stage of the packet processing pipeline for the network packet;

select one element of the group of elements according to a hash value generated for the network packet and the one destination resolution stage; and

read an entry in a pointer table for the one destination resolution stage mapped to the selected element, wherein the respective forwarding decision for the network packet is based on the entry read from the pointer table.

20. The system of claim 14, wherein the device is an application specific integrated circuit (ASIC), a system-on-chip (SoC), or a field-programmable gate array (FPGA).