Power efficient and rule movement optimized TCAM management

A network device allocates a number of blocks of memory in a ternary content-addressable memory (TCAM) of the network device to each database of multiple databases, and assigns unused blocks of memory of the TCAM to a free pool. The network device also detects execution of a run mechanism by the TCAM, and allocates, based on the execution of the run mechanism, one of the unused blocks of memory to a filter or rule of one of the multiple databases.

BACKGROUND

Computing and communication networks typically include network devices, such as routers, firewalls, switches or gateways, which transfer or switch data, such as packets, from one or more sources to one or more destinations. Network devices may operate on the packets as the packets traverse the network, such as by forwarding or filtering the packet-based network traffic.

A ternary content-addressable memory (TCAM) is commonly used in network devices and other communication devices for quickly identifying content within a packet. A network device may support a number of different features, such as a network device that functions as both a router and a firewall or a router capable of routing both Internet protocol, version 4 (IPv4) and IPv6 routing prefixes. A single TCAM device may be used to support multiple features. With the increasing number of features requiring TCAM support, such as various security and firewall features, deep packet inspection, routing, and tunnel termination features, sharing of a TCAM space can be a cost effective solution for many designs.

A TCAM may be programmed for various types of access control lists (ACLs) (e.g., port ACLs, virtual local area network (VLAN) ACLs, route ACLs, etc.) for both ingress and egress. An ACL may include a set of rules that are explicitly programmed by a network administrator or implicitly programmed by protocols. Each type of ACL is associated with a lookup which corresponds to a database stored in the TCAM. Each database logically belongs to one or more blocks of memory space in the TCAM. With static allocation of the size of each database in the TCAM (e.g., during initialization), a network device or components of a network device are limited by the database size. For example, some databases may overflow with information while other databases may be empty.

Updating an ACL (e.g., adding or deleting a single rule) leads to a large number of rule movements in the TCAM because of the order dependency of the rules. A run mechanism may be used to minimize movement of TCAM rules while updating an ACL. The run mechanism achieves this by maintaining details associated with the run mechanism and by sprinkling (e.g., putting spaces between) rules among available TCAM space (e.g., for a database or for the entire TCAM). The run mechanism can prevent rule movements, but the inherent behavior of sprinkling rules (e.g., throughout an entire TCAM memory space) is very inefficient in terms of power consumption. Power consumed by the TCAM forms a significant part of the power consumed by many network devices. The power consumed by a TCAM depends on how many blocks of memory (e.g., individual units of memory that need to be part of a TCAM lookup cycle) are enabled for lookup.

SUMMARY

According to one aspect, a method, implemented by a network device, may include allocating, by the network device, a number of blocks of memory in a ternary content-addressable memory (TCAM) of the network device to each database of a plurality of databases; assigning, by the network device, unused blocks of memory of the TCAM to a free pool; detecting, by the network device, execution of a run mechanism by the TCAM; and allocating, by the network device and based on the execution of the run mechanism, one of the unused blocks of memory to a filter or rule of one of the plurality of databases.

According to another aspect, a network device may include a memory to store a plurality of instructions, and store a TCAM. The network device may also include a processor to execute instructions in the memory to allocate a number of blocks of memory in the TCAM to each database of a plurality of databases, and assign unused blocks of memory of the TCAM to a free pool. The processor may also execute instructions in the memory to detect execution of a run mechanism by the TCAM, where the run mechanism is configured to add one or more filters or rules to the plurality of databases, and allocate, based on the execution of the run mechanism, one of the unused blocks of memory to a filter or rule of one of the plurality of databases.

According to still another aspect, a device may include a TCAM, and a processor to allocate a number of blocks of memory in the TCAM to each database of a plurality of databases, assign unused blocks of memory of the TCAM to a free pool, and detect execution of a run mechanism by the TCAM. The processor may also determine a lowest, based on location, unused block of memory of the TCAM that is greater than a highest, based on location, allocated block of memory of the TCAM assigned to one of the plurality of databases, and allocate, based on execution of the run mechanism, the determined unused block of memory to a filter or a rule of a particular database of the plurality of databases. The processor may further detect underutilization of the TCAM, and reassign, to the free pool, one of the allocated blocks of memory of the TCAM when the TCAM underutilization is detected.

