Fast rule lookup with arbitrary IP range configurations
First Claim
1. A method for associating at least one rule with a key, comprising:
- arranging a plurality of objects in a table that is based on an ordering of information associated with each object;
if the key is provided, employing at a search method to determine a starting entry in the table;
if the starting entry in the table is unequal to the provided key, employing another search method to determine an object in the table that is relatively equivalent to the key; and
enabling the processing of the key based on at least one rule associated with the object.
1 Assignment
0 Petitions
Accused Products
Abstract
Enabling a relatively fast look up for a rule associated with an arbitrarily selectable IP address. In one embodiment, RSBound objects are sorted into an array where each RSBound object is composed of a bound IP address (BIP), sister BIP, type, index, sister index, and a configured rule. The BIPs are derived from arbitrary user-specified IP addresses or IP address ranges. Each single IP address configuration derives one RSBound entry, where the BIP is the given IP address itself; and each IP range configuration derives two RSBound entries, and the range'"'"'s lower bound and upper bound are their respective BIPs. The array is sorted primarily based on the RSBound'"'"'s BIP value, and their type and pair information are the tiebreakers. If a configured rule needs to be searched for a given IP address, a binary search is performed first to find a starting entry, from where a jump-skip search is performed to find the best matching rule for the given IP address. Additionally, although this invention is well suited for IP range matching, it can also be used to match keys with arbitrary ranges of other non-IP address types, e.g., mobile telephone numbers.
6 Citations
21 Claims
-
1. A method for associating at least one rule with a key, comprising:
-
arranging a plurality of objects in a table that is based on an ordering of information associated with each object;
if the key is provided, employing at a search method to determine a starting entry in the table;
if the starting entry in the table is unequal to the provided key, employing another search method to determine an object in the table that is relatively equivalent to the key; and
enabling the processing of the key based on at least one rule associated with the object. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A network device for associating at least one rule with a key, comprising:
-
a memory for storing instructions;
a processor for enabling actions based on the instructions, including;
arranging a plurality of objects in a table that is based on an ordering of information associated with each object;
if the key is provided, employing at a search method to determine a starting entry in the table;
if the starting entry in the table is unequal to the provided key, employing another search method to determine an object in the table that is relatively equivalent to the key; and
enabling the processing of the key based on at least one rule associated with the object. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A network device for associating at least one rule with a key, comprising:
-
a means for arranging a plurality of objects in a table that is based on an ordering of information associated with each object;
a means for employing at a search method to determine a starting entry in the table if the key is provided;
a means for employing another search method to determine an object in the table that is relatively equivalent to the key if the starting entry in the table is unequal to the provided key; and
a means for enabling the processing of the key based on at least one rule associated with the object.
-
Specification