Method for speeding up internet protocol address lookups with efficient use of memory

[0002] 1. Field of the Invention

[0003] The present invention relates to a method for Internet Protocol address lookups with efficient use of memory, more particularly, to a method for speeding up Internet Protocol address lookups by constructing Prefix Information Tables to represent the information on the routing table in the router.

[0004] 2. Background of the Invention

[0005] The speed of conventional Internet Protocol (IP) lookup in the routers has become unsatisfactory owing to the dramatically increased traffic flow in the Internet, and comparable bandwidths needed. To find the output port for a destination address indicated by a packet sent in a router, the Internet router has to look up for the longest matching prefix, which is called Best Matching Prefix (BMP), for the destination address. But in prior art, the Internet Protocol lookup schemes are complicated and need lots of time to locate the BMP, and thus form a bottleneck on the Internet. In the present invention, a brand new scheme for IP lookups is introduced, which is capable of enhancing the speed of the IP lookups efficiently. The main concept behind the scheme is grounded upon two Prefix Information Tables (PITs), which are respectively the PIT at level m, and the PIT at level n. The two PITs partition the conventional binary tree expanded by the routing table into segments. Next comes with a matching process for the IP address needed to be routed by the router in the PIT at level m or/and the PIT at level n to find the segment the IP address locates on the binary tree. Once the segment on the binary tree is decided, either the output port for the destination address is found or the Lookup Table is addressed. In the Lookup Table addressed, a matching process for the destination address is to be conducted to locate the BMP, and thus the output port is known through the Lookup Table.

[0006] In this invention, there needs only 1 hash plus 2 memory accesses for the worst cases. In an IPv4 backbone router with 41,000 routing entries, there needs, on an average, 0.53 hashes plus 1.4 memory accesses. With the use of 50 ns SDRAM, the scheme offers a lookup speed up to 10 millions packets per second. Furthermore, the lookup speed can be improved linearly with the speedup of the memory used. Additionally, the update to the routing table is easy and is low on the overhead and the memory needed for the forwarding table is only about 0.6 MBytes. The scheme and the advantages the scheme offers mentioned above can efficiently settle the problems occurred in prior art on the IP lookup issue.

[0007] The Internet Protocol (IP) address lookup scheme in the most primitive work is to put prefixes on a router into hash tables, respectively, based on their lengths. When a packet is sent into the router, a hash process is launched through the prefix hash tables. The hash process goes through from the longest to the shortest prefix hash table. The IP lookup scheme is based on the conventional Trie for the Best Matching Prefix (BMP), which is shown in FIG. 1. In the worse cases, 32 hashes are needed for the IP lookup; in the average cases, over 10 hashes are needed. The speed this scheme performs apparently cannot meet the requirements for the future high-speed routers.

[0008] The first prior art in this section is suggested by M. Waldvogel, G. Varghese, J. Turner and B. Plattner, entitled “Scalable High Speed IP Routing Lookups”, for IP routing lookups. Compared with the traditional IP lookup based on a Trie, the solution organizes the prefix IP addresses according to their lengths into hash tables (one hash table for each prefix length). Binary search is then used over the hash tables (instead of the routing entries themselves) for the BMP, which is shown in FIG. 2. Coupled with some optimizations, such as Mutating Binary Search, which exploits the traffic characteristics of the Internet, used to further reduce the complexity, the access times of memory, the speed of IP lookups can be further improved.

[0009] The binary search is started with putting “markers” into the hash tables at each level. Alternatively, each prefix P of length L has to place markers at all levels shorter than L. The markers indicate that there exist the prefixes of greater lengths in the subtree spanning from the node itself. The scheme starts the hash search at the median length of the Trie and progresses using binary search. If there is a match, all lengths greater than the median (the lower half of the Trie) are searched recursively; otherwise, all lengths less than the median (the upper half of the Trie) are searched instead. Additionally, Mutating Binary Search can be adopted to reduce the time of searching for the BMP; namely, whenever an entry is accessed, the searching proceeds with the subtree expanded from the entry.

[0010] In the algorithm, the size of the forwarding table is independent on the time for IP lookups, and the memory access time is in 2-based logarithm relationship with the length of the IP address, and which is advantageous to support for the future IPv6. In this scheme, an average numbers hash processes is 2, and log₂(the bit number of the IP address) for the worst cases. Since the length of the IP address is 32 bits in the IPv4 backbone, 5 hashes are needed for the worse cases. The approach has the advantages of being scalable (for future IPv6) and reduced IP lookup time. However, the data structures used are complicated and the update of an entry in the routing table might result in a large number of the entries being updates in the lookup table as the markers need to be reentered in tables at every level of the Trie. So making the lookup table update has to rebuild the tree periodically.

