Multi-resolution tree for longest match address lookups

[0002] The present invention relates to forwarding devices in general. More particularly, the present invention relates to a method and apparatus for performing longest match address lookups for routing a packet or cell of information in a network.

[0003] The popularity of communications networks such as the Internet and World Wide Web (WWW) is growing at a phenomenal rate. Part of the reason for this growth is the rich amount of content available through these networks, as well as the ability to provide interactive communications services. For example, it is currently possible to place a telephone call using the Internet rather than the Public Switched Telephone Network (PSTN). Moreover, it is possible to engage in multi-media communications over the Internet, such as video conferencing, telecontrol, distributed computer applications, multimedia conferencing, remote visualization, high definition television (HDTV) and even virtual reality.

[0004] The increase in usage of the Internet increases the basic unit of transfer used by the Internet, namely data packets. The Internet is already required to process hundreds of thousands of packets per second, with indications that it must process millions of packets per second to maintain pace with user demand. In response to this demand, communications technologies have been developed which significantly improve the number of packets which can be moved through the network.

[0005] A problem still persists, however, with a class of network devices which are integral to combining disparate networks together. These network devices are collectively referred to as forwarding devices, examples of which include packet switches, routers and bridges. The basic function of a forwarding device is exactly as it sounds, that is, the forwarding device takes a data packet, looks up forwarding information needed to route the packet to its destination, and forwards the packet to another network device using the forwarding information.

[0006] A forwarding device accomplishes this basic routing or directing function by utilizing a routing table. A routing table comprises destination addresses and forwarding information used by the forwarding device to direct a packet to its next or ultimate destination. In recent years, the sheer number of destination addresses required for the routing table have caused forwarding devices to become saturated in terms of processing power and memory allocation. Lookup algorithms designed to compare a destination address retrieved from a packet with the ever-growing number of destination address stored in the routing table are far too slow and inefficient to meet current forwarding device throughput requirements.

[0007] In an attempt to reduce the number of destination addresses required for a routing table, a new Internet addressing scheme was developed which is referred to as Classless Interdomain Routing (CIDR). CIDR aggregates or groups IP addresses together in hierarchical levels, similar to the hierarchical addressing scheme used to route a telephone call to a specific call recipient using a telephone number. Take for example the telephone number 412-555-1212. The area code (i.e., 412) indicates the general area of the call recipient, while the next three digits (e.g., 555) further narrows down the location to a more specific local, while the last four digits (i.e., 1212) identifies the precise location of the called party. CIDR groups IP addresses together in a similar hierarchical pattern, with the leftmost bits of an IP address giving the location of a particular network, while the location of a network device or host becomes increasingly specific as the address reads to the rightmost bit. For example, a typical Internet address under the IP version 4 (IPv4) addressing scheme might be 1.1.1.2 in decimal form, which is represented in binary form as a sequence of 32 binary bits, i.e., 00000001.00000001.00000001.00000010. CIDR is a method of identifying those address bits which are meaningful for routing a packet to its next destination. Since the Internet is comprised of a plurality of forwarding devices, it is sometimes unnecessary to have a complete destination address for each packet in the routing table. Rather, an abbreviated address could be used which merely represents forwarding information to the next forwarding device. This is referred to as “hop-by-hop forwarding.” Thus, instead of using 00000001.00000001.00000001.00000010 to index forwarding information for a packet, CIDR assigns a prefix for each address, the prefix comprising an IP address and some indication of the leftmost contiguous significant bits within this address. For example, the CIDR prefix 1.1.1.2/16 would mean that only the first 16 bits of the address 1.1.1.2 are significant for routing purposes. The result is fewer destination addresses are required for each Internet forwarding device's routing table.

[0008] Although CIDR reduced the number of destination addresses stored in a routing table, CIDR also complicated the lookup algorithms required to lookup forwarding information stored in the table. Under CIDR, routing to all destinations is always performed on a longest match basis. It may occur that a routing table may have different length prefixes of the same network which match the destination address of a packet. When a forwarding device must decide between two different length prefixes of the same network, it will always follow the longer mask. By way of analogy, if a switch in the PSTN had a choice to route a call using just the area code, or the area code and next three digits, the switch would use the area code plus three digits to route the call since it is more precise. As an example for a forwarding device, assume that a forwarding device has the following two CIDR prefixes in its routing table: (1) 198.32.1.0/24 via path 1 and (2) 198.32.0.0/16 via path 2. When trying to deliver traffic to host 198.32.1.1., the forwarding device tries to match the destination with the longest prefix and in this case would deliver the traffic via path 1. Thus, the longest match rule imposed by CIDR requires that for each destination address embedded within a packet, the lookup algorithm must search the entire routing table for the longest prefix.

[0009] The CIDR longest match rule can be better understood with reference to FIG. 1. FIG. 1 is a diagram for a logical representation of the longest match rule. A data packet is received by a forwarding device with an IP address of 124.13.7.5. The forwarding device uses a lookup algorithm to search for matching prefixes within a routing table 16. Routing table 16 contains prefixes with varying levels of granularity, with the meaningless bits represented by the letter “X”. The search first uncovers the matching prefix 124.X.X.X (referred to as match preference three). Since the longest match rule requires that the entire routing table be searched for the longest prefix that matches the destination address, the forwarding device must continue searching routing table 16. The continued search uncovers a second match preference of 124.13.X.X. Since the address 124.13.7.5 more closely resembles 124.13.X.X, this match preference is more desirable the match preference three since it more specifically identifies a route for the packet. Finally, the search uncovers a first match preference of 124.13.7.X. Since this prefix is the closest match to the address 124.13.7.5 in routing table 16, the forwarding device will use the forwarding information associated with this prefix to route the packet to its next destination.

