CN1138384C

CN1138384C - Query device and method applied to network device

Info

Publication number: CN1138384C
Application number: CNB011022930A
Authority: CN
Inventors: 陈俊儒; 王耀宗
Original assignee: Acute Tech Corp
Current assignee: Acute Tech Corp
Priority date: 2001-01-21
Filing date: 2001-01-21
Publication date: 2004-02-11
Anticipated expiration: 2021-01-21
Also published as: CN1300147A

Abstract

A query device and method applied to a network device are used for querying a network address query table. The inquiry device mainly comprises: a grammar analyzer for obtaining network address information of the incoming packets. A specific amount of shift control logic for generating a characteristic independent distribution (i.i.d.) hash index based on network address information of an incoming packet. The output of each shift control logic is selected one by the selector, and the corresponding forwarding information can be output by inquiring the network address look-up table. By the arrangement of the displacement control logic of the invention, the query engine can more efficiently construct the registration (flowentry) of each data flow and quickly execute the service classification belonging to the data flow packet.

Description

Be applied to the inquiry unit and the method for network equipment

Technical field

The present invention relates to a kind of query engine of network equipment, refer to the query engine of the hash function of a kind of selectable properties independent distribution (Identity Independent Distribution is hereinafter to be referred as I.I.D.) especially, with effective requester network address lookup table.

Background technology

For improving the search efficiency of the network address, in INFOCOMM 2000 periodicals, Xu Jun people such as (Jun Xu) delivers a kind of new cache architecture (route caching scheme), can support the package of layer-4 to classify (referring to " A Novel Cache Architecture to SupportLayer-Four Packet Classification at Memory Access Speeds " literary composition) by memory access rate.This new route cache architecture is based upon a kind of brand-new and do not rely on the related framework (dynamic set-associative scheme) of dynamic set on the basis of parallel hash framework (statistically independent parallel hashing scheme) of statistical.The designed route cache architecture (route cache) of Xu Jun designs at the query demand of layer-4.This route cache architecture comprises general N subitem set associative framework (N-way set-associative scheme), wherein N hash function h ₁, h ₂..., h _NSatisfy following characteristic: suppose to have individual hash key (hash key) X arbitrarily, this hash key is at process hash function h ₁(x), h ₂(x) ..., h _N(x) after etc. the computing, the result who is produced can be the aleatory variable with characteristic independent distribution (I.I.D.).

With reference to figure 1, when the demand (request) of an inquiry arrives, layer-4 address＜the DA that is constituted by 104 bits in this demand, SA, DP, SP, PRO〉101, can be respectively by N different hardware hash arithmetic unit 102 parallel processing, producing N Hash Value, and (104-r)-tail tag (tags) of bit with r bit.The output of hash arithmetic unit 102 is sent to N independently SLDRAM (Synchronize LinkDynamic Random Access Memory) storage block (banks) 103.Each gets tail tag value that the tail tag field of login (entry) will be exported with hash arithmetic unit 102 simultaneously and compare abreast soon.If the successful matching of one of them login will be as last " next-hop " output of multiplexer 105 corresponding to " next-hop " field of this login.Relatively, inquiry error (lookup miss) then can be handled by a replacement logic (Replacement Logic) 106.

The advantage of the cache architecture of Xu Jun is to reduce the collision probability effectively.Yet how Xu Jun does not disclose the hash function that from GF (2) definition matrix down selection has the I.I.D. characteristic, and each hash function is individually corresponding to this matrix.

Summary of the invention

Main purpose of the present invention provides a kind of easy to implement in network equipment and the high query engine of efficient, is to utilize the I.I.D. hash function to reach the purpose of quick search network address inquiry table.

Another object of the present invention provides a kind of query engine of the Layer-4 of can be applicable to network equipment, so that package forwarding mechanism fast to be provided.

Another purpose of the present invention provides a kind of hash mechanism easy to implement, has the hash function of I.I.D. characteristic with selection, and then reduces the probability of collision, improves the efficient of requester network address lookup table.

The inquiry unit that the present invention is applied to network equipment is achieved in that and comprises:

One syntax analysis device in order to the package that receive to arrive, and is analyzed the network address message of the package of this arrival;

One plural groups displacement control logic is connected in aforementioned syntax analysis device, and receives aforementioned network address message, and produces a plurality of hash index with characteristic independent distribution characteristic;