DETAILED DESCRIPTION

Implementations described herein may include systems and/or methods that provide power efficient and rule movement optimized TCAM management for network devices. The systems and/or methods may modify a run mechanism so that rule movements in a TCAM are optimized and so that the TCAM is power efficient (e.g., for a network device containing the TCAM). The run mechanism may be modified since it may be allocated only a portion of the TCAM space, rather than the entire TCAM space (e.g., as is typically done for the run mechanism). The systems and/or methods may also select blocks of memory in the TCAM in such a way that the modified run mechanism is more efficient in rule movement.

The terms “component” and “device,” as used herein, are intended to be broadly construed to include hardware (e.g., a processor, a microprocessor, an application-specific integrated circuit (ASIC), field-programmable gate array (FPGA), a chip, a memory device (e.g., a read only memory (ROM), a random access memory (RAM), etc.), etc.) or a combination of hardware and software (e.g., a processor, microprocessor, ASIC, etc. executing software contained in a memory device).

NETWORK CONFIGURATION

FIG. 1is a diagram of an example network in which systems and/or methods described herein may be implemented. As illustrated, network100may include one or more network devices110interconnected by a network120. Components of network100may interconnect via wired and/or wireless connections or links. Two network devices110and a single network120have been illustrated inFIG. 1for simplicity. In practice, there may be more network devices110and/or networks120. Also, in some instances, one or more of the components of network100may perform one or more tasks described as being performed by another one or more of the components of network100.

Network device110may include a data transfer device, such as a gateway, a router, a switch, a firewall, a network interface card (NIC), a hub, a bridge, a proxy server, an optical add-drop multiplexer (OADM), or some other type of device that processes and/or transfers traffic. In one implementation, network device110may include a device that is capable of transmitting information to and/or receiving information from other network devices110via network120.

Network120may include one or more networks of any type. For example, network120may include a local area network (LAN), a wide area network (WAN), a metropolitan area network (MAN), a telephone network (such as the Public Switched Telephone Network (PSTN), Public Land Mobile Network (PLMN), a wireless network), an intranet, the Internet, an optical fiber (or fiber optic)-based network, or a combination of networks.

AlthoughFIG. 1shows example components of network100, in other implementations, network100may contain fewer components, different components, differently arranged components, or additional components than depicted inFIG. 1.

NETWORK DEVICE CONFIGURATION

FIG. 2illustrates a diagram of example components of network device110. As shown, network device110may include input ports210, a switching mechanism220, output ports230, and a control unit240.

Input ports210may be a point of attachment for a physical link and may be a point of entry for incoming traffic (e.g., packets). Input ports210may carry out data link layer encapsulation and decapsulation. Input ports210may look up a destination address of an incoming packet in a forwarding table to determine its destination port (i.e., route lookup). In some implementations, input ports210may send (e.g., may be an exit point) and/or receive (e.g., may be an entry point) packets.

Switching mechanism220may interconnect input ports210with output ports230. Switching mechanism220may be implemented using many different techniques. For example, switching mechanism220may be implemented via busses, crossbars, and/or shared memories.

Output ports230may store packets and may schedule packets for service on an output link (e.g., a physical link) Output ports230may include scheduling algorithms that support priorities and guarantees. Output ports230may support data link layer encapsulation and decapsulation, and/or a variety of higher-level protocols. In some implementations, output ports230may send packets (e.g., may be an exit point) and/or receive packets (e.g., may be an entry point).

Control unit240may use routing protocols and one or more forwarding tables for forwarding packets. Control unit240may interconnect with input ports210, switching mechanism220, and output ports230. Control unit240may compute a forwarding table, implement routing protocols, and/or run software to configure and manage network device110. Control unit240may handle any packet whose destination address may not be found in the forwarding table.

In one implementation, control unit240may include a bus250that may include a path that permits communication among a processor260, a memory270, and a communication interface280. Processor260may include one or more processors, microprocessors, ASICs, FPGAs, or other types of processing units that may interpret and execute instructions. Memory270may include a RAM, a ROM device, a magnetic and/or optical recording medium and its corresponding drive, and/or another type of static and/or dynamic storage device that may store information and instructions for execution by processor260. Communication interface280may include any transceiver-like mechanism that enables control unit240to communicate with other devices and/or systems.