[0010] Different lookup solutions such as the hash, radix tree, Patricia tree and cached variations thereof, have been developed to perform longest match lookups required by CIDR. The conventional lookup solutions, however, are unsatisfactory for a number of reasons. For example, all of the conventional solutions suffer under the fact that the number of steps necessary for a longest match lookup can grow large in certain cases. This leads to more frequent memory accesses, which slow down the lookup process. Current state of the art solutions such as Patricia trees or radix trees can degenerate to as many as 32 memory accesses per IPv4 address lookup. This is because Patricia tree or radix tree algorithms compare individual bits of a destination address with individual bits stored in the routing table. Since there are 32 bits in the destination address, there are 32 levels of bits stored in the routing table. Therefore, it is possible that each bit of the destination address must be compared with each level of the routing table if the longest match prefix happens to be at the bottom level. Since each bit comparison requires at least one memory access, a single lookup using Patricia tree or radix tree solutions could require up to 32 memory accesses for a worst case scenario. Moreover, these solutions only work for limited amount of addresses, caches have to be populated and de-populated often, and they require fairly complex lookup algorithms which further slow down forwarding device throughput.

[0011] The following example will help demonstrate the above problems. Current user demands indicate that forwarding devices need to process at least a million packets per second. A million packets per second is equivalent to 1 millisecond per packet, or 1000 nanoseconds per packet. It is desirable for forwarding devices to utilize inexpensive 60 nanosecond Dynamic Random Access Memory (DRAM) to store routing tables in order to decrease hardware costs associated with forwarding devices. Thus, every time the forwarding device needs to access a piece of data in a routing table stored in inexpensive DRAM, it takes 60 nanoseconds. Conventional lookup algorithms such as those associated with the Patricia tree solution require at least 32 memory accesses per IPv4 address lookup assuming a worst case scenario, which at 60 nanoseconds per access requires 1920 nanoseconds per packet or lookup. Consequently, forwarding devices using conventional lookup algorithms are not capable of processing one million packets per second, since this would require 1000 nanoseconds per lookup, and the best conventional lookup algorithms can only reach 1920 nanoseconds per lookup under worst case conditions.

[0012] Various techniques such as “pipelining” and “parallel processing” have been implemented to improve the performance of conventional lookup algorithms. Even with these performance enhancing techniques, however, forwarding devices utilizing conventional lookup algorithms are not capable of reaching the desired throughput speeds without significantly increasing the cost of the forwarding device itself.

[0013] Another problem with conventional forwarding devices is the maintenance of the routing table. According to principles well-known in the art, the routing table,for a forwarding device must be periodically updated to reflect address and routing changes throughout the network. Conventional maintenance techniques, however, cannot update a routing table without preventing the forwarding device from utilizing the routing table. This is because conventional techniques read-lock those routing table entries that are currently being updated. This means that if a packet destination address requires the lookup of a routing table entry that is currently being updated, the packet will have to wait until the updating process is finished before being forwarded, or in the worst case scenario, be dropped from the network entirely.

[0014] In view of the foregoing, it can be appreciated that a substantial need exists for a innovative longest match lookup solution which solves the above-discussed problems.

[0015] One embodiment of the invention comprises a method and apparatus for forwarding packets in a network. A routing table is constructed using p-structures. An address for a packet is received. The address is matched with a longest prefix stored in the routing table. A decision value associated with the longest prefix is retrieved. The packet is forwarded in accordance with the decision value.

[0016] This embodiment of the invention matches an address with the longest stored prefix by first initializing a current partition member to a first partition member. The address is then translated into a p-structure index utilizing partition information stored for the current partition member. A decision value associated with the index is stored. A test is made to determine if there is a pointer associated with the index. If there is a pointer associated with the index, the current partition member is set to a next partition member associated with the pointer. This process is repeated until there are no more pointers associated with last index.

[0017] This embodiment of the invention translates the address into a p-structure index utilizing partition information stored for the current partition member by first storing the address in a register. A mask associated with the current partition member is then retrieved. The address is then masked with the partition mask, and shifted to the right in accordance with a shift value associated with the current partition member.

[0018] With these and other advantages and features of the invention that will become hereinafter apparent, the nature of the invention may be more clearly understood by reference to the following detailed description of the invention, the appended claims and to the several drawings attached herein.

[0019] FIG. 1 is a diagram for a logical representation of the longest match rule.

[0020] FIG. 2 is a diagram of a communications network suitable for practicing one embodiment of the invention.

[0021] FIG. 3 is a block diagram of a forwarding device suitable for practicing one embodiment of the invention.

[0022] FIG. 4 is a diagram representing exemplary p-structures for a routing table.

[0023] FIG. 5(a) is a first block flow diagram of steps for constructing a routing table in accordance with one embodiment of the invention.

[0024] FIG. 5(b) is a second block flow diagram of steps for constructing a routing table in accordance with one embodiment of the invention.

