CN103001878A - Determination method and device for media access control (MAC) address Hash collision - Google Patents

Abstract

The invention provides a determination method and device for media access control (MAC) address Hash collision. The method comprises performing N-order Hash on key values, obtaining N Hash values, enabling N to be an integer larger than 2; respectively using M Hash values to search M Hash tables in a one-to-one correspondence mode, obtaining M Hash table items, and enabling M to be smaller than N; using (N-M) Hash values in the N Hash values except the M Hash values to undergo ergodic comparison with the Hash values in the M Hash table items, and searching and/or studying MAC addresses where Hash collision exists. According to an embodiment, by performing multiple-order Hash on the key values, the probability of the Hash collision is effectively reduced, and accordingly occupation of a ternary content addressable memory (TCAM) space is greatly reduced.

Description

Definite method and the device of MAC Address hash-collision

Technical field

The present invention relates to field of computer technology, relate in particular to definite method and the device of a kind of media interviews control (MAC) Address-Hash conflict.

Background technology

A position visits record to Hash table (Hash table also cries hash table) in the table by key value is mapped to.This mapping function is called hash function, and the array of put is called Hash table.May obtain same hash address to different keywords, i.e. Key1 ≠ Key2, and f (Key1)=f (Key2), this phenomenon claims hash-collision.The advantage of Hash table lookup method is to search fast, and the memory space utilance is high.Shortcoming is that the time of searching is unfixing, and the conflict time of searching longer more.

MAC (Media Access Control, media interviews control) address is the sign of identifying LAN node, and the whole world is unique.MAC Address is 48, represent with 12 hexadecimal numbers, wherein, front 24 by IEEE (Institute of Electrical and Electronics Engineers, IEEE-USA) distributes, be used for recognition network equipment vendors, consist of OUI (OrganizationalUnique Identifier, organize unique identifier), specified voluntarily by network equipment vendor for rear 24.

In Ethernet, two layers of forwarding need to be to MAC+VSID (Virtual Switching InstanceDoman, the virtual switch instance territory) carrying out forwarding lookup and study searches, because MAC Address has 48, general 16 of VSID, totally 64 of MAC+VSID can not distribute a list item for each address in practice, therefore generally realize by Hash table.

Fig. 1 is that a kind of MAC searches flow chart in the prior art, at first searches Hash table, if there is hash-collision, continues to search conflict solution table; Fig. 2 is that another kind of MAC searches flow chart in the prior art, at first searches conflict solution table, if do not mate, continues to search Hash table.Both differences are the sequencing that Hash table and conflict solution table are searched.The Hash table scheme of a success should be to remove as few as possible to search conflict solution table, minimizing takies conflict solution table place memory, conflict solution table generally is placed among the TCAM (Ternary Content Addressable Memory, three-state content addressing memory).

In the prior art, as long as hash-collision occurs, just list item is write hash-collision solution table, hash-collision is larger, and is more to the TCAM resource occupation, increases the TCAM capacity and can be subject to again the large and high restriction of cost of TCAM power consumption.

Summary of the invention

The embodiment of the invention provides a kind of definite method and device of MAC Address hash-collision, with minimizing hash-collision probability, and then greatly reduces taking the TCAM space.

The embodiment of the invention provides definite method of a kind of media interviews control (MAC) Address-Hash conflict, and the method comprises:

Key assignments is Hash N time, obtains N cryptographic Hash, N is the integer greater than 2;

Use respectively M cryptographic Hash one by one correspondence search M Hash table, obtain M hash table, described M is less than described N;

Use that (N-M) the individual cryptographic Hash except a described M cryptographic Hash and the cryptographic Hash in the described M hash table travel through comparison in the described N cryptographic Hash, search and/or learn to exist the MAC Address of hash-collision.

Preferably, described searching exists the MAC Address of hash-collision to comprise:

If traveled through the clauses and subclauses that rear existence equates, then calculate the MAC table address, search corresponding MAC table, compare with key assignments field and described key assignments in the described MAC table, if the two is equal, then determine to find the MAC Address that has hash-collision.

