Network packet header modification for hardware-based packet processing

Patent metadata

Field	Value
Publication number	US-9860168-B1
Application number	US-201514860494-A
Country	US
Kind code	B1
Filing date	Sep 21, 2015
Priority date	Sep 21, 2015
Publication date	Jan 2, 2018
Grant date	Jan 2, 2018

Abstract

A packet processor may implement network packet modification. A network packet may be received at a packet processor. A packet header modification may be identified for the network packet. The packet processor may access a memory to traverse a dependency graph for the packet header modification to obtain an operation to apply the packet header modification and dependent operations to update fields in the packet header to be changed as a result of the packet header modification. The dependency graph may have been stored in the memory prior to receiving the network packet. The obtained operations may be performed according to the traversal of the dependency graph. The modified packet may then be transmitted.

First claim

What is claimed is:

1. A networking device, comprising:
a plurality of physical network interfaces; and
a packet processor, configured to:
receive a network packet via one of the physical network interfaces;
determine a packet header modification for the network packet;
access different locations in a memory identified for the packet header modification corresponding to a traversal of a dependency graph stored in the memory for the packet header modification, wherein at least one of the different locations is determined from a prior entry of the dependency graph, to obtain:
an operation to apply the packet header modification; and
one or more dependent operations to update respective fields of the network packet that store values to be changed as a result of the packet header modification;

for each access in the memory according to the traversal of the dependency graph, perform the operation to apply the packet header modification or one of the one or more dependent operations; and
upon completion of the traversal of the dependency graph, transmit the modified network packet via one of the physical network interfaces.

2. The networking device of claim 1 , wherein the traversal of the dependency graph is performed according to a depth first search technique.

3. The networking device of claim 1 , wherein the memory is a static random access memory.

4. The system of claim 1 , further comprising:
at least one processor; and
a system memory that stores program instructions that when executed by the at least one processor cause the at least one processor to implement a packet modification interface, wherein the packet modification interface is configured to:
receive another dependency graph for a new packet header modification to be applied at the packet processor; and
store the other dependency graph in the memory;

wherein the packet processor is further configured to:
receive another network packet;
determine the new packet header modification for the other network packet;
access different locations in the memory identified for the new packet header modification corresponding to a traversal of the other dependency graph for the new packet header modification to obtain:
an operation to apply the new packet header modification; and
one or more dependent operations to update respective fields of the other network packet that store values to be changed as a result of the new packet header modification;

for each access in the memory according to the traversal of the other dependency graph, perform the operation to apply the new packet header modification or one of the one or more dependent operations to update respective fields of the other network packet that store values to be changed as a result of the new packet header modification; and
transmit the other network packet via one of the physical network interfaces.

5. A method, comprising:
receiving, at a packet processor, a network packet;
identifying, by the packet processor, at least one packet header modification for the network packet;
traversing, by the packet processor, a dependency graph stored in a memory in the packet processor for the at least one packet header modification, wherein at least one entry of the dependency graph is determined from a prior entry of the dependency graph, wherein the traversing obtains:
an operation to apply the at least one packet header modification; and
one or more dependent operations to update respective fields of the network packet, the respective fields storing values to be changed as a result of the at least one packet header modification;

performing, by the packet processor, the operation to apply the at least one packet header modification to the network packet, and performing the one or more dependent operations to update the respective fields of the network packet, wherein the operation and the one or more dependent operations are performed as the operation and the dependent operations are obtained according to the traversing of the dependency graph; and
transmitting, by the packet processor, the modified network packet.

6. The method of claim 5 , wherein identifying the at least one packet header modification for the network packet comprises accessing packet metadata for the network packet that indicates the at least one packet header modification and wherein the packet metadata comprises a location of an entry in the memory for a root node of the dependency graph that describes the at least one packet header modification to the network packet.

7. The method of claim 6 , wherein one or more other entries are stored in the memory for respective nodes in the dependency graph corresponding to the one or more dependent operations, wherein the entry and the one or more other entries each store a respective number of child nodes of the node corresponding to the entry, and wherein traversing the dependency graph comprises selecting a next node in the dependency graph for traversal based, at least in part, on the respective number of child nodes stored in an entry of a previously processed node in the dependency graph.

8. The method of claim 7 , wherein the entry and the one or more other entries further comprise:
a respective operation identifier; and
a respective location of a bit field in the network packet in which to perform the operation as identified by the operation identifier.

9. The method of claim 8 , wherein at least one of the entry or the one or more other entries further comprises an operand, wherein the operation performed for the at least one entry applies the operand.

10. The method of claim 5 , wherein the memory is a random access memory (RAM).

11. The method of claim 5 , further comprising:
prior to receiving the network packet:
receiving the dependency graph for the packet header modification; and
storing the dependency graph in the memory.

12. The method of claim 5 , wherein the packet processor is implemented by an application specific integrated circuit (ASIC).

13. A system, comprising:
a device configured to perform packet processing, the device comprising;
one or more network interfaces configured to transmit and receive packets via a network connection to the device; and
a packet processing pipeline, configured to:
receive a network packet via one of the one or more network interfaces;
determine a packet header modification for the network packet;
traverse a dependency graph stored in a memory for the packet header modification, wherein at least one entry of the dependency graph is determined from a prior entry of the dependency graph, wherein the traversal of the dependency graph identifies:
an operation to apply the packet header modification; and
one or more dependent operations to update respective fields of the network packet storing values to be changed as a result of the packet header modification;

perform the operation to apply the packet header modification to the network packet, and perform the one or more dependent operations to update the respective fields of the network packet, wherein the operation and the one or more dependent operations are performed as the operation and the dependent operations are obtained according to the traversal of the dependency graph; and
transmit the modified network packet via one of the one or more network interfaces.

14. The system of claim 13 , wherein a respective entry stored for at least one of the operation or the one or more dependent operations comprises:
an operand;
an operation identifier; and
a location of a bit field in the network packet in which to apply the operation identified by the operatio

Assignees

• Amazon Tech Inc

Inventors

• Seshadri Kiran Kalkunte

Classifications

• H04L45/74 Primary

  Address processing for routing · CPC title

• H04W24/02 Primary

  Arrangements for optimising operational condition · CPC title

• H04L69/22

  Parsing or analysis of headers · CPC title