[0025] FIG. 6 is a diagram of an example for the population of a routing table in accordance with one embodiment of the present invention.

[0026] FIG. 7(a) is a first block flow diagram of steps performed by a forwarding decision module in accordance with one embodiment of the present invention.

[0027] FIG. 7(b) is a second block flow diagram of steps performed by a forwarding decision module in accordance with one embodiment of the invention.

[0028] FIG. 8 is a diagram of a destination address converted to a p-structure index for a routing table in accordance with one embodiment of the present invention.

[0029] FIG. 9 is a diagram showing a second example of a routing table constructed in accordance with one embodiment of the present invention.

[0030] FIG. 10 illustrates a block diagram of a conventional router suitable for practicing another embodiment of the invention.

[0031] Referring now in detail to the drawings wherein like parts are designated by like reference numerals throughout, there is illustrated in FIG. 2 a diagram of a communications network suitable for practicing one embodiment of the invention. A network 18 is comprised of multiple hosts 20, 22, and 24, which are connected via network links to forwarding devices 26, 28 and 30, respectively. Although network 18 has been reduced in size for explanation purposes, it can be appreciated that actual networks may have thousands of forwarding devices, with numerous hosts connected to each forwarding device.

[0032] Network 18 is a connectionless-oriented network utilizing the Transmission Control Protocol/Internet Protocol (TCP/IP). Each network device in network 18 is assigned a unique address using the Internet Protocol Version Four (IPv4) or Six (IPv6) addressing scheme. This unique address is used by forwarding devices 26, 28 and 30 to direct or route a data packet from one host to another host.

[0033] FIG. 3 is a block diagram of a forwarding device suitable for practicing one embodiment of the invention. In this embodiment of the invention, forwarding devices 26, 28 and 30 are general purpose computers configured with special software and/or hardware to perform the functionality for this embodiment of the invention. As shown in FIG. 3, a forwarding device 40 comprises a main memory module 42, a central processing unit (CPU) 44, a bus adapter 46, a forwarding decision module 48, and a routing table constructor module 50, each of which is connected to a CPU/memory bus 52 and an Input/Output (I/O) bus 54 via bus adapter 46. Further, forwarding device 40 contains multiple I/O controllers 58 connecting an external memory 56, a keyboard 60, a database 62, a monitor 64, and a packet network interface 66 to I/O bus 54.

[0034] The overall functioning of forwarding device 40 is controlled by CPU 44, which operates under control of executed computer program instructions that are stored in main memory 42 or external memory 56. Main memory 42 may be any type of high-speed machine readable storage device, such as random access memory (RAM), dynamic read only memory (DRAM), static read only memory (SRAM), read only memory (ROM), programmable read only memory (PROM), erasable programmable read only memory (EPROM), electronically erasable programmable memory (EEPROM), and so forth. External memory 56 may be any type of machine readable storage device which is capable of storing data but from which data can be accessed at lower speeds than main memory 42, such as magnetic storage media (i.e., a magnetic disk) or optical storage media (e.g., CD-ROM). Further, forwarding device 40 may contain various combinations of machine readable storage devices through other I/O controllers, which are accessible by CPU 44, and which are capable of storing a combination of computer program instructions and data. For example, database 62 may comprise the same structure listed with reference to main memory 42 or external memory 56, but is located remotely from forwarding device 40.

[0035] CPU 44 includes any processor of sufficient processing power to perform the functionality for this embodiment of the invention. Examples of CPUs suitable to practice this embodiment of the invention include the Pentium family of processors, such as the Pentium®, Pentium® Pro and Pentium® II processors, available from Intel Corporation.

[0036] Bus adapter 46 is used for transferring data between CPU/memory bus 52 and I/O bus 54. Bus adapter 46 operates using techniques and principles that are well-known to those skilled in the art.

[0037] I/O controllers 58 are used to control the flow of information between forwarding device 40 and external devices or networks such as external memory 56, keyboard 60, database 62, monitor 64 and packet network interface 66. The functions of these external devices are well-known, and will not be described in detail herein. By way of brief explanation, however, packet network interface 66 is used for communications between forwarding device 40 and other network nodes connected to network 18. In this embodiment of the invention, interface 66 is configured to communicate packets using the TCP/IP protocol. It can be appreciated, however, that other packet interfaces suitable for use with other packet transfer protocols can be implemented in forwarding device 40 and still fall within the scope of the invention. Further, forwarding device 40 could have multiple interfaces depending on the required number of physical connections to network 18.

[0038] Routing table construction module 50 implements the functionality for organizing, constructing and maintaining a routing table 68 stored in main memory 42. Module 50 specifies a data structure used for routing table 68, and the algorithms used to construct and maintain routing table 68 in accordance with the data structure.

[0039] Forwarding decision module 48 implements the functionality for a longest match address lookup algorithm suitable for use with a routing table organized in accordance with the principles outlined with routing table constructing module 50. Forwarding decision module 48 performs longest match address lookups for any length address lookups which are, for example, part of routing table 68 stored in main memory 42.

[0040] In this embodiment of the invention, the functionality of routing table constructing module 50 and forwarding decision module 48 is demonstrated utilizing the IPv4 addressing scheme and CIDR. It can be appreciated, however, that the functionality of modules 48 and 50 can be implemented for other addressing schemes (e.g., IPv6) and still fall within the scope of the invention.