Preferably, after the key assignments field in the described MAC table of described usefulness and described key assignments compare, also comprise:

If the two is unequal, then determine not exist the MAC Address of hash-collision.

Preferably, described study exists the MAC Address of hash-collision to comprise:

If traveled through the clauses and subclauses that rear existence equates, then determine to exist hash-collision, this key assignments is learnt in the conflict solution table;

If there are not equal clauses and subclauses after having traveled through, then calculate the idle entry number in the described M hash table, if the idle entry number in the described M hash table is zero, then this key assignments is learnt in the described conflict solution table; If the idle entry number in the described M hash table not all is zero, then search and whether exist cryptographic Hash to equal the clauses and subclauses of arbitrary cryptographic Hash in described (N-M) individual cryptographic Hash in hash-collision table corresponding to the non-vanishing hash table of idle entry number, if exist, then this key assignments is learnt in the described conflict solution table, if there is no, judge then whether the conflict list item is full in this hash-collision table, if full, then this key assignments learnt in the described conflict solution table.

Preferably, described judge in this hash-collision table that the conflict list item is whether full after, also comprise:

If less than, then described (N-M) individual cryptographic Hash is write in the described hash-collision table, calculate the MAC table address, this key assignments is learnt in the described MAC table.

The embodiment of the invention also provides definite device of a kind of media interviews control (MAC) Address-Hash conflict, is applied in the network processing unit, and this device comprises:

The Hash module is used for key assignments is Hash N time, obtains N cryptographic Hash, and N is the integer greater than 2;

Search module, be used for using respectively M cryptographic Hash one by one correspondence search M Hash table, obtain M hash table, described M is less than described N;

Processing module travels through comparison for (N-M) individual cryptographic Hash of using a described N cryptographic Hash except a described M cryptographic Hash and the cryptographic Hash in the described M hash table, searches and/or learn to exist the MAC Address of hash-collision.

Preferably, described processing module specifically is used for: if traveled through the clauses and subclauses that rear existence equates, then calculate the MAC table address, search corresponding MAC table, compare with key assignments field and described key assignments in the described MAC table, if the two equates, then determines to find the MAC Address that has hash-collision.

Preferably, described processing module also is used for: if the two is unequal, then determine not exist the MAC Address of hash-collision.

Preferably, described processing module specifically is used for:

If traveled through the clauses and subclauses that rear existence equates, then determine to exist hash-collision, this key assignments is learnt in the conflict solution table;

If there are not equal clauses and subclauses after having traveled through, then calculate the idle entry number in the described M hash table, if the idle entry number in the described M hash table is zero, then this key assignments is learnt in the described conflict solution table; If the idle entry number in the described M hash table not all is zero, then search and whether exist cryptographic Hash to equal the clauses and subclauses of arbitrary cryptographic Hash in described (N-M) individual cryptographic Hash in hash-collision table corresponding to the non-vanishing hash table of idle entry number, if exist, then this key assignments is learnt in the described conflict solution table, if there is no, judge then whether the conflict list item is full in this hash-collision table, if full, then this key assignments learnt in the described conflict solution table.

Preferably, described processing module also is used for: if less than, then described (N-M) individual cryptographic Hash is write in the described hash-collision table, calculate the MAC table address, this key assignments is learnt in the described MAC table.

The embodiment of the invention effectively reduces the probability of hash-collision by key assignments being done repeatedly Hash, thereby greatly reduces taking the TCAM space.

Description of drawings

Fig. 1 is that a kind of MAC of the prior art searches flow chart;

Fig. 2 is that another kind of MAC of the prior art searches flow chart;

Fig. 3 is the schematic diagram of used in the present invention couple of Hash lookup table embodiment;

List item Relations Among schematic diagram when Fig. 4 is the two Hash lookup of the embodiment of the invention;

Fig. 5 is the flow chart of the two Hash lookup processes of the embodiment of the invention;

Hash-collision schematic diagram when Fig. 6 is embodiment of the invention mac learning;

