Method and apparatus for performing radix lookups using transition tables with pointers

[0002] This invention relates generally to data communications networks, and more particularly, to a method and apparatus for performing radix search tree lookups using transition tables with pointers.

[0003] There are numerous known methods for searching for data in a data structure stored in a memory of a computer system to find a particular item of information. It is desirable to implement methods for organizing and searching for data in the data structure in a way that reduces the amount of memory required to store the data and perform the search in a more efficient manner.

[0004] A table or a file is a group of data elements, each of which may be called an entry or a record in the table. Generally, a key is associated with each record. The key is used to differentiate among different records. The key associated with a particular record may or may not need to be unique, depending on the search method utilized in accessing the table. In addition, the key may or may not be embedded within the record itself.

[0005] A search method accepts a key value as input and attempts to locate a record within a table stored in the memory of a computer system whose associated key is the key value. The search method may return a record, or a pointer to the record. The contents of the record may be data, program code, or a pointer to either data or program code. If the search of a table is unsuccessful in finding the key, then there is no record in the table associated with the key value. Typically, if the search is unsuccessful, an insertion is performed to add a new record with the key value as its key.

[0006] A table is stored in a data structure in the memory or an external storage, e.g., magnetic disk, of a computer system. The form of the data structure may be an array of records, a tree, a linked list, etc. Certain search methods are generally more applicable to one form and location of a data structure than another. Thus, the data structure in which a table is stored is, in part, selected according to the search method to be used to access information within the table. The present invention is related to search operations on a file or table that is organized as a tree structure.

[0007] One known search method utilizes a tree to facilitate searching a table stored in the memory of a computer system. This search method forms a tree based on symbols of which the keys are comprised. This is generally referred to as a radix search tree. For example, if the key is comprised of the hexadecimal characters 0 through F, each successive hexadecimal digit position in the key determines 1 of 16 possible children of a given node in the tree.

[0008] When the set of keys in a table is sparse, known methods of storing a table of keys in a tree for later radix searching wastes a large amount of memory space. Therefore, there is a need for a way of storing information in a tree structure in the memory of a computer system and for subsequently searching the tree such that the amount of memory required to store a sparse table of keys is minimized. There is a further need for searching a tree in the memory of a computer system in a fast, efficient manner.

[0009] The present invention provides a method, apparatus, and article of manufacture for performing a radix search tree lookup with a key using a transition table with pointers. The key is used as a transition index into the transition table. A first pointer associated with the transition index is then used as a pointer into a first block of entries in a result table. A sum of transition bits in the transition table below the transition index is used as a result index into the first block of entries in the result table. The result index into the first block of entries may be used to reference a result of the radix search tree lookup. Extra space is added in the result table to enable insertion of entries after the first block of entries. A second pointer is used to add redundant entries from the first block of entries into a second block of entries in the result table.

[0010] The present invention is illustrated by way of example and may be better understood by referring to the following description in conjunction with the accompanying drawings, in which like references indicate similar elements and in which:

[0011] FIG. 1 is a system diagram which shows a computer hardware environment compatible with the present invention;

[0012] FIG. 2 shows a simple radix lookup compatible with the present invention;

[0013] FIG. 3 shows a simple radix lookup with valid bit table compatible with the present invention;

[0014] FIG. 4 shows a valid bit table with compressed result table compatible with the present invention;

[0015] FIG. 5 shows a 64 Kbit valid bit table with count compatible with the present invention;

[0016] FIG. 6 shows a 64 Kbit valid bit table with pointers compatible with the present invention;

[0017] FIG. 7 shows a valid bit table with hashing compatible with the present invention;

[0018] FIG. 8 shows a transition bit table example compatible with the present invention;

[0019] FIG. 9 shows a transition table representing single entry ranges compatible with the present invention;

[0020] FIG. 10 shows a 64 Kbit transition bit table with pointers with forced adjacencies compatible with the present invention;

[0021] FIG. 11 shows a 64 Kbit transition bit table with pointers with redundant entries compatible with the present invention;