[0011] Gupta, Lin, and McKeown presented a fast IP routing lookup scheme in the hope of achieving a speed up to a gigabit per second by means of Longest Prefix Matching in hardware process, which is referred to as the second prior art in this section. In the scheme, IP addresses each are divided into two sections, the first 24 bits and the last 8 bits. A table TBL24 is created to accommodate the prefixes with lengths less than or equal to 24 bits. If the first bit is 0, then the other 15 bits is used to indicate the next hop. On the contrary, the first bit is 1, then the other 15 bits stands for a pointer which points to TBLlong, which is created to accommodate the prefixes which are longer than 24 bits. The implemented hardware for the lookup scheme is shown in FIG. 3.

[0012] In accordance with this scheme, an average time of 1 (in fact, a little more than 1) memory access is needed, and the maximum number of 2 memory accesses are needed. Although the IP lookups scheme is very efficient in speed, it may call for 33MB DRAM to store data structures needed. The use of memory is instead very inefficient. The scheme is not able to support efficiently the future Internet Protocol scheme, which have address fields of 128 bits. Furthermore, a distributed database management is hard to implemented based on this scheme.

[0013] The present invention is aimed to provide a method for speeding up Internet Protocol (IP) address lookups with efficient use of memory. The lookup process may include the characteristics as follows. First, the lesser time of accessing memory for IP lookups the better. Second, for the worst case, the time of accessing memory must be limited in a range in order to attain the IP lookup speed. Third, in accessing memory, it is preferred to execute with pipelined operation. Last, it is desired to have a smaller size of memory required for data structures. Additionally, it will be better if the data structures used are more concise and compact.

[0014] According to one aspect of the present invention, a method for speeding up Internet Protocol address lookups with efficient use of memory is disclosed. The method includes the following steps: First, establishing a Prefix Information Table (PIT), PIT-m, corresponding to a subtree expanding from a node on m-th level on the Trie, and a PIT, PIT-n, corresponding to a subtree expanding from a node on n-th level on the Trie for partitioning the Trie into several segments to map into all IP addresses. Then looking up the Best Matching Prefix (BMP) for the Internet Protocol address through the PIT-m and the PIT-n for finding an output port or for finding the Lookup Table (LT) corresponding to the IP address. Finally, checking up the LT for finding a BMP, and thus an exact output port is obtained. The PIT-m format comprises: an m-bit entry number identification, a 1-bit direction identification, a 1-bit prefix identification, and a 14-bit pointer; and the PIT-n comprises: n-bit entry number identification, 1-bit direction identification, a 1-bit prefix identification, and 14-bit pointer. While in Lookup Tables, there store output ports corresponding to prefix entries. By use of a fraction of an IP address as an index into the Lookup Table, an exact output port can be found.

[0015] The foregoing aspects and many of the attendant advantages of this invention will become more readily appreciated as the same becomes better understood by reference to the following detailed description, when taken in conjunction with the accompanying drawings, wherein:

[0016] FIG. 1 is a diagram indicating a method of a conventional IP routing lookups.

[0017] FIG. 2 is a diagram indicating a method for binary search on a Trie in a first prior art.

[0018] FIG. 3 is a diagram indicating a method for speeding up the lookups for IP routing by accessing memory in hardware in a second prior art.

[0019] FIG. 4 is a diagram illustrating the tree expanded with prefixes entries.

[0020] FIG. 5 is a diagram illustrating the prefixes-expanding tree with three major segments according to the present invention.

[0021] FIG. 6A is the format of the Prefix Information Table (PIT) when I=0, according to the present invention.

[0022] FIG. 6B is the format of the Prefix Information Table (PIT) when I=1, according to the present invention.

[0023] FIG. 7 is a diagram illustrating the mapping from a subtree spanning from the node 24.64.1 to the LT-8 (24)

[0024] FIG. 8 is a diagram illustrating the proposed IP lookups scheme and the hardware realization of the same.

[0025] FIG. 9 is a diagram illustrating a practical example for the proposed IP lookups scheme.

[0026] In prior art, the lookup approaches either use complicated data structures, resulting in increased complexity while updating the routing entries; or they are not scalable to the future IPv6. In view of this, the present invention proposes a scalable IP lookup mechanism that is memory efficient.

