Method and apparatus used in hashing algorithm for reducing conflict probability

• US 5,633,858 A
• Filed: 02/29/1996
• Issued: 05/27/1997
• Est. Priority Date: 07/28/1994
• Status: Expired due to Term

• Current Assignee: Accton Technology Corporation
• Original Assignee: Accton Technology Corporation
• Inventors: Cheng, Ray-Guang, Hwang, Lain-Chyr, Chang, Chung-Ju, Yu, Ji-Hsiang
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US08/608,704
• Time in Patent Office: 453 Days
• Field of Search: 370/13, 370/13.1, 370/17, 370/60, 370/60.1, 370/79, 370/85.1, 370/85.2, 370/85.3, 370/85.13, 370/94.1, 370/94.2, 370/94.3, 370/110.1, 371/32, 371/33, 371/37.1, 371/40.1, 371/67.1, 371/69.1, 371/71, 395/185.01, 395/185.02, 395/185.03, 395/185.05, 395/200.02, 395/421.06, 395/421.07, 395/421.1, 395/421.11, 395/500, 395/650, 395/800 , 395/846, 395/848, 395/860, 395/863
• US Class Current: 370/255
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

The present invention is related to a method adapted to be used in hashing algorithm for reducing conflict probability which comprises the steps of receiving a first physical address of a frame; generating a hashing address corresponding to the first physical address; comparing a second physical address corresponding to the hashing address with the first physical address to determine if the first and the second physical addresses match with each other; completing a packet calling process when the first and the second physical addresses match with each other, but going back to the comparing process when the first and the second physical addresses do not match with each other, to determine whether there is another second physical address corresponding to the hashing address and matching with the first physical address; and ending the packet calling process when a number of times that the comparing process is proceeded is greater than a reference value. By this method, a specific conflict probability is obtained, and according to the results, the conflict probability and the broadcasting probability are reduced and the source of the network is saved.

Claims

1. A method adapted to be used in hashing algorithm for reducing conflict probability, comprising the steps of:

receiving a first physical address of a frame;

generating a hashing address corresponding to said first physical address;

comparing a second physical address corresponding to said hashing address with said first physical address to determine if said first and said second physical addresses match with each other;

completing a packet calling process when said first and said second physical addresses match with each other, but going back to said comparing process when said first and said second physical addresses do not match with each other, to determine whether there is another second physical address corresponding to said hashing address and matching with said first physical address;

ending said packet calling process when a number of times that said comparing process is proceeded is greater than a reference value; and

the resulting conflict probability is less than a designated value, which is substantially equal to ##EQU9## wherein m is the length of said first physical address;

n is the length of said hashing address;

.sup. m is the total number of said second physical addresses;

2ⁿ is the number of hashing addresses to be held in a routing table; and

therefore

1/2ⁿ is the probability that a specific address in the routing table is selected;

.sup. m-n is the number of physical addresses that hash to the same address in the routing table; and

therefore ##EQU10## is the probability that an address hashes to a selected address in the routing table;

N is the total number of routing tables; and

N-1 is number of a back-up routing table.

2. A method according to claim 1, wherein a definition that said second physical address and said first physical address match with each other is that said second physical address and said first physical address are identical.

3. A method according to claim 1, wherein said packet calling process is a learning procedure.

4. A method according to claim 3, wherein said completing said packet calling process is to complete a learning procedure which records a source address in a routing table to identify from which port said source address comes.

5. A method according to claim 3, wherein said ending packet calling process is to execute a modifying step which substitutes a physical address for another physical address in a routing table.

6. A method according to claim 3, wherein said first physical address is a source address of said frame.

7. A method according to claim 1, wherein said packet calling process is a routing procedure which requests a destination address from a routing table to identify to which port said source address goes.

8. A method according to claim 7, wherein said completing said packet calling process is to complete a routing procedure.

9. A method according to claim 7, wherein ending said packet calling process is to execute a broadcasting step which sends a packet to every port except the source port itself.

10. A method according to claim 7, wherein said first physical address is a destination address of said frame.

12. A method according to claim 1, wherein said second physical address is stored in a routing table and said reference value is equal to a number of routing tables.

13. A method according to claim 12, wherein said number of said routing tables is at least two, and the volumes of said at least two routing tables are the same.

14. A method according to claim 12, wherein said number of said routing tables is at least two, the volumes of said at least two routing tables are different, and a number of bits of said hashing address matches with a volume of the routing table having the largest volume.

15. A method according to claim 1, wherein said hashing address is generated by an XOR method.

16. A method according to claim 1, wherein said hashing address is generated by a cyclic redundancy coating (CRC) method.

17. A method according to claim 1, further comprising a step of determining whether said frame is effective after receiving said first physical address of said frame, and executing said comparing step when said frame is effective, but ending said packet calling process when said frame is ineffective.

18. A method according to claim 5, further comprising a step of comparing agings of all of the second physical addresses which have been compared with said first physical address when there is no second physical address matching with said first physical address.

19. A method according to claim 18, wherein said ending packet calling process is to execute said modifying step by substituting said first physical address for the second physical address with the largest aging.

11. A method adapted to be used with hashing algorithm for reducing conflict probability, comprising the steps of:

receiving a first physical address of a frame;

generating a hashing address corresponding to said first physical address;

comparing a second physical address corresponding to said hashing address with said first physical address to determine if said first and said second physical addresses match with each other;

completing a packet calling process when said second physical address and said first physical address match with each other, but going back to said generating and comparing processes when said second physical address and said first physical address do not match with each other, to determine whether there is another second physical address corresponding to said hashing address and matching with said first physical address; and

ending said packet calling process when a number of times that said generating and comparing processes are proceeded is greater than a reference value; and

the resulting conflict probability is less than a designated value, which is substantially equal to ##EQU11## wherein m is the length of said first physical address;

n is the length of said hashing address;

.sup. m is the total number of said second physical addresses;

2ⁿ is the number of hashing addresses to be held in a routing table; and

therefore 1/2ⁿ is the probability that a specific address in the routing table is selected;

2^m-n is the number of physical addresses that hash to the same address in the routing table; and

therefore ##EQU12## is the probability that an address hashes to a selected address in the routing table;

N is the total number of routing tables; and

N-1 is number of a back-up routing table.

20. A method adapted to be used in a hashing algorithm for reducing conflict probability, comprising the steps of:

receiving a first physical address of a frame;

generating a single hashing address corresponding to said first physical address;

comparing at least two second physical addresses corresponding to said hashing address with said first physical address simultaneously to determine if said first and any of said second physical addresses match with each other;

completing a packet calling process when said first and one of said second physical addresses match with each other;

ending said packet calling process when there is non of said second physical addresses matching with said first physical address; and

the resulting conflict probability is less than a designated values, which is substantially equal to ##EQU13## wherein m is the length of said first physical address;

n is the length of said hashing address;

.sup. m is the total number of said second physical addresses;

2ⁿ is the number of hashing addresses to be held in a routing table; and

therefore

1/2ⁿ is the probability that a specific address in the routing table is selected;

2^m-n is the number of physical addresses that hash to the same address in the routing table; and

therefore ##EQU14## is the probability that an address hashes to a selected address in the routing table;

N is the total number of routing tables; and

N-1 is number of a back-up routing table.