Network device110may perform certain operations, as described in detail below. Network device110may perform these operations in response to processor260executing software instructions contained in a computer-readable medium, such as memory270. A computer-readable medium may be defined as a physical or logical memory device. A logical memory device may include memory space within a single physical memory device or spread across multiple physical memory devices. The software instructions may be read into memory270from another computer-readable medium, such as a data storage device, or from another device via communication interface280. The software instructions contained in memory270may cause processor260to perform processes that will be described later. Alternatively, hardwired circuitry may be used in place of or in combination with software instructions to implement processes described herein. Thus, implementations described herein are not limited to any specific combination of hardware circuitry and software.

AlthoughFIG. 2shows example components of network device110, in other implementations, network device110may contain fewer components, different components, differently arranged components, or additional components than depicted inFIG. 2. Alternatively, or additionally, one or more components of network device110may perform one or more other tasks described as being performed by one or more other components of network device110.

FIG. 3is a diagram of further example components of network device110. As illustrated, network device110may include a group of input IOCs300-1through300-L (collectively referred to as “input IOCs300” and, in some instances, singularly as “input IOC300”); a group of input PFEs310-1through310-M (collectively referred to as “input PFEs310” and, in some instances, singularly as “input PFE310”); a switching fabric320, a group of output PFEs330-1through330-N (collectively referred to as “output PFEs330” and, in some instances, singularly as “output PFE330”); a group of output IOCs340-1through340-P (collectively referred to as “output IOCs340” and, in some instances, singularly as “output IOC340”); fabrics350; and a TCAM360. As further shown inFIG. 3, input IOCs300may correspond to input ports210(FIG. 2); input PFEs310, output PFEs330, and fabrics350may correspond to switching mechanism220(FIG. 2); and output IOCs340may correspond to output ports230(FIG. 2).

Input IOC300may include an input/output card that may be a point of attachment for a physical link and may be a point of entry for incoming packets to network device110. As shown inFIG. 3, each of input IOCs300may interconnect with multiple input PFEs310(e.g., point-to-multipoint connections), via fabric350. Input IOC300may include a variety of physical interfaces for receiving packets provided to network device110. For example, input IOC300may include one or more Ethernet interfaces with small form-factor pluggable (SFP) connectors, one or more Ethernet interfaces with RJ-45 connectors, one or more Ethernet interfaces with XFP (e.g., 10 Gigabit SFP) connectors, and/or other interfaces.

Input PFE310may include a component that may process incoming packets (e.g., received from input IOC300) prior to transmitting the packets to another PFE (e.g., output PFE330). Input PFE310may also perform route lookup for packets, using forwarding tables, to determine destination information. If the destination information indicates that the packets should be sent to another PFE (e.g., output PFE330) via switching fabric320, then input PFE310may prepare the packets for transmission to the other PFE, if necessary, and may send the packets to the other PFE, via switching fabric320.

Switching fabric320may include a switching component that may allow efficient communication between input PFEs310and output PFEs330. For example, switching fabric320may include a hardwired non-blocking minimal spanning switch capable of connecting T inputs to T outputs in any combination.

Output PFE330may include a component that may process packets (e.g., received from input PFE310via switching fabric320) prior to transmitting the packets to a network (e.g., network120). Output PFE330may also perform route lookup for packets, using forwarding tables, to determine destination information. If the destination information indicates that the packets should be sent out on a physical interface (e.g., one of output IOCs340) connected to output PFE330, then output PFE330may prepare the packets for transmission by, for example, adding any necessary headers, and may transmit the packets to one of output IOCs340.

Fabric350may include a switching component that may allow efficient communication between input IOCs300and input PFEs310and between output PFEs330and output IOCs340. For example, fabric350may include a hardwired non-blocking minimal spanning switch capable of connecting S inputs to S outputs in any combination.

TCAM360may include a CAM, a TCAM, or some other type of content-addressable memory device. A CAM may include a type of associative computer memory that is designed for high-speed searching applications. Unlike standard random access computer memory in which the memory returns a data word based on a supplied address, a CAM may be designed such that, in response to a data word, the CAM may perform a parallel search of its entire memory to determine if that data word is stored. If the data word is found, the CAM may return a list of the storage addresses where the data word was found.