[0022] FIG. 12 shows a block diagram of a hardware implementation compatible with the present invention;

[0023] FIG. 13 shows a block diagram of a hardware implementation of a 64 Kbit valid bit table followed by radix 16 tables compatible with the present invention;

[0024] FIG. 14 shows a compressed radix with transition field format compatible with the present invention;

[0025] FIG. 15 shows a compressed radix tree with transition field example compatible with the present invention;

[0026] FIG. 16 illustrates an example lookup using a key of 0x 41 and the table of FIG. 15;

[0027] FIG. 17 shows a 64 Kbit valid bit table followed by radix 256 tables compatible with the present invention.

[0028] In the following description of a preferred embodiment, reference is made to the accompanying drawings which form a part hereof, and in which is shown by way of illustration a specific embodiment in which the invention may be practiced. It is to be understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the present invention. A preferred embodiment of the present invention, described below, enables a remote computer system user to execute a software application on a network file server.

[0029] Hardware Environment

[0030] FIG. 1 shows a computer hardware environment that could be used with the present invention. The present invention is typically implemented using a computer 100, wherein the computer 100 comprises a processor 106, random access memory (RAM) 130, and read-only memory (ROM) and/or other components. The computer 100 may be coupled to I/O devices, such as a monitor 102, keyboard 108, mouse device 110, fixed and/or removable data storage devices 112 and 114, and printer 118. The computer 100 could also be coupled to other I/O devices, including a local area network (LAN) or wide area network (WAN) via interface cable 120. Those of ordinary skill in the art will recognize that any combination of the above components, or any number of different components, peripherals, and other devices, may be used with the computer 100.

[0031] Generally, the computer 100 operates under control of an operating system 122, which is represented by the display 104 on the monitor 102. The present invention is preferably implemented using one or more computer programs or applications 124, which are represented by the window displayed on the monitor 102 operating under the control of the operating system 122. The operating system 122 and computer program 124 are loaded from a data storage devices 112 and/or 114 into the memory 130 of the computer 100 for use during actual operations.

[0032] In the preferred embodiment of the present invention, the operating system 122 and the computer program 124 are useably embodied in a computer-readable medium, e.g., data storage devices 112 and/or 114 which could include one or more fixed or removable data storage devices, such as a floppy disk drive, hard drive, CD-ROM drive, tape drive, etc. Further, the operating system 122 and the computer program 124 are comprised of instructions which, when read and executed by the computer 100, causes the computer 100 to perform the steps necessary to implement and/or use the present invention. Those of ordinary skill in the art will recognize that many modifications may be made to this configuration, including the number, size, and types of components, without departing from the scope of the present invention.

[0033] In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be evident, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to facilitate description.

[0034] In one embodiment, steps according to the present invention are embodied in machine-executable software instructions, and the present invention is carried out in a processing system by a processor executing the instructions, as will be described in greater detail below. In other embodiments, hardwired circuitry may be used in place of, or in combination with, software instructions to implement the present invention.

[0035] Valid Bit Tables

[0036] A radix lookup uses a key or pieces of a key as an address into a table, as shown in FIG. 2. For example, if a 16 bit key were being looked up, a 64K entry table of results would be referenced by the entire key. The value in the table is the result of the lookup.

[0037] If the desired result is large, the result table can become quite large. This becomes especially wasteful if the table is sparsely populated. If this is the case, it is desirable to shrink the size of the result entries.

[0038] In a valid bit table, the only result is if the entry is valid or not, as shown in FIG. 3. A single bit is sufficient to do this. In this case, the result table would have 64K entries and each entry would be a bit. The bit would be referenced with the key as before and the result would indicate if the key were valid or not.