One choice device is connected in aforementioned plural groups displacement control logic and receives aforementioned plural groups hash index, and selects wherein hash index output;

One data stream list stores soon the get data stream message of other end points to the data stream of end points, and receives the hash index that aforementioned choice device is exported, and according to the judgement of passing on of the package of corresponding login message of this hash index output and arrival; And

One Compare Logic receives the login message that aforementioned network address message and aforementioned data stream table are exported, and exports one according to the login message that is received and select signal and control signal;

Wherein, aforementioned choice device is selected plural groups hash index according to the aforementioned selection signal of aforementioned Compare Logic.

The control signal that aforementioned Compare Logic is exported comprises successful inquiring control signal and inquiry error control signal.

Aforementioned Compare Logic is when comparing received login message for empty login, then with the successful inquiring control signal activation in the aforementioned control signal.

Aforementioned Compare Logic then changes aforementioned selection signal, to select another hash index when to compare received login message be not empty login.

Aforementioned Compare Logic is relatively crossed in the time of still can't finding empty login after a plurality of login messages, then with the activation of the error of the inquiry in aforementioned control signal control signal.

Above-mentioned displacement control logic comprises:

One bit shift register is divided into plurality of sections, in order to according to a number of setting the hash key of number, carries out the displacement of this plurality of sections; And

The XOR arithmetic unit is in order to carry out the XOR computing of above-mentioned plurality of sections.

At least comprise step:

Obtain the network address from the header of a package that arrives;

The network address of cutting apart this m position is plurality of sections S _i, each section has the n position, wherein

Carry out section S _BaseAnd section S _ExtendThe XOR computing, to produce a hash index with characteristic independent distribution characteristic, wherein this section S _BaseFormation, be the result that this each section is carried out the XOR computing, and this section S _ExtendFormation, be to section S ₀Displacement is by the result of the position that number depended on of a specific hash key; And

Have the hash search index one network address inquiry table of characteristic independent distribution characteristic with this, pass on message with generation.

More comprise step: by inserting binary zero, so that above-mentioned section

Have and section S ₀Identical length.

The above-mentioned network address is data stream address, and above-mentioned network address inquiry table is a data stream table.

The above-mentioned network address is purpose IP address, and above-mentioned network address inquiry table is a routing table.

The above-mentioned network address is a MAC Address, and above-mentioned network address inquiry table is a filter table.

When above-mentioned when having characteristic independent distribution characteristic hash index, pass on above-mentioned arrival package to a processor not at above-mentioned network address inquiry table.

The present invention is a kind of query engine of network equipment, comprises: a syntax analysis device, and in order to the network address information of the package of obtaining arrival.The displacement control logic of specific quantity in order to the network address information according to the package that arrives, produces the hash index of characteristic independent distribution (I.I.D.).The output of each displacement control logic is selected one by one via selector, can be by requester network address lookup table, and export the corresponding information of passing on.

The present invention more proposes a kind of method that is applied to the query engine of network equipment, and the method includes the steps of: at first, partly obtain network address information from the header of the package that arrives.Then, the network address with the m position is divided into a plurality of section S _i, each section has the n position, wherein Then, carry out section S _BaseAnd S _ExtendThe XOR computing, to produce I.I.D. hash index.Wherein, section S _BaseBe to form by the mode of on each section, carrying out the XOR computing, and section S _ExtendBe to change section S by wheel ₀Several certain number bit and form, determine and the bit of these several certain number is numbers according to the hash key.Afterwards, utilize I.I.D. hash search index network address inquiry table, the information of passing on generation.

Description of drawings

Fig. 1 is the cache architecture schematic diagram of a conventional art.

Fig. 2 is a functional block diagram according to the query engine framework of the network equipment of preferred embodiment of the present invention.

Fig. 3 is the functional block diagram of the multiple subitem hash mechanism of foundation preferred embodiment of the present invention.

Fig. 4 is a flow chart according to the operation workflow of the displacement control logic of preferred embodiment of the present invention.

Embodiment

For solving the problem of traditional hash collision, and provide a kind of inquiry mechanism of the layer-4 of being applicable to network equipment, the invention provides a kind of hardware execution mode of simple hash mechanism, be to select one to have characteristic independent distribution (Identity Independent Distribution, hereinafter to be referred as I.I.D.) the hash function of characteristic, with requester network address lookup table more effectively.The network equipment that hash mechanism of the present invention is tabled look-up applicable to any needs, to produce the judgement (packet forwardingdecision) that package passes on, as layer-2, layer-3, and interchanger (switch), router (router) or the bridger (bridge) etc. of layer-4.

