Composite Searches to Minimize Both Worst-Case and Average Performance
Original Publication Date: 2004-May-25
Included in the Prior Art Database: 2004-May-25
It is proposed to combine two different search algorithms in a way that exploits their characteristics in a most efficient manner.
Composite Searches to Minimize Both Worst -Case and Average Performance
Many search algorithms have been developed over the last years for packet classification. The task of these algorithms is to find an entry in a given data structure
(e.g., routing table, mac address table, multi-field firewall rule set) that matches the input key, which is typically comprised of information that is extracted from a packet
(e.g., IP source and destination addresses, TCP/UDP port numbers). Examples of match conditions are exact-match, longest prefix-match, range-match. The following text focusses on routing tables, however, the same applies to search structures in general.
Two examples of such schemes are the Patricia tree and the BaRT algorithm. The following differences can be distinguished between those schemes:
1) Patricia tree: first a minimum of selected input key bits is tested in order to restrict the number of possible matching entries to one. Next this key (which is stored in a leaf node) is tested against the entire input key.
2) BaRT algorithm: the input key is completely processed in successive steps from left to right in segments of 8 bits. At the end of these processing steps the result is known - no test needs to be performed and no search key needs to be stored in a leaf node.
The BaRT algorithm provides deterministic performance that is independent of the characteristics of the routing table: e.g., a 32-bit address is processed in at most 32/8=4 steps requiring...