[0027] The basic concept is to expand the routing table on a Trie, where the nodes on the Trie represent the prefix entries in the corresponding routing table that are scattered throughout the Trie according to the lengths of the prefixes. This invention defines the level of a node by initially letting the root be at level 0. The height or depth of a tree is the maximum level of any node in the tree. To quickly identify the approximate location of the entry and the output port for the destination address, the present scheme partitions the routing Trie into segments. Namely, the scheme shrinks the range to be searched from the Trie with a height of 32 to a subtree with a height of 8 or 16. In the subtree, the output port of the BMP can be found. The scheme is illustrated in FIG. 4.

[0028] The data structures used contain prefix information indicating the routing direction and the associated segment, and lookup tables providing the output port corresponding to the IP address in an associated subtree. Only when there are over two different output ports in the associated subtree, will the lookup table need to exist. When there is just one output port in the associated subtree, the information of the single output port in the associated subtree is attached to a corresponding entry in the prefix information table. Thus, the size of the forwarding table is considerably reduced, and the scheme retains the advantages of the binary search used in prior art. There is no need to save the prefix information for each level on the Trie, and therefore significantly reduces the complexity of updating, facilitates the updating of the forwarding table, and reduces the overload.

[0029] For the current routers, many routing prefixes are stored in the database of the routers. In the present invention, the Trie with prefixes as nodes are segmented into three regions: level 0-16, level 17-24, and level 25-32, as is shown in FIG. 5. Two data structures are used for the proposed scheme, and they are Prefix Information Table (PIT) and lookup table (LT), respectively. The PIT contains the prefix information and provides information to guide the binary search for the BMP. In the Trie, there are two PITs located on level 16 and level 24, respectively. The lookup table provides the associated output ports corresponding to the associated subtree.

[0030] The Prefix Information Table and the lookup table will be described in more detail as follows:

[0031] As discussed earlier, the Trie is segmented into three regions: level 0-16, level 17-24, and level 25-32. Two PITs, one at level 16(PIT-16) and the other at level 24(PIT-24), are also constructed to aid the lookup process. For example, the first 16 bits of the prefixes with their lengths longer than or equal to 16 are taken and stored in PIT-16. The information of a PIT-16 format comprises a 16-bit entry number identification, a 1-bit prefix identification, a 1-bit direction identification, and a 14-bit pointer. To facilitate the lookup process, the entries on the Trie can be sorted into tree:

[0032] (1) Pure Prefix (X): The entry itself is a prefix and there are no other nodes on the Trie that belong to the subtree expanded from the entry itself as a root. In the case, P=1, I=0, and Ptr has the value of the output port that the packet should be sent to get to its next hop.

[0033] (2) Pure marker (M): The entry is created by one or more nodes on the Trie that belong to the subtree expanded from the entry itself as a root. The entry itself is not a prefix. For the PIT-16, the value of the entry is obtained by taking the first 16 bits from the prefix In this case, P=0, I=1, and Ptr points to the associated Lookup Table (as will be discussed below).

[0034] (3) Prefix and Marker (XM): The entry itself is a prefix and there are other nodes on the Trie that belong to the subtree expanded from the entry itself as a root. For the PIT-16, the value of the entry is obtained by taking the first 16 bits from the prefix. In this case, P=1, I=1, and Ptr points to the associated Lookup Table.

[0035] It is noted that an entry in PIT-16 indicates that there exists at least one node in the subtree with the entry itself as a root down to the leaves (level 32) of the Trie. Multiple nodes on the subtree can be represented by a single entry in the PIT-16. This is the same as applied to the PIT-24.

[0036] When I=0 in the PIT entry, the marker indicates the information of the output port. If I=1 in the PIT entry, there exists possibly longer matching prefix. There is, then, a need to search for the best matching prefix on the next step by referring to the Ptr. The value of P indicates whether the entry is a prefix. If P=1, the entry is a prefix. On the contrary, P=0 indicates the entry is not a prefix, but a marker.

[0037] The establishment of the PIT-24 is just the same as that of the PIT-16. But the prefix information the PIT-24 stores is the prefixes with lengths longer than or equal to 24 bits. The first 24 bits of the prefixes are stored in the PIT-24. The information of a PIT-24 format comprises a 24-bit entry number identification, a 1-bit prefix identification, a 1-bit direction identification, and a 14-bit pointer. The entries on the Trie can be sorted into tree:

[0038] (1) Pure Prefix (X): The entries are prefixes provided with 24 bits. The entry itself is a prefix and there are no other nodes on the Trie that belong to the subtree expanded from the entry itself as a root. In the case, P=1, I=0, and Ptr has the value of the output port that the packet should be sent to get to its next hop.