In an implementation, the CAM may particularly be a TCAM. A TCAM may include a CAM that allows states in the CAM to be specified as “don't care” states. For example, a TCAM might have an entry such as “10XX0,” where “X” may indicate the “don't care” state. This entry may match any of the four search keys: “10000,” “10010,” “10100,” or “10110.” TCAM360may be implemented for two entries that are written to TCAM360for each search item: a first entry corresponding to a pattern that is to be matched; and a second “mask” entry that specifies which fields in the first entry are “don't care” states. The first value may be the pattern and the second value may be the mask entry “11001”, where a “0” may indicate that corresponding data in the pattern is to be masked (i.e., it is a “don't care” state).

An address of a highest priority match that corresponds to a particular search key may, after output by TCAM360, be input to an action lookup table to obtain an action corresponding to the match. The action may include, for example, drop (discard) the corresponding data unit, accept (i.e., pass or do not drop) the data unit, increment a counter, or other actions. The action may then be implemented. The priority for the highest priority match may be defined by, for example, lower address values in TCAM360having a higher priority. In other implementations, priority may be defined differently.

In an implementation, TCAM360may include an ACL TCAM that includes multiple databases, and each database may include an ACL. An ACL may include a set of rules that are explicitly programmed by a network administrator or implicitly programmed by protocols. Further details of TCAM360are provided below in connection with one or more ofFIGS. 4A-7B.

AlthoughFIG. 3shows example components of network device110, in other implementations, network device110may contain fewer components, different components, differently arranged components, or additional components than depicted inFIG. 3. Alternatively, or additionally, one or more components of network device110may perform one or more other tasks described as being performed by one or more other components of network device110.

TCAM CONFIGURATIONS AND OPERATIONS

FIGS. 4A-4Eare diagrams illustrating example operations capable of being performed by a run mechanism on TCAM360. The run mechanism may typically work by taking the entire space of TCAM360(e.g., per database), and splitting the space into pages (e.g., into one or more blocks of memory space). As shown inFIG. 4A, TCAM360may be split by the run mechanism into one-hundred pages labeled PAGES 0-99. When adding a rule to TCAM360, the run mechanism may select a page from a largest run (e.g., number of blocks of memory space) available. By doing this, at any given time when inserting a rule in TCAM360, the run mechanism may ensure that a page will be free (e.g., memory space for the rule will be available) without any rule movement within TCAM360. The run mechanism may also add a filter (e.g., filter X) without moving any rules associated with another filter (e.g., filter Y) provided in TCAM360because the pages of TCAM360may be independently managed per filter. In such an arrangement, the run mechanism may utilize all available memory space of TCAM360.

It may be assumed, for example, that four pages of TCAM360are to be allocated for rules of a particular firewall. The run mechanism may execute a first run that allocates a first rule410of the particular firewall to PAGE 50 of TCAM360, as shown inFIG. 4B. After the first run, TCAM360may include free or available space at PAGES 0-49 and PAGES 51-99. The run mechanism may execute a second run that allocates a second rule420of the particular firewall to PAGE 25 of TCAM360, as shown inFIG. 4C. After the second run, TCAM360may include free space at PAGES 0-24, PAGES 26-49, and PAGES 51-99.

The run mechanism may execute a third run that allocates a third rule430of the particular firewall to PAGE 75 of TCAM360, as shown inFIG. 4D. After the third run, TCAM360may include free or available space at PAGES 0-24, PAGES 26-49, PAGES 51-74 and PAGES 76-99. The run mechanism may execute a fourth run that allocates a fourth rule440of the particular firewall to PAGE 12 of TCAM360, as shown inFIG. 4E. After the fourth run, TCAM360may include free space at PAGES 0-11, PAGES 13-24, PAGES 26-49, PAGES 51-74, and PAGES 76-99.

AlthoughFIGS. 4A-4Eshow example operations capable of being performed by the run mechanism on TCAM360, in other implementations, the run mechanism may perform fewer operations, different operations, or additional operations than depicted inFIGS. 4A-4E.