Fig. 7 is Hash collision table schematic diagram in the embodiment of the invention mac learning;

Fig. 8 is the flow chart of embodiment of the invention mac learning process;

Fig. 9 is the structural representation of definite device of embodiment of the invention MAC Address hash-collision.

Embodiment

For making the purpose, technical solutions and advantages of the present invention clearer, hereinafter in connection with accompanying drawing embodiments of the invention are elaborated.Need to prove that in the situation of not conflicting, the embodiment among the application and the feature among the embodiment be combination in any mutually.

Hash-collision in the embodiment of the invention mainly is present in following two kinds of situations:

When 1) MAC searches, find key value and not yet learn in the list item, but and learn to have produced hash-collision into the key assignments of list item, find same MAC table list item, at this moment, need to finding key value and showing that the Compare field compares among the result, judge whether it is this corresponding list item that finds key value;

2) hash-collision during mac learning.

For above-mentioned two kinds of hash-collisions, the embodiment of the invention provides definite method of a kind of media interviews control (MAC) Address-Hash conflict, and the method comprises:

Key assignments is Hash N time, obtains N cryptographic Hash, N is the integer greater than 2;

Use respectively M cryptographic Hash one by one correspondence search M Hash table, obtain M hash table, described M is less than described N;

Use that (N-M) the individual cryptographic Hash except a described M cryptographic Hash and the cryptographic Hash in the described M hash table travel through comparison in the described N cryptographic Hash, search and/or learn to exist the MAC Address of hash-collision.

Above-mentioned M is preferably N-1, and for example N is that 3, M is 2, and certainly, N can also be 3 for 4, M, and in addition, M can also be 2, etc.

Wherein, the hash-collision when searching for MAC, adopt following processing scheme:

As shown in Figure 3, be the schematic diagram of used in the present invention couple of Hash lookup table embodiment, can learn the list item definition of two Hash lookup tables by this figure:

Hash table is defined as n Hash list item (List), and each Hash List (be called for short HL) comprises m Hash clauses and subclauses, and whether valid bit representation clauses and subclauses are effective, and the Hash field is that key assignments is done cryptographic Hash behind the Hash.

MAC table capacity is n*m list item, each list item comprises two parts, Compare (being called for short Comp) field is original key assignments, judge hash-collision when being used for searching, the reason that this hash-collision produces is: the key assignments when searching is not yet learnt in the list item, but and learn to have produced hash-collision into the key assignments of list item, find same MAC table list item, at this moment, need to finding key value and showing that the Compare field compares among the result, judge whether it is this corresponding list item that finds key value.MAC result (MAC Result) is used for depositing the MAC forwarding information.

As shown in Figure 4, list item Relations Among schematic diagram in this embodiment, is done Hash three times to key assignments when being the two Hash lookup of the embodiment of the invention, produces three cryptographic Hash: HashA, HashB, HashC; Search respectively Hash table A, Hash table B with HashA, HashB, lookup result is Hash entry A, Hash entry B, i.e. the described Hash List of Fig. 3; Then with the hash value among HashC and Hash List A, the Hash ListB relatively, if do not find equal clauses and subclauses, then do not match clauses and subclauses in the two Hash lookups of expression; If find equal clauses and subclauses, continue to search the MAC table, with the Compare field in the MAC table and the comparison that finds key value, if equate, expression finds the coupling clauses and subclauses; If unequal, expression does not find the coupling clauses and subclauses.

As shown in Figure 5, be the flow chart of the two Hash lookup processes of the embodiment of the invention, this process comprises:

Step 101, do Hash three times to finding key value, obtain three cryptographic Hash: HashA, HashB, HashC;

Step 102, search Hash table A, Hash table B with HashA, HashB correspondence, obtain Hash entry Hash List A and Hash List B;

Step 103, relatively (travel through first Hash List A with the hash value among HashC and Hash List A, Hash List B traversal, if without occurrence, travel through again Hash List B), if do not have equal clauses and subclauses after having traveled through all clauses and subclauses, then the two Hash tables of expression do not match clauses and subclauses;

