Patent Publication Number: US-6715029-B1

Title: Method and apparatus for possibly decreasing the number of associative memory entries by supplementing an associative memory result with discriminator bits from an original set of information

Description:
FIELD OF THE INVENTION 
     This invention especially relates to computer and communications systems, including programming and using an associative memory such as, but not limited to a content-addressable memory; and more particularly, the invention relates to possibly decreasing the number of associative memory entries by supplementing an associative memory result with discriminator bits from an original set of information. 
     BACKGROUND OF THE INVENTION 
     The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP). 
     A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Additionally, one or more security operations are typically performed on each packet. But before these operations can be performed, a packet classification operation must typically be performed on the packet. 
     Packet classification as required for, inter alia, access control lists (ACLs) and forwarding decisions, is a demanding part of switch and router design. The packet classification of a received packet is increasingly becoming more difficult due to ever increasing packet rates and number of packet classifications. For example, ACLs require matching packets on a subset of fields of the packet flow label, with the semantics of a sequential search through the ACL rules. IP forwarding requires a longest prefix match. Various applications that use packet classification, such as Security Access Control, Quality of Service etc., typically need to perform many matches on source and destination port numbers, protocol and other header fields, etc. Additionally, supporting IPv6 and various tunneling techniques has increased the complexity of packet forwarding. For example, an IPv6 requires 128 bit forwarding and tunneling requires additional bits. 
     Known approaches of packet classification include using custom application-specific integrated circuits (ASICs), custom circuitry, software or firmware controlled processors, binary and ternary content-addressable memories (CAMs). The use of programmable software or firmware have advantages as they provide some level of flexibility, which becomes especially important as new protocols and services are added to existing network. Customer typically desire to use their existing hardware (e.g., routers, switches etc.) to support these new protocols and services. However, known software and firmware implementations are relatively slow, and typically place a performance bound which may be incompatible with new requirements. 
     CAMs are increasingly being used in packet classification especially because of their performance. A typical implementation performs a lookup operation on a CAM with the CAM result being used as input to a memory, which produces the actual result used in processing a packet. However, these content-addressable memories are typically expensive in terms of power consumption and space, and are limited in the size of an input word (e.g., 72, 144, etc.) on which a lookup operation is performed. Desired are new methods and apparatus for providing needed matching capabilities, while possibly decreasing the size of an associative memory required or increasing the packet processing capabilities supported by an associative memory. 
     SUMMARY OF THE INVENTION 
     Systems and methods are disclosed for possibly decreasing the number of associative memory entries by supplementing an associative memory result with discriminator bits from an original set of information. One embodiment operates on a set of information, the set of information including a lookup word portion and a discriminator portion. A lookup word is derived based on the lookup word portion. A lookup operation is performed on an associative memory, such as, but not limited to a binary or ternary content-addressable memory, using the lookup word to generate an associative memory result. A memory lookup operation is performed on a memory based on the associative memory result and the discriminator portion. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The appended claims set forth the features of the invention with particularity. The invention, together with its advantages, may be best understood from the following detailed description taken in conjunction with the accompanying drawings of which: 
     FIG. 1 is a block diagram of an embodiment for programming an associative memory and packet processor; 
     FIGS. 2A-B are block diagrams of exemplary embodiments performing packet processing; 
     FIGS. 3A-C are exemplary sets of information having lookup word and discriminator portions; 
     FIG. 4 is a block diagram of a process for determining a partitioning of a set of information into lookup word and discriminator portions; and 
     FIG. 5 is a flow diagram of a process for used in one embodiment for producing a result based on lookup word and discriminator portions of a set of information. 
    
    
     DETAILED DESCRIPTION 
     Systems and methods are disclosed for possibly decreasing the number of associative memory entries by supplementing an associative memory result with discriminator bits from an original set of information. Embodiments described herein include various elements and limitations, with no one element or limitation contemplated as being a critical element or limitation. Each of the claims individually recite an aspect of the invention in its entirety. Moreover, some embodiments described may include, but are not limited to, inter alia, systems, networks, integrated circuit chips, embedded processors, ASICs, methods, and computer-readable medium containing instructions. The embodiments described hereinafter embody various aspects and configurations within the scope and spirit of the invention, with the figures illustrating exemplary and non-limiting configurations. 
     As used herein, the term “packet” refers to packets of all types or any other units of information or data, including, but not limited to, fixed length cells and variable length packets, each of which may or may not be divisible into smaller packets or cells. The term “packet” as used herein also refers to a packet indication, such as, but not limited to all or part of a packet or packet header, a data structure value, pointer or index, or any other part or identification of a packet. Moreover, these packets may contain one or more types of information, including, but not limited to, voice, data, video, and audio information. The term “item” is used herein to include a packet or any other information or data. Furthermore, the term “system” is used generically herein to describe any number of components, elements, sub-systems, devices, packet switch elements, packet switches, routers, networks, computer and/or communication devices or mechanisms, or combinations of components thereof. The term “computer” is used generically herein to describe any number of computers, including, but not limited to personal computers, embedded processors and systems, control logic, ASICs, chips, workstations, mainframes, etc. The term “device” is used generically herein to describe any type of mechanism, including a computer or system or component thereof. The terms “task” and “process” are used generically herein to describe any type of running program, including, but not limited to a computer process, task, thread, executing application, operating system, user process, device driver, native code, machine or other language, etc., and can be interactive and/or non-interactive, executing locally and/or remotely, executing in foreground and/or background, executing in the user and/or operating system address spaces, a routine of a library and/or standalone application, and is not limited to any particular memory partitioning technique. The steps and processing of signals and information illustrated in the figures are typically be performed in a different serial or parallel ordering and/or by different components in various embodiments in keeping within the scope and spirit of the invention. Moreover, the terms “network” and “communications mechanism” are used generically herein to describe one or more networks, communications mediums or communications systems, including, but not limited to the Internet, private or public telephone, cellular, wireless, satellite, cable, local area, metropolitan area and/or wide area networks, a cable, electrical connection, bus, etc., and internal communications mechanisms such as message passing, interprocess communications, shared memory, etc. The terms “first,” “second,” etc. are typically used herein to denote different units (e.g., a first element, a second element). The use of these terms herein does not necessarily connote an ordering such as one unit or event occurring or coming before the another, but rather provides a mechanism to distinguish between particular units. Moreover, the phrase “based on x” is used to indicate a minimum set of items x from which something is derived, wherein “x” is extensible and does not necessarily describe a complete list of items on which the operation is based. Additionally, the phrase “coupled to” is used to indicate some level of direct or indirect connection between two elements or devices, with the coupling device or devices modify or not modifying the coupled signal or communicated information. The term “subset” is used to indicate a group of all, less than all, or none of the elements of a set. Moreover, the term “or” is used herein to identify an alternative selection of one or more, including all, of the conjunctive items. 
     Methods and apparatus are disclosed for possibly decreasing the number of associative memory entries by supplementing an associative memory result with discriminator bits from an original set of information. One embodiment operates on a set of information, the set of information including a lookup word portion and a discriminator portion. A lookup word is derived based on the lookup word portion. A lookup operation is performed on an associative memory, such as, but not limited to a binary or ternary content-addressable memory, using the lookup word to generate an associative memory result. A memory lookup operation is performed on a memory based on the associative memory result and the discriminator portion. 
     FIG. 1 illustrates one embodiment of a system, which may be part of a router or other communications or computer system, for programming and using a packet processor and an associative memory, such as, but not limited to a binary or ternary content-addressable memory. In one embodiment, programming engine  100  receives or determines a list of entries, an identification of lookup word and discriminator portions of data items, possibly a mask to program associative memory  130 , and corresponding values to program memory  140 . Programming engine  100  typically also configures packet processor to extract appropriate lookup word and discriminator portions of a set of information. 
     In one embodiment, programming engine  100  includes a processor  102 , memory  101 , storage devices  104 , and programming interface  105 , which are coupled via one or more communications mechanisms  109  (shown as a bus for illustrative purposes). Various embodiments of programming engine  100  may include more or less elements. The operation of programming engine  100  is typically controlled by processor  102  using memory  101  and storage devices  104  to perform one or more tasks or processes. Memory  101  is one type of computer-readable medium, and typically comprises random access memory (RAM), read only memory (ROM), flash memory, integrated circuits, and/or other memory components. Memory  101  typically stores computer-executable instructions to be executed by processor  102  and/or data which is manipulated by processor  102  for implementing functionality in accordance with the invention. Storage devices  104  are another type of computer-readable medium, and typically comprise solid state storage media, disk drives, diskettes, networked services, tape drives, and other storage devices. Storage devices  104  typically store computer-executable instructions to be executed by processor  102  and/or data which is manipulated by processor  102  for implementing functionality in accordance with the invention. 
     As used herein and contemplated by the invention, computer-readable medium is not limited to memory and storage devices; rather computer-readable medium is an extensible term including other storage and signaling mechanisms including interfaces and devices such as network interface cards and buffers therein, as well as any communications devices and signals received and transmitted, and other current and evolving technologies that a computerized system can interpret, receive, and/or transmit. 
     FIG. 2A illustrates one embodiment of a system, which may be part of a router or other communications or computer system, for programming and using a packet processor and an associative memory, such as, but not limited to a binary or ternary content-addressable memory. Information  200 , such as packets or portions thereof, is received by processing engine  210 . Control logic  211  typically controls the operation of processing engine  210  and forwards a set of received information to a selection mechanism  212 , which selectively provides a lookup word  213  to associative memory  220  and a discriminator  214  to memory  230 . In one embodiment, selection mechanism  212  is simply hardwired circuitry. In one embodiment, selection mechanism  212  comprises a dynamic, static, and/or programmable mechanism, including such devices as a matrix, shift register, and other selection devices to selectively extract lookup word  213  and discriminator  214 . In one embodiment, discriminator  214  includes a small number (e.g., between one and sixteen) of bits of information  200 . 
     Associative memory  220  typically performs a lookup operation based on lookup word  213 , which may optionally include information from another source or other statically or dynamically programmed information. The produced associative memory result  225  and discriminator  214  are used by control  228  to produce address  229 , which is provided to memory  230  to produce result  231 . Control  228  can manipulate associative memory result  225  and discriminator  214  in any conceivable manner to produce address  229 . In one embodiment, memory result  225  and discriminator  214  are concatenated together to produce memory address  229 . In one embodiment, control  228  manipulates and possibly performs a hashing operation to generate address  229 . In one embodiment, memory result  225  and discriminator  214  are provided directly to memory  230 . Based on associative memory result  225  and discriminator  214 , memory  230  produces result  231 , which is typically used by processing engine  210  to process information  200  (e.g., a received packet.) 
     FIG. 2B illustrates one embodiment of a system, which may be part of a router or other communications or computer system, for programming and using multiple virtual portions of a single associative memory, such as, but not limited to a binary or ternary content-addressable memory. In one embodiment, processing engine  250  includes a processor  251 , memory  252 , storage devices  254 , and interface  255 , which are coupled via one or more communications mechanisms  259  (shown as a bus for illustrative purposes). Various embodiments of processing engine  250  may include more or less elements. The operation of processing engine  250  is typically controlled by processor  251  using memory  252  and storage devices  254  to perform one or more tasks or processes. 
     Information  290 , such as packets or portions thereof, is received by processing engine  250 , which extracts a lookup word  260  and discriminator  265 , which are provided to associative memory  270  and memory  280  respectively via interface  255 . A lookup operation is performed on lookup word  260  by associative memory  270  to produce associative memory result  271 , which is used, along with discriminator  265 , as input to control  278  to produce address  279  used by memory  280  to produce one or more results  281 . In one embodiment, associative memory result  271  and discriminator  265  are provided directly to control memory  280 . 
     FIGS. 3A-C illustrate an exemplary extraction locations for the lookup word and discriminator portions of information  300 . As shown in FIG. 3A, lookup word portion  301  and discriminator portion  302  are both contiguous blocks of bits within information  300 . As shown in FIG. 3B discriminator portion  312  is contiguous within a distributed lookup word portion  311  within information  300 . As shown in FIG. 3C, lookup word portion  321  and discriminator portion  322  are extracted from distributed locations within information  300 . Selection mechanism  212  (FIG.  2 A), processing engine  250  (FIG.  2 B), or another selection mechanism used in one embodiment selectively, whether statically or programmatically, extracts the appropriate lookup word and discriminator portions. 
     FIG. 4 illustrates a flow diagram of one process used in one embodiment for determining a partitioning of a set of information into lookup word and discriminator portions, and for optionally configuring or programming a lookup word generator (e.g., a selection mechanism) to extracting the appropriate portions of a received set of information. Processing begins with process block  400 . If, as determined in process block  402 , while there are more sets of discriminator bits, process blocks  404 - 412  are repeatedly performed. Each possible set of discriminator bits may include a single bit or multiple bits, which each bit located in any position within a set of information. In process block  404 , a next set of discriminator and lookup word bits are selected. Then, as determined in process block  406 , while there are more exemplary configuration files to test, a new configuration file is selected in process block  408 , an associative memory programming is determined for the current configuration file, and the results are recorded in process block  412 . In one embodiment, the results include the number of resultant associative memory entries. 
     When all sets of discriminator bits have been tested as determined in process block  402 , the results are analyzed in process block  420  to determine and select the appropriate discriminator and lookup word portions. For example, a selection of the discriminator and lookup word portions may be selected based on a minimum number of associative memory entries, and possibly a number of memory locations required. Next, in process block  422 , the lookup word generator is configured to produce the required lookup word and discriminator portions of a received set of information. In one embodiment, the configuration is either manually or automatically configured, such as by physically routing connections or programming a lookup word generator. Processing is complete as indicated in process block  424 . 
     FIG. 5 illustrates a process used in one embodiment to receive and process packets (or other types of sets of information.) Processing begins with process block  500 , and proceeds to process block  502 , wherein a packet is received. Next, a set of information is extracted from the received packet. In process block  506 , the lookup word and discriminator portions are extracted, and in process block  508 , an associative memory lookup is performed based on the lookup word portion to produce an associative memory result. Next, in process block  510 , a memory lookup operation is performed based on the associative memory result and the discriminator portion to produce a result, which is used in process block  512  to process the packet. Processing returns to process block  502  to receive and process more packets. 
     In view of the many possible embodiments to which the principles of our invention may be applied, it will be appreciated that the embodiments and aspects thereof described herein with respect to the drawings/figures are only illustrative and should not be taken as limiting the scope of the invention. For example and as would be apparent to one skilled in the art, many of the process block operations can be re-ordered to be performed before, after, or substantially concurrent with other operations. Also, many different forms of data structures could be used in various embodiments. The invention as described herein contemplates all such embodiments as may come within the scope of the following claims and equivalents thereof.