FIG. 5is a diagram of an example portion of TCAM360. As shown, TCAM360may include one or more vendors510-1through510-3(collectively referred to as “vendors510”); one or more instances520-1and520-2(collectively referred to as “instances520”); one or more databases530-1through530-3(collectively referred to as “databases530”); one or more filters540-1and540-2(collectively referred to as “filters540”); and one or more rules550-1through550-3(collectively referred to as “rules550”).

As further shown inFIG. 5, INSTANCE1520-1and INSTANCE2520-2may be associated with VENDOR2510-2. DATABASE1530-1, DATABASE2530-2, and DATABASE3530-3may be associated with INSTANCE1520-1. FILTER1540-1and FILTER2540-2may be associated with DATABASE3530-3. RULE1550-1, RULE2550-2, and RULE3550-3may be associated with FILTER1540-1.

Vendors510may include identifications of vendors that provide one or more devices and/or components of devices provided in network device110. For example, network device110may include ASICs provided by a first vendor (e.g., VENDOR1510-1), FPGAs provided by a second vendor (e.g., VENDOR2510-2), and processors provided by a third vendor (e.g., VENDOR3510-3).

Instances520may include one or more devices and/or components of devices provided in network device110. For example, instances520may include one or more ASICs, one or more FPGAs, and/or other components. Instances520may interconnect with each other and/or with TCAM360via wired or wireless connections.

An ASIC may include an integrated circuit customized for a particular use, rather than intended for a general-purpose use. For example, an ASIC may include a chip designed to execute one or more operations of a device (e.g., input IOC300, input PFE310, etc.) provided in network device110. In an implementation, an ASIC may be associated with TCAM360, with one or more databases stored in TCAM360, etc.

A FPGA may include an integrated circuit designed to be configured by a customer (e.g., “field-programmable”). For example, a FPGA may be configured to execute one or more operations of a device (e.g., input IOC300, input PFE310, etc.) provided in network device110. In an implementation, a FPGA may be associated with TCAM360, with one or more databases stored in TCAM360, etc.

Other components may include one or more devices that may be associated with TCAM360. In an implementation, other components may be associated with one or more databases stored in TCAM360. An example of other components may include an integrated circuit with programmable logic.

Databases530may include local databases and/or global databases. A local database may include a logical entity that may be defined by a set of entries that are searchable during a hardware lookup cycle. In an implementation, a local database may include a database with a unique database identifier (ID) and one or more ACLs (e.g., sets of rules), and whose rules are programmed for a particular component. A global database may include a logical entity that may be defined by a set of entries that are searchable during a hardware lookup cycle. In an implementation, a global database may include a database with a unique database identifier (ID) and one or more ACLs (e.g., sets of rules). Unlike a local database, a global database may include rules that are programmed for every component.

Filters540may include ternary bit strings that are stored in decreasing priority order. Given a packet header, a search for a best matched filter with a highest priority may be performed on all TCAM360entries in parallel. An index of a first matched filter may be used to access memory of TCAM360to retrieve associated data.

Rules550may provide instructions for handling packets (e.g., instructions for handling denial of service (DoS) attacks, etc.). Rules550may be explicitly programmed by a network administrator or implicitly programmed by protocols. Each of rules550may include two components: a rule header and a rule option. The rule header may include one of more fixed fields (e.g., a protocol field, a source Internet protocol (IP) field, a source port field, a destination IP field, a destination port field, etc.). The rule option may provide instructions (e.g., instructions that specify, for example, intrusion patterns to be used to scan a packet).

AlthoughFIG. 5shows example elements of a portion of TCAM360, in other implementations, TCAM360may include fewer elements, different elements, differently arranged elements, or additional elements than depicted inFIG. 5.

FIG. 6is a diagram of example operations capable of being performed by a portion of TCAM360. In one implementation, the entire memory space of TCAM360may not be allocated to the run mechanism since customers may not utilize the entire memory space of TCAM360and/or may utilize a small portion of TCAM's360memory space. If such customers utilized the entire memory space of TCAM360, TCAM360may unnecessarily consume power to minimize rule movement (e.g., via the run mechanism) which may only occur occasionally.