Fig. 2 shows the basic framework of the query engine 10 of the network equipment that the layer-4 service can be provided.When the network equipment of layer-4 was received a package, just the package that will arrive was sent to query engine 10, to make the judgement that package passes on.The header of the package that arrives partly will be analyzed by syntax analysis device (parser) 11, offer package sorter 12 respectively with the information with header, layer-3 logical one 4, and layer-2 logical one 8.Relevant layer-2 and layer-3 pass on the framework of engine and are known by the general personnel that grasp this skill, therefore detailed description no longer.Generally with regard to the layer-3 service that network equipment provided, syntax analysis device 11 can transfer to layer-3 logical one 4 with the purpose IP address of arrival package, with table of query and routing 141, and makes the corresponding output port port of routing table 141 outputs.Then, the information of output port just is sent to and merges logic (Merge Logic) 16.On the other hand, in the service level of layer-2, the MAC Address of arrival package can be transferred to layer-2 logical one 8, with query filter table (filtering table) 181, and outputs to corresponding output port.This output port can be sent to too and merge logical one 6.Merge 6 of logical ones and utilize the information of output port how to handle the package of this arrival, and transmit output port information to passing on engine (forwarding engine) 17 to instruct input port.Any inquiry error (lookupmiss) will be sent to CPU, and (Central Process Unit CPU) 13 does further to handle with the package that will arrive.

A rule list (rule table) 131 is arranged among the CPU13, with differentiation (servicedifferentiation) as service type, wherein also has filtering packets (packet filtering), strategy choosing footpath (policyrouting), flow restriction (traffic rate limiting) can be taken into account payment functions such as (accounting andbilling).Rule list 131 can be defined by the system/network manager, or downloads from policy server (policy server).The data structure of rule list 131 comprises: source IP addresses (source IPaddress), source IP addresses shielding (source IP address mask), purpose IP address (destination IP address), purpose IP address mask (destination IP address mask), come destination port range (source port range), destination interface scope (destination port range), agreement ID (protocol ID), permissible input rate (allowed input rate), each jumps behavior (the Per-hop behavior of journey, PHB), reach the next journey fields such as (hop) of jumping.Every rule can comprise more than one data flow (flow).The example that several rules are below arranged, these examples only supply the usefulness of explanation, but not in order to limit the scope of the invention.For example:

Rule 1, (Service Differentiation) distinguished in service: the information that should receive EF PHB from the next package of sub-network 1.2.3.x.

Rule 2, filtering packets (Packet Filtering): refusing all is the package of 7.8.9.x from 4.5.6.x and purpose.

Rule 3, strategy choosing footpath (Policy Routing): transmit all voice IP (voice-over-IP) packages, and be sent to 20.4.5.6 by the atm network that separates from 10.2.3.x.

Rule 4 can be taken into account payment (Accounting; Billing): give the highest priority with all image data flows (video traffic) that are sent to 80.90.100.200, and will be chargeed with the flow that this mode transmits.

Rule 5, rate of discharge restriction (Traffic Rate Limiting): determine that sub-network 30.7.8. can not pour in the above Email of 5Mbps, and determine that whole flow control is at 20Mbps.

When package sent query engine 10 to, the header information of the package of arrival will be used as data stream address (flow address), with the data stream list 121 of inquiry package sorter 12.To the package of any new arrival, package can cause the inquiry error of data stream list.Then, package just can be sent to CPU13, with the rule that is defined in the foundation rule list 131, further package is classified.Should will utilize the algorithm of CPU computing to install in advance, so that the package that arrives is classified.

Each package that is sent to CPU13 can meet at least one above-mentioned defined rule.Every rule is specified a kind of classification that package can be sorted out, as Per-Hop Behavior (PHB).Based on the classification of these appointments, package just can be transmitted according to the classification of these services.Simultaneously, CPU13 can produce new data inputs (entry) for belonging to the arrival package of this data flow in data stream list 121.In a preferred embodiment of the present invention, package sorter (packet classifier) 12 has the ability of automatic study (Auto-learning).Just, package sorter 12 will be learnt the mode of passing on (forwarding behavior) of CPU13, selects as PHB, and this selection is recorded in the data stream list 121.

