Method and apparatus used in hashing algorithm for reducing conflict probability

Claim 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 n is the number of hashing addresses to be held in a routing table; and therefore 1/2 n 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.

Claim 2

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 n is the number of hashing addresses to be held in a routing table; and therefore 1/2 n 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.

Claim 12

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 n is the number of hashing addresses to be held in a routing table; and therefore 1/2 n 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.

Claim 13

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 n is the number of hashing addresses to be held in a routing table; and therefore 1/2 n 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.

Claim 22

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 n is the number of hashing addresses to be held in a routing table; and therefore 1/2 n 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.

Claim 23

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 n is the number of hashing addresses to be held in a routing table; and therefore 1/2 n 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.