Method and apparatus for recognizing data traveling on a data transmission network using a dichotomizing search process
First Claim
1. A method for processing data items on a data transmission network, comprising the steps:
- receiving, in a station of the network, an identifier having a high portion and a low portion;
determining if the high portion of the received identifier corresponds to said station;
performing a dichotomizing search on a search table corresponding to said high portion by comparing the low portion of the received identifier with entries of said search table, if said high portion of the received identifier is determined to correspond to said station.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus for recognizing whether data on a network is intended for a terminal of the network. An identifier having a high-order portion and a low-order portion is received by a terminal. The terminal looks up, in a direct read table, whether the direct read table contains an entry corresponding to the high portion. The direct read table can contain, for each high portion, a size of a search table corresponding to low portions of the received identifier, a flag or bit, indicating that there a search table for a particular high portion, and an address of the search table. If the direct read table determines that there is a search table for the received high portion, a dichotomizing search process is executed to find an entry in the search table corresponding to the low portion. The dichotomizing search process divides the search table in half to determine if the received low portion of the identifier is in the lower or upper part of the search table. If it is in the lower portion, the search process divides the lower portion into two halves and searches these halves for the entry corresponding to the lower portion. This divide and search process continues until an entry in the search table is found which corresponds to the low portion, or a predefined maximum number of divide and search operations are performed.
11 Citations
14 Claims
-
1. A method for processing data items on a data transmission network, comprising the steps:
-
receiving, in a station of the network, an identifier having a high portion and a low portion; determining if the high portion of the received identifier corresponds to said station; performing a dichotomizing search on a search table corresponding to said high portion by comparing the low portion of the received identifier with entries of said search table, if said high portion of the received identifier is determined to correspond to said station. - View Dependent Claims (2, 3, 4)
-
-
5. A method for processing data traveling on a data transmission network, comprising the steps:
-
receiving, in a station of the network, an identifier having a high portion and a low portion; determining if the high portion of the received identifier corresponds to said station by looking up, in a read table, if there is an entry in the read table which corresponds to the high portion; determining an address of a search table which corresponds to said high portion, said search table having a beginning, a middle, and an end; performing a dichotomizing search on said search table for said low portion of the received identifier when the determining step determines that said high portion corresponds to said station, by performing a dichotomizing search which performs the steps; determining if the received low portion is less than, equal to, or greater than said middle of said search table; terminating the dichotomizing search and indicating that said middle of said search table corresponds to said low portion, if said low portion is equal to said middle of said search table; setting said end of said search table equal to said middle of said search table, calculating a new middle of said search table and performing the steps of the dichotomizing search, if said low portion is less than said middle of said search table; and setting said beginning of said search table equal to said middle of said search table, calculating a new middle of said search table and performing the steps of the dichotomizing search, if said low portion is greater than said middle of said search table.
-
-
6. An apparatus for processing data items on a data transmission network, comprising:
-
receiving means, connected to the network for receiving an identifier having a high portion and a low portion; means, connected to the receiving means, for determining if said high portion of the received identifier corresponds to said station; means for performing a dichotomizing search, connected to the determining means, on a search table corresponding to said high portion by comparing said low portion of the received identifier with entries of said search table, if said high portion of the received identifier is determined to correspond to said station. - View Dependent Claims (7, 8, 9)
-
-
10. An apparatus for processing data traveling on a data transmission network, comprising:
-
receiving means for receiving, in a station of the network, an identifier having a high portion and a low portion; first determining means, connected to the receiving means, for determining if the high portion of the received identifier corresponds to said station by looking up, in a read table, if there is an entry in the read table which corresponds to said high portion; second determining means, connected to the first determining means, for determining an address of a search table which corresponds to said high portion, said search table having a beginning, a middle, and an end; dichotomizing searching means, connected to the second determining means, for performing a dichotomizing search on said search table for said low portion in the received identifier when the determining step determines that said high portion corresponds to said station, by performing a dichotomizing search which performs the steps; determining if the received low portion is less than, equal to, or greater than said middle of said search table; terminating the dichotomizing search and indicating that said middle of said search table corresponds to said low portion, if said low portion is equal to said middle of said search table; setting said end of said search table equal to said middle of said search table, calculating a new middle of said search table and performing the steps of the dichotomizing search, if said low portion is less than said middle of said search table; and setting said beginning of said search table equal to said middle of said search table, calculating a new middle of said search table and performing the steps of the dichotomizing search, if said low portion is greater than said middle of said search table.
-
-
11. An apparatus for processing data traveling on a data transmission network, comprising:
-
receiving means for receiving, in a station of the network, an identifier having a high portion and a low portion; a memory for storing a base address of a direct read table; first determining means, connected to the receiving means and the memory, for determining if said high portion of the received identifier corresponds to said station by looking up, at an address of the direct read table corresponding to a sum of said high portion and said stored base address, if there is an entry in the direct read table which corresponds to said high portion; second determining means, connected to the first determining means, for determining an address of a dichotomizing search table which corresponds to said high portion, said search table having a beginning, a middle, and an end; dichotomizing searching means for performing a dichotomizing search on said dichotomizing search table for said low portion of the received identifier after the first determining means determines that said high portion corresponds to said station, by performing a dichotomizing search which performs the steps; determining if the received low portion is less than, equal to, or greater than said middle of said search table; terminating the dichotomizing search and indicating that said middle of said search table corresponds to said low portion, if said low portion is equal to said middle of said search table; setting said end of said search table equal to said middle of said search table, calculating a new middle of said search table and performing the steps of the dichotomizing search, if said low portion is less than said middle of said search table; and setting said beginning of said search table equal to said middle of said search table, calculating a new middle of said search table and performing the steps of the dichotomizing search, if said low portion is greater than said middle of said search table. - View Dependent Claims (12)
-
-
13. A method for processing data items on a data transmission network, comprising the steps of:
-
receiving, in a station of the network, an identifier having a high portion and a low portion; looking up an entry in a read table corresponding to the high portion of the received identifier, information pertaining to a search table; performing a dichotomizing search on the search table, using said information pertaining to the search table, to determine an entry corresponding to the low portion of the received identifier.
-
-
14. An apparatus for processing data items on a data transmission network comprising:
-
means for receiving, in a station of the network, an identifier having a high portion and a low portion; means for looking up, connected to the means for receiving, information pertaining to a search table corresponding to the high portion; and means for performing a dichotomizing search on the search table, using said information pertaining to the search table, to determine an entry corresponding to the low portion of the received identifier.
-
Specification