[0039] The valid bit table wastes very little space on invalid results because only a single bit is used, but does not provide a large result for valid entries. To improve on this, an additional table can be added that only contains the results for valid entries, as shown in FIG. 4. Valid entries are accessed in the following manner. The result table contains as many entries as there are valid results. An entry that is at location N in the result table is associated with the valid bit that is the Nth valid bit in the bit table. To determine the location of a result given a valid bit, the valid bits from N−1 to 0 must be summed. For example, in an 8 entry bit table with 3 valid results corresponding to a key of 2, 5 and 7, a key of 7 would result in the bit table being referenced at bit 7. The fact that bit 7 is set indicates the entry is valid and the result is available. Bit 7 is the third valid bit that is set. The result for bit 7 must be the third entry in the result table at location 2, counting addresses from 0. The value 2 is computed by summing all the valid bits below the valid bit selected.

[0040] This method can be extended to large bit strings as in the previous example. The problem then becomes that the summation of all the valid bits below the bit selected may require a large number of memory accesses. This problem can be solved by keeping a count along with the bit string at even intervals that records the number of valid entries to that point, as shown in FIG. 5. The address of the result is then the sum of the count plus the number of one's beyond the count but below the bit selected. An example of this is a 64 Kbit string with count values every 16 bits. The count value must be at most 16 bits long to cover the possible 64 Kbit results. This is shown pictorially in FIG. 5, which for convenience, shows the bit field rotated.

[0041] In the example shown in FIG. 5, N is the count value of the bit field above it. N is the count or sum of all the valid entries to the left of the segment. The result entry is then the count field plus the bits in the selected bit field segment that are to the left of the selected bit. The sizes of 16 bits of valid and a 16 bit offset are not required. The count must be large enough to account for the maximum number of results. The bit field associated with the count may be as large as convenient. 16 bits is convenient because both the field and the count can be read in a single 32-bit memory reference.

[0042] The result arrangement described above provides for the efficient use of memory. It is effective in tables with a large number of entries since there is a fixed overhead associated with the bit field and count representation. One problem with this type of arrangement is the difficulty in adding or removing entries from the table. Adding an entry to the beginning of the table would force all of the counts after the addition to be incremented by one. One way of improving this is to replace the count by a simple pointer, as shown in FIG. 6. The pointer points to a block of memory allocated for that pointer/bit field. The block is at least as large as the number of valid entries associated with that bit field. For example, if a pointer/bit field had a bit field that was 01001001001000101 which has 6 valid results, the pointer would point to a block of 6 consecutive entries in the result table. To allow for adding and deleting entries, space is allocated between these blocks. The fact that a pointer is used, rather than a count, is what allows space to be added between blocks. Because a pointer is used, the result blocks may be placed anywhere in the result table.

[0043] Valid Bit Tables with Hashing

[0044] Hashing may also be used for performing lookups. In hashing, the key is compressed by using a hash function and the compressed value is then used to reference a table of results, as shown in FIG. 7. Included in the result is a bit indicating the result is valid and a full copy of the key the entry represents. The key is required in the result because the compression may result in multiple keys hashing to the same location. To reduce the chance of hashing to the same location, hash tables are typically larger than the number of results. A result table that is three times larger than the number of results is typical. Even larger tables would further reduce the chance of collisions.

[0045] Valid bit tables can be used to reduce the required storage of hash results. This is accomplished by replacing the normal key with a compressed key. No other changes are required. The selected result must include a full key to compare against the original key.

[0046] Transition Bit Tables

[0047] The ability to represent ranges within a table is useful in packet-switched networking applications. The valid bit method described above does not represent ranges very well. For example, if a range of 0x4560 to 0x456f were represented with the valid bit scheme, it would require 16 duplicate entries in the result table, one for 0x4560, one for 0x4561 and so on.

[0048] An improvement on this method represents transitions in the bit field rather than valid or invalid entries shown in FIG. 8. A one in the bit field indicates the end of a range rather than a single valid entry. The mechanics of computing the address of the result corresponding to the range are nearly the same as the case of the valid bit tables. Because a one in the bit field indicates the end of a range, this also indicates a transition to a new result. The offset of a result is then obtained by summing the number of 1's to the left, or the least significant bits (LSB), of the selected bit. This is the same process as used with valid bits. The only difference is that in a transition bit table, there is no “invalid” entry, every range has a result, even if the result will indicate the range is invalid. An example is shown in FIG. 8. In the example, three ranges are represented, 0-2, 3-5, 6-7. A key of 7 would result in the transition field being referenced at bit 7. The transition bits over the range 0-6 in the transition bit table are summed to provide the offset of 2, counting from 0, into the result table. FIG. 9 shows an example of how a transition table represents a range of one as indicated by the ranges 0—0, 1—1, 2—2, and 3—3.