[0041] The functionality of each of modules 48 and 50 may be implemented in hardware, software, or a combination of hardware and software, using well known signal processing techniques. In this embodiment of the invention, the functionality for modules 48 and 50 is implemented in software, with the overall functioning of modules 48 and 50 controlled by CPU 44. CPU 44 operates under control of executed program instructions which are stored in main memory 42 or various combinations of machine readable storage devices, which are accessible by CPU 44, and which are capable of storing a combination of computer program instructions and data required to implement the functionality of modules 48 and 50. CPU 44 is capable of executing multiple processes at the same time, and in this way implements the functions of modules 48 and 50. The processes for modules 48 and 50, however, can also be executed by multiple CPUs (i.e., parallel processing) which will be described in more detail later in this detailed description.

[0042] It is worthy to note that modules 48 and 50 are shown as separate functional modules in FIG. 3. It can be appreciated, however, that the functionality for modules 48 and 50 can be combined to form a single module, or separated into further modules, and still fall within the scope of the invention.

[0043] The operation of modules 48 and 50 will be described in general form, with specific examples to follow. The operations of these modules may be better understood, however, if the general principles underlying the organization of routing table 68 are first described.

[0044] The organization of routing table 68 begins with the underlying assumption that an address is split according to some given, fixed boundaries or partitions. The partition for an address is represented as an ordered set of numbers:

[0045] Θ={θ_n:nεN}

[0046] For example, an address may be partitioned as {12, 10, 12}, meaning that the address is split into three stages with consecutively 12, 10 and 12 bits each. The number of partitions defines the maximum number of memory accesses forwarding device 40 will have to make in order to find the longest matching address to the destination address of a packet. It should be noted that for a given i there are maximally 2^θi−1p-structures necessary.

[0047] Although this embodiment of the invention will work with partitions of any size, the exact size of the partitions will be generally influenced by the distribution of lengths of address prefixes used to build a routing table in a system. Further, the exact size of the partitions will determine the balance between memory requirements and the maximal number of steps forwarding decision module 48 has to perform for the lookup of a full address. Within these general parameters, a partition size can be developed which is optimized for a particular system utilizing this embodiment of the present invention.

[0048] In addition, the notion of a complementing subset of a bit sequence will be helpful for understanding the organization of routing table 68. A complementing subset of a bit sequence is defined for a binary number: $B_{\alpha ,\beta }=b_{\beta }{b}_{\beta -1}\dots b_{\alpha }\dots b_0=\sum _{n=\alpha }^{\beta }{b}_n*2^n=b_{\beta }\dots b_{\alpha }\underset{\underset{\alpha }{⏟}}{00\dots 0}$

[0049] as

[0050] {circumflex over (B)}_a:={λεN:λ<2^a{circumflex over ( )}λ≧0}

[0051] which translates, e.g., for a bit sequence B_3.2=1100₂into {circumflex over (B)}₂=00₂,01₂,10₂,11₂. Generally, an abbreviation will be used based on the fact that 32 bit IPv4 addresses with some number of first significant bits are traditionally written as e.g. 128.128.1.0/24 which stands for:

[0052] B_7.31=10000000′10000000′00000001′00000000₂,

[0053] an address of which only the first bold 24 bits are significant. In addition, it will prove beneficial to define a length function in connection with a partition. Number of bits of the first n elements of a partition should be defined as: $\lambda \left(n\right)=\sum _{v=1}^n{\theta }_v.$

[0054] An underlying structure for routing table 68 is a block of memory with 2^(θx)entries representing the decision needed for the forwarding step and a pointer to a possible next partition structure (herein after referred to as a “son” or “p-structure”) of block size 2^(θx+1).

[0055] FIG. 4 is a diagram representing exemplary p-structures for a routing table. FIG. 4 illustrates a set of p-structures 70 and 72 for a partition of {2,2}, which splits the address into two partitions of 2 bits each. Each p-structure is represented as an array having two parts, the first part containing forwarding information (hereinafter referred to as a “decision value”), and the second part containing a pointer to another p-structure or son if present (“p-structure pointer”). When a prefix B is inserted into the routing table, its decision value is written into the appropriate entry, and also into all entries of the p-structure indexed by the set {circumflex over (B)}. For example, for the binary index of “11”, a decision value of “14” is listed for p-structure 70, with a p-structure pointer to p-structure 72. In turn, p-structure 72 has a decision value of “21” for binary index “1100”, but since p-structure 72 has no sons, there is no p-structure pointer necessary for p-structure 72. Thus, when forwarding decision module 48 looks up an entire 32 bit address, it need only split the address into |Θ| parts by doing the necessary masking and shifting operations, and using the resulting numbers as indices into p-structures to obtain the decisions necessary. In essence, this structure increases the lookup speed at the price of management of a tree of p-structures and controlled memory waste.

[0056] Routing table constructing module 50 organizes, constructs, and maintains routing table 68 for forwarding device 40. Module 50 performs the construction of routing table 68 in conformance with the p-structure organizational principles discussed previously. In general, module 50 inserts an IPv4 prefix into an existing tree of p-structures which ultimately allows to set-up a forwarding table used by forwarding decision module 48 for longest match lookup of an IPv4 address in the existing tree of p-structures. This process is sometimes referred to as “populating” and “de-populating” the routing table. The process by which module 50 populates and de-populates routing table 68 is described with reference to FIGS. 5(a) and 5(b).