If there be clauses and subclauses and thevalid position 1 that equates instep 104, the address that record matching list item HashList is corresponding is RamAddr, and skew corresponding to coupling clauses and subclauses is index among the record HashList;

Step 105, calculating MAC table address: RamAddr*m+index search the MAC table;

Step 106, with the Compare field in the MAC table with find key value comparison, if equate, expression finds the coupling clauses and subclauses; If unequal, expression does not find the coupling clauses and subclauses.

Wherein, the hash-collision during for mac learning, adopt following processing scheme:

As shown in Figure 6, the hash-collision schematic diagram when being embodiment of the invention mac learning, among this embodiment, Key1 is through twice Hash, respectively Hash List j among Hash List i and the Hash table B among the corresponding Hash table A; According to preferentially writing many this principles of Hash table of idle clauses and subclauses, suppose the idle clauses and subclauses of Hash Listj of Hash table B at this moment more than the Hash List i of Hash table A, so Key1 writes the Hash Listj of Hash table B;

During study Key2, Key2 is done Hash twice, Hash List k among Hash List i and the Hash table B among the corresponding Hash table A of difference, namely the HashA value of Key2 and Key1 is identical, has produced hash-collision; Suppose that the idle clauses and subclauses of Hash List i of Hash table A at this moment are more than the Hash List k of Hash table B, therefore Key2 writes the Hash List i of Hash table A, if at this moment the HashC value of Key2 and Key1 is identical, produced hash-collision, because Key1 writes the Hash List i of Hash table A, Key1 can match these clauses and subclauses among the Hash List i of Hash table A when searching, cause the mistake coupling.

The condition that this hash-collision exists is: the HashA of Key1 and Key2, HashB have one to produce hash-collision (such as the HashA among Fig. 6), the key assignments of rear interpolation will write in the Hash table that produces hash-collision (the Hash table A in showing such as Fig. 6), and HashC produces hash-collision.

In order to solve this hash-collision, define a hash-collision table.

As shown in Figure 7, it is Hash collision table schematic diagram in the embodiment of the invention mac learning, the hash-collision table definition is n conflict list item (Collision List, CL), each Collision List list item comprises k Hash clauses and subclauses (the hash-collision degree of depth is k), and whether valid bit representation clauses and subclauses are effective.

As shown in Figure 8, be the flow chart of embodiment of the invention mac learning process, this process comprises:

Step 201, key assignments is done Hash three times, obtain three cryptographic Hash: HashA, HashB, HashC;

Step 202, search Hash table A, Hash table B with HashA, HashB, obtain Hash List A, Hash List B;

Step 203, with the hash value among HashC and Hash List A, Hash List B traversal relatively (travel through first Hash List A, if without occurrence, travel through again Hash List B).If occurrence is arranged, andvalid position 1, there is hash-collision in expression, and this key assignments is learnt conflict solution table;

Step 204, the clauses and subclauses that if there is no equate are calculated idle entry number among Hash table A and the Hash table B list item HashList, and recording the many hash table addresses of idle entry number is RamAddr, and another hash table address is designated as RamAddrOther; If there are not idle clauses and subclauses in Hash table A and Hash table B list item HashList, this key assignments is learnt conflict solution table;

If there are idle clauses and subclauses instep 205 Hash table A or Hash table B list item HashList, search hash-collision table (Collision Table, CT), whether exist the hash value to equal the clauses and subclauses of HashC and valid=1 in the traversal conflict list item (Collision List), if exist, this key assignments is learnt conflict solution table;

If do not exist the hash value to equal the clauses and subclauses of HashC and valid=1 amongstep 206 hash-collision table (CollisionTable) the Collision List, judge whether Collision List is full, if CollisionList is full, this key assignments is learnt conflict solution table;

Ifstep 207 Collision List less than, HashC is write Hash table; Writing address is RamAddr+index;

HashTable[RamAddr][index].hash＝HashC

HashTable[RamAddr][index].valid＝1

