Abstract:
A content addressable memory (CAM) simultaneously searches packet categories in the CAM, and automatically allocates network resources, such as bandwidth, between the categories. Categories and their allocation are based on various data characteristics, such as video, voice, graphic, or text. Bandwidth allocations determined by the user give priority to video data over graphics, for example. Graphics data, in turn, is given more bandwidth than voice or text data. A dynamic average of the bandwidth usage of each priority category is maintained. Enablement of priority categories is determined, at least in part, based on whether or not the average usage is above or below an allocated level.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to content addressable memories, and more specifically, to content addressable memories having bandwidth allocation for use in high speed data communication networks.  
           [0003]    2. Brief Description of the Related Art  
           [0004]    Modern communications systems transmit data over digital networks. System resources are finite, so allocation of those resources becomes necessary. For example, system capacity limitations may restrict the amount of data that can be transmitted by the network, or a user may wish to give priority to certain categories of data over others.  
           [0005]    Practically all digital networks make use of some form of packet or block type data format to dynamically route data packets or blocks through the network. The data contained in the packets can be categorized in various ways, including type of packet, packet content, size, creation date, and urgency of delivery, for example. Depending on the purpose of the communications system and the preferences of the user, it may be necessary to limit or expand the amount of bandwidth to be allocated to a particular category of data.  
           [0006]    Content addressable memories (CAMs) are used in communications systems as search engines for routing paths in data network routers and switches. The packets being routed can be viewed as belonging to a particular category. Typically, a CAM issues a single search result that is independent of a packet category. Consequently, it is necessary for the user to handle bandwidth allocation, for example, by discarding search results for certain categories. A significantly more efficient way of utilizing a CAM as a search engine is needed.  
         BRIEF SUMMARY OF THE INVENTION  
         [0007]    The present invention provides a CAM modified to simultaneously search packet categories in the CAM, and automatically allocate network resources, such as the bandwidth, among the categories. Categories and their allocation can be based on various data characteristics. For example, packets can be categorized as containing various types of data, such as video, voice, graphic, or text. Bandwidth allocations are determined by the user so certain categories of data are given priority over other categories of data. For example, video data can be given priority over graphics data, which, in turn, can be given priority over voice or text data. According to a preferred embodiment, a dynamic average of the bandwidth usage of each priority category is maintained. Enablement of priority categories is determined based on whether or not the average usage is above or below an allocated level. Other features and advantages of the present invention will become apparent from the following description of the invention which refers to the accompanying drawings. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0008]    [0008]FIG. 1 is a block diagram of an exemplary embodiment of a CAM according to the present invention.  
         [0009]    [0009]FIG. 2 illustrates a priority code circuit according to an exemplary embodiment of the present invention.  
         [0010]    [0010]FIG. 3 is a block diagram of a CAM according to an alternative embodiment of the present invention.  
         [0011]    [0011]FIG. 4 illustrates a priority code circuit according to an alternative embodiment of the present invention.  
         [0012]    [0012]FIG. 5 is a block diagram of a CAM according to a second alternative embodiment of the present invention.  
         [0013]    [0013]FIG. 6 illustrates a priority encoder circuit according to an exemplary embodiment of the present invention.  
         [0014]    [0014]FIG. 7 is a block diagram of a bandwidth percentage averager according to an exemplary embodiment of the present invention.  
         [0015]    [0015]FIG. 8 is a block diagram of an exemplary embodiment of a priority bandwidth allocation circuit according to the present invention.  
         [0016]    [0016]FIG. 10 is a block diagram of an averager having a variable range of averaging according to the present invention.  
         [0017]    [0017]FIG. 11 is a flow chart of a decisions circuit according to an exemplary embodiment of the present invention.  
         [0018]    [0018]FIG. 12 is a block diagram of a microprocessor-based system including a CAM according to the present invention.  
         [0019]    [0019]FIG. 13 illustrates a router which includes a CAM and a priority encoder according to an exemplary embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0020]    Referring to FIG. 1, a block diagram illustrates a modified CAM  2  according to an exemplary embodiment of the present invention. CAM  2  includes a plurality of CAM storage locations which store CAM words (e.g., M 0 ) and which also have associated respective storage locations (e.g., C 0 ) for storing a priority coded with each CAM word. When a searched-for word is simultaneously presented to each of the CAM storage locations, those that match indicate the match to a plurality of priority encoders  4 ,  6 ,  8 ,  10 , each of which, when presented with multiple matches of a CAM word, encode the highest priority match from which an address of a word can be deduced. In the present embodiment, four priority encoders  4 ,  6 ,  8 ,  10  are shown, although the invention is not so limited.  
         [0021]    Each priority encoder  4 ,  6 ,  8 ,  10  is assigned a particular category of packets. Priority encoder  4 , for example, is assigned a video category, while voice data is assigned to priority encoder  6 . Similarly, priority encoder  8  is assigned graphics-based data, while text-based data is assigned to priority encoder  10 .  
         [0022]    Each priority encoder receives the match inputs from CAM words M 0 -Mn having data in the same category as the priority encoder. The priority code section C 0 -Cn added to each respective CAM word M 0 -Mn, defines which of the priority encoders  4 ,  6 ,  8 ,  10  is to be used in case of a match between the data stored in that CAM word, and the data in a comparand register (not shown). Thus, if a match is found at CAM word M 0 , and the priority code C 0  indicates that the data is in a video category, priority encoder  4  is used to encode the match. If, on the other hand, the priority code C 0  indicates that the data is in a voice-based category, priority encoder  8  is used to encode the match. Matches in each of the remaining CAM words M 1 -Mn similarly have a respective priority code C 1 -Cn for selecting a priority encoder used for priority encoding multiple matches of data words.  
         [0023]    A CAM word M 0 -Mn may be associated with more than one priority encoder  4 ,  6 ,  8 ,  10  at any given time. For example, a match found at CAM words M 2  may be indicated by priority code C 2  to be categorized as both video data and text-based data. Consequently, priority encoders  4  and  10  are used to priority encode the word match.  
         [0024]    A bandwidth allocation control circuit  12  receives information from each of the priority encoders indicating that a priority encoder is seeing at least one match at its match inputs, and provides the priority encoders with an enabling signal which allows the priority encoders  4 ,  6 ,  8 ,  10  to perform their encoding functions. Bandwidth usage in each category is monitored, as described further below. Based on the calculated bandwidth usage and pre-programmed policies, bandwidth allocation control circuit  12  determines which category, or categories, of encoding, that is, which of priority encoders  4 ,  6 ,  8 ,  10  may be enabled to encode the match signals on their inputs.  
         [0025]    Once an encoder&#39;s category is enabled, a highest priority match is encoded by the enabled priority encoder and provided to multiplexer  14 . Multiplexer  14 , also controlled by bandwidth allocation control circuit  12 , decodes and outputs address information for highest priority stored words which match the search word.  
         [0026]    Referring to FIG. 2, an embodiment is illustrated of an exemplary priority code circuit  16 , which can be used as priority code circuits C 0 -Cn in FIG. 1. Priority code circuit  16  receives active signals on a match line by way of a match detector  18 , indicating that associated word data in a CAM corresponds to comparand data. Active matches detected by match detector  18  are provided to NAND gates N 1 -Nn, along with stored priority code flip-flop values F 1 -Fn. A bit pattern priority code at the outputs PRIORITY 1 -PRIORITYn is indicated by a logic low at each output if the detected match has a priority code equal to the corresponding flip-flop stored priority value. This stored bit pattern priority code points to a specific one or more of priority encoders  4 ,  6 ,  8 ,  10  for priority encoding the matching words as a result of a CAM memory search. For example, a matching CAM word contains a priority code that matches the value stored in flip-flop F 1 , priority encoder  4  will be used for priority encoding the matching CAM word. Similarly, if a matching CAM word contains a priority code matching the values in flip-flops F 2  and F 3 , priority encoders  6  and  8 , respectively, will be used to priority encode the matching CAM word.  
         [0027]    Referring to FIG. 3, an alternative embodiment of the present invention is illustrated. CAM  20  of FIG. 3 is similar to the exemplary embodiment of FIG. 1, except that priority code data pointing to a specific priority encoder is stored as an encoded binary number. For n bit binary presentation, there are 2 n  unique combinations. Using a “one-hot” decoder, the representation, for example, in priority code stored in the code circuits CX 0 -CXn is decoded by the decoder to one out of 2 1  active outputs of the priority assigned. Accordingly, decoders D 0 -Dn following priority code circuits CX 0 -CXn are used such that only a single priority encoder  4 ,  6 ,  8 ,  10  may be selected at any given time. Otherwise, FIG. 3 operates in the same manner as described above for FIG. 1.  
         [0028]    [0028]FIG. 4 illustrates an embodiment of an exemplary priority code circuit  22 , used as priority code circuits CX 0 -CXn, and a decoder  24  used as a decoder D 0 -Dn, in FIG. 3. Priority code circuit  22  receives active signals on a match line by way of a match detector  25 , indicating that word data in a CAM corresponds to comparand data. Active matches detected by match detector  25  are provided to NAND gates NG 1 -NGn of decoder  24 , along with stored one-hot encoded flip-flop values of priority code circuit  22 . A priority code PRIORITY 1 -PRIORITYn is indicated by a logic low if the detected match has a priority code equal to the corresponding stored priority value, causing a CAM word match to be priority encoded by the corresponding priority encoder based on its priority coded category, similar to the priority encoder selection operation described above in connection with FIG. 2.  
         [0029]    [0029]FIG. 5 illustrates a second alternative embodiment of the present invention. CAM  30  is similar to CAM  2  illustrated in FIG. 1, except that a user can override the bandwidth allocation control set by control circuit  36 , and force, using priority assignment data in the comparand register, which priority encoder will be enabled, at any given time, regardless of the bandwidth allowed by the control circuit  36 . Thus, CAM  30  includes comparand register  32 , and comparand priority code  34 . Comparand priority code  34  is used to override an enable determination by bandwidth allocation control circuit  36 , such that the category indicated by the priority code attached to the comparand data is given priority over the category that may have been determined to have priority by the bandwidth allocation control circuit  36 .  
         [0030]    [0030]FIG. 6 illustrates a typical priority encoder  40 , such as could be used as priority encoder  4 ,  6 ,  8 , or  10 , for example, in each of the CAMs  2 ,  20 , and  30 . Priority encoder  40  shown in FIG. 4, utilizes a “thermometer” type of arrangement of logic gates to determine which of the inputs has the highest priority. Priority encoder  40  is arranged as a series of stages arranged from bottom to top, each stage having progressively lower priority.  
         [0031]    In the exemplary embodiment of FIG. 6, a priority encoder stage includes a NOT gate, a NAND gate, and a NOR gate. A highest priority stage includes NOT gate  42 , which inverts an ENABLE signal and supplies it to NOR gate  44 . NOR gate  44  also receives a signal on match line input IN_N 0 . ENABLE also is supplied to NAND gate  46 , along with match line input N 0 . The result from NOR gate  44  is supplied on output terminal PO 0  to an address encoder  48 . Address encoder  48  provides an address output corresponding to the highest priority match line detected by the priority encoder to a multiplexer, such as multiplexer  14  shown in FIGS. 1, 3, and  5 , for example.  
         [0032]    Priority encoder  40  includes several such stages, of which six are shown in FIG. 6. Thus, the result from NAND gate  46  is supplied to the next logically lowest priority stage (physically higher on the “thermometer”) made up similarly of NOT gate  52 , NOR gate  54 , and NAND gate  56 . NOR gate  54  supplies a signal to output terminal PO 1 , and NAND gate  56  supplies its signal to the third lowest priority stage made up of NOT gate  62 , NOR gate  64 , and NAND gate  66 , the stage delivering an output signal on PO 2 . Similar fourth- and fifth-lowest priority stages are shown which include NOT gates  72  and  82 , NOR gates  74  and  84 , and NAND gates  76  and  86 , respectively, the stages providing output signals on PO 3  and PO 4  to address encoder  48 . A final sixth stage includes NOR gate  88 , providing its output signal on PO 5 .  
         [0033]    In operation, matches are indicated on match lines IN_N 0 -IN_N 6  as logic 0, the ENABLE signal having a logic high. Thus, in the first stage, if match line IN_N 0  is low, output PO 0  will be high, indicating a highest priority match.  
         [0034]    Priority encoder  40  includes an ACTIVE output, which goes to a logic LOW every time any input to the priority encoder is active. The ACTIVE signal is provided by multiple-input NAND gate  90 , to the bandwidth control circuit ( 12  in FIGS. 1 and 3;  36  in FIG. 5), NAND gate  90  receives input signals from each of the signal lines IN_N 0 -IN_N 5 .  
         [0035]    For each priority category, the CAM is equipped with a usage averager  100 , an exemplary embodiment of which is illustrated in FIG. 7. Usage in each priority code category is calculated over a range of n routed packets. Averager  100  includes an n-bit shift register  102 , which is shifted each time activity occurs in any priority category as indicated by the ORing of all PRIORITY USED signals. More specifically, if a routed packet is in the priority to which the averager is assigned, a logic “1” is written into the shift register. If the routed packet is in a different priority, a logic “0” is written to the shift register.  
         [0036]    The PRIORITY USED signal also is provided to the UP input of an up/down counter  104 , having log 2 n bits. Each time a “1” is written to shift register  102 , up/down counter  104  increments one count. The output of shift register  102  is supplied to a DOWN input of up/down counter  104 , such that every a “1” appears at the output of the register, the counter decrements one count. Consequently, up/down counter  104  holds a dynamic average in the priority code category to which the counter is assigned, with respect to the last n routed packets.  
         [0037]    A magnitude comparator  106  connected to up/down counter  104  determines whether the number of packets routed in the assigned priority code category is below or above the percentage bandwidth allocated to that priority code.  
         [0038]    Referring to FIG. 8, an exemplary embodiment of a bandwidth allocation control circuit  110  is illustrated, such as would be provided in bandwidth allocation control circuit  12  of FIGS. 1 and 3, and bandwidth allocation control circuit  36  of FIG. 5. Bandwidth allocation circuit  110  includes the averager  100  of FIG. 7. Averager  100  receives enabled match detection signals by way of AND gate  112 , which also provides signals to one of the priority encoders  4 ,  6 ,  8 ,  10  described above.  
         [0039]    The PRIORITY ALLOWED output of averager  100  is supplied to a decision circuit  116 . In addition, decision circuit  116  receives a indication that the priority is active, along with HIGHER and LOWER PRIORITY ALLOWED signals, the purpose of which is explained below in connection with the decision circuit flow chart.  
         [0040]    [0040]FIG. 9 illustrates an exemplary implementation of the averager in a priority encoder according to the present invention. As shown in FIG. 9, a plurality of priority encoders PRIORITY ENCODER  0  . . . PRIORITY ENCODER n each are implemented as priority encoder  114  of FIG. 8. Matches from CAM words are supplied to a priority encoder  114  in each priority category, and CAM word match activity in each priority category also is supplied to a plurality of averagers  100  associated respectively with each PRIORITY ENCODER  0  . . . n. The usage results from the averagers  100  are supplied to decision circuit  116  for use in bandwidth allocation control determinations.  
         [0041]    An averager  120  having a variable range of averaging according to an alternative embodiment of the present invention is illustrated in FIG. 10. Averager  120  uses a plurality of n-bit shift registers SR 1 -SRm coupled to a multiplexer  122 . Shift registers SR 1 -SRm are arranged in a cascade, such that the output of shift register SR 1  is supplied to shift register SR 2  as well as multiplexer  122 . Similarly, an output signal from shift register SR 2  is provided to shift register SR 3  and multiplexer  122 . The remaining shift registers SR 3 -SRm- 1  are arranged similarly, with the last shift register SRm supplying its output only to multiplexer  122 .  
         [0042]    The output from multiplexer  122  is coupled to the DOWN input of up/down counter  124 , which operates in a manner similar to that of up/down counter  104  discussed above in connection with averager  100 . Thus, up/down counter  124  also receives a PRIORITY USED input, and holds a dynamic average with respect to the last (SR x n) routed packets in the priority code category to which the counter is assigned.  
         [0043]    The range of routed packets (SR x n) over which the dynamic average is taken is determined under control of multiplexer  122 . Depending on the range desired, multiplexer  122  will accept outputs from 1, 2, 3, up to m n-bit shift registers. Thus, the range over which the dynamic average is taken can be adjusted in increments of n bits.  
         [0044]    The output of up/down counter  124  is supplied to magnitude comparator  126 . Thus, averager  120  can replace averager  100  in bandwidth allocation circuit  110  shown in FIG. 8.  
         [0045]    [0045]FIG. 11 illustrates a decision circuit flow chart  140  according to an exemplary embodiment of the present invention. The bandwidth allocation control circuit for an assigned priority code category waits for a new packet at step  142 . When a new packet is pending at step  144  in the category, a determination is made as to whether another packet is being allowed in a higher priority at step  146 . If a higher priority packet is being allowed to be priority encoded by the associated priority encoder, the new packet is not, and the control circuit returns to waiting for new packets at step  142 .  
         [0046]    If no higher priority packet is being allowed for priority encoding, a determination is made as to whether the new packet is within its allocated bandwidth at step  148 . If so, priority encoding of the packet is allowed at step  150 . If not, a determination is made as to whether encoding for a packet is being allowed in a lower priority at step  152 . If not, priority encoding of the new packet is allowed at step  150 . If so, the control circuit returns to waiting for new packets at step  142 .  
         [0047]    Referring to FIG. 12, a processor system  200  is represented which used a CAM  210  employing a priority encoder  211  according to the present invention. Processor system  200  generally comprises a central processing unit (CPU)  202 , such as a microprocessor, that communicates with one or more input/output (I/O) devices  204  over a bus  206 . The processor system  200  also includes random access memory (RAM)  208 . One or more CAM devices  210  also communicate with CPU  202 , CAM  210  utilizing a priority encoder  211  according to the present invention. In the case of a computer implementation for accessing a database, for example, the system may include peripheral devices such as a floppy disk drive  212  and a compact disk (CD) ROM drive  214  which also communicate with CPU  202  over the bus  206 .  
         [0048]    [0048]FIG. 13 illustrates a router  300  including a CAM containing a priority encoder according to an exemplary embodiment of the present invention. Router  300  is connected to a CAM array memory chip  304  as may be used in a communications network, such as, e.g., part of the Internet backbone, or a local area network. Router  300  includes a plurality of input lines and a plurality of output lines. Data transmitted from one location to another is sent in packet form. Prior to the packet reaching its final destination, packet are received devices, such as router  300 , for decoding data identifying the packet&#39;s ultimate destination, and deciding which output line and what forwarding instructions are required for the packet.  
         [0049]    The present invention provides an apparatus and method for allocating encoding multiple simultaneous matches in a CAM. While preferred embodiments of the invention have been described and illustrated above, it should be understood that these are exemplary of the invention and are not to be considered as limiting. Additions, deletions, substitutions, and other modifications can be made without departing from the spirit or scope of the present invention. Accordingly, the invention is not to be considered as limited by the foregoing description but is only limited by the scope of the appended claims.