As shown inFIG. 6, TCAM360may include one or more databases610-1through610-3(collectively referred to as “databases610”); one or more filters and/or rules620-1through620-3(collectively referred to as “filters/rules620”); a free pool630of one or more blocks of memory640-1through640-9(collectively referred to as “blocks640”); one or more unused blocks of memory650; and a run mechanism660(e.g., allocated to a portion of TCAM360rather than the entire memory space of TCAM360).

Databases610may include the features described above in connection with databases530. For example, databases610may include local databases and/or global databases. A local database may include a logical entity that may be defined by a set of entries that are searchable during a hardware lookup cycle. In one implementation, a local database may include a database with a unique database identifier (ID) and one or more ACLs (e.g., sets of rules), and whose rules are programmed for a particular component. A global database may include a logical entity that may be defined by a set of entries that are searchable during a hardware lookup cycle. In one implementation, a global database may include a database with a unique database identifier (ID) and one or more ACLs (e.g., sets of rules). Unlike a local database, a global database may include rules that are programmed for every component.

Filters/rules620may include the features described in connection with filters540and rules550. For example, filters620may include ternary bit strings that are stored in decreasing priority order. Given a packet header, a search for a best matched filter with a highest priority may be performed on all TCAM360entries in parallel. An index of a first matched filter may be used to access memory of TCAM360to retrieve associated data. Rules620may provide instructions for handling packets (e.g., instructions for handling DoS attacks, etc.). Each of rules620may include two components: a rule header and a rule option. The rule header may include one of more fixed fields (e.g., a protocol field, a source IP field, a source port field, a destination IP field, a destination port field, etc.). The rule option may provide instructions (e.g., instructions that specify, for example, intrusion patterns to be used to scan a packet).

Free pool630may include a pool of blocks of memory640that may be allocated to one or more databases610and/or one or more filters/rules620. As shown inFIG. 6, block640-1may be allocated to filter/rule620-1(e.g., for storing information associated with filter/rule620-1) of database610-1; block640-5may be allocated to filter/rule620-2(e.g., for storing information associated with filter/rule620-2) of database610-2; and block640-7may be allocated to filter/rule620-3(e.g., for storing information associated with filter/rule620-3) of database610-3. In one implementation, some of blocks640(e.g., unused blocks650) of free pool630may not be allocated to one or more databases610and/or one or more filters/rules620. This may enable TCAM360to minimize power consumption.

Each of blocks640may include an independent unit of memory space (e.g., of any size) that may be turned on or off to save power consumed by TCAM360. In one example, each of blocks640may be one kilobyte in size so that run mechanism660may optimize filter/rule movement in TCAM360and may minimize power consumption by TCAM360. In other examples, each of blocks640may be larger than one kilobyte in size to accommodate filters that are larger than one kilobyte in size.

Run mechanism660may split TCAM360into pages (e.g., one or more blocks of memory space). When adding a rule to TCAM360, run mechanism660may select a page from a largest run available. By doing this at any given time when inserting a rule in TCAM360, run mechanism660may ensure that a page will be free (e.g., memory space for the rule will be available) without any rule movement within TCAM360. Run mechanism660may also add a filter (e.g., filter X) without moving any rules associated with another filter (e.g., filter Y) provided in TCAM360because the pages of TCAM360may be independently managed per filter. However, run mechanism660may be modified so that it utilizes only a portion of the memory space of TCAM360.

In one implementation, run mechanism660may be modified so that no blocks640of free pool630are assigned to run mechanism660initially. When space is required by run mechanism660(e.g., for a rule, filter, and/or database), one of unused blocks650of free pool630may be assigned to run mechanism660, as indicated by reference number670. Based on assignment of unused block650(e.g., block640-4), run mechanism660may have memory space available for rule/filter/database allocation, rule movement may be minimized (e.g., by run mechanism660), and power consumption (e.g., by TCAM360) may be minimized. Block640-4may be added (e.g., by run mechanism660) to a database and may be considered a new run (e.g., having a size of block640-4) that is available to run mechanism660. Depending on the sequence of block640-4in blocks640of free pool630(e.g., allocated to databases610), run mechanism660may seamlessly function with a larger database size. If utilization of TCAM360is determined to decrease, unused blocks640of free pool630(e.g., that were previously allocated to a database610) may be reclaimed by free pool630or may remain allocated to avoid unnecessary rule movement by TCAM360.