Ifstep 208 Collision List less than, HashC is write the hash-collision table, judge conflict when being used for new key assignments study; Writing address is RamAddrOther+index;

CollisionTabel[RamAddrOther][index].hash＝HashC

CollisionTabel[RamAddrOther][index].valid＝1

Step 209, this key assignments is learnt MAC table, writing address is RamAddr*m+index.

The embodiment of the invention effectively reduces the probability of hash-collision by key assignments being done repeatedly Hash, thereby greatly reduces taking the TCAM space.

As shown in Figure 9, be the structural representation of definite device of embodiment of the invention MAC Address hash-collision, this determines application of installation in network processing unit, this device comprises Hash module 11,searches module 12 andprocessing module 13, wherein:

The Hash module is used for key assignments is Hash N time, obtains N cryptographic Hash, and N is the integer greater than 2;

Search module, be used for using respectively M cryptographic Hash one by one correspondence search M Hash table, obtain M hash table, described M is less than described N;

Processing module travels through comparison for (N-M) individual cryptographic Hash of using a described N cryptographic Hash except a described M cryptographic Hash and the cryptographic Hash in the described M hash table, searches and/or learn to exist the MAC Address of hash-collision.

Wherein, described processing module specifically is used for: if traveled through the clauses and subclauses that rear existence equates, then calculate the MAC table address, search corresponding MAC table, compare with key assignments field and described key assignments in the described MAC table, if the two equates, then determines to find the MAC Address that has hash-collision.In addition, described processing module also is used for: if the two is unequal, then determine not exist the MAC Address of hash-collision.Concrete processing procedure can be referring to Fig. 5.

Similarly, described processing module specifically is used for: if traveled through the clauses and subclauses that rear existence equates, then determine to exist hash-collision, this key assignments is learnt in the conflict solution table; If there are not equal clauses and subclauses after having traveled through, then calculate the idle entry number in the described M hash table, if the idle entry number in the described M hash table is zero, then this key assignments is learnt in the described conflict solution table; If the idle entry number in the described M hash table not all is zero, then search and whether exist cryptographic Hash to equal the clauses and subclauses of arbitrary cryptographic Hash in described (N-M) individual cryptographic Hash in hash-collision table corresponding to the non-vanishing hash table of idle entry number, if exist, then this key assignments is learnt in the described conflict solution table, if there is no, judge then whether the conflict list item is full in this hash-collision table, if full, then this key assignments learnt in the described conflict solution table.In addition, described processing module also is used for: if less than, then described (N-M) individual cryptographic Hash is write in the described hash-collision table, calculate the MAC table address, this key assignments is learnt in the described MAC table.Concrete processing procedure can be referring to Fig. 8.

Above-mentioned definite device can effectively reduce the probability of hash-collision by key assignments being done repeatedly Hash, thereby greatly reduces taking the TCAM space.

One of ordinary skill in the art will appreciate that all or part of step in the said method can come the instruction related hardware to finish by program, said procedure can be stored in the computer-readable recording medium, such as read-only memory, disk or CD etc.Alternatively, all or part of step of above-described embodiment also can realize with one or more integrated circuits.Correspondingly, each the module/unit in above-described embodiment can adopt the form of hardware to realize, also can adopt the form of software function module to realize.The present invention is not restricted to the combination of the hardware and software of any particular form.

Above embodiment is only unrestricted in order to technical scheme of the present invention to be described, only with reference to preferred embodiment the present invention is had been described in detail.Those of ordinary skill in the art should be appreciated that and can make amendment or be equal to replacement technical scheme of the present invention, and do not break away from the spirit and scope of technical solution of the present invention, all should be encompassed in the middle of the claim scope of the present invention.

Claims (10)

1. definite method that (MAC) Address-Hash conflicts is controlled in media interviews, it is characterized in that the method comprises:

Key assignments is Hash N time, obtains N cryptographic Hash, N is the integer greater than 2;

Use respectively M cryptographic Hash one by one correspondence search M Hash table, obtain M hash table, described M is less than described N;

