Abstract:
The routing address lookup problem is one of the major bottlenecks in high performance routers and deals with forwarding of packets. In the Internet domain it is known as “IP address lookup problem.” This invention provides a new and easy way to preprocess routing tables which gives efficient packet/message forwarding and is feasible in the time and the space it consumes. More precisely, the method for m-bit IP addresses gives a balanced trade-off between performing a binary search on T with O(log|T|) accesses, where |T| is the number of entries in T, and executing a single access on a table of 2 m  entries obtained by fully expanding T. While the prior art starts out from space-efficient data structures and aim at lowering the O(log|T|) access cost, the invention starts out from the expanded table with 2 m  entries and aim at compressing it without an excessive increase in the number of accesses. The embodiment results in a lookup which takes exactly three memory accesses in tables which occupy O(2 m/2 +|T| 2 ) space in the worst case. Since the Internet is more structured real routing tables for IP with m=32 bits, should take even much smaller space. For most routers the cache is sufficient to include our tables whereas dedicated routers need only a few megabytes cache for large tables. The impact of fast lookup is increased network bandwidth.

Description:
FIELD OF THE INVENTION 
     The invention relates to routing in networks, more particularly to a method and apparatus for facilitating fast routing at a network node. The routing (forwarding) stage it deals with is called “address lookup in routing (forwarding) tables.” Given information designating which destination address has to be forwarded to which output port at a node, the stage organizes the information such that the on line search for this information (when a message/packet arrives at the node) is efficient in time and space consumed. The invention concerns with setting, performing and maintaining this stage. The invention is suitable (and is tuned to) the prevalent setting of Internet routing where addresses are called IP addresses. The invention is related to fast methods for solving the above problem within a standard processor architecture and with a small number of memory accesses. Due to fast routing, the invention is related to the issue of increased network bandwidth. 
     BACKGROUND OF THE INVENTION 
     Computer networks are expected to exhibit very high performance in delivering data because of the explosive growth of Internet nodes (from 100,000 hosts in 1989 to over 60 millions as of 1999). The network bandwidth, which measures the number of bits that can be transmitted in a certain period of time, is thus continuously improved by adding new links and/or by improving the performance of the existing ones. 
     Routers are at the heart of the networks in that they forward packets from input interfaces to output interfaces on the ground of the packets&#39; destination Internet address, which we simply call IP address. They choose which output interface corresponds to a given packet by performing an IP address lookup at their routing table. As routers have to deal with an ever increasing number of links whose performance constantly improves, the address lookup is now becoming one of the major bottlenecks in high performance forwarding engines. 
     The IP address lookup problem was just considered a simple table lookup problem at the beginning of Internet. Now, it is unconceivable to store all existing IP addresses explicitly because, in this case, routing tables would contain millions of entries. In the early 1990s people realized that the amount of routing information would grow enormously, and introduced a simple use of prefixes to reduce space (see Fuller, V., Li, T., Yu, J., and Varadhan, K. “Classless inter-domain routing (CIDR): an address assignment and aggregation strategy” RFC 1519, 1993,). Specifically, IP protocols use hierarchical addressing, so that a network contains several subnets which in turn contain several host computers. Suppose that all subnets of the network with IP address 128.96.*.* have the same routing information apart from the subnet whose IP address is 128.96.34.*. We can succinctly describe this situation by just two entries (128.96 and 128.96.34) instead of many entries for all possible IP addresses of the network. However, the use of prefixes introduces a new dimension in the IP address lookup problem: For each packet, more than one table entry can match the packet&#39;s IP address. In this case, the applied rule consists of choosing the longest prefix match, where each prefix is a binary string that has a variable length from 8 to 32 in IPv4 (see Postel, J. “Internet protocol”, RFC 791, 1981,). For example, let us consider Table 1 where ε denotes the empty sequence corresponding to the default output interface, and assume that the IP address of the packet to be forwarded is 159.213.37.2, that is, 10011111 11010101 00100101 00000010 in binary. Then, the longest prefix match is obtained with the fourth entry of the table and the packet is forwarded to output interface D. Instead, a packet whose IP address is 159.213.65.15, that is, 10011111 11010101 01000001 00001111 is forwarded to output interface C. 
     Looking for the longest matching prefix in IP routing tables represents a challenging problem since lookups must be answered very quickly. In order to get a bandwidth of, say, 10 gigabits per second with an average packet length equal to 2,000, a router should forward 5 millions of packets per second. It means that each forwarding has to be performed in approximately 200 nanoseconds and, consequently, each lookup must be realized much faster. 
     DESCRIPTION OF RELATED ART 
     Several approaches have been proposed in the last few years in order to solve the IP address lookup problem. Hardware solutions, though very efficient, are expensive and some of them may become outdated quite quickly (See U.S. patent application Ser. No. 034,444, 1995 by McAuley, A., Tsuchiya, P., and Wilson, D. “Fast multilevel hierarchical routing table using content-addressable memory” as well as Newman, P., Minshall, G., Lyon, T., and Huston, L. “IP switching and gigabit routers” in IEEE Communications Magazine (January 1997)). Modern routers will use software or hardware and software combination. Next we will review the known software solutions. 
     A traditional implementation of routing tables (see Stevens, W., and Wright, C. “TCP/IP Illustrated, Volume 2 The Implementation” Addison-Wesley Publishing Company, Reading, Mass., 1995) use a version of Patricia tries, a very well-known data structure (Morrison, D. “PATRICIA—Practical Algorithm To Retrieve Information Coded In Alfanumeric” in Journal of ACM 15,4 (October 1968), 514-534). In this case, it is possible to show that, for tables with n elements, the average number of examined bits is 1.44 log n (log n is logarithm to the base 2 of the number n). Thus, for n=32000, this value is bigger than 21. When compared to millions of address lookup requests served in one second, 21 table accesses are too many. Another variation of Patricia tries has been proposed in order to examine k bit each time (in Pei, T.-B. and Zukowski, C. “Putting routing tables into silicon” in IEEE Network, 1992, pages 42-50). However, this variation deals with either the exact matching problem or with the longest prefix matching problem restricted to prefixes whose lengths are multiples of k. 
     A more recent approach (by Nilsson, S., and Karlsson, G. “Fast address look-up for internet routers” in ALEX (February 1998), Università di Trento, pp. 9-18) was inspired by the three-level data structure of Degermark, M. at al. (“Small forwarding tables for fast routing lookups”, in ACM Computer Communication Review 27, 4 (October 1997), 3-14). which uses a scheme to compress multi-bit trie nodes using a bitmap, and is based on the compression of the routing tables by means of level compressed tries, which are a powerful and space efficient representation of binary tries. This approach seems to be very efficient from a memory size point of view but it requires many bit operations which, on the current technology, are time consuming. 
     Another approach is based on binary search on hash tables organized by prefix lengths (in Waldvogel, M. et al. “Scalable high speed IP routing lookups”, in ACM Computer Communication Review 27, 4 (October 1997), 25-36). This technique is more memory consuming than the previous one but, according to the experimental evaluation presented by the authors, it seems to be very efficient from the time point of view. 
     A completely different way of using binary search is described in Lampson at al. (in “IP lookups using multi-way and multicolumn search” ACM INFOCOM Conference, (April 1998)). It is based on multi-way search on the number of possible prefixes rather than the number of possible prefix lengths and exploits the locality inherent in processor caches. 
     The most recent software solution to the IP address lookup problem is the one based on controlled prefix expansion (by Srinivasan, V., and Varghese, G. in “Fast address lookups using controlled prefix expansion” in ACM SIGMETRICS Conference (September 1998) and available full version to appear in ACM TOCS). This approach, together with optimization techniques such as dynamic programming, can be used to improve the speed of most IP lookup algorithms. When applied to trie search, it results into a range of algorithms whose performance can be tuned and that, according to the authors, provide faster search and faster insert/delete times than earlier lookup algorithms. 
     SUMMARY AND OBJECTIVES OF THE INVENTION 
     Any solution for m-bit IP addresses in a routing table T can be seen as a trade-off between performing a binary search on T with O(log|T|) accesses (where |T| is the number of prefixes in T) and executing a single access on a table of 2 m  entries obtained by fully expanding T. The above two methods are simple and available in the art. The results described in the prior art give space-efficient data structures and aim at lowering the O(log|T|) bound on the number of accesses which may be too slow for the increasing pace of messages sent via a typical router. The invention, instead, starts out from the fully expanded table with 2 m  entries and aim at compressing it without an excessive increase in the (constant) number of accesses. For this reason, we call it an expansion/compression method. 
     We exploit the fact that the relation between the 2 32  IP addresses and the very few output interfaces of a router is highly redundant for m=32. By expressing this relation by means of strings (thus expanding the original routing table), these strings can be compressed (using the run-length encoding scheme) in order to provide an implicit representation of the expanded routing table which is memory efficient. More important, this representation allows us to perform an address lookup in exactly three memory accesses and three clock cycles independently of the IP address. Intuitively, the first two accesses depend on the first and second half of the IP address, respectively, and provide an indirect access to a table whose elements specify the output interfaces corresponding to groups of IP addresses (see FIG.  1 ). 
     The invention gives a general paradigm which is a method for organizing a routing table for forwarding of network messages. It essentially works by associating each possible address with an address&#39;s first portion according to some sorting. Then the method employs compacting of this representation according to a first portion (prefix) into a first index set. Then it creates a unified compressed representation of a second portion of an address (suffix) and it uses this unified representation to designate at least another index set. Using the index sets the method creates a table indexed by the sets, where the table contains the output port/interface (next hop) entries corresponding to their respective addresses. 
     One of the strengths and novelties of the invention is that it completely avoids any special machinery for the longest prefix match described in the prior art. It transforms any IP prefix lookup into an indirect and standard access to a space-efficient array of memory locations. Consequently, its dominant cost is really given by the number of memory accesses with no hidden cost due to the processor architecture, such as branch prediction and other architectural features known to those skilled in the art. 
     The invention proposed here works for all routers belonging to the Internet and will be useful for a long period of time as the Internet grows. Moreover, its dominant cost is really given by the small number of memory accesses and it can be easily implemented in hardware where the hardware technology may vary and where tables can be written in hardware registers/tables. 
     We note that even though the theoretical upper bound on the worst-case memory size is O(2 m/2 +|T| 2 ), in fact theory is quite far from practice and that the characteristics of the routing tables will vary much slower than the rate at which cache memory size will increase. Also, sometimes only certain addresses are allowed to be routed within a sub-network. In this case the method can be adapted to deal with partial addresses and the expansion is limited. 
     The invention can be used to maintain routing tables in a fashion which is adaptive to the changing traffic pattern. In this sense the invention can also be viewed as a maintenance procedure. 
     It is the intent to combine the address finding disclosed in the invention with any routing or sub-routing mechanism that forwards information within networks or inside network elements (like routing stages in a complex switch). The methodology of actual forwarding/routing (after the forwarding goal is determined) can vary as well and can be based on combining time division or wave division multiplexing, using dedicated hardware and optics, and so on. The one familiar with the art is aware of the ways to combine quick addressing with various forwarding and routing routines. The description as an IP addressing is merely demonstrative and is not restrictive. 
     Based on the method disclosed, an apparatus can be devised (in hardware, software program or combination thereof) which is part of a router which is a computer performing the task of a network node. The node contains memory, cache memory and processing elements. The apparatus comprising means which are able to perform the various parts and stages as part of a router&#39;s function facilitating message forwarding and network routing. 
     It is the objective of this invention to achieve an adaptive mechanism to organize the IP lookup table (for message forwarding according to IP address). 
     It is further an objective of the invention to allow routing and forwarding mechanism that only looks at the IP address table a constant number of times (3 times). This results in a new mechanism for lookup, which is much faster and which implies increased speed of the routing mechanism and increased network bandwidth. 
     It is an objective of the invention to have a mechanism which is simple and runs on standard processors with no special computing power. To achieve the method&#39;s basic paradigms and operational stages new mechanisms are disclosed inhere. 
    
    
     DESCRIPTION OF THE DRAWING 
     FIG. 1 is a schematic representation of the overall IP address lookup data structures. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     We describe our embodiment of the invention solving the IP address lookup problem in terms of m-bit addresses. 
     The embodiment consists of two parts: 
     1. The preprocessing part, preparing the lookup tables. 
     2. The message/packet forwarding part, where given the destination, the tables are used to determine the output port/next hop of that message/packet. 
     The preprocessing part runs in two phases, expansion and compression. 
     1. In the expansion phase, we implicitly derive the output interfaces for all the 2 m  possible addresses. 
     2. In the compression phase, we fix a value 1≦k≦m and find two statistical parameters α k  and β k  related to some combinatorial properties of the items in the routing table at hand. These two parameters characterize the space occupancy of the embodiment. 
     When our tables fit into an L2 cache, the method is extremely fast and a 1 megabyte such cache will suffice for most of backbone and enterprise routers. For dedicated routers, it is expected to have a few megabytes dedicated cache memory for the tables and dedicated hardware which can easily implement our tables and lookups. 
     Preliminaries and Notations 
     We need precise notation describing strings of bits, which are common in the literature. Given the binary alphabet Σ={0, 1}, we denote the set of all binary strings of length k by Σ k . We indicate the length of a string x by |x|. Given two strings α and β, we say that α is a prefix of β (of length |α|) if |α|≦|β| and the first |α| bits of β are equal to those in α (e.g., 101110 is a prefix of 1011101101110). Moreover, we denote by α·β the concatenation of α and β, that is, the string whose first |α| bits are equal to α and whose last |β| bits are equal to β (e.g., the concatenation of 101110 and 1101110 is 1011101101110). Finally, given a string α and a string set S, we define α·S={x|x=α·β with βεS} as the concatenation of α and each string β in S. 
     A routing table T relative to m-bit addresses is a sequence of pairs (p, h) where the route p is a string with |p|≦m and the next hop h is an integer in [1 . . . H], with H denoting the number of next hops. In the following we will denote by |T| the size of T, that is, the number of pairs in the sequence. Moreover, we will assume that T always contains the pair (ε, h ε ) where ε denotes the empty string and h ε  corresponds to the default next hop. 
     The IP address lookup problem can now be stated as follows. Given a routing table T and xεΣ m , compute the next hop h x  corresponding to address x. We have to uniquely identify a pair (p x , h x ) for which p x  is the longest prefix of x appearing in T. That is, 
     (a) p x  is a prefix of x, and there exists h x  such that (p x , h x )εT; 
     (b) |p x |&gt;|p| for any other pair (p, h)εT, such that p is a prefix of x. 
     Conditions (a)-(b) are well defined since T contains the default pair (ε, h ε ) and so h x  always exists. 
     The Embodiment: Expansion Phase 
     We now describe the preprocessing part of the invention formally. The first step intuitively extends the routes of T that are shorter than m in all possible ways by preserving the information regarding their corresponding next-hop interfaces. We say that T is in decreasing (respectively, increasing) order if the routes in its pairs are lexicographically sorted in that order (lexicographic sorting is known in the art). 
     Computing Step 1 
     We take T in decreasing order and number its pairs according to their ranks, obtaining a sequence of pairs T 1 , T 2 , . . . , T |T|  such that T i  precedes T j  if and only if i&lt;j. As a result, if p j  is a prefix of p i  then T i  precedes T j . We use this property to suitably expand the pairs. 
     Computing Step 2 
     With each pair T i =(p i , h i ) we associate its expansion set, denoted EXP(T i ), to collect all m-bit strings that have p i  as a prefix. Formally, EXP(T i )=(p i ·Σ m−|p   i| )×{h i }, for 1≦i≦|T|. (Using portions other than the prefix is possible and understood to those skilled in the art). 
     Computing Step 3 
     We then define the expansion of T on m bits, denoted T′, as the union T′=∪ i=1   |T| T′ i  where the sets T′ i  are inductively defined and computed as follows: T′ 1 =EXP(T 1 ), and T′ i =EXP(T i )⊖∪ 1≦j&lt;i T′ j , where the operator ⊖ removes from EXP(T i ) all pairs whose routes already appear in the pairs of ∪ 1≦j&lt;i T′ j . 
     In this way, we fill the entries of the expanded table T′ consistently with the pairs in the routing table T, as stated by the following fact. 
     Fact 1 
     If (p x , h x )εT is the result of the IP address lookup for any m-bit string x, then (x, h x )εT′. 
     Since we took all expansions T′ is made up of 2 m  pairs and that, if we had enough space, we could solve the IP address lookup problem with a single access to T′. We therefore need to compress T′ somehow. 
     The Embodiment: Compression Phase 
     This phase heavily relies on a parameter k to be fixed later on, where 1≦k≦m. We are given the expanded table T′ and wish to build three tables row, col and next_hop to represent the same information as T′ in less space by a simple run length encoding (RLE) scheme (see Nelson, M., The Data Compression Book, M&amp;T Books, San Mateo, Calif., 1992). We note that other encoding schemes may be possible and are within the scope of the current invention. 
     Computing Step 4 
     We begin by clustering the pairs in T′ according to the first k bits of their strings. The cluster corresponding to a string xεΣ k  is T′ (x) ={(y, h xy )|yεΣ m−k  and (x·y, h xy )εT′}. 
     Note that |T′ (x) |=2 m−k . We can define our first statistical parameter to denote the number of distinct clusters. 
     Definition 2 
     Given a routing table T with m-bit addresses, the row k-size of T for 1≦k≦m is 
     
       
         α k   =|{T′   (x)   |xεΣ   k }|. 
       
     
     Parameter α k  is the first measure of a simple form of compression. Although we expand the prefixes shorter than k, we do not increase the number of distinct clusters as the following fact shows. 
     Fact 3 
     For a routing table T, let r k  be the number of distinct next-hop interfaces in all the pairs with routes of length at most k, and let n k  be the number of pairs whose routes are longer than k, where 1≦k≦m. We have α k ≦r k +n k ≦|T|. 
     Computing Step 5 
     We now describe the compression based upon the RLE scheme. It takes a cluster T′ (x)  and returns an RLE sequence s (x)  in two logical steps: 
     1. Sort T′ (x)  in ascending order (so that the strings are lexicographically sorted) and number its pairs according to their ranks, obtaining T′ (x) ={(y i , h i )} 1≦i≦2     m−k   . 
     2. Transform T′ (x)  into s (x)  by replacing each maximal run (y i , h i ), (y i+1 , h i+1 ), . . . , (y j , h i+l ), such that h i =h i+1 = . . . =h i+l , by a pair &lt;h i , l+1&gt;, where l+1 is called the run length of h i . 
     The previous steps encode the 2 m−k  pairs of strings and interfaces of each cluster T′ (x)  into a single and (usually) shorter sequence s (x) . Note that, by Definition 2, α k  is the number of distinct RLE sequences s (x)  so produced. 
     Computing Step 6 
     We further process them to obtain an equal number of equivalent RLE sequences s′ (x) . The main goal of this step is to obtain sequences such that, for any i, the i-th pair of any two such sequences have the same run length value. 
     We show how to do it by means of an auxiliary function φ(s, t) defined on two nonempty RLE sequences s=&lt;a, f&gt;·s 1  and t=&lt;b, g&gt;·t 1  as follows:          ϕ        (     s   ,   t     )       =     {         t             if                   s   1       =       t   1     =   ε       ,                 〈     b   ,   f     〉     ·     ϕ        (       s   1     ,     t   1       )                   if                 f     =     g                 and                   s   1         ,       t   1     ≠   ε     ,                 〈     b   ,   f     〉     ·     ϕ        (       s   1     ,       〈     b   ,     g   -   f       〉     ·     t   1         )                   if                 f     &lt;     g                 and                   s   1         ,       t   1     ≠   ε     ,                 〈     b   ,   g     〉     ·     ϕ        (         〈     a   ,     f   -   g       〉     ·     s   1       ,     t   1       )                   if                 f     &gt;     g                 and                   s   1         ,       t   1     ≠     ε   .                                        
     The purpose of φ is to “unify” the run lengths of two RLE sequences by splitting some pairs &lt;b, f&gt; into &lt;b, f 1 &gt;, . . . , &lt;b, f r &gt;, such that f=f 1 + . . . +f r . The unification defined by is φ a variant of standard merge, except that it is not commutative as it only returns the (split) pairs in the second RLE sequence. 
     In order to apply unification to a set of RLE sequences s 1 , s 2 , . . . , s q , we define function Φ(s 1 , . . . , s q ) that returns RLE sequences s′ 1 , s′ 2 , . . . , s′ q  as follows. First, 
     
       
           s′   q =φ(φ( . . . φ(φ(φ( s   1   , s   2 ), s   3 ), s   4 ) . . . , s   q−1 ), s   q ). 
       
     
     As a result of this step, we obtain that the run lengths in s′ q  are those common to all the input sequences. Then, s′ i =φ(s′ q , s i ) for i&lt;q: in this way, the pairs of the set of RLE sequences s 1 , s 2 , . . . , s q  are equally split. 
     This finishes the computation. 
     We are now ready to define the second statistical parameter. Given an RLE sequence s, let its length |s| be the number of pairs in it. Regarding the routing table T, let us take the α k  RLE sequences s 1 , s 2 , . . . , s α     k    obtained by the distinct clusters T′ (x)  with xεΣ k , and apply the unification Φ (s 1 , s 2 , . . . , s α     k   ) defined above. 
     Definition 4 
     Given a routing table T with m-bit addresses, the column k-size β k  of T, for 1≦k≦m, is the (equal) length of the RLE sequences resulting from Φ(S 1 , s 2 , . . . , s α     k   ). That is, 
     
       
         β k   =|s′   α     k   |. 
       
     
     Although we increase the length of the original RLE sequences, we have that β k  is still linear in |T|. 
     Fact 5 
     For 1≦k≦m, β k ≦2|T|−α k . 
     Putting the Phases Together and the Packet Processing 
     The embodiment achieves a compact representation which is easy to search as we will show now. It stores a routing table T in a sufficiently compact way to guarantee always a constant number of accesses. 
     Here is a summary of the main computational steps for building T: 
     1. Find the α k  distinct clusters without their explicit construction. 
     2. Produce the RLE sequences corresponding to the distinct clusters. 
     3. Unify the RLE sequences by applying Φ and number the resulting sequences, all of length β k , from 1 to α k . 
     4. Store the next hops of the r-th LRE sequence in row r of table next_hop, which hence has  αk  rows and β k  columns. 
     5. Set row[x[1 . . . k]]=r for each string x such that cluster T′ (x[1 . . . k])  has been encoded by the r-th RLE sequence. 
     6. Let f 1 , . . . , f β     k    be the run lengths in any LRE sequence, and let sum(c)=Σ i=1   c f i  denote the sum of the first c run lengths (where sum(0)=0). Set col[x[k+1 . . . m]]=c for each string x, such that x[k+1 . . . m] encodes an integer q with sum(c−1)≦q&lt;sum(c). 
     The time complexity of the above procedure is bounded by O(2 k +2 m−k +|T| 2 ) because we use simple sorting, merging and scanning. We let #bytes(n) denote the number of bytes necessary to store an integer n, and a word be sufficiently large to contain the involved integers. We achieve the following: 
     Result 6 
     Given a routing table T with m-bit addresses and H next-hop interfaces, we can store T into three tables row, col and next_hop of total size 
     
       
         2 k ·#bytes(α k )+2 m−k ·#bytes(β k )+α k ·β k ·#bytes( H ) 
       
     
     in O(2 k +2 m−k +|T| 2 ) worst-case time, for 1≦k≦m, so that an IP address lookup for a string x of m bits takes exactly three accesses given by the following calculation per message/packet (which is three table accesses): 
     
       
           h   x =next_hop[row[ x [1  . . . k ]], col[ x[k +1  . . . m]]]   
       
     
     where x[ . . . j] denotes the substring of x starting from the i-th bit and ending at the j-th bit. 
     We wish to point out that the result represents a reasonable trade-off between performing a binary search on T with O(log|T|) accesses and executing a single access on a table of 2 m  entries obtained by T. 
     Note that once the next hop is determined the router places the message on the output port corresponding to the next hop. 
     Implementing the method as a software program or as a hardware device combined with software program at a hosting computer are known to those who are skilled in the art. In fact, numerous implementations in software, hardware, firmware and combination thereof, are possible which represent applications of the principles and paradigms of the present invention. All variation on the treatment and processing of message destination addresses prior, during and after the lookup stage are possible and the embodiment is merely one example of address processing. Further, combining the invention with alternate routing mechanisms and devices can readily be devised by those who are skilled in the art without departing from the scope of the present invention. 
     A Demonstrative Example 
     Next we describe a small example of the application of our invention to a routing table. This illustrates the applicability of the suggested approach to a destination domain made out of binary strings and output interfaces (next hops) domain named by single letters. This and its generalizations to other domains are apparent to those skilled in the art. As our example, let us consider the routing table T shown in Table 2 where m=4 and H=3. 
     The first step of the expansion phase consists of sorting T in decreasing order. The result of this step is shown in Table 3. This table is now expanded as shown in Table 4: the third column of this table shows the corresponding sub-tables T′ i  according to the definition of the expanded table T′. 
     Let us now enter the compression phase: to this aim, we choose k=2. We then have the following four clusters and the corresponding RLE sequences (shown between square brackets): 
     
       
           T′   (00) ={(00 ,A ),(01 ,A ),(10 ,C ),(11 ,B )} [ s   1   =&lt;A, 2 ×&lt;C, 1 &gt;&lt;B, 1&gt;] 
       
     
     
       
           T′   (01) ={(00 ,C ),(01 ,C ),(10 ,C ),(11 ,C )} [ s   2   =&lt;C, 4&gt;] 
       
     
     
       
           T′   (10) ={(00 ,B ),(01 ,B ),(10 ,B ),(11 ,B )} [ s   3   =&lt;B, 4&gt;] 
       
     
     
       
           T′   (11) ={(00 ,C ),(01 ,C ),(10 ,C ),(11 ,C )} [ s   4   =s   2 ] 
       
     
     In this case α k =3 (since T′ (01) =T′ (11) , r k =3 and n k =2. We now unify the RLE sequences by applying function φ. In particular, we have that 
     
       
           s′   3 =φ(φ( s   1   ,s   2 ), s   3 )=φ(&lt; C, 2 &gt;&lt;C, 1 &gt;&lt;C, 1 &gt;,s   3 )=&lt; B, 2 &gt;&lt;B, 1 &gt;&lt;B, 1&gt; 
       
     
     and 
     
       
           s′   2 =φ( s′   3   ,s   2 )=&lt; C, 2&gt;&lt; C, 1&gt;&lt; C, 1&gt; 
       
     
     
       
           s′   1 =φ( s′   3   ,s   1 )=&lt; A, 2&gt;&lt; C, 1&gt;&lt; B, 1&gt;= s   1 . 
       
     
     Clearly, β k =3. Thus, #bytes(α k )=#bytes(β k )=#bytes(H)=1 so that the memory occupancy is equal to 4+4+9=17 bytes (observe that the original table T occupies 6+6=12 bytes). In summary, the overall data structures is shown in FIG.  1 . 
     Parameter Choice Tuning 
     We can observe the network traffic and investigate how the choice of the parameters above (say k) is affecting the actual performance based on destination statistics. This information can be used in recomputing the table adaptively. 
     Repeated Application of the Method 
     As the network changes, routing information changes since new network nodes are added or old one are eliminated. There are known method to collect the topology and determine routing information per destination. As the routing table information gets renewed, the methods here may be extended to work on-line. First, if the number of changes is small (one or two addition, for example), the IP lookup can first identify whether a package belongs to this set of newly added/deleted addresses and act accordingly: follow the new rule for the added nodes otherwise consult the prepared lookup tables. In case there are many changes, the above tables computed by the expansion compression phases has to be repeated. 
     It is possible that the method we disclose will be used only partially in a node and for certain destinations, a separate table or other data structure will be maintained, especially for frequent destinations whose next hop information can be made available, say to a parallel process. Such variations and combination of use are familiar to the skilled in the art and do not depart from the basic invention. 
     Preprocessing Packets 
     The destination addresses on packets and messages may be shifted, masked, encrypted or hashed. In each case a possible preprocessing of the address is needed to first move the packet into the representation according to which the routing tables were defined. The pre-processing may involve adjusting the destination tag, since some routing methods apply such swapping as part of the routing between different parts of the network. 
     REFERENCES 
     [1] USA PATENTS: 
     [2] McAuley, A., Tsuchiya, P., and Wilson, D. Fast multilevel hierarchical routing table using content-addressable memory. U.S. patent application Ser. No. 034,444, 1995. 
     [3] OTHER PUBLICATIONS: 
     [4] Deering, S., and Hinden, R. Internet protocol, version 6 (IPv6). RFC 1883, (http://www.merit.edu/internet/documents/rfc/rfc1883.txt) 1995. 
     [5] Degermark, M., Brodnik, A., Carlsson, S., and Pink, S. Small forwarding tables for fast routing lookups.  ACM Computer Communication Review  27, 4 (October 1997), 3-14. 
     [6] Fuller, V., Li, T., Yu, J., and Varadhan, K. Classless inter-domain routing (CIDR): an address assignment and aggregation strategy. RFC 1519 (http://www.merit.edu/internet/documents/rfc/rfc1519.txt), 1993. 
     [7] Lampson, B., Srinivasan, V., and Varghese, G. IP lookups using multiway and multicolumn search. In  ACM INFOCOM Conference  (April 1998). 
     [8] Morrison, D. Patricia—Practical Algorithm To Retrieve Information Coded In Alfanumeric.  Journal of ACM  15, 4 (October 1968), 514-534. 
     [9] Nelson, M.  The Data Compression Book . M&amp;T Books, San Mateo, Calif. 1992. 
     [10] Newman, P., Minshall, G., Lyon, T., and Huston, L. IP switching and gigabit routers.  IEEE Communications Magazine  (January 1997). 
     [11] Nilsson, S., and Karlsson, G. Fast address look-up for internet routers. In ALEX (February 1998), Università di Trento, pp. 9-18. 
     [12] Pei, T.-B., and Zukowski, C. Putting routing tables into silicon.  IEEE Network  (January 1992), 42-50. 
     [13] Postal, J. Internet protocol. RFC 791, (http://www.merit.edu/internet/documents/rfc/rfc0791.txt) 1981. 
     [14] Srinivasan, V., and Varghese, G. Fast address lookups using controlled prefix expansion. In  ACM SIGMETRICS Conference  (September 1998). Available full version to appear in ACM TOCS. 
     [15] Stevens, W., and Wright, G. TCP/IP  Illustrated, Volume  2  The Implementation . Addison-Wesley Publishing Company, Reading, Mass., 1995. 
     [16] Waldvogel, M., Varghese, G., Turner, J., and Plattner, B. Scalable high speed IP routing lookups.  ACM Computer Communication Review  27, 4 (October 1997), 25-36. 
     
       
         
               
             
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 An example of routing table 
               
             
          
           
               
                   
                 Prefix 
                 Output interface 
               
               
                   
                   
               
               
                   
                 ε 
                 A 
               
               
                   
                 10011111 
                 B 
               
               
                   
                 10011111 11010101 
                 C 
               
               
                   
                 10011111 11010101 00 
                 D 
               
               
                   
                 10011111 11110 
                 E 
               
               
                   
                   
               
             
          
         
       
     
     
       
         
               
             
               
               
               
             
           
               
                 TABLE 2 
               
             
             
               
                   
               
               
                 An example of routing table T 
               
             
          
           
               
                   
                 Route 
                 Next-hop 
               
               
                   
                   
               
               
                   
                 ε 
                 A 
               
               
                   
                 10 
                 B 
               
               
                   
                 001 
                 B 
               
               
                   
                 01 
                 C 
               
               
                   
                 0010 
                 C 
               
               
                   
                 00 
                 A 
               
               
                   
                   
               
             
          
         
       
     
     
       
         
               
             
               
               
               
             
           
               
                 TABLE 3 
               
             
             
               
                   
               
               
                 The sorted routing table T 
               
             
          
           
               
                   
                 Route 
                 Next-hop 
               
               
                   
                   
               
               
                   
                 10 
                 B 
               
               
                   
                 01 
                 C 
               
               
                   
                 0010 
                 C 
               
               
                   
                 001 
                 B 
               
               
                   
                 00 
                 A 
               
               
                   
                 ε 
                 C 
               
               
                   
                   
               
             
          
         
       
     
     
       
         
               
             
               
               
               
             
           
               
                 TABLE 4 
               
             
             
               
                   
               
               
                 The expanded routing table T′ 
               
             
          
           
               
                 Route 
                 Next-hop 
               
               
                   
               
               
                 1000 
                 B 
                 T′ 1   
               
               
                 1001 
                 B 
               
               
                 1010 
                 B 
               
               
                 1011 
                 B 
               
               
                 0100 
                 C 
                 T′ 2   
               
               
                 0101 
                 C 
               
               
                 0110 
                 C 
               
               
                 0111 
                 C 
               
               
                 0010 
                 C 
                 T′ 3   
               
               
                 0011 
                 B 
                 T′ 4   
               
               
                 0000 
                 A 
                 T′ 5   
               
               
                 0001 
                 A 
               
               
                 1100 
                 C 
                 T′ 6   
               
               
                 1101 
                 C 
               
               
                 1110 
                 C 
               
               
                 1111 
                 C