[0057] FIG. 5(a) is a first block flow diagram of steps for constructing a routing table in accordance with one embodiment of the invention. At step 74 a current partition member is initialized to a first partition member, and a bit counter to zero. At step 76 a prefix and a decision value for the prefix are received. The prefix comprises an address and a masklength. At step 78 an index is built by masking the address using a mask associated with the current partition member.

[0058] Module 50 determines whether all partition members have been tested, or the bit counter is greater than the masklength, at step 82. If either condition is true at step 82, than control is passed back to step 74 to insert the next prefix, or alternatively, the algorithm ends. If both conditions are not true, however, control is passed to step 80. At step 80 the bit counter is set to a bit size for the current partition member. At step 84 module 50 determines if a current p-structure has been allocated for the current partition member. If not, then a current p-structure is allocated for the current partition member at step 86, and control passed to step 88 (as indicated by the letter “E”). If there has been a p-structure allocated at step 84, then control is passed directly to step 88 (as indicated by the letter “D”).

[0059] FIG. 5(b) is a second block flow diagram of steps for constructing a routing table in accordance with one embodiment of the invention. Module 50 determines whether the bit counter is greater than or equal to the masklength at step 88. If true at step 88, then module 50 writes the decision value for all entries in the current p-structure corresponding to the bits given in the address, and all bit combinations for the length of the bit size for the current partition member at step 90 given that a decision value was not already stored by a previous longer prefix, and control is passed to step 92. If false at step 88, then control is passed to step 92. At step 92 module 50 stores a pointer to the next p-structure in the p-structure for the current partition member. At step 93 module 50 increments the bit counter by the bit size of the next partition member. At step 94 module 50 sets the current partition member to the next partition member. At step 95 module 50 sets the current p-structure to the next p-structure, and control is passed to step 82 (as indicated by the letter “F”).

[0060] FIG. 6 is a diagram of an example for the population of a routing table in accordance with one embodiment of the present invention. As shown in FIG. 6, a ‘first’ p-structure has two prefixes, the second longer than the first and covering a part of the address-space the first one covered as well.

[0061] FIG. 6 is a logical representation for building a routing table in accordance with one embodiment of the invention. Assume that module 50 is constructing a routing table, and needs to insert prefixes 100₂/1 and 110₂/2 into the table. As shown in FIG. 6, module 50 inserts prefix 100₂/1 with a decision value of 1 into a p-structure 96. Since only the first bit is meaningful for routing purposes, which in this case is a “1”, the decision value 1 is inserted for all indices wherein the first bit equals “1”. Afterwards, module 50 then inserts prefix 110₂/2 with a decision value of 2 into p-structure 96, forming a new state for the p-structure referred to as p-structure 98. Since the first two bits are meaningful for routing purposes, which in this case is “11”, the decision value 2 is inserted for all indices wherein the first two bits equals “11”. To ensure the proper overwriting of the decision values for 100₂/1, however, module 50 inserts the decision value for 110₂/2 only in those indices which match the number of meaningful bits indicated for 110₂/2, which are “110” and “111”.

[0062] Forwarding decision module 48 performs the functionality for receiving a destination address for a packet and looking for forwarding information for the destination address in routing table 68 in conformance with the longest match rule. Forwarding decision module 48 assumes that routing table 68 has been constructed in accordance with the p-structure organizational principles discussed above. The process implemented by module 48 will be discussed in more detail with reference to FIGS. 7(a) and 7(b).

[0063] FIG. 7(a) is a first block flow diagram of steps performed by a forwarding decision module in accordance with one embodiment of the present invention. Module 48 begins by receiving a destination address from a packet sent over network 18 at step 100. The mask for the current partition is set to the mask for the first partition at step 102. At step 104 the mask for the current partition is applied to the destination address using conventional techniques, which in this embodiment of the invention is a bit AND operation. The result of the mask is then shifted to the right a predetermined number of bits that is associated with the current partition at step 106. The shifted result becomes the index of the array holding a decision value for the address, and is used to retrieve the decision value at step 108. The decision value is then tested to determine whether it is a valid decision value at step 110. A valid decision value is a decision value which provides actual forwarding information for routing the packet.

[0064] FIG. 7(b) is a second block flow diagram of steps performed by a forwarding decision module in accordance with one embodiment of the invention. If the decision value is valid at step 110, the decision value is stored at step 112 (as indicated by the letter “A”), and control is passed to step 114. If the decision value is not valid at step 110, then step 112 is bypassed and control is passed directly to step 114 (as indicated by the letter “B”).

[0065] In addition to storing a decision value for the index, the array potentially stores a p-structure pointer for a son of the first p-structure. Thus, module 48 determines whether a son exists for the current index value at step 114. If there is a son at step 114, then the mask for the current partition is set to the mask for the second partition at step 118, and control is passed to step 104 (indicated by the letter “C”). Steps 104, 106, 108, 110, 112 and 114 are then repeated for the son. This continues for every son until there are no more sons determined at step 114.