[0039] (2) Pure marker (M): The entries are prefixes provided with longer than 24 bits. The entry is created by one or more nodes on the Trie that belong to the subtree expanded from the entry itself as a root. The entry itself is not a prefix. For the PIT-24, the value of the entry is obtained by taking the first 24 bits from the prefix. In this case, P=0, I=1, and Ptr points to the associated Lookup tables (as will be discussed below).

[0040] (3) Prefix and Marker (XM): The entries are prefixes provided with 24 bits or longer than 24 bits. The entry itself is a prefix and there are other nodes on the Trie that belong to the subtree expanded from the entry itself as a root. For the PIT-24, the value of the entry is obtained by taking the first 24 bits from the prefix. In this case, P=1, I=1, and Ptr points to the associated Lookup Tables.

[0041] The PIT format is given as FIG. 6A for the case I=0, and FIG. 6B for the case I=1. When searching for an prefix entry in a PIT, hash process is needed.

[0042] In the preferred embodiment according to the present invention, there are three types of Lookup Tables as shown in FIG. 5. In the Lookup Tables LT-i(j), i is the height of the table corresponding to the subtree, and j is the level of the root of the subtree. Lookup Tables (LTs) provide a mapping between the subtree and the output port. The three types of the LTs are:

[0043] 1. LT-15(0): LT-15 contains all possible mapping of the entries to the output ports from level 0 to 15. Namely, all lookup information in the top segment in FIG. 5 is included in a LT-15(0). As a trade-off between the lookup speed and the memory usage, making the complete tree available reduce the lookup time with a modest increase of the memory usage.

[0044] 2. LT-7(16): It is an LT pointed to by an entry in PIT-16. The entries of the LT consist of the leaves at the fully expanded subtree of height 7 and provide a mapping between the leaf nodes and their output ports. Namely, all lookup information in the middle segment in FIG. 5 is included in several LT-7(16). It has 128 (2⁷) entries.

[0045] 3. LT-8(24): It is an LT pointed to by an entry in PIT-24. The entries of the LT consist of the leaf nodes at the fully expanded subtree of height 8 and provide a mapping between the leaf nodes and their output ports. Namely, all lookup information in the bottom segment in FIG. 5 is included in several LT-8(24). It has 256 (2⁸) entries.

[0046] Referring to FIG. 7, which depicts the mapping between the complete binary subtree expanded from the node corresponding to the prefix 24.64.1 and the corresponding LT-8, which can be seen in FIG. 7, wherein all the prefixes from the 24.64.1.0 to 24.64.1.191 correspond to the output port A, while ones from the 24.64.1.192 to 24.64.1.255 correspond to the output port B.

[0047] The steps of the proposed IP lookup includes:

[0048] When a packet arrives, the destination address carried by the packet is extracted and the following procedures are followed:

[0049] Take the first 16 bits of the destination (DA). Then a hash process is launched for the 16 bits in the PIT-16. If no math is found, then the lookup should go back to the LT-15(0) since the number of the bits must be less then 16. Take the first 15 bits of the DA as an index into LT-15(0). The output port can be found through the LT-15(0). Exit.

[0050] If a match is found in the PIT-16 for the first 16 bits of the DA, then look at the value of the I corresponding to the matched entry. If I=0, then BMP is found. Exit.

[0051] If I=1, the lookup must proceed since BMP is not yet found. At the time, the first 24 bits of the DA is extracted and the 24 bits of address is hashed into the PIT-24. If no match is found, the BMP must locate in the middle segment of FIG. 5; namely, the longest matching fraction of the DA locates in the 16-23 bits of the DA. The lookup must continue back to the LT-7(16) the Ptr points to in the PIT-16. The 16-22 bits of the DA is then extracted as an index into the LT-7(16) to find the exact output port. Exit.

[0052] If a match is happened, then the bit number of the DA is longer than or equal to 24 bits is known. Then look at the value of the I corresponding to the matched prefix entry. If I=0, then the BMP is found. The Ptr shows the output port.

[0053] If I=1, the lookup must proceed since BMP is not yet found. The location of the BMP is in the bottom segment of FIG. 5; namely, the longest matching fraction of the DA locates in the 24-32 bits. The lookup must continue to the LT-8(24), pointed to by the Ptr points to, corresponding to the PIT-24. The 23-32 bits of the DA is extracted as an index into the LT-8(24) to find the exact output port Exit.

[0054] The description of the above-mentioned access for the IP lookup according to the scheme proposed by the present invention can be formulated by the following algorithm:

