System and method for efficiently searching a forwarding database that is split into a bounded number of sub-databases having a bounded size
View Patent ↗A method, apparatus, and storage medium product are provided for forming a forwarding database, and for using the formed database to more efficiently and quickly route packets of data across a computer network. The forwarding database is arranged into multiple sub-databases. Each sub-database is pointed to by a pointer within a pointer table. When performing a longest-match search of incoming addresses, a longest prefix matching algorithm can be used to find the longest match among specialized “spear prefixes” stored in the pointer table. After the longest spear prefixes are found, the pointer table will direct the next search within a sub-database pointed to by that spear prefix. Another longest-match search can be performed for database prefixes (or simply “prefixes”) within the sub-database selected by the pointer. Only the sub-database of interest will, therefore, be searched and all other sub-databases are not accessed. Using a precursor pointer and a sub-database of optimally bounded size and number ensures power consumption be confined only to the sub-database being accessed, and that higher speed lookup operations can be achieved since only the sub-database of interest is being searched.
1. A method of locating a prefix in a forwarding database of N number of prefixes, wherein the database is provided within a memory device, the method comprising:
maintaining, in the memory device, a pointer table having a set of spear prefixes that point to a respective set of sub-databases;
finding a longest spear prefix match among the spear prefixes within the pointer table;
selecting a sub-database of prefixes from a set of sub-databases pointed to by the longest matching spear prefix within the pointer table,
wherein said selecting comprises accessing only a portion of the memory device containing the sub-database pointed to by the longest matching spear prefix within the pointer table and not accessing any other portion of the memory such that power consumption is reduced and a speed at which a longest prefix match is located within the database is increased; and
finding the longest prefix match among the prefixes within the selected sub-database,
wherein the longest prefix match within the selected sub database determines a next hop address.
2. The method as recited in claim 1 , wherein the finding, selecting and finding are performed in software or hardware.
3. The method as recited in claim 1 , wherein said selecting comprises selecting a sub-database having no more than T number of prefixes from among the set of sub-databases, where T is less than N.
4. The method as recited in claim 1 , wherein said portion of the memory is a block within a plurality of memory blocks.
5. The method as recited in claim 1 , wherein said selecting comprises accessing only a portion of the memory device containing the sub-database pointed to by the longest matching spear prefix within the pointer table and not accessing any other portion of the memory in order to increase storage capacity by storing in the memory only the bits used in the pointer table and only the least significant bits used in the sub-databases.
6. The method as recited in claim 5 , wherein said portion of the memory is a block within a plurality of memory blocks.
7. The method as recited in claim 1 , wherein said prefix corresponds to a destination address corresponding to a packet of data.
8. The method as recited in claim 1 , wherein said prefix corresponds to an Internet Protocol (IP) address.
9. The method as recited in claim 1 , wherein a binary sequence of each of the prefixes within the selected sub-database begin with a binary sequence equivalent to the binary sequence of the longest matching spear prefix.
10. A system comprising:
one or more processors; and
a memory operatively coupled to the one or more processors, the memory for storing instructions which, when executed by the one or more processors, causes the one or more processors to maintain a pointer table having a set of spear prefixes that point to a respective set of sub-databases,
find a longest spear prefix match among the spear prefixes within the pointer table,
select a sub-database of prefixes from a set of sub-databases pointed to by the longest matching spear prefix within the pointer table,
wherein the processor accesses only a portion of the memory containing the sub-database pointed to by the longest matching spear prefix within the pointer table during the select and
further wherein the processor does not access any other portion of the memory such that power consumption is reduced and a speed at which a longest prefix match is located within the database in increased, and
find the longest prefix match among the prefixes within the selected sub-database,
wherein the longest prefix match within the selected sub database determines a next hop address.
11. The system of claim 10 , wherein a binary sequence of each of the prefixes within the selected sub-database begin with a binary sequence equivalent to the binary sequence of the longest matching spear prefix.
12. The system of claim 10 , wherein each of the sub-databases contains a bounded number of prefixes, wherein the prefixes are bound between a minimum number of prefixes and a maximum number of prefixes.
13. The system of claim 10 , wherein the number of sub-databases is bounded between a minimum number of sub-databases and a maximum number of sub-databases.
14. The system of claim 13 , wherein the number of sub-databases is bounded between N/T and (2N/T)+1, where T is the maximum number of prefixes in each of the sub-databases and wherein N is the total number of prefixes in a database.
15. A computer-readable storage medium for storing computer executable instructions that when executed by a processor perform steps for locating a prefix in a forwarding database of N number of prefixes, the steps comprising:
maintaining a pointer table having a set of spear prefixes that point to a respective set of sub-databases;
finding a longest spear prefix match among the spear prefixes within the pointer table;
selecting a sub-database of prefixes from a set of sub-databases pointed to by the longest matching spear prefix within the pointer table,
wherein said selecting comprises accessing only a portion of the memory device containing the sub-database pointed to by the longest matching spear prefix within the pointer table and not accessing any other portion of the memory such that power consumption is reduced and a speed at which a longest prefix match is located within the database is increased; and
finding a longest prefix match among the prefixes within the selected sub-database
wherein the longest prefix match within the selected sub database determines a next hop address.
16. The storage medium of claim 15 , wherein a binary sequence of each of the prefixes within the selected sub-database begin with a binary sequence equivalent to the binary sequence of the longest matching spear prefix.
17. The storage medium of claim 15 , wherein each of the sub-databases contains a bounded number of prefixes, wherein the prefixes are bound between a minimum number of prefixes and a maximum number of prefixes.
18. The storage medium of claim 15 , wherein the number of sub-databases is bounded between a minimum number of sub-databases and a maximum number of sub-databases.
19. The storage medium of claim 18 , wherein the number of sub-databases is bounded between N/T and (2N/T)+1, where T is the maximum number of prefixes in each of the sub-databases and wherein N is the total number of prefixes in a database.