Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
2001-01-30
2003-10-14
Nguyen, Chau (Department: 2663)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
C370S400000
Reexamination Certificate
active
06633548
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to field of network addressing. More specifically, the present invention is directed to a method and an apparatus for managing a ternary content addressable memory (TCAM) table.
BACKGROUND
Internet Protocol (IP) is a source route type of network where forwarding is made based on a destination Internet address. Address forwarding is made on a hop-by-hop basis. The destination address is looked up in a routing table to determine where a next hop is. The packet is then forwarded to the next hop. A routing protocol is used to make sure that as the packet travels through the network it will eventually reaches its destination.
The growth of the Internet causes routing tables to grow faster than the router technology. The router would have to keep millions of entries in its database corresponding to the millions of computers on the Internet. The look up process of the destination address in the routing table is an important part of the IP forwarding process. One of the Internet protocols is IP version 4 (“IPv4”). The address space for the IPv4 is 32 bits wide. Under the IPv4, there are two schemes of IP addresses. One IP address scheme is “classful”, while another IP address scheme is “classless”. Each IP or Internet address comprises a network id and a host id. The network id identifies the network on which the host resides. The network id is sometimes referred to as a network prefix. The host id identifies the particular host on the given network. The classful IP address scheme comprises multiple classes: A, B, C, D and E. Under class A, the network id is 8 bits wide, and the host id is 24 bits wide. Under class B, the network id is 16 bits wide, and under class C the network id is 24 bits wide. Each of the classes is used to support different size networks having different number of hosts. Network ids of all zeroes and all ones are reserved for default route and loop back function respectively. Class D is used for multicast, and class E is reserved. The classful IP address scheme does not efficiently accommodate different sizes of networks. Routers in the “old style” networks generally use the classful IP address scheme.
The classless IP address scheme is often referred to as CIDR (“classless inter-domain routing”). Basically, CIDR eliminates the concept of class A, B, and C networks and replaces this with an IP address prefix. CIDR can be used to perform route aggregation in which a single route can cover the address space of several “old-style” network numbers and thus replaces a lot of the old routes. CIDR makes it possible to utilize the available address space more efficiently and allows for continuous, uninterrupted growth of the Internet. Newer routers use the CIDR address scheme.
IP packet forwarding is processed at each router. To accelerate the lookup process, a set of address prefixes is stored as compared to millions of Internet addresses. Route lookup using the address prefixes is referred to as longest prefix match. In longest prefix match, each destination address is a string of 32 bits. The forwarding decision relies on using the destination address and finding an entry having the longest prefix match. The destination address is compared against the set of address prefixes to find a next route to forward the packet. There may be multiple prefix matches, however, the route having the longest prefix match would be selected. The longest match algorithm assumes that the host is part of the network having the longest prefix match.
The traditional lookup process is software based using hashes and trees. There may be multiple lookup per packet. However, as the number of packets increases, faster look up processes are necessary. One hardware lookup approach uses high-speed ternary content-addressable memory (TCAM). TCAM is a memory device that provides fast searches such as looking up for an entry in a route table database. TCAM allows retrieval of a location of a content given a partial content. Thus given a content (e.g., destination address), TCAM provides a location information (e.g., route) to that content. In addition, TCAM allows masking on bit fields and as such can be used to determine longest prefix matches. Each TCAM memory location has a corresponding mask register. A “1” in the mask register forces a match on the corresponding bit in the TCAM memory location where an address of a next hop for a next route is pre-stored. The prefix is stored in the mask register.
Management of the TCAM memory (“TCAM table”) is essential to provide the correct longest prefix match in the shortest time.
SUMMARY OF THE INVENTION
A method and a system for managing a TCAM table are disclosed. A new route is inserted into the TCAM table at an available location using an index. The new route is added into a Patricia tree organized by a mask length associated with the new route. Routes having common prefixes with the new route are searched for in Patricia trees organized by longer mask lengths and in Patricia trees organized by shorter mask lengths to locate a chain for the new route. The chain for the new route groups routes having common prefixes. The routes in the chain are sequenced in an order of longer prefix first such that a route at a top of the chain has a longest prefix. A swap of routes in the chain is performed to accommodate the new route and to maintain the longer prefix first order.
Other features and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description that follows below.
REFERENCES:
patent: 6018524 (2000-01-01), Turner et al.
patent: 6289414 (2001-09-01), Feldmeier et al.
patent: 6457061 (2002-09-01), Bal et al.
patent: 6490279 (2002-12-01), Chen et al.
patent: 6546391 (2003-04-01), Tsuruoka
PCT Notification of Transmittal of The International Search Report or The Declaration for PCT Counterpart Application No. PCT/US02/01948 Containing International Search Report (Jan. 22, 2003).
Tsunemasa Hayashi and Toshiaki Miyazaki, “High-Speed Table Lookup Engine for Ipv6 Longest Prefix Match,” XP-001016968, 1999 IEEE Global Telecommunications Conference—Globecom '99, vol. 2, pp. 1576-1581 (Dec. 5, 1999).
MUSIC Semiconductors, Application Brief AB-N6 “What Is A CAM (Content-Addressable Memory)?” Sep. 30, 1998 Rev. 2a, Hackettstown, New Jersey 07840.
MUSIC Semiconductors, Application Brief AB-N13 “A New Epoch in IP Networking” May 5, 1999 Rev.0, Santa Clara, California 95054.
NetLogic Microsystems, Application Note NCS018, “A Basic Controller For The CIDR Co-Processor TM Longest Prefix Match Engine” Jul. 2000, Mountain View, CA 94043.
Co-Processor TM Longest Prefix Match Engine Jul. 2000, Mountain View, CA 94043.
Ichiriu, Mike, “High Performance Layer 3 ForwardingThe Need for Dedicated Hardware Solutions,” NetLogic Microsystems White Paper (2000).
“Advantages of CAM in ASIC-Based Network Address Processing,” Music Semiconductors, Application Brief AB-N11, Rev. 1.2A Draft (Sep. 30, 1998).
“Using the 128-bit Wide Ternary IPCAM for 64-bit Applications,” Netlogic Microsystems, Application Note NCS08, Rev. 1.0 (date prior to Jan. 30, 2001).
“Using the Ternary NL82721 IPCAM™ for Longest Prefix Match,” Netlogic Microsystems, Application Note NCS05, Rev. 1.2 (date prior to Jan. 30, 2001).
“Using the Ternary NL82721 IPCAM™ for Subnet Masking,” Netlogic Microsystems, Inc, Application Note NCS04, Rev. 1.0 (date prior to Jan. 30, 2001).
Bachmutsky Alex
Chandler Vijay
Ho Chi Fai
Tzeng Henry
Blakely , Sokoloff, Taylor & Zafman LLP
Do Nhat
Nguyen Chau
Nokia Intelligent Edge Routers Inc.
LandOfFree
Method and apparatus for ternary content addressable memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for ternary content addressable memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for ternary content addressable memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3170772