US 6,606,681 B1Grant
Optimized content addressable memory (CAM)
Issue Date:2003-08-12
•8 Claims
•5 Drawing Sheets
Abstract
A method and apparatus for realizing a content addressable memory. The content addressable memory including an associative memory portion including N entries, each entry including a key and an M-bit type indicator. The content addressable memory further including a random access memory portion. The random access memory portion includes K*N entries where a single key stored as an entry in the associative memory portion is mapped to K entries in the random access memory portion, where K is greater than 1.
Metadata
Assignee
- Cisco Systems, Inc.
Inventor
- Necdet Uzun
Application Information
Application Number:US 09/792,625
Filing Date:2001-02-23
Priority Date:2001-02-23
Art Unit:7
Classifications
IPC:
G06F 1200H04L 1228
Field of Search:
711108370392709238709249
Patent Drawings (5 sheets)
Description
Technical Field
[0002] This invention relates generally to packet switched communication systems.
Background
[0003] With reference to computing systems, memory refers to a place where the computing system holds information, such information able to be accessed and worked on as appropriate. Random Access Memory (RAM) can be used in a personal computer to temporarily store data that is currently being accessed or worked on. Read-only memory can be used for storage of information that does not change. A conventional memory structure includes a memory space of data that includes a plurality of entries, each identifiable by a specific location in the memory space. Each entry has a name (the address) that serves to locate the contents within the memory space.
[0004] An associative memory element, more commonly referred to as content addressable memory (CAM), includes a different structure. CAM element objects are selected based on their contents, not based on their location in the memory space. Each CAM element includes a key and associated data. Examples of associative memory elements include a hash table and set-associative table. A content addressable memory is searched (searching of the keys in the CAM memory space) and returns a data value (data word) upon detecting a valid match condition for a given key. The CAM contains all keys to be compared during a search operation. In a conventional CAM, each key (i.e., entry) in the CAM is associated with a single data word. The association can be by location, that is, entries in the CAM can map directly to data stored in a RAM. As such, the associative data portion of the CAM can be of the form of an actual data word or a pointer to the data word that is associated with the corresponding key.
[0005] In use, a CAM is searched whenever the information associated with a key is needed. A search is performed in the valid portion of the CAM. If a match is detected, a data word associated with the matching key is returned. Where the association is by location, the address of the key is obtained when a match is detected. Using the returned address, data can be read from, for example, a RAM that is used to store the associated data words.
[0006] An example of a conventional CAM including associated RAM for storing data words is shown in FIG. 1a.The CAM 100 includes a plurality of entries 102, each including a valid bit 104 and a key 106. The valid bit is set for each valid entry in CAM 100. Not shown, but associated with each entry in the CAM 100, is an address for a given entry. Data words are stored in an external RAM 108. Data words are located in RAM 108 in accordance with the addresses associated with the given entries (keys) in CAM 100. An external search engine 110 provides keys to be searched for in the information space associated with CAM 100. Thereafter, the valid portion of the CAM 100 (all valid entries) is searched. The address of a matching key is obtained upon detection of a match. The address is in turn forwarded to control logic 111. Control logic 111 uses the address to access the appropriate data word stored in the RAM 108 (the data word associated with the key being searched).
[0007] Another example of a conventional CAM is shown in FIG. 1b,which is used to make forwarding decisions of packets in a router or switch. Each entry 102 in CAM 150 can include a tag 112. The tag 112 is used to designate the entry as being either a source address or destination address. Accordingly, the same key can be stored multiple times in CAM 150 as a source address and as a destination address. Depending on whether the search invoked by search engine 110 is for a destination address or source address, different hits will result in CAM 150 for the same key. The number of entries or blocks in CAM 150 is equal to the sum of the number of source addresses and destination addresses that are to be searched.
[0008] CAM memory tends to be expensive (relative to RAM). As the information base associated with a CAM grows, such as when multiple copies of the same key are included in the CAM, costs rise. What is desired is a means to be able to minimize the CAM size while still realizing the benefits derived from an associative memory structure.
Summary
[0009] In one aspect, the invention provides a content addressable memory including an associative memory portion including N entries, each entry including a key. The content addressable memory further includes a random access memory portion. The random access memory portion includes K*N entries where a single key stored as an entry in the associative memory portion is mapped to K entries in the random access memory portion, where K is greater than 1.
[0010] Aspects of the invention can include one or more of the following features. Each entry in the random access memory portion can be associated with a single key and can include information based on the key type. The type can be a source or destination address. The type can be a MAC address or an MPLS label. Each entry can include an M-bit type indicator, where M is greater than 1. The number of types can be two, source and destination addresses. The content addressable memory can be configured such that K=M.
[0011] In another aspect the invention provides a content addressable memory including an associative memory portion including N entries, each entry including a key and an M-bit type indicator, where M is greater than 1. The content addressable memory further includes a random access memory portion. The random access memory portion includes N entries including K portions where a single key stored as an entry in the associative memory portion is mapped to a single entry in the random access memory including the K portions, where K is greater than 1.
[0012] In another aspect, the invention provides a content addressable memory for storing MAC addresses and MPLS labels and includes an associative memory portion including N entries. Each entry includes a key and an M-bit type indicator, where M is greater than 1. Each key is of the form of a MAC address or MPLS label or both as indicated by the type indicator. The content addressable memory further includes a random access memory portion. The random access memory portion including K*N entries where a single key stored as an entry in the associative memory portion is mapped to up to K entries in the random access memory portion, where K is greater than 1.
[0013] In another aspect, the invention provides a method for storing MAC addresses in a content addressable memory. The content addressable memory includes an associative portion and a random access portion. The associative portion includes one or more entries each including an address. The random access portion is operable to store information relevant to each address. The method includes associating a single address with plural entries in the random access memory when the single address is maintained in the associative portion of the content addressable memory for two different contexts, one dependent on whether the address is a source address and one dependent on whether the address is a destination address.
[0014] In another aspect, the invention provides a method for storing MAC addresses in a content addressable memory. The content addressable memory includes an associative portion and a random access portion. The associative portion includes one or more entries each including an address. The random access portion is operable to store information relevant to each address. The method includes determining if an address is present in the associative portion for a first context, either as a source address or destination address. If the address is present, marking the address in the associative portion to indicate that the address is to be associated with a second context. Information relevant to the second context and associated with the address is added to the random access portion including mapping the address to relevant information stored in the random access portion associated with the first context and the second context.
[0015] In another aspect, the invention provides a method for storing MAC addresses and MPLS labels in a content addressable memory. The method includes determining if a key is present in a first entry in the associative portion for a first context, either as a source address or destination address or both. If so, a portion of the key to be associated with an MPLS label is located. A same portion for all other keys in the content addressable memory is checked to see if the portion matches. If not, the address in the associative portion of the first entry is marked to indicate that the address is to be associated with a second context, the second context being an MPLS label. Information relevant to the second context and associated with the address is added to the random access portion including mapping the address to relevant information stored in the random access portion associated with the first context and the second context.
[0016] Aspects of the invention can include one or more of the following features. If the portion matches, a second portion of the key to be associated with a second MPLS label is located. A same portion for all other keys in the content addressable memory is checked to see if the second portion matches. If not, the address in the associative portion is marked to indicate that the address is to be associated with a second context, the second context being an MPLS label. Information relevant to the second context and associated with the address is added to the random access portion including mapping the address to relevant information stored in the random access portion associated with the first context and the second context.
[0017] Aspects of the invention can include one or more of the following advantages. An optimized CAM is proposed that minimizes the CAM portion of a device at the expense of an external RAM portion of the device. The RAM portion of the device associated with the optimized CAM can be scaled up to accommodate a larger information base while keeping the associated CAM portion of the device the same size or smaller. The optimized CAM can include multi-use elements. The multi-use elements allow the optimized CAM to exploit the whole of the information base to be stored and searched while minimizing the number of entries required to support such operations. The optimized CAM provides a means to combine the search space for the information base to include both Ethernet MAC addresses and MPLS labels. The optimized CAM provides silicon area saving as well as saving in search time with respect to conventional CAM solutions for the same size of search information base. The optimized CAM enables supporting a mix of Ethernet type and MPLS type packets in the same network. One application of the optimized CAM is to implement a resilient packet ring media access controller (MAC). A resilient packet ring MAC provides functionality to allow spatial reuse of bandwidth and resiliency in a ring-based media. The resilient packet ring MAC can operate with Ethernet/802.3 and MPLS packets.
[0018] The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims.
Description of Drawings
[0019] FIG. 1ais a block diagram of a conventional CAM.
[0020] FIG. 1bis a block diagram of another conventional CAM.
[0021] FIG. 2ais a block diagram of a lookup block including an optimized CAM block.
[0022] FIG. 2bis a block diagram of an optimized CAM block.
[0023] FIG. 2cis a block diagram of a data structure stored in the optimized CAM block of FIG. 2b.
[0024] FIG. 2dis a block diagram of a data structure for an entry in the status memory of FIG. 2b.
[0025] FIG. 2eis a block diagram of a data structure for a virtual entry in the status memory of FIG. 2b.
[0026] FIG. 3 is a block diagram for an alternative data structure stored in the optimized CAM block of FIG. 2bfor supporting MAC addresses and MPLS labels.
[0027] FIG. 4 is a block diagram for an alternative data structure stored in the optimized CAM block of FIG. 2bfor supporting MAC addresses and plural MPLS labels.
[0028] Like reference symbols in the various drawings indicate like elements.
Detailed Description
[0029] An optimized CAM is presented for use in plural digital switching applications. The optimized CAM can be used in conjunction with a Spatial Reuse Protocol (SRP) [RFC2892] forwarding block in a node of a network ring. The SRP forwarding block can be used to decide what traffic to add to the ring. The optimized CAM can be used in association with a lookup block of the SRP forwarding block. The lookup block performs searches for packets and returns relevant information. The relevant information can include decision information as to whether to pass a given packet using the SRP forwarding block to the ring or alternatively redirect the packet to a host associated with a respective node. The lookup block can be used for other operations (other than forwarding or filtering) such as for accounting, billing, traffic management or legacy operations.
[0030] Look-Up Block
[0031] Referring now to FIG. 2a,a lookup block 200 includes an optimized CAM block 202, control logic 204 and memory 206.
[0032] Data packets enter optimized CAM block 202 and the address for each packet is extracted from the packet header and provided as a search string to a CAM. A hit is made if there is a match with a key stored in the CAM. Optimized CAM block 202 provides as an output a hit indication on hit signal line 208 and associated status bits on status bus 210 to control logic 204. Details of the optimized CAM block 202 are described in greater detail below in association with FIGS. 2band 2c.
[0033] Control logic 204 receives the hit signal and associated status bits on hit signal line 208 and status bus 210. Control logic 204 is used to monitor the optimized CAM block 202 output including to count the number of times an address in the CAM has been matched, and the number of bytes in the matched packets. Control logic 204 provides as an output a destination address match signal 222, source address match signal 224, byte counter signal 226 and a packet counter signal 228 to convey accounting information to a next block in the system.
[0034] Memory 206 stores accounting information associated with lookup block 200. In one implementation, memory 206 is a dual bank SRAM (1024 words×144 bits SRAM) and is used to store the number of times an address in the CAM has been matched as well as the accumulated number of bytes in the matched packets. In one implementation, memory 206 is sized to store 1024 entries of 144 bits per entry. In this implementation, bits 0 through 71 are associated with source addresses while bits 72 through 143 are associated with destination addresses. The 144-bit entries can be stored in two banks of 1024 words×72 bits where the most significant bit of the address chooses the bank (e.g., Bank 0 is for Source Addressee [SA] and Bank 1 is for Destination Addressee [DA]).
[0035] Optimized CAM Block
[0036] Optimized CAM block 202 is shown in more detail in FIG. 2band includes a packet processing engine 252, CAM control logic 254, CAM (information space) 256, status memory 258, flip-flops 260 and selectors 262. Optimized CAM block 202 finds matches between addresses contained in a packet with that of the addresses associated with a given node (and stored in CAM 256).
[0037] Packet processing engine 252 receives as an input packets for processing and operates to extract address information from each packet. Packet processing engine 252 forwards the extracted address information in the form of a search string to CAM control logic 254 via selector 262a.
[0038] CAM control logic 254 receives search strings for processing and includes means for initiating and controlling searches of the information stored in CAM 256. CAM control logic 254 also receives masking information through selector 262bfor use in masking portions of a key when executing a search. Masking search strings is described in greater detail below. CAM control logic 254 configures CAM 256 into its operational modes (access and search modes), the details of which are described in greater detail below. In addition, CAM control logic 254 controls reset, read, write and probe operations. CAM probe operations can be invoked to check that the CAM search routine is operational (during prototype testing) or during normal operations to determine if an address exists in the CAM 256. CAM control logic includes plural registers for use in loading search strings and keys as well as controlling the operation of CAM 256.
[0039] CAM 256 is the repository of keys. CAM 256 includes one or more entries each including a key. Each entry in CAM 256 includes location data designating where in the information space associated with CAM 256 an entry is located. The location data, or address for the entry, maps to status bits stored at a complementary location in status memory 258. The structure and contents of status memory 258 is described in greater detail below. A data structure for entries stored in CAM 256 is shown in FIG. 2c.Each entry 270 includes a tag with source/destination address bits 272 and a key 274. In one implementation, the source/destination address bits 272 are two binary bits and indicate if the associated key entry (address) is a source or destination address or both. This aids in the searching of CAM 256 as will be described in greater detail below. In one implementation, the source/destination bits 272 are set as described in Table 1.
| TABLE 1 |
|---|
| Source/Destination Address bits |
[0040] Key 274 can be a 48 bit MAC address. Alternatively, key 274 can be an MPLS label or tag. The use of MPLS labels is described in greater detail below. In one implementation, there is no restriction on the ratio of source addresses compared to destination addresses stored in CAM 256. In one implementation, CAM 256 is sized to store a maximum of 1024 different 48-bit MAC Addresses (1024 words by 52 bits, where two bits are used for DA/SA, 48 for MAC address and two bits are unused).
[0041] CAM 256 includes a valid bit (not shown) associated with each address location. Whenever a full reset or address location reset occurs, the valid bit is un-set. Operationally, CAM 256 only examines entries having a valid bit that is set. The valid bit is set when data is written to a given address location.
[0042] CAM 256 includes a search routine (not shown). The search routine is invoked upon receipt of a search string from CAM control logic 254. The search routine compares the search string to the CAM's key entries, masking bits in accordance with any received masking information, and returns an address for a matching entry as an output. CAM 256 operates in two modes, search and access. In search mode, CAM 256 operates on search strings received from CAM control logic 254 and locates matching keys and their associated status address information as described above. In access mode, CAM 256 operates as a RAM, and can be read from or written to using conventional address and data busses (not shown) supported by CAM 256.
[0043] Status memory 258 can be of the form of an SRAM. Status memory 258 includes information status bits associated with the keys in CAM 256. Each address location in the CAM 256 has a direct relationship with the data stored in the status memory 258 (e.g., the address stored in CAM location 0×25 has its corresponding status bits stored in the status memory at location 0×25). The hit address determined in a search of CAM 256 for a given key is provided to status memory 258 so that the associated status information (bits) can be fed into the next block (the control logic block 204) of the device. In one implementation, the data structure for an entry stored in status memory 258 is four binary bits (0:3). In this implementation, bit 0 is associated with destination addresses, while bits (1:3) are associated with source addresses. Forwarding decisions for the packet are determined based on the values of the status bits. The status bits are set up in accordance with the information described in Table 2.
| TABLE 2 |
|---|
| Status Bits |
[0044] As described above, status memory 258 includes entries with portions (bits) associated with each of source addresses and destination addresses, respectively. Control logic 204 and other portions of the device read/use the appropriate portions of the status bits. In the example above, if the address being searched is a destination address, then only bit 0 of the status bits is read, the remaining bits being ignored. Conversely, if the address being searched is a source address, status bits (1:3) are used, with bit 0 being ignored.
[0045] The configuration described above should not be construed as limiting. In the example above, where each key can be either a source or destination address or both, a single entry stored in CAM 256 is mapped to plural chunks of status information that are in turn stored in an entry in status memory 258. The “entry” in status memory 258 can be sized in accordance with the information required to be stored. The entry includes plural portions (i.e., one portion associated with each chunk of status information (e.g., one portion for the relevant source address information and one for the relevant destination address information)), each of which can include plural bits, bytes or words of data. Referring now to FIG. 2d,a general block diagram for an entry in status memory 258 is shown. Each entry 275 includes first and second portions 276 and 277, respectively. In the implementation described above, the first portion can be dedicated to include relevant information for destination addresses and be sized to be one bit in length, while the second portion can be dedicated to include relevant information for source addresses and be sized to be three bits in length. Status memory 258 can have a width (in words or bytes or bits) to accommodate the information that is required to be stored for each of the different types of keys (e.g., source address, destination address) stored in CAM 256. Status memory 258 can dedicate any number of bits/bytes/words to each key type for a given entry.
[0046] Status memory 258 includes a one-to-one mapping of entries in CAM 256 with an entry in the status memory 258. As described above, each entry includes two (or more, as described below) portions. Which portions are relevant depends on the type of address being searched (for example, source or destination).
[0047] In one implementation, each entry in CAM 256 is associated with plural locations (forming a single “virtual entry”) in status memory 258. For example, referring now to FIG. 2e,each entry in CAM 256 can be associated with a virtual entry 280 in status memory 258 and include two (or more) contiguous words 282. Logic can be included to map the address provided from CAM 256 to the tuple (or other defined set of words) stored in status memory 258. Which word of the tuple (or set) is read, can depend on the type of address being searched for. In this example, CAM 256 includes N addressable entries, while status memory 258 includes K*N physical addressable entries (corresponding to N virtual entries). Accordingly, optimized CAM block 202 provides a 1 to N mapping from entries in CAM 256 to relevant information stored in a respective entry or “virtual entry” of status memory 258. Mapping schemes are described in greater detail below.
[0048] Referring again to FIG. 2b,flip flops 260a-bprovide a delayed and synchronized hit status signal for output by optimized CAM block 202 to control logic 204 of FIG. 2a.The hit status and status address, can also be provided directly to a microcontroller.
[0049] a. Searching
[0050] The search for a destination address includes setting the CAM mask and search bits as appropriate (the DA search bit to ‘1’, and the SA bit to ‘0’) provided from CAM control logic 254, and applying the extracted destination address received from the packet processing engine 252 to search bits [47:0]. If a match is made (and DAH Status bit=1), the destination match address signal 222 is held high for the entire packet.
[0051] The search for a source address includes setting the CAM mask and search bits as appropriate (the DA search bit to ‘0’, and the SA bit to ‘1’) provided from CAM control logic 254, and applying the extracted source address received from the packet-processing engine 252 to search bits [47:0]. If a match is made, the source address match signal 224 is held high for the entire packet (SAM Status Bit is not required).
[0052] b. Adding Entries to the CAM 256
[0053] When a new Ethernet entry (MAC address) for a destination address (or source address) needs to be added to the CAM 256, the full address is searched in the CAM 256 for a possible existing source address (destination address) entry with the same value. If a matching entry is found, the same entry (location) is used for both the source and destination address. The source/destination bits are set to indicate that the entry is both a source and destination address. In addition, the relevant destination information (source information) can be provided and stored in the status memory as appropriate.
[0054] MPLS Labels and Ethernet addresses
[0055] As described above, the optimized CAM block 202 can include a mapping from each CAM 256 entry (N entries in total) to plural physical entries (K*N) in status memory 258. In the implementation described, each of the physical entries in status memory 258 corresponded to relevant information associated with a particular type of key stored in CAM 256. Addresses of different types can be stored in CAM 256. The example above described source and destination addresses as might be associated with Ethernet packets. However, other packet formats can be supported. For example, MPLS labels can be stored in CAM 256 along with Ethernet source and destination addresses. An alternative data structure associated with entries in CAM 256 is shown in FIG. 3. Each entry 300 includes tag bits 302 and a key 304. The tag bits indicate the type of key stored. In one implementation, tag bits 302 can include 3 bits for designating whether the key (address) stored in CAM 256 for a given entry is a source address, destination address, both and/or an MPLS label. In one implementation, two source/destination address bits 306 are included and indicate if the associated key entry (address) is a source or destination address or both. In one implementation, the source/destination bits are set as described in Table 1. Tag 302 also includes a single MPLS label bit 308 to indicate that the address stored is an MPLS label.
[0056] Conventional MPLS labels are 20 bits in length, while Ethernet source or destination addresses are sized to be 48 bits. When used as an MPLS label, CAM 256 only evaluates 20 bits of a given key. In one implementation, the relevant 20 bits are the first twenty bits of the key. Alternatively, the last twenty bits or some other combination of bits can be identified as being relevant for evaluation when searching for an MPLS label. Table 3 includes a description for how to set the tag bit values for a combined Ethernet address and MPLS label information space.
| TABLE 3 |
|---|
| Source/Destination Address/MPLS label bits |
[0057] Key 304 can be a 48 bit MAC address or an MPLS label or both. Key 304 can be both an MPLS label and a MAC address where its length is 48 bits, and where 20 of the bits are associated with an MPLS label. In one implementation, there is no restriction on the ratio of source addresses compared to destination addresses or MPLS labels stored in the CAM 256. In one implementation, CAM 256 is sized to store a maximum of 1024 different 48-bit MAC Addresses or MPLS label (1024 words by 52 bits, where three bits are used for DA/SA/MPLS, 48 for MAC address or MPLS label and one bit is unused). As described above, CAM 256 can include a valid bit associated with each address location.
[0058] Where, as here, CAM 256 includes three types of entries (source address, destination address and MPLS label), status memory 258 is appropriately sized (3*N) to include a physical entry (or portion of a wide entry) that is relevant to each type of key (address). Again, a mapping from a hit address presented by CAM 256 to a relevant portion of an entry, or to a physical entry in a larger virtual entry in status memory 258 may be required. Alternatively, only the relevant portion of an entry in status memory 258 may be read and passed to a next block in the system. In one implementation, CAM 252 includes 1024 entries and a status memory 257 is composed of a 3072 entry RAM (or 1024 triple-entry RAM) to support a fully populated and integrated MAC address and MPLS label information space.
[0059] a. Operation
[0060] When an Ethernet packet arrives, its destination (or source address) is extracted from the packet header. The search for destination address (or source address) is performed by selecting (using masking of individual CAM bits) the valid bit, appropriate tag bits 302 (3 bits) and the key 304 (48 bits) and applying destination address (or source address) at the search input of the CAM 256. If there is a hit, the index (hit address) output of the CAM 256 is used as the read address of the RAM to read the corresponding data entry from status memory 258.
[0061] When an MPLS packet arrives, the search for a matching MPLS label includes selecting (using masking of individual 20 CAM bits) the appropriate tag bit 302 (3 bits) and the key 304 (20 bits). Upon a hit, the relevant information (the corresponding data entry) from status memory 258 is read.
[0062] b. MPLS label selection
[0063] When a new MPLS label needs to be assigned to a new connection, the MPLS label can be chosen in a way that its 20 bit value matches to a predetermined portion (as many bits as the size of an MPLS label—20 bits) of an existing source address/destination address (48 bits) already stored in the CAM 256. This can be accomplished since MPLS labels have no global meaning and can be chosen independently by a local node according to its label resources.
[0064] MPLS labels may be assigned as outlined above using source address and destination address values starting from the top of the CAM 256 if there is at least one Ethernet entry present. The tag bits 302 associated with the selected entry are set to indicate that the entry can also be an MPLS label by setting tag bit 308. A pointer (not shown) can be used to remember the last used location. The next time an MPLS label is needed, the same process is repeated starting from the pointer location if there is at least one unassigned Ethernet entry in CAM 256. Otherwise, an unused number can be assigned randomly or using any other method. When an unused number is assigned, the unused number is added to CAM 256 as a new entry.
[0065] Before committing to a mapping between a source address/destination address entry and a 20 bit MPLS label (i.e., one entry is to serve as both a source/destination address and an MPLS label), a search for the 20 bit MPLS label value is performed over the remaining portion of the CAM 256 information space. If plural hits arise (i.e., hit address is different than the address of the proposed MPLS label), then the proposed MPLS label is not unique in the information space, and as such another Ethernet entry is selected.
[0066] c. Adding Entries to the CAM 256
[0067] When a new Ethernet entry for a destination (source) address needs to be added to the CAM 256, the first full address is searched in the CAM 256 for a possible existing source (destination) address entry with the same value. If it is found, the same location is used for both. If it is not found, a new search in the CAM 256 for a possible existing MPLS label with the same 20 bit value is performed. If a matching MPLS label is found, the same location is used for the destination (source) address entry as well. If there is no match found in the CAM 256, this new destination (source) address entry is inserted to an empty location by writing the destination address into the key field 304, setting the valid bit to valid, and setting tag bits 308 to an appropriate value (e.g., 100 for a destination address or 010 for a source address).
[0068] If CAM 256 becomes almost full with source/destination address and MPLS entries and if there are unmapped source addresses or destination address entries, some of the existing unmapped MPLS entries can be reassigned so that they map to a previously unmapped source/destination address. The change can be communicated to the downstream node so that labels are swapped correctly. Note that while a change is being communicated to the downstream node, both the new and old MPLS labels should be kept in the CAM 256. Right after a confirmation is received, the old value can be removed from the CAM 256.
[0069] Plural MPLS Labels
[0070] In one implementation, plural MPLS labels can be mapped to a single source/destination address. An alternative data structure associated with entries in CAM 256 that include plural MPLS labels is shown in FIG. 4. Each entry 400 includes tag bits 402 and a key 404. The tag bits indicate the type of key stored. In one implementation, tag bits 402 can include 4 bits for designating whether the key (address) stored in CAM 256 for a given entry is a source address, destination address or both and whether the entry includes one or two MPLS labels. In one implementation, two source/destination address bits 406 are included and indicate if the associated key entry (address) is a source or destination address or both. In one implementation, the source/destination bits are set as described in Table 1. Tag 402 also includes two MPLS label bits 408 to indicate that the address stored includes one or two MPLS labels.
[0071] As described above, conventional MPLS labels are 20 bits in length, while Ethernet source or destination addresses are sized to be 48 bits. When used as an MPLS label, only 20 bits of the key are evaluated. Accordingly, a key can include a single source or destination address or can accommodate up to two MPLS labels. When searching for an MPLS label, CAM 256 only evaluates the relevant 20 bits of a given key associated with an MPLS label. In one implementation, the first 20 bits are used for a first MPLS label and the last 20 bits are used for the second MPLS label. Alternatively, some other combination of bits can be identified as being relevant for evaluation when searching from among the two embedded MPLS labels. Table 4 includes a description for how to set the tag bit values for a combined Ethernet address and MPLS label information space where two MPLS labels can be included in a single entry.
| TABLE 4 |
|---|
| Source/Destination Address/multiple MPLS tag bits |
[0072] Key 404 can be a 48 bit MAC address or up to two MPLS labels or both. Key 404 can be both an MPLS label and a MAC address where its length is 48 bits, and where 20 (or 40) of the bits are associated with MPLS label(s). In one implementation, there is no restriction on the ratio of source addresses compared to destination addresses or MPLS labels stored in the CAM 256. In one implementation, CAM 256 is sized to store a maximum of 1024 different 48-bit MAC Addresses or MPLS labels (1024 words by 52 bits, where four bits are used for DA/SA/MPLS1/MPLS2 and 48 for MAC address or MPLS labels). As described above, CAM 256 can include a valid bit associated with each address location.
[0073] Where, as here, CAM 256 includes four types of entries (source address, destination address, MPLS label 1 and MPLS label 2), status memory 258 is appropriately sized (4*N) to include a physical entry (or portion of a wide entry) that is relevant to each type of key (address). Again, a mapping from a hit address presented by CAM 256 to a relevant portion of an entry, or to a physical entry in a larger virtual entry in status memory 258 may be required. Alternatively, only the relevant portion of an entry may be read and passed to a next block in the system. In one implementation, CAM 252 includes 1024 entries and a status memory 258 composed of a 4096 entry RAM (or 1024 quadruple-entry RAM) to support a fully populated and integrated MAC address and MPLS label information space.
[0074] a. Searching
[0075] As before, when an Ethernet packet arrives, its destination (or source address) is extracted from the packet header. The search for destination address (or source address) is performed by selecting (using masking of individual CAM bits) the valid bit, appropriate tag bit 402 (4 bits) and the key 404 (48 bits) and applying destination address (or source address) at the search input of the CAM 256. If there is a hit, the index (hit address) output of the CAM 256 is used as the read address of the RAM to read the corresponding data entry from status memory 258.
[0076] When an MPLS packet arrives, the search for the MPLS label is performed by selecting (using masking of individual CAM bits) the appropriate tag bit 402 (4 bits) and the key 404 (20 bits), first in a portion designated for storing a first MPLS label (i.e., MPLS1 space), then, if no hit is detected, in a second portion designated for storing a second MPLS label (i.e., MPLS2 space). Upon a hit, the relevant information (the corresponding data entry) from status memory 258 is read.
[0077] b. MPLS label selection
[0078] When a new MPLS label needs to be assigned to a new connection, the label is chosen in a way to match with one of two predetermined 20-bit portions of an existing source/destination address (48 bits) in CAM 256. Selecting and mapping labels is as described above.
[0079] c. Adding Entries to the CAM 256
[0080] Entries can be added to CAM 256 as described above.
[0081] d. Multiple Hits
[0082] Note that there may be multiple hits in MPLS searches if precaution is not taken when labels are assigned since an MPLS label is shorter than a MAC address (i.e., 20 bit portions of two MAC addresses may be equal). Either of the following three techniques can be used to resolve the multiple hit problem.
[0083] In a first technique, a multiple hit signal can be added to CAM 256. The multiple hit signal indicates that there are at least two matches when a search is performed. Note that multiple hits should not happen when a new MAC address is inserted since a probe should happen prior to an insertion. However, a multiple hit may happen in the MPLS portion of the CAM 256, whenever a new MAC address is inserted. When a probe in MPLS label portion(s) of a new MAC address indicates a multiple hit, the MPLS labels should be reassigned using the method described above before the new MAC entry is inserted. This way the MPLS searches will never result in a multiple hit later on.
[0084] In the second technique, CAM 256 does not need a multiple hit signal. Before adding a new entry, CAM 256 reads and compares the CAM information space to determine if there will be a multiple hit after adding the new entry. If there is no multiple hit, the compare operation will produce no results (and accordingly a multiple hit would not arise if the proposed entry were added). If the compare operation does not produce a hit, then the label can be assigned or added. If the new MAC entry will produce a multiple hit, the multiple hit can be resolved by reassigning existing MPLS labels to some other value that does not cause a multiple hit. Any reassignment has to be communicated to the upstream node.
[0085] Normally multiple hits should not happen as MAC addresses tend to be uncorrelated. However, if the same vendor produces multiple nodes in a network at the same time, they are likely to be assigned sequential numbers. When sequential numbers are used, multiple hits can be avoided (or reduced) by intelligently mapping the MAC address filed into 2 MPLS label fields in a way that resulting labels are somewhat randomized. One way of doing that would be using even bits of the MAC address for one label and using odd bits for the other label. Another way of reducing multiple hits is adding a few bits to the key field and concatenating them to the MAC addresses so that these few bits can be chosen (assigned) in a way to eliminate multiple hits in the MPLS label searches.
[0086] A number of embodiments of the invention have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention. Accordingly, other embodiments are within the scope of the following claims.
Claims
Certificate of Correction present
The claims shown below may not include correction changes. Use the corrected PDF for authoritative text.
What is claimed is:
1. A method for storing MAC addresses and MPLS labels in a content addressable memory, the content addressable memory including an associative portion and a random access portion, the associative portion including one or more entries each including a key, the random access portion for storing information relevant to each key, the method comprising:
determining if a key is present in a first entry in the associative portion for a first context, either as a source address or destination address or both;
locating a first key portion of the key to be associated with an MPLS label;
checking first key portion for all other keys in the content addressable memory to see if the first key portion matches;
if the first key portion does not match, marking the address in the associative portion of the first entry to indicate that the address is to be associated with a second context, the second context being an MPLS label; and
adding information relevant to the second context and associated with the address to the random access portion including mapping the address to relevant information stored in the random access portion associated with the first context and the second context.
2. The method of claim 1, further comprising:
if the first key portion matches, locating a second key portion of the key to be associated with a second MPLS label;
checking the second key portion for all other keys in the content addressable memory to see if the second key portion matches;
if the second key portion does not match marking the address in the associative portion to indicate that the address is to be associated with a second context, the second context being an MPLS label; and
adding information relevant to the second context and associated with the address to the random access portion including mapping the address to relevant information stored in the random access portion associated with the first context and the second context.
3. The method of claim 1, wherein the first context corresponds to an Ethernet address.
4. The method of claim 1, wherein the first entry includes two MPLS labels.
5. An apparatus for storing MAC addresses and MPLS labels in a content addressable memory, the content addressable memory including an associative portion and a random access portion, the associative portion including one or more entries each including a key, the random access portion for storing information relevant to each key, the apparatus comprising:
means for determining if a key is present in a first entry in the associative portion for a first context, either as a source address or destination address or both;
means for locating a first key portion of the key to be associated with an MPLS label;
means for checking the first key portion for all other keys in the content addressable memory to see if the first key portion matches;
means for marking, if the first key portion does not match, the address in the associative portion of the first entry to indicate that the address is to be associated with a second context, the second context being an MPLS label; and
means for adding information relevant to the second context and associated with the address to the random access portion including mapping the address to relevant information stored in the random access portion associated with the first context and the second context.
6. The apparatus of claim 5, further comprising:
means for locating, if the first key portion matches, a second key portion of the key to be associated with a second MPLS label;
means for checking the second key portion for all other keys in the content addressable memory to see if the second key portion matches;
means for marking, if the second key portion does not match, the address in the associative portion to indicate that the address is to be associated with a second context, the second context being an MPLS label; and
means for adding information relevant to the second context and associated with the address to the random access portion including mapping the address to relevant information stored in the random access portion associated with the first context and the second context.
7. The apparatus of claim 5, wherein the first context corresponds to an Ethernet address.
8. The apparatus of claim 5, wherein the first entry includes two MPLS labels.
Patent Citations (44)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US3648254(A) | 1972-03-01 | Beausoleil | Applicant |
| US4296475(A) | 1981-10-01 | Nederlof et al. | Applicant |
| US4791606(A) | 1988-12-01 | Threewitt et al. | Applicant |
| US4996666(A) | 1991-02-01 | Duluk, Jr. | Applicant |
| US5088032(A) | 1992-02-01 | Bosack | Applicant |
| US5319763(A) | 1994-06-01 | Ho et al. | Applicant |
| US5383146(A) | 1995-01-01 | Threewitt | Applicant |
| US5440715(A) | 1995-08-01 | Wyland | Applicant |
| US5450351(A) | 1995-09-01 | Heddes | Applicant |
| US5481540(A) | 1996-01-01 | Huang | Applicant |
| US5515370(A) | 1996-05-01 | Rau | Applicant |
| US5740171(A) | 1998-04-01 | Mazzola et al. | Applicant |
| US5841874(A) | 1998-11-01 | Kempke et al. | Applicant |
| US5842040(A) | 1998-11-01 | Hughes et al. | Applicant |
| US5898689(A) | 1999-04-01 | Kumar et al. | Applicant |
| US5920886(A) | 1999-07-01 | Feldmeier | Applicant |
| US5930359(A) | 1999-07-01 | Kempke et al. | Applicant |
| US5956336(A) | 1999-09-01 | Loschke et al. | Applicant |
| US5978885(A) | 1999-11-01 | Clark, II | Applicant |
| US6000008(A) | 1999-12-01 | Simcoe | Applicant |
| US6041389(A) | 2000-03-01 | Rao | Applicant |
| US6047369(A) | 2000-04-01 | Colwell et al. | Applicant |
| US6061368(A) | 2000-05-01 | Hitzelberger | Applicant |
| US6069573(A) | 2000-05-01 | Clark, II et al. | Applicant |
| US6081440(A) | 2000-06-01 | Washburn et al. | Applicant |
| US6091725(A) | 2000-07-01 | Cheriton et al. | Applicant |
| US6097724(A) | 2000-08-01 | Kartalopoulos | Applicant |
| US6134135(A) | 2000-10-01 | Andersson | Applicant |
| US6137707(A) | 2000-10-01 | Srinivasan et al. | Applicant |
| US6141738(A) | 2000-10-01 | Munter et al. | Applicant |
| US6148364(A) | 2000-11-01 | Srinivasan et al. | Applicant |
| US6154384(A) | 2000-11-01 | Nataraj et al. | Applicant |
| US6175513(B1) | 2001-01-01 | Khanna | Applicant |
| US6181698(B1) | 2001-01-01 | Hariguchi | Applicant |
| US6199140(B1) | 2001-03-01 | Srinivasan et al. | Applicant |
| US6236658(B1) | 2001-05-01 | Essbaum et al. | Applicant |
| US6237061(B1) | 2001-05-01 | Srinivasan et al. | Applicant |
| US6240003(B1) | 2001-05-01 | McElroy | Applicant |
| US6243667(B1) | 2001-06-01 | Kerr et al. | Applicant |
| US6246601(B1) | 2001-06-01 | Pereira | Applicant |
| US6295576(B1) | 2001-09-01 | Ogura et al. | Applicant |
| US6307855(B1) | 2001-10-01 | Hariguchi | Applicant |
| US6377998(B2) | 2002-04-01 | Noll et al. | Examiner |
| US2001/0053150(A1) | 2001-12-01 | Clear et al. | Examiner |
Non-Patent Literature (10)
- Jon P. Wade and Charles G. Sodini, “A Ternary Content Addressable Search Engine,” IEEE Journal of Solid-State Circuits, vol. 24, No. 4, Aug. 1989, pp. 1003-1013.Applicant
- Teuvo Kohonen, Content-Addressable Memories, 1987, pp. 128-129 and 142-144, Springer-Verlang, New York.Applicant
- Brian Dipert, ed., “Special-purpose SRAMs Smooth the Ride,” EDN, Jun. 24, 1999, pp. 93-104.Applicant
- “Extending the LANCAM Comparand,” Application Brief AB-N3, Rev. 1.0a Draft, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 4 pages.Applicant
- “Advantges of CAM in ASIC-Based Network Address Processing,” Application Brief AB-N11, Rev. 1.2a Draft, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 4 pages.Applicant
- “Virtual Memory Applications of the MU9C1480A LANCAM,” Application Note AN-N3, Rev. 1a, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 12 pages.Applicant
- “Using the MU9C1965A LANCAM MP for Data Wider than 128 Bits,” Application Note AN-N19, Rev. 1a, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 16 pages.Applicant
- “Fast IPv4 and IPV4 CIDR Address Translation and Filtering Using the MUAC Routing CoProcessor (RCP),” Application Note AN-N25, Rev. 0a, Music Semiconductors, Milpitas, CA, Oct. 1, 1998, 16 pages.Applicant
- “Using MUSIC Devices and RCPs for IP Flow Recognition,” Application Note AN-N27, Rev. 0, Music Semiconductors, Milpitas, CA, Oct. 21, 1998, 20 pages.Applicant
- “Wide Ternary Searches Using Music CAMs and RCPs,” Application Note AN-N31, Rev. 0, Music Semiconductors, Milpitas, CA, Apr. 13, 1999, 8 pages.Applicant