The header information that package sorter 12 use syntax analysis devices 11 are provided is to form data stream address (flow address), the inquiry of the line data stream table 121 of going forward side by side.So-called " data flow " is that a kind of application is to using the package stream of (application-to-application) (flow), and " data flow " is by source IP (SIP), purpose IP (DIP), agreement (PRO), comes source port (SP), and the bit combination that bit constituted (bit-combination) of destination interface information such as (DP).Data stream list 121 writes down source IP addresses, purpose IP addresses, comes source port, destination interface, agreement ID, reaches information such as rule index, to produce the metering ID (MID) corresponding to the package that arrives.

For explaining orally conveniently, the embodiment that attempts some data flow is as follows:

Data flow-1: from IP 1.2.3.4, port 1500 to IP 100.2.3.4, port 150, wait the package that comes, be one to meet the data flow of rule-1, in data stream list 121 login (entry).

Data flow-2: from IP 1.2.3.8, port 2500 to IP 200.2.3.4, the package that port 250 arrives also belongs to the data flow of EF (expedited forwarding).

Traffic policy management devices (Traffic Profile Manager) 15 is safeguarded a gauge table 151.The data structure of gauge table 151 comprises: the empty hurdle (token bucket) of symbol, the input rate (allowedinput rate) of allowing, last more new login (last time update entry, token enoughPHB, token not enough PHB, and token not enough next hop).Whether gauge table 151 quantitative statistics of call wire upper reaches and flow parameters meet the scheme (profile) of setting with the flow of determination data stream.Gauge table 151 is the activity of (in-profile) and scheme outer (out-of-profile) in the record scheme respectively also.The metering ID that gauge table 151 will be exported according to data stream list 12, output one decision of passing on is given and is passed on engine (forwarding engine) 17.Gauge table 151 also exportable one passes on port and judges to merging logical one 6.With above-mentioned example is example, and data flow-1 should meet the flow scheme (traffic profile) that rule-1 is defined with data flow-2.Any inquiry error also will be delivered to CPU13 and handle.

Query engine 10 has the mechanism of requester network address lookup table, including but not limited to data stream list 121, and gauge table 151, routing table 141 and filter table 181.Inquiry with data stream list 121 is an example, the invention provides a hash mechanism, and it can select an I.I.D. hash function with more effective data query stream table 121.Consult Fig. 2, to show the hash mechanism of most preferred embodiment of the present invention.Hash mechanism can translate to more scattered, more equally distributed address with the scope (universe) of hash key.

Consult Fig. 3, data stream list 121 is as the usefulness of other end points to the caching data stream information of the data flow of end points (end-to-end).Login in every data stream list 121 with one fully the filter of appointment (fully specified filter) (promptly not comprising the general-purpose character, no wildcards) correspond to a data flow.Owing to,, flow table 121 with implementation data so the computing of hash can more effectively be carried out without general-purpose character (wildcarding).

For the hash function of I.I.D. characteristic is provided, the present invention uses and has obtained the I.I.D. matrix that proves on a kind of mathematics, by L.Carter and M.Wegman at " Universal Classes of HashingFunctions; " propose in one literary composition, (referring to J.Computer and System Sciences, vol.18, no.2, pp.143-154,1979.) to produce a plurality of I.I.D. hash functions.According to this, the generation of I.I.D. hash function, available data streams address＜SIP, DIP, SP, DP, PRO〉multiply by the I.I.D. matrix and reach.

I.I.D. matrix can be represented in the following manner:

Wherein, B represents the hash index of n position, and Q represents the set of all n * m matrix, and T represents conversion equipment, and A represents the data stream address of m position.According to this, each hash function is B ^T=QA ^TLinear transformation, this linear transformation is m ^-Binary bit stream (bit-stream) A=a of position ₀a ₁... a _M-1Correspond to the binary bit stream of n-position, B=b ₀6 ₁... b _N-1

At this, the k-bit stream is regarded as the vector of k-dimension, so that GF (2)={ 0,1} defines.Q is n * m matrix, is defined and each hash function corresponds to this matrix Q individually by GF (2).Product among the GF (2) and add operation be respectively by boolean AND (with Fu Hao ﹠amp; The expression) and the operand of XOR ( represents with symbol) performed.Therefore, each position of B is calculated as follows: b _i=(a ₀﹠amp; q _{I, 0}) (a ₁﹠amp; q _{I, 1}) ... (a _M-1﹠amp; q _{I, m-1}), i=0,1,2 ..., n-1.