AlthoughFIG. 6shows example operations of TCAM360, in other implementations, TCAM360may perform fewer operations, different operations, or additional operations than depicted inFIG. 6.

FIGS. 7A and 7Bare diagrams of further example operations capable of being performed by a portion of TCAM360. As shown inFIGS. 7A and 7B, TCAM360may include databases610, filters/rules620, free pool630of blocks of memory640, unused blocks of memory650, and run mechanism660. Databases610, filters/rules620, free pool630, blocks640, unused blocks650, and run mechanism660may include the features described above in connection withFIG. 6.

TCAM space is typically divided into multiple databases for isolating the databases during parallel searches. The order in which blocks of a TCAM are assigned to a database may need to be tracked so that if there are multiple matches returned during a parallel search, a lowest index from a lowest block may be returned. Based on this restriction, how a block is assigned or unassigned in the modified run mechanism may reduce unnecessary rule movement in TCAM360(e.g., during allocation or de-allocation of blocks640). If TCAM360randomly selects (e.g., for run mechanism660) a block640from free pool630(e.g., as was done inFIG. 6) and run mechanism660appends the randomly selected block640to a database, one or more rules of TCAM360may need to be moved to maintain the order (e.g., the precedence) of blocks in TCAM360.

Although any one of unused blocks650of free pool630may be assigned to run mechanism660, as shown inFIG. 6, run mechanism660may be further modified to ensure that rule movement in TCAM360is minimized. When space is required by run mechanism660(e.g., for a rule, filter, and/or database), as shown inFIG. 7A, this may be accomplished by assigning, to run mechanism660a lowest block number of unused blocks650that is above a highest block640allocated to databases610, as indicated by reference number710. For example, since block640-7is the highest block640allocated to databases610and block640-8is the lowest unused block650above block640-7, run mechanism660may be assigned block640-8(e.g., for allocating to a rule, filter, and/or database). In such an arrangement, the addition of unused block650of free pool630(e.g., block640-8) to run mechanism660may not cause rule movement in TCAM360(e.g., to accommodate block640-8).

In one implementation, if there is no unused block650that is above a highest block640allocated to databases610(e.g., so as to avoid rule movement in TCAM360), run mechanism660may be assigned the smallest unused block650(e.g., block640-2) in free pool630. This may minimize the probability of rule movement for any future requests for unused blocks650of free pool630.

With reference toFIG. 7B, when a block640allocated to one of databases610is to be used by another one of databases610, TCAM360may select a highest block640assigned to one of databases610, as indicated by reference number720. For example, since block640-7is the highest block640assigned to one of databases610, block640-7may be freed for use by other databases610, as indicated by reference number730. In one implementation, block640-7may be reassigned to free pool630when TCAM360requires extra space. In another implementation, block640-7may be immediately reassigned to free pool630. Such an arrangement may ensure that rule movement in TCAM360is minimized.

AlthoughFIGS. 7A and 7Bshow example operations of TCAM360, in other implementations, TCAM360may perform fewer operations, different operations, or additional operations than depicted inFIGS. 7A and 7B.

EXAMPLE PROCESS

FIGS. 8-10are flow charts of a process800for providing power efficient and rule movement optimized TCAM management according to implementations described herein. In one implementation, process800may be performed by network device110. In another implementation, some or all of process800may be performed by one or more components (e.g., control unit240) of network device110.

As illustrated inFIG. 8, process800may include allocating a particular number of blocks of memory in a TCAM to each database of multiple databases (block810), and assigning unused blocks of memory to a free pool (block820). For example, in implementations described above in connection withFIG. 6, free pool630may include a pool of blocks of memory640that may be allocated to one or more databases610and/or one or more filters/rules620. Block640-1may be allocated to filter/rule620-1(e.g., for storing information associated with filter/rule620-1) of database610-1; block640-5may be allocated to filter/rule620-2(e.g., for storing information associated with filter/rule620-2) of database610-2; and block640-7may be allocated to filter/rule620-3(e.g., for storing information associated with filter/rule620-3) of database610-3. In one example, some of blocks640(e.g., unused blocks650) of free pool630may not be allocated to one or more databases610and/or one or more filters/rules620. This may enable TCAM360to minimize power consumption (e.g., by run mechanism660).