[0066] If there is no son at step 114, then module 48 determines whether there is a valid decision value stored for the address at step 116. If there is a valid decision value stored at step 116, then the decision value is used to route the packet to its destination. If there is not a valid decision value stored at step 116, then the default setting for this condition is to drop the packet at step 122. It is worthy to note that this default condition can be modified to suit the desires of the network administrator or network designer, and still fall within the scope of the invention.

[0067] FIG. 8 is a diagram of a destination address converted to a p-structure index for a routing table in accordance with one embodiment of the present invention. Assume that the partition for routing table 68 is {12, 12, 8}. The precomputed mask and shift values for each partition member are shown in Table 1.

[0068] Assume that a packet has a destination address represented in decimal of 0.0.1.2. The binary equivalent of IP address 0.0.1.2 is shown in block 130. Using the above precomputed masks and shift values shown in Table 1, the mask for the first partition member is retrieved at step 102 and is shown in block 132. The mask is then applied to the address shown in block 130 at step 104, and produces a masked address which is shown in block 134. The shift value associated with the first partition member is 20, as shown in Table 1. The masked address shown in block 134 is then shifted by 20, producing a shifted masked address that is shown in block 136. This shifted masked address is the index into the p-structure array for the first partition as shown in block 138.

[0069] If the index for the p-structure array indicates that there is a son for this index, then the above described process is continued for the second partition member. This process continues for each son utilizing the appropriate partition member, until there are no more sons remaining for the index value.

[0070] As can be appreciated from the example described above with reference to FIG. 8, the steps performed by module 48 are relatively few, and are optimized for the routing table constructed in accordance with the p-structure principles described above. As a result, the longest matching address for each packet can be retrieved extremely fast, and

[0071] FIG. 9 is a diagram showing a second example of a routing table constructed in accordance with one embodiment of the present invention. The diagram shown in FIG. 9 will be helpful in describing a further example of the longest matching address algorithm performed by forwarding decision module 48. Sample destination addresses will be used to explain how module 48 operates therefore forwarding device 40 can process packets at a correspondingly high rate. It is estimated that forwarding device throughput can be increased using the principles of this embodiment of the invention on the order of two to eight times the throughput achievable by forwarding devices utilizing conventional longest match algorithms, depending on the particular implementation and whether the algorithms are performed in software or hardware. By utilizing techniques such as pipe-lining and parallel processing, it is possible to increase forwarding device throughput even more.

[0072] The following examples of the operation of this embodiment of the present invention will focus on an address lookup given a routing table (or tree) that is already initialized through the insertion of the necessary prefixes in accordance with partition principles described previously. The routing table is based on a partition of {12, 12, 8}, and its current state reflects executed insertion of the following prefixes:

[0073] 1.0.0.0/8 or written in hexadecimal notation 1.0.0.0/8 with decision 1;

[0074] 1.48.0.0/11 or written in hexadecimal notation 1.30.0.0/11 with decision 2;

[0075] 0.0.0.0/23 or written in hexadecimal notation 0.0.0.0/23 with decision 3;

[0076] 1.31.255.0/24 or written in hexadecimal notation 1.1F.FF.0/24 with decision 4.

[0077] It is worthy to note that the insertion of the last prefix creates a rather peculiar part of the tree, at first inspection it seems as if the decision should be written into the node corresponding to the second member of the partition since/24 is exactly λ(2). The inventors of this embodiment of the invention, however, have recognized that the binary complement of this number is filled using this decision. As shown in FIG. 9, this binary complement is the node represented in level 3, ranging from 1.31.255.0 to 1.31.255.255 or in hexidecimal form 01.1F.FF.00 to 01.1F.FF.FF.

[0078] Each of the following examples will be described using the steps performed by forwarding decision module 48, as described with reference to FIGS. 7(a) and 7(b). Each example demonstrates a unique facet of the behavior of modules 48 and/or 50.

[0079] The first example destination address is 0.0.1.244. For address 0.0.1.244, module 48 will mask the value 0 into variable index, shift it by 20 bits to the right, and still holding 0 for index value access the entry in block 1. These steps were described before in more detail with reference to FIG. 8. This entry holds 0 as decision and points to node 2 as son. The next iteration of the loop will preserve the bold bits 00000000′00000000′00000001′00000000 of the address which are the bits 9 to 20 counted from the right. After shifting those bits 8 times to the right the resulting index of 1 will be used to access decision 3 in block 2. Since no son exists there, this is the best match.

[0080] The destination address for the second example is 1.0.0.0. Once the proper index is found using the steps described with reference to FIG. 8, the resulting index will in the first step match the decision 1 in the entry of block 1 indexed by bits 00000001′0000. Since no pointer to a son is present in this entry, this will be the best match as well.

[0081] The destination for the third example is 1.16.0.0. The resulting index will match decision 1 in the entry of block 1 indexed by bits 00000001′0001 and take the son pointer to block 3. The next iteration of the loop uses the bold bits 00000001′00010000′00000000′00000000 from the address and finds a decision 0 and no son pointer. Thus, decision 1 from the first iteration of the loop is the best match.

[0082] The destination address for the final example is 1.31.255.140. After the resulting index is determined, the first step takes decision 1 from block 1 and pursues the pointer to block 3. Here in the next iteration of the loop for a change the bold bits 00000001′00011111′11111111′00000000 are extracted, shifted 8 times to the right, and a pointer to block 4 is followed. In block 4 the remaining bold part of the address 1.31.255.140 is used to find the entry of interest which yields the decision 4 as the decision value. Since no son pointer is found, it is the best decision for this address.