[0049] As with the valid bit tables, the transition bit tables can be used to represent larger tables. As with the methods described above, this creates a need for an additional count field to prevent the need to sum all bits below the selected bit. Transition tables also suffer from the problem that the table is difficult to update because all the count fields above a new or deleted entry must be adjusted when making changes. This problem can be alleviated by using pointers rather than counts, as shown in FIG. 10.

[0050] Using pointers in a transition table is not quite as effective as is the case in the valid bit tables, because unlike a valid bit table, the leading zero's in a transition bit table have a result. The result is the same result as any trailing zero's in the previous field. This forces the pointer in the second field to point to the trailing entry in the result table of the first field and eliminates the ability to add empty space between entries.

[0051] The inability to add empty space between entries may be corrected by adding additional redundant entries when separating two regions with shared results, as shown in FIG. 11. While this requires additional memory, the benefits gained by allowing easy insertion and deletion are typically considered acceptable by system designers.

[0052] Hardware Implementation

[0053] One key to the efficient implementation of the present invention is the ability to quickly sum all the bits in a field left of the selected bit. The example shown in FIG. 12 demonstrates the method for a 4 bit key and 16 bit field. It will be recognized by one of ordinary skill in the art that this method can be applied to any n bit key and 2**n bit field. For valid bit tables, the bit selected by the key must be checked. If the bit is set, it is a valid entry. If the bit is not set, the entry is invalid and no further work is required. Transition bit tables do not perform this check. The key is used to generate a mask. The mask generated has all the bits set to one which are less significant than the bit selected by the key. For example, if the key were 5, the mask generated would be 11111000000000000, where the LSB is on the left. The mask and the bit field are bitwise ANDed together which produces a value with only those bits less significant than the selected bit set. These bits are summed to produce the desired result.

[0054] Key Lookup

[0055] The present invention provides a means for performing a lookup of a key with a single access into a valid or transition bit field. The table can represent valid entries or ranges. While this technique is useful, as the size of the key grows, the amount of memory required becomes quite large and the method becomes increasingly inefficient. For example, a table sufficient for a 16 bit key would require 16 Kbytes of memory for the bit field and the result pointer. If this were used to represent the first 16 bits of lookup on a typical Internet IPv4 table with 40000 entries, this would provide an efficiency of 1.2 bits of memory per bit of key represented. If the lookup were extended to 20 bits, the efficiency drops to 32 bits of memory per bit of key represented. A different mechanism must therefore be used to perform lookups for larger keys.

[0056] A fast and efficient compressed radix lookup mechanism may be used with valid bit fields and transition fields. The basic approach is to start the lookup with a large bit field lookup, either valid or transition type, and follow it with lookups with smaller granularity. This is required because the top of a lookup tree is much more dense than the bottom. A reasonable approach is to start with a 16 bit lookup and follow it with several smaller lookups.

[0057] A radix 16 or compressed radix approach may be used in conjunction with the valid bit approach described above, as shown in FIG. 13. The search begins with a large radix lookup, 64K for example. The results of that lookup are additional radix 16 lookups. It will be recognized by one of ordinary skill in the art that other radix can be used, with radix 8, 32 and 64 being reasonably efficient when implemented as compressed radix trees.

[0058] In the example shown in FIG. 13, the first 16 bits of the key are used to reference the 64K valid bit table. In the associated result table, the result entries are compressed radix 16 entries that continue the lookup of bits 16 to 19 of the key. The remaining 4 bits are looked up in another compressed radix 16 entry in another piece of memory.