Allow Q refer to n * all possible set of m matrix, wherein n represents 2 ⁿThe data stream list of size, m represents the number of the data stream address of m position.Allow Q _h∈ Q is needed set of matrices, and 0≤h≤n-1 (index h refers to the hash function selector).And, allow q _{I, j}Refer to Q _hAssembly, wherein i represents ranks number (rownumber), j represents Field Count (column number), (0≤i≤n-1 and 0≤j≤m-1).Then, with this understanding:

When j＜n,

If j equals (i+h) mod n, q _{I, j}=1;

Otherwise, q _{I, j}=0;

When j 〉=n,

If i equals j modn, q _{I, j}=1;

Otherwise, q _{I, j}=0.

According to this condition, the I.I.D. hash function can be chosen out from the I.I.D. matrix.Therefore, based on q _{I, j}Definition, b _i=a _{(i+h) modn} a _I+n a _I+n..., i=0 wherein, 1,2 ..., n-1.

According to this condition, suppose to have a hash key X or a data stream address arbitrarily, the hash function h of then multiple subitem N (themulti-way N) ₁(x), h ₂(x) ..., h _N(x) all be the aleatory variable of I.I.D.Just, each hash index is as h ₁(X), can be regarded as a memory headroom address in the data stream list 121.Suppose to have a special data stream address, the hash index that these produced is all inevitable inequality.Being the I.I.D. characteristic of these hash keys of clearer demonstration, is the example explanation with 5 * 19Q matrix, and wherein hash function selector h is 2.Then, Q ₂Through calculating and showing below:

By above matrix as can be known, the arrangement of data stream address in matrix is to distribute scatteredly.And, Q _hThe linear distribution of all ranks vectors (row vectors) all is independently.Select (Q at above-mentioned matrix _h) program form after, just needn't carry out any and computing matrix correlation.

The hardware of above-mentioned method is implemented to utilize easy displacement control logic 22 to reach.Displacement control logic 22 comprises a bit shift register and a plurality of xor logic door.The computing of displacement control logic 22 as shown in Figure 4.According to preferred embodiment shown in Figure 3, each data stream address all can be carried out 4 times hash computing by four displacement control logics 22.In other words, the embodiment of Fig. 3 is under the consideration of cost, but the maximum access datas of each data stream address flow table 121 four times.

Its method is, at first, obtains the data stream address 21 of m position, step 301 from syntax analysis device 11.Then, data stream address 21 is cut into k tune S _i,

Each section S _iComprise n position, the matrix of expression 1 * n.If last section

Remaining position is arranged, then with " 0 " step 302 is filled up in rightmost position.After, Yi Bian carry out S _iThe displacement of section, the figure place of its displacement is by the hash bond number decision that sets, Yi Bian carry out each section S _iThe XOR computing, step 303.In other words, after each XOR computing, section S ₀H-bit (is 4 at this) earlier by displacement to the right.The selected hash index of selector (index _hSo) produce, promptly

Make hash index S _Base=S ₁XOR S ₂XOR...S _K-1Because any data stream address A can be expressed as a ₀, a ₁, a ₂..., a _m, S _BaseSection can be expressed as S _{Base, i}So, S _{Base, i}=a _N+i a _2n+i ....

Step 304-step 311 is relevant S ₀The wheel of h-bit change (rotate) and displacement (shift), to produce the hash index of each I.I.D..Step 304: establish i=0.Then, set S _Extend=Rotate S ₀Key[i] bits, to produce a new section, step 305.S _ExtendAssembly can S _{Extend, i}Represent.So, based on the computing that wheel changes, S _{Extend, i}=a _{(i+h) mod n}Then, to carry out S _BaseAnd S _ExtendThe mode of XOR running, produce I.I.D. hash index.Index _h=S _BaseXOR S _Extend, step 306.Work as Index _hDuring for result calculated, Index _hAssembly can use Index _{H, i}Expression.Therefore, Index _{H, i}=a _{(i+h) modn} _An+i a _2n+i ....According to this, the result of wheel commentaries on classics (rotation) and XOR computing is equal to the computing (matrix operation) of matrix.

Check i then whether less than the number (key number) of hash key, step 307.If execution in step 308 adds 1 with the value with i, execution in step 305 then.Repeat these steps, produce all up to 4 hash keys, execution in step 309 finishes then.