[0055] Hash processes are used through the lookup scheme as proposed above. There may happen to collisions during a hash process. When collisions happen, one or more than one memory access is needed. To prevent this from occurring, the PIT-16 is expanded to a full table in place of the hash table in an attempt to reduce the hash processes as least as possible. In the worst case according to the above method for processing the IP routing, the PIT-16 is first looked through, and a match is found but I=1. Then the lookup proceeds with a hash process in the PIT-24. If no output port for the DA is found, looking up through LT-7(16) or LT-8(24) is needed. In the case, a hash process and 2 memory accesses are necessary for the output port.

[0056] To facilitate the study of the method for the lookup process according to the present invention, FIG. 8 is drawn to illustrate.

[0057] A practical example for the proposed IP lookups scheme is illustrated in FIG. 9 and described as follows:

[0058] Suppose that the following entries are in the examplary routing table shown in FIG. 9: 20.92.32/24, 20.92.32.192/26, 26.64/16, 24.64.192/20, 24.64.128/24, where the number after the “/” sign presents the bit length of the prefix corresponding to the entry. The routing table entries create two entries in PIT=16: one is “20.92” with P=0 and I=1 (created by the first two routing table entries), the other one is “24.64” with P=1 and I=1. The Ptr field of the entry “24.64” is a pointer to the LT-7(16), which all entries from 96 to 103 all store the same output B (Although the Ptr field of the entry “20.92” also points to another LT-7(16), the detail is not shown for the sake of presentation). Similarly, the routing table entries also results in two entries in PIT-24: one is “20.92.32” (created by 20.92.32/24 and 20.92.32.192/26) with P=1, I=1 and another entry “24.64.128” with P=1 and I=0. The Ptr field of the entry “20.92.32” points to the LT-8(24), which all entries from 192 to 255 all store the value of the output port D.

[0059] When a packet arrives at the router, the DA of the packet is first extracted. Assume that the value of the DA is 20.92.32.194. Take the first 16 bits of the A (“20.92”) as an index for PIT-16 and find that the entry is non-empty and the value of I is 1, meaning that although this is a match, there might exist a longer prefix that matches the DA. In this case, take the first 24 bits of the DA as a prefix and hash into the PIT-24. It turns out that the entry “20.92.32” has a match, the value of I=1, and the Ptr points to the LT-8, meaning that there might be a longer prefix that matches the DA. The bits 24 to 31 (the value is “194”) of the DA are used as an index into the LT-8(24) and locate the corresponding output port. It can be found that the output port is D.

[0060] If another packet arrives in the router, the first 16 bits “24.64” is used as an index into the PIT-16. The corresponding entry is non-empty with I=1, meaning that there might be a better BMP down at a lower level. Therefore, PIT-24 is visited by taking the first 24 bits of the DA as a key for hashing. This time, the hash fails (meaning that the BMP should not be of level 24 or below). Consequently, the BMP entry should be of a length between 16 and 23. As a result, the Ptr field of the previously located PIT-16 entry is used to get to the LT-7(16) corresponding to the “24.64” entry. Take the bits 16 to 24 of the DA “97” as an index into the LT-7(16), the output port B is obtained.

[0061] Assume another packet with the DA “24.64.128.154” enters the router, the first 16 bits of the DA “24.64” is processed to index to the PIT-16. In the PIT-16, there exists an entry “24.64”, and the value of I of that entry is 1. The hash through the PIT-24 is needed, and the first 24 bits of the DA is extracted to do the hash. As a result, the entry “24.64.128” is found and I=0. The BMP is found to be “24.64.128”, and the output port H is known through the Ptr.

[0062] The present invention can be further called for upon the future IPv6 with the concept set forth above to access lookup for IP addresses. The establishment of the scheme for the IPv6 is described as follows:

[0063] The Trie with prefixes as nodes are segmented into i sections. The Prefix Information Tables are established as PIT-m₁, PIT-m₂, PIT-m₃, . . . , PIT-m_i, as the format on the Trie for the router in IPv4. DA is hashed in a given PIT-m_j(1<j<i). According to I and P, either the PIT the BMP locates in is found with the approach analogy to the one used in IPv4, or a given lookup table is checked through, unless the BMP and the output port are obtained. In a PIT-m_jformat, there are at least 4 types of information: entry number for m_ibits, direction identification for 1 bit, prefix identification for 1 bit, and Ptr for 14 bits.

[0064] As is understood by a person skilled in the art, the foregoing preferred embodiments of the present invention are illustrated of the present invention rather than limiting of the present invention. It is intended to cover various modifications and similar arrangements included within the spirit and scope of the appended claims, the scope of which should be accorded the broadest interpretation so as to encompass all such modifications and similar structure.