[0083] The computer program instructions necessary to implement the functionality of modules 50 and 48 can be derived from the flow diagrams illustrated in FIGS. 5(a), 5(b), 7(a) and 7(b), and the following “pseudo-code”. The pseudo-code notation utilizes syntax from the “MODULA-2” programming language, as well as several mathematical operators used to enhance the logical structure of the solution. The mathematical operators are defined as. follows:

[0084] |X| stands for the number of elements in set X.

[0085] X₂stands for the binary notation of a number X.

[0086] In addition, ‘C’-notation is used for bit-oriented manipulations of numbers as follows:

[0087] x&y stands for binary ‘AND’ operation between x and y.

[0088] x|y stands for binary ‘OR’ operation between x and y.

[0089] ˜x stands for binary complement of x.

[0090] x<<y stands for a shift of x to the left by y bits.

[0091] x>>y stands for a shift of x to the right by y bits.

[0092] To better understand the following pseudo-code, it may be helpful to define the following PASCAL or Modula-2 syntax:

[0093] ADDR (x) stands for address of a variable x.

[0094] x{circumflex over ( )} stands for de-reference of the address x or for the value of the variable x is pointing to.

[0095] Routing Table Construction Module Pseudo-Code

[0096] (* Declarations, Definitions and Initialization *)

[0097] TYPE IPAddress: INTEGER OF SET OF 0 . . 11111111′11111111′11111111′11111111₂;

[0098] TYPE IPMask: INTEGER OF SET OF $\underset{\underset{\alpha }{⏟}}{0\dots 0}\underset{\underset{\beta }{⏟}}{1\dots 1}\underset{32-\alpha -\beta }{{\underbrace{0\dots 0}}_2};$

[0099] TYPE MaskLength: INTEGER OF SET OF 0. . 32;

[0100] TYPE pSTRUCTURE: STRUCTURE OF BEGIN

[0101] son: POINTER TO mSTRUCTURE; (* next level *)

[0102] decision: INTEGER; (* decision this structure holds*) END;

[0103] TYPE mSTRUCTURE: STRUCTURE OF BEGIN p1: pSTRUCTURE;

[0104] fatherbits: INTEGER; (* how many bits had the father that wrote this entry *) END;

[0105] TYPE mNode: ARRAY [0 . . ] OF mSTRUCTURE;

[0106] (* this is an open array that actually presents mSTRUCTUREs that can be indexed based on significant bits. The number of elements of the array will depend on the level at which this structure is implemented *)

[0107] (* The type mNode and mNodePtr will be intermingled in the code [much like in C] because they represent really the same thing, namely a pointer to the beginning of an array of varying number of elements. At different points, use of either type is more natural in the context of operations performed on it. *)

[0108] TYPE mNodePtr: POINTER TO mNode;

[0109] Θ: ARRAY [1 . . n] OF INTEGER: {θ₁to θ_n};

[0110] Entries: ARRAY [1 . . |Θ|]:={2^θ₁to 2^θ_n};

[0111] (* precomputed array of shifts & masks that have to be performed on the address for the partition given *)

[0112] AddrParts: ARRAY [1 . . |Θ|] OF STRUCT BEGIN

[0113] mask: IPMask;

[0114] shifts: INTEGER; END;

[0115] TreeRoot: mNodePtr; (* root of the complete MR-Tree *)

[0116] CONSTANT

[0117] NO_DECISION: INTEGER:=0;

[0118] (* no decision exists for this entry *)

[0119] CONSTANT

[0120] TREE_ENDED: INTEGER:=1;

[0121] (* tree ends here, no more memory to store further entries *)

[0122] CONSTANT

[0123] TREE_ON_ANOTHER_CPU: INTEGER:=2;

[0124] (* this part of the tree resides on another CPU *)

[0125] PROCEDURE Init ( )

[0126] (* first initialize the AddrParts which holds the information needed to determine which bits of the full address have to be masked out when looking at a member of the partition and how many down-shifts are needed to align first bit of the part masked right *)

[0127] (* returns the requested part of the address shifted down so it can be used for an index *)

[0128] (* This function basically computes λ(Part) *)

[0129] (* writes all entries in the level of the trie starting from index BitsGiven up to BitsGivenLen bits in the Node *)

[0130] (* Insert a Prefix into Tree *)

