Method for making flow table multiple levels, and multi-level flow table processing method and device

Patent metadata

Field	Value
Publication number	US-10075375-B2
Application number	US-201415022079-A
Country	US
Kind code	B2
Filing date	Sep 26, 2014
Priority date	Sep 16, 2013
Publication date	Sep 11, 2018
Grant date	Sep 11, 2018

Abstract

An embodiment of the present document discloses a flow table multi-leveling method, a multi-level flow table processing method and device; wherein the multi-leveling method includes: generating a second flow table, separating a target logic rule in a first flow table and forwarding actions corresponding the target logic rule to the second flow table, to make the first flow table and the second flow table orthogonal to form a ternary content addressable memory (TCAM) flow table; wherein the first flow table saves a plurality of logic rules and all forwarding actions corresponding to the plurality of logic rules respectively; continuously generating new flow tables in the same manner of generating the second flow table, until the number of flow tables reaches a preset upper limit.

First claim

What is claimed is:

1. A flow table multi-leveling method, comprising:
generating a second flow table, separating a target logic rule in a first flow table as well as forwarding actions corresponding to the target logic rule to the second flow table, to make the first flow table and the second flow table orthogonal to form a ternary content addressable memory (TCAM) flow table; wherein the first flow table saves a plurality of logic rules as well as all forwarding actions corresponding to the plurality of logic rules respectively;
continuously generating new flow tables in a same manner of generating the second flow table, until a number of flow tables reaches a preset upper limit.

2. The method of claim 1 , wherein, logic rules in the first flow table and the second flow table comprise one or more match fields, and each match field corresponds to one or more forwarding actions;
the step of separating the target logic rule in the first flow table as well as forwarding actions corresponding to the target logic rule to the second flow table comprises:
calculating mapping gains of all logic rules in the first flow table, and determining a logic rule with a maximum mapping gain as the target logic rule;
separating the target logic rule in the first flow table as well as all forwarding actions corresponding to the target logic rule to the second flow table; wherein, a same match field of the target logic rule is not repeatedly saved in the second flow table.

3. The method of claim 2 , wherein, continuously generating new flow tables in a same manner of generating the second flow table comprises:
calculating mapping gains of all remaining logic rules in the first flow table, determining a logic rule with a maximum mapping gain in the remaining logic rules in the first flow table as a new target logic rule;
separating the new target logic rule in the first flow table as well as all forwarding actions corresponding to the new target logic rule to a third flow table, to make the first flow table, the second flow table and the third flow table orthogonal to form a TCAM table; wherein a same match field of the target logic rule is not repeatedly saved in the third flow table.

4. The method of claim 3 , wherein, the first flow table is configured with a first jump flow entry used for saving a jump address of each forwarding action in the first flow table, the second flow table is configured with a second jump flow entry used for saving a jump address of each forwarding action in the second flow table; wherein, a jump address of the first jump flow entry is the second flow table or a forwarder, a jump address of the second jump flow entry is the forwarder;
after separating the new target logic rule in the first flow table as well as all forwarding actions corresponding to the new target logic rule to the third flow table, the method further comprises:
configuring a third jump flow entry for the third flow table;
configuring a jump address for each forwarding action in the third flow table;
saving the jump address of each forwarding action in the third flow table to the third jump flow entry;
updating jump addresses in the first jump flow entry and the second jump flow entry.

5. The method of claim 4 , wherein,
the step of configuring a jump address for each forwarding action in the third flow table comprises:
configuring the jump address of each forwarding action in the third flow table as the forwarder;
the step of updating jump addresses in the first jump flow entry and the second jump flow entry comprises:
updating the jump addresses in the first jump flow entry and the second jump flow entry, to make the jump address of the first jump flow entry be the second flow table or the third flow table or the forwarder, and make the jump address of the second jump flow entry be the third flow table or the forwarder.

6. A multi-level flow table processing method, comprising:
determining a logic rule of a target packet;
matching logic rules saved in each flow table with the logic rule of the target packet based on an order of valid bits to obtain a set of forwarding actions of each flow table consistent with the matching;
taking an intersection of sets of forwarding actions of all the flow tables to obtain common forwarding actions for each set of forwarding actions;
forwarding the target packet based on the common forwarding actions for each set of forwarding actions;
wherein, the multi-level flow tables are sequenced based on the valid bits, the multi-level flow tables are orthogonal to form a ternary content addressable memory (TCAM) flow table; a first flow table at a first level saves at least one logic rule and all forwarding actions corresponding to the at least one logic rule, and each of remaining flow tables only saves one logic rule and all forwarding actions corresponding to the logic rule.

7. The method of claim 6 , wherein, the logic rules saved in each flow table comprise one or more match fields, each match field corresponds to one or more forwarding actions; each flow table in the multi-level flow tables is further configured with a jump flow entry used for saving a jump address of each forwarding action in a flow table corresponding to the jump flow entry, thereby after obtaining a set of forwarding actions of the first flow table, it is to jump to a lower-level flow table based on the jump address corresponding to each forwarding action in the set of forwarding actions.

8. A flow table multi-leveling device, comprising: a generating circuitry, configured to: generate a second flow table; and
a separating circuitry, configured to separate a target logic rule in a first flow table as well as forwarding action corresponding to the target logic rule to the second flow table, to make the first flow table and the second flow table orthogonal to form a TCAM flow table; wherein the first flow table saves a plurality of logic rules as well as all forwarding actions corresponding to the plurality of logic rules respectively;
the generating circuitry is further configured to: continuously generate new flow tables in a same manner of generating the second flow table, until a number of flow tables reaches a preset upper limit.

9. The device of claim 8 , wherein, logic rules in the first flow table and the second flow table comprise one or more match fields, and each match field corresponds to one or more forwarding actions;
the separating circuitry comprises:
a calculating sub-circuitry, configured to: calculate mapping gains of all logic rules in the first flow table, and determine a logic rule with a maximum mapping gain as the target logic rule; and
a separating sub-circuitry, configured to: separate the target logic rule in the first flow table as well as all forwarding actions corresponding to the target logic rule to the second flow table; wherein, a same match field of the target logic rule is not repeatedly saved in the second flow table.

10. The device of claim 9 , wherein,
the calculating sub-circuitry is further configured to: calculate mapping gains of all remaining logic rules in the first flow table, determine a logic rule with a maximum mapping gain in the remaining logic rules in the first flow table as a new target logic rule;
the separating sub-circuitry is further configured to: separate the new target logic rule in the first flow table and all forwarding actions corresponding to the new target logic rule to a third flow table, to make the first flow table, the second flow table and the third flow table orthogonal to form a TCAM table; wherein, a same match field of the target logic rule is not repeatedly saved in the third flow table.

11. The device of claim 10

Assignees

• Zte Corp

Inventors

• Liu Bin
• Li Yong
• Niu Xiaobing
• Jin Depeng
• Liu Zhongjin

Classifications

• H04L45/64

  using an overlay routing layer · CPC title

• H04L45/54

  Organization of routing tables · CPC title

• H04L45/742

  Route cache; Operation thereof · CPC title

• H04L45/74

  Address processing for routing · CPC title

• H04L12/6418 Primary

  Hybrid transport · CPC title