Abstract:
A method of storing addresses in a database comprising generating original prefixes representing the addresses to be stored in the database. The prefix lengths are determined dynamically. Reduced prefixes are generated by collapsing or expanding the original prefixes such that a number of reduced prefixes is less than a number of original prefixes. The reduced prefixes are stored in the database.

Description:
RELATED APPLICATIONS  
       [0001]     This Application claims priority from co-pending U.S. Provisional Application Ser. No. 60/658,167, with inventors Srihari Cadambi, Srimat Chakradhar, Hirohiko Shibata, filed Mar. 7, 2005, which is incorporated in its entirety by reference. 
     
    
     FIELD  
       [0002]     This disclosure teaches pre-processing techniques to reduce the number of prefix lengths in IP routing and other networking databases.  
       BACKGROUND  
     1. References  
       [0003]     The following papers provide useful background information, for which they are incorporated herein by reference in their entirety, and are selectively referred to in the remainder of this disclosure by their accompanying reference codes in square brackets (i.e., [3] for the paper by Srinivasan. 
    1. Technologies, S., SiberCAM Ultra-18M SCT1842. 2002.     2. N. McKeown and P. Gupta, Algorithms for Packet Classification. IEEE Network, 2001. 15(2): p. 24-32.     3. V. Srinivasan, G. Varghese, S. Suri, M. Waldvogel, Fast and scalable layer four switching. ACM SIGCOMM Computer Communication Review, Proceedings of the ACM SIGCOMM &#39;98 conference on Applications, technologies, architectures, and protocols for computer communication, 1998. 28(4).     4. S. Cadambi, S. Chakradhar, N2SE: The NEC Network Search Engine. 2004.     5. S Cadambi, J. Kilian, P Ashar, H Shibata, BCAM: A High-Performance, Low-Power Network Router Using Bloomier Filters. 2004, NEC Laboratories America, Inc.     6. S. Cadambi, J. Kilian, P. Ashar, Inexpensive and Fast Content Addressable Memory. 2004, NEC Laboratories America, Inc.     7. S. Dharmapurikar, K. Prabhakar, D. Taylor,. Longest prefix matching using bloom filters in Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications. August 2003.     8. B. Chazelle, J. Kilian, R. Rubinfeld and A. Tal, The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables. Proceedings, Symposium on Discrete Algorithms (SODA), 2004.     9. V. Srinivasan, G. Varghese, Fast Address Lookups Using Controlled Prefix Expansion. ACM Transactions on Computer Systems (TOCS), 1999. 17(1): p. 1-40.     10. V. Srinivasan, G. Varghese, Method and Apparatus for Fast Hierarchical Address Lookup using Controlled Expansion of Prefixes. 2000, Washington University, St Louis: USA.    
 
       2. Introduction  
       [0014]     An increased use of applications with high bandwidth requirements, such as video conferencing and real-time movies, has resulted in a steep growth in internet traffic as well as an increase in the number of hosts. In order to provide acceptable performance, communication links are being upgraded to support higher data rates. However, higher link speeds translate to better end-to-end performance only if network routers, which filter and route Internet Protocol (IP) packets, are commensurately faster. A significant bottleneck in a network router is the IP address lookup, which is the process of forwarding a packet to its destination. This is commonly known as IP forwarding. Other important tasks performed by network routers such as packet classification are also made faster if this basic lookup process is accelerated.  
         [0015]     Given a set of prefixes, the lookup problem consists of finding the longest prefix that matches an incoming header. A prefix corresponds to an internet address, or its initial portion. This problem is referred to as Longest Prefix Matching, or LPM. Three major categories of hardware solutions for LPM are content-addressable memories (CAMs), tree-based algorithmic solutions and hash-based solutions.  
         [0016]     The disclosed teachings are aimed at prefix pre-processing techniques that will benefit tree-based and hash-based solutions.  
       3. Background Information on Prefix Processing  
       [0017]     A prefix of length L is a regular expression whose L most significant bits are valid, while all other bits are considered as “don&#39;t-cares”. This description is restricted to regular expressions that are integers (for instance, an internet address). The number of valid bits in a prefix is referred to as the prefix length.  
       a) Longest Prefix Matching  
       [0018]     A prefix refers to an IP address or its initial portion. For instance, “100.10” is a prefix of “100.10.1.2”. A prefix database contains forwarding information for “100.10”. However, it may contain more refined forwarding information for the larger prefix “100.10.1.2”. Therefore, an incoming IP address must be compared with all prefixes, and the forwarding information corresponding to the longest matching prefix must be discovered.  
         [0019]     For instance, consider a router which forwards “.com” packets to port A. If the router is located such that the domain “nec.com” is more easily accessible via port B, it should route “nec.com” packets to port B. Therefore, incoming packets with “nec.com” as their destination address will be forwarded to B, while all other “.com” packets to port A.  
         [0020]     A simple prefix table is shown in  FIG. 1 . The prefix table of  FIG. 1  is used as a running example throughout this document.  
         [0021]     Popular implementations of LPM include Ternary CAMs (TCAMs) [1], tree-based solutions and hash-based solutions. The prefix processing techniques disclosed in this disclosure benefits the latter two approaches, both of which are briefly introduced below.  
       b) Tree-Based Solutions  
       [0022]     The basic tree data structure for the prefix table in  FIG. 1  is shown in  FIG. 2 . A tree is constructed from the given prefixes. At each node of the tree corresponding to level L, the L′th bit of the incoming header is examined, and action is taken depending on whether the bit is 1 or 0. For instance, at the root, the first bit of the header is examined. If this bit is 0, the header matches prefix P0 and no other prefix. If this bit is 1, then further checks are necessary to correctly determine the longest matching prefix. This requires traversal of the tree. Hence, the latency of discovering the longest prefix match depends on the depth of the tree.  
         [0023]     Several improvements have been proposed for the tree-based algorithm [2, 3]. A common enhancement is to avoid the bit-by-bit comparison, and “jump” to the next prefix length by comparing several bits at each node of the tree. Such a technique is greatly benefited by a reduction in the number of prefix lengths.  
         [0024]     c) Hash-Based Solutions  
         [0025]     Hash-based approaches construct a hash table for each distinct prefix length.  FIG. 3  shows the hash-based approach for the example prefix table. The hash table for each prefix length is optimized to provide very fast queries. All hash tables are accessed in parallel (in a hardware implementation). A priority encoder at the output of the hash tables selects the longest matching prefix.  
         [0026]     Several improvements to the hash-based approach exist ([4-8]). These references use sophisticated techniques to improve the performance of hash tables which otherwise have a poor worst-case search latency. However, the basic architectural template remains the same.  
       d) Related Art: Controlled Prefix Expansion  
       [0027]     Varghese, et al ([9, 10]) proposed a prefix expansion technique where the given prefixes are expanded into prefixes belonging to a pre-selected set of prefix lengths.  
       SUMMARY  
       [0028]     To overcome the disadvantages discussed above, the disclosed teachings provide a method of storing addresses in a database comprising generating original prefixes representing the addresses to be stored in the database. The prefix lengths are determined dynamically. Reduced prefixes are generated by collapsing or expanding the original prefixes such that a number of reduced prefixes is less than a number of original prefixes. The reduced prefixes are stored in the database.  
         [0029]     Another aspect of the disclosed teachings is a computer program product including computer-readable media that includes instructions to enable a computer to perform the disclosed techniques. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0030]     The above objectives and advantages of the disclosed teachings will become more apparent by describing in detail preferred embodiments thereof with reference to the attached drawings in which:  
         [0031]      FIG. 1  shows a simple prefix table.  
         [0032]      FIG. 2  shows a basic tree-based solution for  FIG. 1 .  
         [0033]      FIG. 3  shows a basic hash-based solution for  FIG. 1 .  
         [0034]      FIG. 4  shows an exemplary implementation of the disclosed prefix collapsing technique.  
         [0035]      FIG. 5  shows an exemplary implementation of the disclosed prefix expansion technique.  
         [0036]      FIG. 6  shows an exemplary implementation of an overall technique. 
     
    
     DETAILED DESCRIPTION  
       [0037]     Synopsis  
         [0038]     In the disclosed techniques, the given prefixes are not expanded into a pre-determined set of prefix lengths. On the other hand, the prefix lengths are determined dynamically using the disclosed prefix processing algorithm. Sometimes prefixes are collapsed into shorter prefix lengths. The best prefix lengths are determined based on an objective function, which minimizes the number of prefix lengths.  
         [0039]     An objective  
         [0040]     Given a prefix set SP and an integer C, expand or collapse the prefixes in SP to a new set SP′ such that the number of prefix lengths in SP′ is minimized and the number of prefixes in each prefix length is less than C.  
         [0041]     Exemplary Embodiment  
         [0042]     The exemplary embodiment discussed herein uses a greedy algorithm as outlined below. It produces good solutions in practice. Each prefix length that are collapsed or expanded prefixes into is considered a bin with a given capacity. A bin could be a memory.  
         [0043]     The exemplary embodiment has two parts. The first is prefix collapsing, and the second is prefix expansion.  
         [0044]     Prefix collapsing proceeds as follows ( FIG. 4 ). The largest prefix length (denoted P from  in Box  401  in  FIG. 4 ) is considered first. If this prefix length is empty (i.e., has no prefixes), P from  is decreased until the first populated prefix length if found (Boxes  402 - 404  in  FIG. 4 ). This is the “source” prefix length from which prefixes will be collapsed. Next, a “destination” prefix length P to  is found into which the collapsed prefixes from P from  will be inserted. Boxes  405 - 408  in  FIG. 4  depicts this. In essence, P to  is the largest populated prefix length smaller than P from . Then, a “complete set” S of 2 Pfrom−Pto  prefixes that have a common sub-prefix of length P to  is extracted (Box  409 ,  FIG. 4 ). For example 0000→A, 0001*→A, 0010*→A, 0011→B comprise a complete set of 4 prefixes of length  4  with a common sub-prefix “00”. From S, the largest subset of prefixes that have the same destination is extracted (set SS in Box  409  of  FIG. 4 ). This subset of prefixes is collapsed into a single prefix of length P to . Note that this is possible provided the following two conditions are satisfied, which is ensured by the algorithm in the flowchart of  FIG. 4 : (i) prefixes of length P to  exist (i.e., a new prefix length should not be created) and (ii) the common sub-prefix does not already exist in the set of prefixes of length P to  (the “Collapse” routine in Box  411  ensures this). In the above example consisting of 0000*→A, 0001*→A, 0010*→A, 0011*→B, three out of four prefixes have the same destination A. Therefore, the three prefixes can be collapsed into a single prefix 00*−&gt;A of prefix length  2 , while the fourth prefix 0011*−&gt;B is retained in prefix length  4 . Such a transformation still provides correct longest prefix match operation.  
         [0045]     Prefix expansion proceeds as outlined in the following steps: 
        All prefixes from the largest prefix length L 1  are allocated to as many bins as required. If n L1  bins are needed, n L1-1  bins will be full, while one bin may be partially filled after this expansion.     If a partially filled bin exists, as many prefixes as possible are expanded from the next largest prefix length L 2  and allocated to this bin. If the prefixes in L 2  are exhausted, prefixes are expanded from the next prefix length; continue until the partially filled bin is full.     This is repeated for all prefix lengths.        
 
         [0049]      FIG. 5  shows the prefix expansion algorithm. In Box  501 , P to  is assigned to the largest prefix length. In Box  502 - 504 , P to  is adjusted to the largest populated prefix length. P to  is the destination prefix length into which prefixes will be expanded. Next, P from , the source prefix length from which prefixes will be expanded, is found (Box  505 - 508 ,  FIG. 5 ). In Box  509 , the maximum number of prefixes that can be expanded from P from  into P to  given the capacity constraints of P to  is computed. If this number is 0, the next P from  is found (Box  510 ). Otherwise, the expansion proceeds until the destination prefix length cannot accommodate any more prefixes (Box  511 ).  
         [0050]     These two algorithms together comprise the disclosed prefix pre-processing technique. The overall procedure is shown in  FIG. 6 . The collapse and expand procedure loop is repeated until no further changes are possible.  
         [0051]     Table Updates  
         [0052]     In network routers, prefix tables are regularly updated. Updates include addition of new prefixes, deletion or changing the forwarding information of existing prefixes. Prefix pre-processing makes updates a little more complicated since a prefix may have been collapsed or expanded into a different prefix length.  
         [0053]     Assume that the set of prefix lengths after prefix pre-processing is S={pl1, pl2 . . . plL}. All prefixes that existed prior to prefix pre-processing are labeled as “original” prefixes.  
         [0054]     After prefix pre-processing, a tag is appended to every prefix indicating its original prefix length. The tag may be appended in hardware for hardware implementations or within software data structures for software implementations.  
         [0055]     The following schemes outline the different kinds of updates: 
        Addition of a prefix: A new prefix of length l is collapsed or expanded using the algorithms in  FIG. 4  and  FIG. 5 . If a collision occurs with an existing prefix P′, P′ is overwritten only if its original length (determined by examining its prefix length tag) is less or equal to l.     Removal of a prefix: In order to remove an original prefix P of length l, all prefix lengths in S are examined since P may have been expanded or collapsed into a different prefix length. Prefixes that match P, and whose prefix length tags equal l, are removed.     Changing the forwarding information of a prefix: In order to change the forwarding information of a prefix P of length l, all prefix lengths in S are examined since P may have been expanded or collapsed into a different prefix length. The forwarding information of prefixes that match P, and whose prefix length tags equal l, is changed accordingly.        
 
         [0059]     The above discussed techniques can be implemented in any suitable computing environment. A computer program product including computer readable media that includes instructions to enable a computer or a computer system to implement the disclosed teachings is also an aspect of the invention.  
         [0060]     Other modifications and variations to the invention will be apparent to those skilled in the art from the foregoing disclosure and teachings. Thus, while only certain embodiments of the invention have been specifically described herein, it will be apparent that numerous modifications may be made thereto without departing from the spirit and scope of the invention.