[0131] (* generate a new entry, Populate all ‘descendants’ in this level, even if a longer prefix for this particular one already exists. Consider prfx decision

[0132] and inserting 00/2 with decision 2 causes

[0133] Forwarding Decision Module Pseudo-Code

[0134] (* Longest Prefix Match for a 32 bit IPv4 Address *)

[0135] (* abort here meaningfully based on the semantics of the decision *)

[0136] In another embodiment of the invention, module 50 performs maintenance of a routing table utilizing a separate “m-structure” coinciding with a “p-structure.” As discussed previously, conventional maintenance techniques cannot update a routing table without preventing the forwarding device from utilizing the routing table. This is because conventional techniques read-lock those routing table entries that are currently being updated. This means that if a packet destination address requires the lookup of a routing table entry that is currently being updated, the packet will have to wait until the updating process is finished before being forwarded, or in the worst case scenario, be dropped from the network entirely.

[0137] This embodiment of the present invention overcomes the limitations of conventional maintenance techniques by maintaining separate maintenance structures (“m-structures”) that conform to each p-structure for a routing table. The use of m-structures saves fast memory. Module 50 splits the m-structures and p-structures across two different types of memory. The insertion and deletion of prefixes are performed for each m-structure held in inexpensive memory as required by the network. On each access to the m-structure in inexpensive memory, a write-through into fast memory holding the p-structure tree is performed to keep both trees consistent. The write-through is accomplished using a dedicated or shared CPU/memory bus, and is therefore performed at a very high speed. Thus instead of locking out individual entries to the routing table as they are being updated as with conventional routing table maintenance techniques, this embodiment of the invention updates the routing table simultaneously, without locking the individual entities. This decreases the total update time interval, as well as minimizes the risk that a particular entry will be in the process of being updated when needed for routing a packet.

[0138] Thus, this embodiment of the present invention comprises a method and apparatus for updating a routing table comprised of p-structures utilized by a forwarding device. A maintenance routing table is built, the maintenance routing table having a m-structure corresponding to each p-structure for the routing table used by the forwarding device. An instruction is received to update the maintenance routing table by performing one of a group comprising adding, deleting and modifying a prefix. The maintenance routing table is then updated in accordance with said instruction, and replicated to the routing table used by the forwarding device.

[0139] The maintenance routing table is replicated to the forwarding device in several different manners. The maintenance routing table could be replicated to the forwarding device at predetermined intervals, such as once a day at a certain hour. Alternatively, the maintenance routing table could be replicated to the forwarding device whenever the maintenance routing table is updated. Finally, the maintenance routing table could be replicated to the forwarding device upon an actual request by the forwarding device.

[0140] In yet another embodiment of the invention, part of the routing table is used to build a p-structure tree in fast memory, making this approach similar to a cache. This would be appropriate for devices which do not implement enough fast memory to hold an entire p-structure tree. The decision points at which the tree is ‘chopped off’ are indicated using a special holding value, which is demonstrated in the pseudo-code definition using the constant named TREE_ENDED.

[0141] In a further embodiment of the invention, the performance of module 48 could be improved through the utilization of multiple processors. A value is stored in the decision field indicating that a part of the tree resides on another processor, operating in parallel. A p-structure tree is then split across multiple entities that execute the lookup algorithm performed by module 48, without any synchronization. The tree is divided across the processors and the division points marked with a constant such as the proposed TREE_ON_ANOTHER_CPU one. If partitioning of the tree occurs at the first member of address partition, each processor executes only one step of the lookup loop before realizing that another entity is holding the necessary information. Thus, the throughput of module 48 can be accelerated by utilizing the number of available processors, without incurring any overhead for synchronization.

[0142] FIG. 10 illustrates a block diagram of a conventional router suitable for practicing another embodiment of the invention. Referring to FIG. 3, a router 300 includes a router engine 302 having a CPU 304, a memory device 306, and a forwarding decision module 318. Router engine 302 is coupled to various routing tables 308 and databases 310 capable of storing information necessary for router 300 to properly forward packets toward their destination. Databases 310 may include a Link State Database, a Path Database, a Tent Database, and a Forwarding Database. An interface 312 is coupled to router engine 302 and provides the physical connection to a network 18.

[0143] Although a single interface is shown in router 300, routers typically utilize multiple interfaces and a switching fabric to direct packets along the appropriate network link to reach its destination. A single interface is shown with router 300 to simplify router 300 for explanation purposes only. It can be appreciated that router design is well-known in the art, and that any router design implementing the functionality of the embodiments of the present invention falls within the scope of the invention.

[0144] Forwarding decision module 318 is used to perform longest address match lookups in routing tables 308. Forwarding decision module 318 performs similarly to forwarding decision module 48. Routing tables 308 are constructed and maintained utilizing the p-structure principles described for the various embodiments of the invention described above. In this embodiment of the invention, routing tables 308 are constructed and maintained by a routing table constructing module (not shown) that performs substantially as routing table constructing module 50. Further, this routing table constructing module can be either located locally with router 300, or remotely from router 300. In this embodiment of the invention, the routing table constructing module is located at a central server governed by an Internet Service Provider (ISP). The server version of the routing table constructing module is used to construct and maintain routing tables 308 for router 300. In addition, the server version can be used to construct and maintain routing tables for any number of routers connected by network links to the ISP server. This embodiment of the invention would reduce hardware and software costs associated with each individual router or forwarding device, and facilitate routing table populating and de-populating by sending address and route updates to a central ISP server.

[0145] Although various embodiments of the invention are specifically illustrated and described herein, it will be appreciated that modifications and variations of the present invention are covered by the above teachings and within the purview of the appended claims without departing from the spirit and intended scope of the claims. For example, although the implementation of the above-described p-structure principles is described in terms of software and specific program code segments, the various embodiments of the invention could also be implemented in hardware and still fall within the scope of the invention. In another example, although the various embodiments of the invention could be implemented by a general purpose computer, such as described with reference to FIG. 3, it can be appreciated that these embodiments could be implemented as part of a dedicated device, such as described with reference to FIG. 10, and still fall within the scope of the invention.