Four hash keys that displacement control logic 22 produced are chosen according to the control of Compare Logic 24 by selector 23 in order, up to the login of finding a sky (entry).Whether comparator logic 24 is checked the login in the pairing data stream list 121 of this present hash index in order, be idle.If this login just is selected.Otherwise this comparator logic 24 just transmits one and controls signal to selector 23, to choose next available hash key 22.This program repeat carries out, and has been selected all up to each hash index 22.If in the hash search index of the first round, can not find idle position, just the information of inquiry error can be sent to CPU13, to handle the package that arrives.

According to this, when the demand of an inquiry arrived, the data stream address 21 of 104-position will be used to produce the hash index of n-position in this demand.For example, if the value of n is 16, then the size of data stream list is 64K (2 ⁿ=2 ¹⁶).Instinctively, if carry out mode (32-bit → 16-bit) compare, such hash pairing (104-bit → 16-bit) can cause collision probability highly with the hash of IP address.Yet because the present invention has used I.I.D. matrix described above, so the probability of hash collision has been reduced to minimum.

In sum, the selected hash function of the present invention can ensure when tabling look-up, and can make the inquiry of forms and data insertion have the characteristic of I.I.D..Therefore, the present invention can more effectively use memory headroom and can the same fast access internal memory with Layer-3 logic and Layer-2 logic, to finish its work in the same package processing cycle.So, the just login of every data flow of construction and the package that belongs to this data flow carried out classification of service apace of query engine.

Claims

1. A query engine applied to a network device, characterized in that it comprises:

a grammar analyzer, used to receive the incoming packet, and analyze the network address information of the incoming packet;

A complex array displacement control logic, connected to the aforementioned grammar analyzer, and receiving the aforementioned network address information, and generating a plurality of hash indexes with independent distribution characteristics;

A selection device, connected to the aforementioned complex array displacement control logic and receiving the aforementioned complex array hash indexes, and selects one of the hash indexes to output;

A data flow table, storing the cached data flow information of the individual end-to-end data flow, and receiving the hash index output by the selection device, and outputting the corresponding login message and the forwarding decision of the incoming packet according to the hash index; as well as

A comparison logic, receiving the aforementioned network address information and the login information outputted by the aforementioned data flow table, and outputting a selection signal and a control signal according to the received login information;

Wherein, the selection means selects the complex group hash index according to the selection signal of the comparison logic.

2. The query engine according to claim 1, wherein the control signal output by the comparison logic includes a query success control signal and a query failure control signal.

3. The query engine as claimed in claim 2, wherein the comparison logic enables the query success control signal in the control signals when the comparison logic finds out that the received login information is empty.

4. The query engine as claimed in claim 3, wherein the comparison logic changes the selection signal to select another hash index when the comparison logic finds that the received entry information is not an empty entry.

5. The query engine as claimed in claim 3, wherein the comparison logic enables the query error control signal in the control signal when no empty entry can be found after comparing a plurality of login messages.

6. The query engine according to claim 1, wherein the above-mentioned displacement control logic comprises:

a shift register, divided into a plurality of segments, for performing shifting of the plurality of segments according to a set number of hash keys; and

The XOR operation device is used for performing the above-mentioned XOR operation of the plurality of segments.

7. A query method applied to a network device, comprising at least the steps of:

Get the network address from the header of an incoming packet;

Divide the m-bit network address into a plurality of segments S _i , each segment has n bits, where

Execute the XOR operation of the segment S _base and the segment S _extend to generate a hash index with independent distribution characteristics, wherein the formation of the segment S _base is the result of XOR operation on each segment, and the section S _extend is formed as a result of shifting section S ₀ by the number of bits determined by a particular hash key; and

A network address lookup table is queried by the hash index with the property independent distribution property to generate forwarding messages.

8. The method of claim 7, further comprising the steps of:

By filling in binary 0s, the above field has the same length as section S ₀ .

9. The method according to claim 7, wherein said network address is a data flow address, and said network address lookup table is a data flow table.

10. The method according to claim 7, wherein said network address is a destination IP address, and said network address lookup table is a routing table.

11. The method according to claim 7, wherein said network address is a MAC address, and said network address lookup table is a filtering table.

12. The method of claim 7, further comprising the following steps:

Forwarding the incoming packet to a processor when the characteristic hash index with characteristic independent distribution is not in the network address lookup table.