Method, apparatus, and system for supporting flexible lookup keys in software-defined networks

Patent metadata

Field	Value
Publication number	US-9954779-B2
Application number	US-201615147215-A
Country	US
Kind code	B2
Filing date	May 5, 2016
Priority date	Dec 18, 2013
Publication date	Apr 24, 2018
Grant date	Apr 24, 2018

Abstract

A method is described in a network element for supporting flexible lookup keys in a software-defined network. The method includes receiving a packet to be forwarded and determining a next hop for the packet, which includes parsing the packet to identify a superkey comprising a plurality of header field values of the packet; identifying a superkey mask value and a superkey offset value for a first lookup table of a set of one or more lookup tables; generating a table key for the first lookup table based upon the superkey mask value, the superkey offset value, and the superkey; and performing a lookup in the first lookup table using the table key. The lookup identifies an entry of the first lookup table indicating the next hop for the packet. The packet may then be forwarded to the next hop.

First claim

What is claimed is:

1. A method in a forwarding element implemented by a network device in a software-defined network for supporting flexible lookup table keys, the method comprising:
receiving, at the forwarding element, a packet to be forwarded;
generating, by the forwarding element, a table key for a first lookup table based upon a superkey mask value, a superkey offset value, and a superkey, wherein the superkey comprises a plurality of header field values of the packet, and wherein the superkey mask value and the superkey offset value are associated with the first lookup table;
performing, by the forwarding element, a lookup in the first lookup table using the table key, wherein the lookup identifies an entry of the first lookup table indicating a next hop for the packet; and
transmitting, by the forwarding element, the packet to the next hop.

2. The method of claim 1 , further comprising:
identifying a table entry of a plurality of entries of a structure definition table (SDT) that corresponds to the first lookup table, wherein the SDT table entry comprises the superkey offset value and the superkey mask value.

3. The method of claim 1 , wherein said generating the table key comprises:
applying the superkey mask value to a subset of bytes of the superkey identified based upon the superkey offset value.

4. The method of claim 3 , wherein said applying comprises:
performing an AND operation with the subset of bytes of the superkey and the superkey mask value.

5. The method of claim 3 , wherein said generating the table key for the first lookup table further comprises applying a second superkey mask value to another subset of bytes of the superkey identified based upon a second superkey offset value.

6. The method of claim 1 , wherein said first lookup table comprises a hash table, and wherein said performing the lookup in the first lookup table using the table key comprises applying a hash function to the table key to generate an index value to be used to search the hash table.

7. The method of claim 1 , further comprising:
receiving, at the forwarding element, a second packet;
generating, by the forwarding element, a second table key for the first lookup table based upon the superkey mask value, the superkey offset value, and a second superkey generated based upon the second packet;
performing, by the forwarding element, a second lookup in the first lookup table using the second table key to determine to perform another lookup in a second lookup table;
generating, by the forwarding element, a third table key for the second lookup table based upon a second superkey mask value, a second superkey offset value, and the second superkey, and
performing, by the forwarding element, a third lookup in the second lookup table using the third table key to identify an entry of the second lookup table indicating a second next hop; and
transmitting, by the forwarding element, the second packet to the second next hop.

8. The method of claim 1 , further comprising:
receiving, at the forwarding element, a command from a controller in the software-defined network, wherein the command indicates that the forwarding element is to configure the first lookup table;
configuring the first lookup table according to the command; and
configuring a table entry of a structure definition table (SDT) that is to correspond to the first lookup table to include the superkey offset value and the superkey mask value.

9. A device to implement a forwarding element to operate in a software-defined network and support flexible lookup table keys, the device comprising:
one or more line cards, wherein each of the one or more line cards comprises circuitry adapted to:
receive a packet to be forwarded;
generate a table key for a first lookup table based upon a superkey mask value, a superkey offset value, and a superkey, wherein the superkey comprises a plurality of header field values of the packet, and wherein the superkey mask value and the superkey offset value are associated with the first lookup table;
perform a lookup in the first lookup table using the table key, wherein the lookup identifies an entry of the first lookup table indicating a next hop for the packet; and
transmit the packet to the next hop.

10. The device of claim 9 , wherein the circuitry is further adapted to:
identify a table entry of a plurality of entries of a structure definition table (SDT) that corresponds to the first lookup table, wherein the SDT table entry comprises the superkey offset value and the superkey mask value.

11. The device of claim 9 , wherein, to generate the table key, the circuitry is adapted to:
apply the superkey mask value to a subset of bytes of the superkey identified based upon the superkey offset value.

12. The device of claim 11 , wherein, to apply the superkey mask value, the circuitry is adapted to:
perform an AND operation with the subset of bytes of the superkey and the superkey mask value.

13. The device of claim 11 , wherein, to generate the table key for the first lookup table, the circuitry is further adapted to apply a second superkey mask value to another subset of bytes of the superkey identified based upon a second superkey offset value.

14. The device of claim 9 , wherein said first lookup table comprises a hash table, and wherein, to perform the lookup in the first lookup table using the table key, the circuitry is adapted to apply a hash function to the table key to generate an index value to be used to search the hash table.

15. The device of claim 9 , wherein the circuitry is further adapted to:
receive a second packet;
generate a second table key for the first lookup table based upon the superkey mask value, the superkey offset value, and a second superkey generated based upon the second packet;
perform a second lookup in the first lookup table using the second table key to determine to perform another lookup in a second lookup table;
generate a third table key for the second lookup table based upon a second superkey mask value, a second superkey offset value, and the second superkey;
perform a third lookup in the second lookup table using the third table key to identify an entry of the second lookup table indicating a second next hop; and
transmit the second packet to the second next hop.

16. The device of claim 9 , wherein the circuitry is further adapted to:
receive a command from a controller in the software-defined network, wherein the command indicates that the forwarding element is to configure the first lookup table;
configure the first lookup table according to the command; and
configure a table entry of a structure definition table (SDT) that is to correspond to the first lookup table to include the superkey offset value and the superkey mask value.

17. A non-transitory computer readable storage medium having instructions which, when executed by one or more processors of a device, cause the device to implement a forwarding element to act in a software-defined network and support flexible lookup table keys by performing operations comprising:
receiving a packet to be forwarded;
generating a table key for a first lookup table based upon a superkey mask value, a superkey offset value, and a superkey, wherein the superkey comprises a plurality of header field values of the packet, and wherein the superkey mask value and the superkey offset value are associated with the first lookup table;
performing a lookup in the first lookup table using the table key, wherein the lookup identifies an entry of the first lookup table indicating a next

Assignees

• Ericsson Telefon Ab L M
• Ericsson Telefon Ab L M

Inventors

• Pitchai Sridhar
• Hlady Mark

Classifications

• H04L45/64

  using an overlay routing layer · CPC title

• H04L45/745

  Address table lookup; Address filtering · CPC title

• H04L69/22

  Parsing or analysis of headers · CPC title

• H04L45/42

  Centralised routing · CPC title

• H04L45/38 Primary

  Flow based routing · CPC title