As further shown inFIG. 8, process800may include detecting execution of a run mechanism by the TCAM (block830), and allocating an unused block of memory to a filter or rule of one database based on execution of the run mechanism (block840). For example, in implementations described above in connection withFIG. 6, when space is required by run mechanism660(e.g., for a rule, filter, and/or database), one of unused blocks650of free pool630may be assigned to run mechanism660, as indicated by reference number670. Based on assignment of unused block650(e.g., block640-4), run mechanism660may have memory space available for rule/filter/database allocation, rule movement may be minimized (e.g., by run mechanism660), and power consumption (e.g., by TCAM360) may be minimized. Block640-4may be added (e.g., by run mechanism660) to a database and may be considered a new run (e.g., having a size of block640-4) that is available to run mechanism660.

Returning toFIG. 8, process800may include detecting underutilization of the TCAM (block850), and reassigning, to the free pool, one of the allocated blocks of memory when TCAM underutilization is detected (block860). For example, in implementations described above in connection withFIG. 6, if utilization of TCAM360is determined to decrease, unused blocks640of free pool630(e.g., that were previously allocated to a database610) may be reclaimed by free pool630or may remain allocated to avoid unnecessary rule movement by TCAM360.

Process block840may include the process blocks depicted inFIG. 9. As shown inFIG. 9, process block840may include determining a lowest unused block of memory that is greater than a highest allocated block of memory assigned to one of the databases (block900), and allocating the determined unused block of memory, greater than the highest allocated block of memory, to a filter or rule of one of the databases based on execution of the run mechanism (block910). For example, in implementations described above in connection withFIG. 7A, when space is required by run mechanism660(e.g., for a rule, filter, and/or database), run mechanism660may be assigned a lowest block number of unused blocks650that is above a highest block640allocated to databases610, as indicated by reference number710. In one example, since block640-7is the highest block640allocated to databases610and block640-8is the lowest unused block650above block640-7, run mechanism660may be assigned block640-8(e.g., for allocating to a rule, filter, and/or database). In such an arrangement, the addition of unused block650of free pool630(e.g., block640-8) to run mechanism660may not cause rule movement in TCAM360(e.g., to accommodate block640-8).

Process block860may include the process blocks depicted inFIG. 10. As shown inFIG. 10, process block860may include determining a highest allocated block of memory assigned to one of the databases (block1000), and one of reassigning, to the free pool, the determined allocated block of memory when another database of the TCAM requires extra space (block1010) or immediately reassigning, to the free pool, the determined allocated block of memory (block1020). For example, in implementations described above in connection withFIG. 7B, when a block640allocated to one of databases610is to be used by another one of databases610, TCAM360may select a highest block640assigned to one of databases610, as indicated by reference number720. For example, since block640-7is the highest block640assigned to one of databases610, block640-7may be freed for use by other databases610, as indicated by reference number730. In one implementation, block640-7may be reassigned to free pool630when another database of TCAM360requires extra space. In another implementation, block640-7may be immediately reassigned to free pool630when underutilization of a TCAM360database is greater than one block. For example, one block of TCAM360may be reassigned to free pool630when a database has one block underutilization or on-demand when a database needs a block. Such an arrangement (e.g., delayed on-demand freeing of blocks) may save power and may ensure that rule movement in TCAM360is minimized.

CONCLUSION

Implementations described herein may include systems and/or methods that provide power efficient and rule movement optimized TCAM management for network devices. The systems and/or methods may modify the run mechanism so that rule movements in a TCAM are optimized and so that the TCAM is power efficient (e.g., for a network device containing the TCAM). The run mechanism may be modified since it may be allocated only a portion of the TCAM space, rather than the entire TCAM space (e.g., as is typically done for the run mechanism). The systems and/or methods may also select blocks of memory in the TCAM in such a way that the modified run mechanism is more efficient in rule movement.

For example, while series of blocks have been described with regard toFIGS. 8-10, the order of the blocks may be modified in other implementations. Further, non-dependent blocks may be performed in parallel.