[0059] Compressed Radix with Transition Fields

[0060] The valid bit representation of compressed radix tables may also be used with transition bits. The compressed radix with transition fields format is useful in representing ranges, as shown in FIG. 14. Each entry into the compressed radix table in this case has a continue/vector bit, a pointer to a next vector or a result block, and a transition field to represent of range as illustrated in FIG. 14. The use of this compressed radix format is similar to that described above with the exception of the transition field. FIG. 15 shows an example illustrating how transition fields can be used on tables for compressed radix trees to represent ranges. The example represents three ranges:

[0061] 1. 0x00-0x22 with a result of A.

[0062] 2. 0x23-0x45 with a result of B.

[0063] 3. 0x46-0xFF with a result of C

[0064] FIG. 16 shows an example of a compressed radix lookup into the table of FIG. 15 using a key of 0x 41. The first nibble of the key, being a 4, selects the bit position labeled 4 in the transition field. The transition bits to the left of the selected bit position (i.e. the lower order bit positions labeled 0-3 in FIG. 16) are summed up to obtain a value of 3. The next entry into the table is determined by adding the pointer 1 and the summation value of 3 together. This next entry has its Continue/Vector bit set to a C to indicate a continuation in the lookup sequence a pointer 3 in its pointer field. The second nibble of the key, being a 1, selects the bit position labeled 1 in the transition field. The transition bits to the left of the selected bit position (i.e. the lower order bit position labeled 0 in FIG. 16) is summed up to obtain a value of 0. The next entry into the table is determined by adding the pointer 3 and the summation value of 0 together. This next entry has its Continue/Vector bit set to a V to indicate this is the end of the search or lookup and its pointer field returns the result of B.

[0065] Most network tables must represent both specific values and ranges of values. The transition field representation is typically not the most efficient way of representing specific values as each value will require at least two results, one for the value and one for not the value. In light of this, a preferred embodiment of the present invention is able to support both the valid and transition field representations. Differentiating between the two can be accomplished with an additional bit in the entry indicating the type of entry it is, or segmenting memory and using the location in memory as an indication of the entry type.

[0066] Another method of representing both types of entries is to double the size of the transition bit field to allow two bits per transition. In this case, the bits can be encoded to mean

[0067] invalid entry

[0068] start or middle of range

[0069] valid entry

[0070] end of range.

[0071] The advantage of this encoding is that invalid entries do not need to be represented in the corresponding result block. An effect of this encoding is that it double the size of the transition field.

[0072] Larger Radix Searches

[0073] Another possible way of continuing the searches is simply to use the valid/transition bit tables described above with smaller radix values, as shown in FIG. 17. For example, a system could start with a radix 64k lookup (16 bit key) followed by a radix 256 (8 bit) lookup. The problem with this approach is that some 256 bit field may only represent one range. The memory efficiency in this case is quite low. A 256 bit field with associated pointers will require 64 bytes of memory. To reach the efficiency of the compressed radix 16 tables which has a maximum of 8 bits per bit, a radix 256 table must represent 8 entries, which is 8 bits of key * 8 keys in 64 bytes of memory.

[0074] One method of using the longer radix tables in continuing lookups requires three memory references for a 24 bit key, as shown in FIG. 17. In this example, the first 16 bits of the key are used to reference a 64K valid/transition bit table. The result is a pointer to the beginning of a 256 bit valid/transition bit table. This table is then referenced to lookup the remaining 8 bits of the key. The result of this lookup is the result of the overall lookup. This takes three memory references to resolve the lookup, with one additional memory reference required to read the result: the first memory reference is used for the 16 bit valid field and associated pointer, the second memory reference is used for the first result table, the third memory reference is used to reference the valid field and pointer in the 256 bit table, and the fourth memory reference reads the result.

[0075] While the invention is described in terms of preferred embodiments in a specific system environment, those of ordinary skill in the art will recognize that the invention can be practiced, with modification, in other and different hardware and software environments within the spirit and scope of the appended claims.