Prefix processing technique for faster IP routing
View Patent ↗A method of storing addresses in a database comprising generating original prefixes representing the addresses to be stored in the database. The prefix lengths are determined dynamically. Reduced prefixes are generated by collapsing or expanding the original prefixes such that a number of reduced prefixes is less than a number of original prefixes. The reduced prefixes are stored in the database.
1. A method of storing addresses in a database comprising:
generating original prefixes representing the addresses to be stored in the database;
dynamically determining prefix lengths;
generating reduced prefixes by at least one of collapsing and collapsing followed by expanding the original prefixes such that a number of reduced prefixes is less than a number of original prefixes, wherein the expanding is performed using a sub-process comprising:
(a) selecting a largest prefix length;
(b) allocating prefixes of the largest prefix length into one or more bins with preselected capacities;
(c) selecting a bin from the number of bins that is partially filled;
(d) expanding a subset of prefixes of a next largest populated length and allocating them to the selected bin until the selected bin is full;
(e) repeating (a) through (d) for all prefix lengths; and
storing the reduced prefixes in the database.
2. The method of claim 1 , wherein the generating of sub-prefix comprises replacing two prefixes binary bits of 0 and 1 at a specific position with a single prefix with a variable bit at the specific position.
3. The method of claim 1 , wherein the expanding comprises replacing a prefix having a variable bit in a specific position replaced by two prefixes having a 0 and a 1 bits at the specific position, respectively.
4. The method of claim 1 , wherein the said addresses are IP addresses.
5. The method of claim 1 , wherein at least one bin is a memory.
6. The method of claim 1 , wherein collapsing is performed by a sub-process comprising:
(a) generating a set of prefixes P each of the same length L 1 having a common sub-prefix with a length L 2 that is less than said length L 1
(b) extracting a largest subset of prefixes having the same destination from the set of prefixes P;
(c) generating a prefix p of length equal to the sub-prefix length L 2 from the extracted subset if (i) any prefix of length L 2 already exists in the set of prefixes P and (ii) the generated prefix p of length equal to the sub-prefix length L 2 does not already exist in set of prefixes P.