Use that (N-M) the individual cryptographic Hash except a described M cryptographic Hash and the cryptographic Hash in the described M hash table travel through comparison in the described N cryptographic Hash, search and/or learn to exist the MAC Address of hash-collision.

2. method according to claim 1 is characterized in that:

Described searching exists the MAC Address of hash-collision to comprise:

If traveled through the clauses and subclauses that rear existence equates, then calculate the MAC table address, search corresponding MAC table, compare with key assignments field and described key assignments in the described MAC table, if the two is equal, then determine to find the MAC Address that has hash-collision.

3. method according to claim 2 is characterized in that:

After key assignments field in the described MAC table of described usefulness and described key assignments compare, also comprise:

If the two is unequal, then determine not exist the MAC Address of hash-collision.

4. method according to claim 1 is characterized in that:

Described study exists the MAC Address of hash-collision to comprise:

If traveled through the clauses and subclauses that rear existence equates, then determine to exist hash-collision, this key assignments is learnt in the conflict solution table;

If there are not equal clauses and subclauses after having traveled through, then calculate the idle entry number in the described M hash table, if the idle entry number in the described M hash table is zero, then this key assignments is learnt in the described conflict solution table; If the idle entry number in the described M hash table not all is zero, then search and whether exist cryptographic Hash to equal the clauses and subclauses of arbitrary cryptographic Hash in described (N-M) individual cryptographic Hash in hash-collision table corresponding to the non-vanishing hash table of idle entry number, if exist, then this key assignments is learnt in the described conflict solution table, if there is no, judge then whether the conflict list item is full in this hash-collision table, if full, then this key assignments learnt in the described conflict solution table.

5. method according to claim 4 is characterized in that:

Described judge in this hash-collision table that the conflict list item is whether full after, also comprise:

If less than, then described (N-M) individual cryptographic Hash is write in the described hash-collision table, calculate the MAC table address, this key assignments is learnt in the described MAC table.

6. definite device that (MAC) Address-Hash conflicts is controlled in media interviews, it is characterized in that be applied in the network processing unit, this device comprises:

The Hash module is used for key assignments is Hash N time, obtains N cryptographic Hash, and N is the integer greater than 2;

Search module, be used for using respectively M cryptographic Hash one by one correspondence search M Hash table, obtain M hash table, described M is less than described N;

Processing module travels through comparison for (N-M) individual cryptographic Hash of using a described N cryptographic Hash except a described M cryptographic Hash and the cryptographic Hash in the described M hash table, searches and/or learn to exist the MAC Address of hash-collision.

7. device according to claim 6 is characterized in that:

Described processing module specifically is used for: if traveled through the clauses and subclauses that rear existence equates, then calculate the MAC table address, search corresponding MAC table, compare with key assignments field and described key assignments in the described MAC table, if the two is equal, then determine to find the MAC Address that has hash-collision.

8. device according to claim 7 is characterized in that:

Described processing module also is used for: if the two is unequal, then determine not exist the MAC Address of hash-collision.

9. device according to claim 6 is characterized in that:

Described processing module specifically is used for:

If traveled through the clauses and subclauses that rear existence equates, then determine to exist hash-collision, this key assignments is learnt in the conflict solution table;

If there are not equal clauses and subclauses after having traveled through, then calculate the idle entry number in the described M hash table, if the idle entry number in the described M hash table is zero, then this key assignments is learnt in the described conflict solution table; If the idle entry number in the described M hash table not all is zero, then search and whether exist cryptographic Hash to equal the clauses and subclauses of arbitrary cryptographic Hash in described (N-M) individual cryptographic Hash in hash-collision table corresponding to the non-vanishing hash table of idle entry number, if exist, then this key assignments is learnt in the described conflict solution table, if there is no, judge then whether the conflict list item is full in this hash-collision table, if full, then this key assignments learnt in the described conflict solution table.

10. device according to claim 9 is characterized in that:

Described processing module also is used for: if less than, then described (N-M) individual cryptographic Hash is write in the described hash-collision table, calculate the MAC table address, this key assignments is learnt in the described MAC table.

Images