Data structure and system for IP address lookup and IP address lookup system
A tree data structure for storing strings of searchable data divided into substrings has at least one first type node that has a substring associated with it and at least one second type node that does not having a substring associated with it. A second type node is directly linked to a first type node by a fail transition. A first type node is directly linked to a second type node by a match transition. An IP address lookup system has memory for storing a tree data structure and a controller for storing and loading an incoming IP address. The system has a finite state machine having three stages including a first stage for loading the IP address and performing a length calculation, a second stage for searching the data structure to find a match, and a third stage for determine the next-hop address index.
1. An article of manufacture, comprising:
a tangible computer-readable data storage medium; and
instructions stored in the computer-readable data storage medium, wherein when the instructions are executed by a computing device, the instructions cause the computing device to search a data structure as part of routing IP packets;
wherein the data structure comprises a linearized representation of a tree of two or more searchable strings of IP address prefix data, wherein each string is divided into a plurality of substrings, and wherein the tree comprises a plurality of nodes including first-type nodes configured to store corresponding associated searchable substrings and second-type nodes not configured to store corresponding associated searchable substrings; and
wherein the data structure comprises match-failed transition information configured to link to a second-type node from a first-type node and prefix bit transition information configured to link to a first-type node from a second-type node based on a next bit from an IP address for which the data structure is being searched.
2. The article of claim 1 , wherein the first-type nodes each comprise a first field storing the associated searchable substring and a second field storing match-failed transition information.
3. The article of claim 2 , wherein the first field comprises a predetermined number of elements configured to store both the searchable substring and a prefix value indicating whether the searchable substring comprises an end of a string.
4. The article of claim 3 , wherein the elements are binary bits and the prefix value is a single bit comprising 0 or 1.
5. The article of claim 3 , wherein the first field corresponds to an abstract coding character.
6. The article of claim 1 , wherein the second-type node comprises both a first field comprising a NULL value and a second field storing prefix bit transition information.
7. A method for routing IP packets, the method comprising:
storing, by a computing device, a tree of IP address prefixes in a computer-readable storage medium using a linearized data structure that represents the tree, wherein the tree has at least two levels of nodes, including:
a first-level node having a first field for storing an abstract coding character that represents a substring of an IP address prefix; and
at least two second-level nodes linked to the first-level node via a match transition and a match-failed transition, respectively;
wherein the second-level node which is linked to the first-level node via the match-failed transition does not store an abstract coding character and is linked to a third-level node via a prefix transition; and
searching, by the computing device, the data structure to route an IP packet having a destination IP address, wherein said searching includes:
comparing a substring of the destination IP address to the substring of the abstract coding character stored in the first field of the first-level node;
transitioning to the corresponding linked one of the second-level nodes depending on whether said comparing a substring of the destination IP address results in a match or a match failed; and
transitioning to the third-level node by comparing a first bit from the destination IP address to a bit corresponding to the prefix transition.
8. The method of claim 7 , wherein the first-level node comprises both a first field storing the abstract coding character having the associated substring and a second field storing match-failed transition information.
9. The method of claim 8 , wherein the first field comprises a predetermined number of elements configured to store both the substring and a prefix value indicating whether the substring comprises an end of a string.
10. The method of claim 9 , wherein the elements are binary bits and the prefix value is a single bit comprising 0 or 1.
11. The article of claim 1 , wherein the second-type node comprises both a first field comprising a NULL value and a second field storing prefix transition information.
12. The method of claim 7 , wherein:
the computing device is a router, and wherein
the method further comprises:
using, by the router, information in the data structure to identify an exit port on the router to route the IP packet; and
routing, by the router, the data packet to the exit port.