Dynamic unknown L2 flooding control with MAC limits

A technique that may be used to limit the amount of flooding that occurs for a particular virtual local area network (VLAN) in a data network. Limits are established for VLANs processed by an intermediate node. Each limit indicates a number of forwarding database entries that may be associated with a particular VLAN. If the number of entries in the forwarding database reaches the limit established for a particular VLAN, an action is taken which may include limiting the amount of flooding that occurs for that VLAN.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to data networking and in particular to controlling packet flooding on VLANs contained in a data network.

2. Background Information

A data network is a geographically distributed collection of interconnected communication links and segments for transporting data between nodes, such as computers. The nodes typically transport the data over the network by exchanging discrete frames or packets containing the data in accordance with various pre-defined protocols, such as e.g., the Transmission Control Protocol/Internet Protocol (TCP/IP) or the Institute of Electrical and Electronics Engineers (IEEE) 802.3 protocol. In this context, a protocol consists of a set of rules defining how the nodes interact with each other to transfer data between them.

Many types of networks are available, with types ranging from local area net-works (LANs) to wide area networks (WANs). LANs typically connect nodes, such as personal computers and workstations, over dedicated private communication links located in the same general physical location, such as a building or a campus, to form a private network. WANs, on the other hand, typically connect large numbers of geographically dispersed nodes over long-distance communications links, such as common carrier telephone lines. The Internet is an example of a WAN that connects disparate net-works throughout the world, providing global communication between nodes contained in various networks. WANs often comprise a complex network of intermediate network nodes, such as routers or switches, that are interconnected to form the WAN and are often configured to perform various functions associated with transferring traffic through the WAN.

Some organizations implement virtual LANs (VLANs) in their private networks to “logically” group entities, such as users, servers, and other resources within the organization. A VLAN is a logical group of entities, such as end nodes and servers, which appear to one another as if they are on the same physical LAN segment even though they may be spread across a large network comprising many different physical segments. A VLAN operates at the data link layer, which is layer-2(L2) of the Open Systems Interconnect (OSI) reference model.

An organization may utilize one or more intermediate nodes, such as L2switches, to couple various entities in the network that belong to a particular VLAN. These intermediate nodes may employ special hardware or software that is configured to “learn” various information about the entities belonging to the VLAN and place this information in a forwarding database that is used by the intermediate node to forward packets acquired by the node to the various entities. The learned information may include a VLAN and a media access control (MAC) address associated with the entity, as well as a port identifier (ID) of a port on the intermediate node through which the entity may be reached.

Often intermediate nodes employ a content-addressable memory (CAM) to store the forwarding database information. CAMs are usually implemented in hardware as an application specific memory device that allows its entire contents to be searched within a single clock cycle. Two common types of CAMs include binary CAMs and ternary CAMs (TCAMs). A binary CAM performs exact-match searches, whereas a TCAM allows pattern matching with the use of “don't cares” which act as wildcards during a search. Because TCAMs are somewhat more versatile than binary CAMs, intermediate nodes often employ one or more TCAM devices to implement the intermediate node's forwarding database.

TCAM devices are often limited with regards to their storage capacity. For example, a typical TCAM device may contain upwards to 32,768 (32K) entries. In a typical forwarding database arrangement, the TCAMs are configured such that each entry holds forwarding database information associated with a particular entity accessible to the intermediate node. Thus, forwarding databases implemented using TCAM devices are often limited to containing information for only up to 32K entities.

The entries in a forwarding database are typically populated using a technique known as “learning.” Learning involves identifying information about an entity in the network, such as a MAC address, VLAN, and destination port associated with the entity, and placing this information in a forwarding database entry. For example, assume an intermediate node acquires a packet on a source port “C” containing a source MAC address “A.” Further assume the port is associated with a VLAN “B.” The intermediate node applies the MAC address “A” to its forwarding database to determine if an entry associated with entity “A” already exists in the database. Assuming an entry does not exist, the intermediate node “learns” about the entity by placing the entity's address, VLAN and source port information associated with the entity in an entry in its forwarding database. Thus, in the above example, the intermediate node creates an entry in the forwarding database associated with the entity that contains “A,” “B” and “C” to represent the address, VLAN and source port associated with the entity, respectively. The intermediate node may later use this information to forward packets that are destined for the entity.

In addition to learning, an intermediate node may further process a packet by performing a “lookup” operation to identify a destination port associated with the packet and forwarding the packet to the destination port. The lookup operation may involve applying a destination address contained in the packet to the forwarding database to determine if the database contains an entry with an address that matches the destination address. If a matching entry is found, the intermediate node forwards the packet to the destination node via a destination port specified in the matching entry. If a matching entry is not found, the intermediate node may alternatively “flood” the packet out all ports in an attempt to reach the destination node. Flooding usually involves sending a copy of the packet onto each of the intermediate node's ports, except the source port on which the packet was acquired.

One problem with the learning technique described above is that it is possible for entities belonging to a VLAN to occupy all or an inordinate amount of the entries in a forwarding database, thus potentially causing the intermediate node to constantly learn about entities belonging to other VLANs. For example, if the number of entities belonging to a particular VLAN is greater than the number of entries in a forwarding table, it is possible for the forwarding table to contain only entries associated with that VLAN. Entries associated with entities from other VLANs end up being displaced and, consequently, have to be re-learned. This could lead to a continuous cycle of displacement and re-learning that, in turn, may significantly impact the packet processing performance of the intermediate node.

Another problem that may occur when a VLAN's entities occupy all or an inordinate amount of entries in a forwarding table is excessive flooding, particularly when processing packets destined for entities belonging to other VLANs. Such excessive flooding may cause the network's performance to be degraded significantly. For example, assume, as above, a first VLAN has more entities than entries in a forwarding database and that the entities are active and that the entire database is occupied with entries associated with the entities. Packets acquired from a second VLAN would have to be flooded because the forwarding database would not contain an entry associated with the destination addresses of the acquired packets. If the first VLAN continually occupies all the entries in the forwarding database before packets from the second VLAN are acquired and processed, the packets for the second VLAN would have to be continually flooded which, in turn, may lead to excessive traffic being generated and introduced into the network when processing packets for the second VLAN. This excessive traffic may further lead to network congestion and consequently network degradation.

SUMMARY OF THE INVENTION

The present invention overcomes the disadvantages of the prior art by providing a technique that may be used by an intermediate node to control flooding of packets on a virtual local area network (VLAN) contained in a data network. According to the technique, a limit is established for each VLAN wherein the limit indicates a number of forwarding database entries that may be associated with the VLAN. A count is generated which indicates the number of entries in the forwarding database associated with the VLAN. The count is compared with the limit to determine if the count matches the limit. If so, an action is taken to control the flooding of packets on that VLAN.

In the illustrative embodiment, an intermediate node contains one or more Encoded Address Recognition Logic (EARL) devices each of which is configured to learn and forward packets acquired by the intermediate node from a data network. In addition, each EARL device contains a forwarding database and a media access control (MAC) limit database. The forwarding database is configured to hold VLAN, MAC address, and port relationships for packets processed by the intermediate node. The MAC limit database is configured to hold various information about VLANs contained in the network, including a MAC limit and a MAC count for each VLAN. The MAC limit is a pre-defined value that indicates a “ceiling” as to the number of entries in the forwarding database that may be associated with a particular VLAN. The MAC count is a value that indicates the actual number of entries in the forwarding database that are associated with the VLAN.

Each EARL executes a MAC limit process, i.e., a software process that monitors the forwarding database and determines the MAC count value for the VLANs. Moreover, the MAC limit process determines if the MAC count for a VLAN matches the MAC limit for the VLAN and if so, takes a predefined action. This action may include issuing a warning to a system log, limiting learning entries for the VLAN, limiting flooding packets for the VLAN, or shutting down the VLAN.

Advantageously, the present invention provides a technique that limits the number of entries in the forwarding database that may be associated with a VLAN, thus, obviating the use of all or a significant portion of the forwarding database entries by a single or a small group of VLANs. By limiting the number of entries in this manner, the inventive technique limits the amount of flooding traffic that may be generated by processing packets for VLANs that are displaced by e.g., VLANs associated with entities that occupy all or a significant portion of the forwarding database.

DETAILED DESCRIPTION OF AN ILLUSTRATIVE EMBODIMENT

FIG. 1is a schematic block diagram of a computer network100that may be advantageously used with the present invention. The computer network100comprises a collection of communication links and segments connected to a plurality of nodes, such as end nodes110and intermediate nodes200. The network links and segments may comprise local area networks (LANs)120interconnected by intermediate nodes200to form an internetwork of computer nodes. These internetworked nodes communicate by exchanging data packets according to a predefined set of protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP) and the Institute of Electrical and Electronic Engineers (IEEE) 802.3 protocol.

FIG. 2is a high-level partial schematic block diagram of intermediate node200that may be advantageously used with the present invention. Suitable intermediate nodes that may be used with the present invention include the Cisco 6500 Series Routers and Cisco 7600 Series Routers available from Cisco Systems Incorporated, San Jose, Calif. Intermediate node200comprises one or more line cards400, a switch fabric card230, and a supervisor engine card300interconnected by a data bus220. Node200is configured to perform, inter alia, various conventional layer-2(L2) and layer-3(L3) switching and routing functions including switching and routing data packets. Moreover, node200is configured to provide support for various combinations of communication protocols including, e.g., TCP/IP, Ethernet, Asynchronous Transfer Mode (ATM), and multi-channel T3.

The data bus220comprises a point-to-point interconnect bus that interconnects the various cards and allows data and signals to be transferred from one card to another. The switch fabric230is a conventional switch fabric device configured to operate in conjunction with the line cards400and supervisor engine300to improve system bandwidth. To that end, the switch fabric230contains logic that is configured to acquire packets from the supervisor engine300and the line cards400, determine a destination (e.g., a line card400) for the packet, and transfer the packet to the destination.

The line cards400connect (interface) the intermediate node200with the network100. The line cards400transfer and acquire data packets to and from the network via output ports217and input ports215, respectively, using various protocols such as, e.g., ATM, Ethernet, T3. Functionally, the line cards400acquire data packets from the network100via the input ports215and forward the data packets to the data bus220, as well as transmit data packets received from the data bus220to the network100via the output ports217. The ports215,217may comprise, e.g., ATM, Ethernet, Fast Ethernet (FE), Gigabit Ethernet (GE), and frame relay (FR) ports.

The supervisor engine300comprises logic that is, inter alia, configured to manage node200and maintain a centralized forwarding database that it distributes to the line cards400.FIG. 3is a high-level partial schematic block diagram of a supervisor engine that may be advantageously used with the present invention. Supervisor engine300comprises a processor320, system controller330, interface logic360, and memory340. The memory340comprises random access memory (RAM) locations addressable by the system controller330for storing, inter alia, data structures and software programs. An operating system342, portions of which are typically resident in memory340and executed by the processor320, functionally organizes the intermediate node200by, inter alia, invoking network operations in support of software processes executing on the supervisor engine300. These processes may include software functions that implement various routing and switching protocols supported by the intermediate node200, as well as processes that implement various functions performed by the supervisor engine, such as management of the intermediate node. Interface logic360is coupled to the data bus220, and is configured to transfer data between the data bus220and the processor320.

Memory340is illustratively a 128 Megabyte (Mb) memory implemented using Dynamic Random Access Memory (DRAM) devices that contains various software and data structures used by processor320. These data structures include a forwarding database344that contains various forwarding information, such as media access control (MAC) addresses of nodes in the network, as well as virtual local area network (VLAN) identifiers (IDs) and destination port IDs associated with the nodes. System controller330is coupled to the processor320and memory340, and comprises circuitry configured to enable processor320to access (e.g., read, write) memory locations contained in memory340.

Processor320is a conventional routing processor configured, inter alia, to execute instructions contained in memory340for maintaining and distributing forwarding database344. Specifically, processor320executes instructions that acquire information about packets processed by the various line cards400, such as VLAN IDs, ports, and MAC addresses associated with the packets and uses this information to maintain forwarding database344. Moreover, processor320executes instructions to distribute its forwarding database344to the various line cards400that, as will be discussed further below, may process this information to update and maintain their versions of forwarding databases.

FIG. 4is a high-level partial schematic block diagram of a line card400that may be advantageously used with the present invention. Line card400comprises input interface logic420, encoded address recognition logic (EARL)500, data bus interface logic460, output interface logic430and output queuing logic440. Each line card may contain a plurality of input215and output217ports coupled to the network100. The input interface logic420and output interface logic430interface the line card to the network100via the input215and output217ports, respectively, and enable the line card to transfer and acquire data to and from the network. To that end, logic420and430comprise conventional interface circuitry that may incorporate the signal, electrical and mechanical characteristics, and interchange circuits, needed to interface line card400with the network's physical media and protocols running over that media.

The data bus interface logic460contains interface circuitry that interfaces the line card to the data bus220and enables the line card400to transfer and acquire data to and from other cards coupled to the bus220. The output queuing logic440contains circuitry, such as output queues and scheduling control logic, configured to control the transfer of data (e.g., data packets) onto the network100via the output interface430.

The EARL500is illustratively embodied in an application-specific integrated circuit (ASIC) that comprises circuitry configured, inter alia, to acquire data packets and process them in accordance with the inventive technique.FIG. 5is a high-level partial schematic block diagram of an EARL500that may be advantageously used with the present invention. EARL500comprises input interface logic510, data bus interface logic550, a program memory530and a dynamic memory540all coupled to a processing engine520. The input interface logic510contains circuitry configured to acquire data packets from the input interface420and enable the processing engine520to access the packets. Likewise, the data bus interface logic550contains circuitry that enables the processing engine520to direct the transfer of acquired packets to the data bus interface460. In addition, the input interface logic510and data bus interface logic550may contain buffers accessible to engine520that are configured to hold the acquired packets.

The processing engine520is a conventional processor containing various logic, such as arithmetic logic units (ALUs) and execution units (EUs), configured to execute computer executable instructions and manipulate data contained in the program memory530and dynamic memory540. In addition, engine520contains logic configured to access packets acquired by the input interface logic510from the input interface420and direct the transfer of packets to the data bus interface460via the data bus interface logic550. Moreover, engine520contains a conventional timer circuit522which, illustratively, is a programmable interval timer that may be configured by engine520to expire at predetermined intervals.

The program memory530and dynamic memory540are, illustratively, conventional computer readable mediums containing random-access memory locations configured to hold data and computer executable instructions accessible to the processing engine520. Memory530contains a multi-tasking operating system532that functionally organizes processing engine520in a manner that enables engine520to perform various conventional operating system functions, such as providing system services, timer services, and scheduling various software processes for execution. Program memory530also contains a MAC limit process534that is a software process that operates under control of the operating system532and contains computer executable instructions executable by engine520that configure engine520to perform various functions including functions that incorporate aspects of the inventive technique.

Dynamic memory540is, likewise, a computer readable medium containing random-access memory locations accessible to the processing engine520. Memory540contains various data structures, such as forwarding database600and MAC limit database700, which are illustratively used by engine520to process packets in accordance with the inventive technique. It should be noted that memory540may be a content-addressable memory (CAM) implemented using CAM devices accessible to engine520.

FIG. 6is a schematic block diagram of forwarding database600illustrated as a table comprising one or more entries610wherein each entry610represents a node accessible to intermediate node200via the data network. Entry610contains a valid field620, a MAC address field630, a VLAN field640, a port field650and a line card field660. The valid field620is illustratively a one-bit field that holds an indicator indicating whether the remaining fields in the entry610contain valid information. Illustratively, this field holds a value of one if the entry610contains valid information.

The MAC address field630is illustratively a 48-bit field that holds the MAC address of the node represented by the entry610. The VLAN field640holds an identifier that identifies a VLAN associated with the entry610. Likewise, the port field650and line card field660hold identifiers that identify the port and line card400associated with the node represented by the entry610. Illustratively, the identifiers contained in the line card field660and the port field650represent a line card400and an output port217on the line card400through which the node represented by the entry610may be reached, respectively. It should be noted that various entries610in database600may not be associated with a VLAN. For such entries, the VLAN field640contains a value that indicates the entry is not associated with a VLAN.

Functionally, the processor320distributes forwarding database information344contained in the supervisor engine300to each of the line cards400via data bus220. At each line card, the information is acquired by the data bus interface logic460and transferred to the EARL500which processes the information including configuring its forwarding database600using the information. A packet acquired by a line card400at an input port215is transferred to the input interface420which, in turn, transfers the packet to the EARL500. The EARL500applies a destination address contained in the packet to the forwarding database600to determine if an entry610in the database600contains a MAC address630that matches the destination address in the packet. If so, the EARL500examines the content of the line card field660and determines if the packet is switched to an output port217on the line card400or is destined for another card coupled to the data bus220. If the packet is destined for another card (e.g., another line card400), the EARL500transfers the packet along with the port information650via the data bus interface460onto the data bus220to the switch fabric230. The switch fabric230, in turn, transfers the packet and port information650to the card for further processing.

If the packet is not destined for another card, i.e., it is destined for an output port217contained on the line card400itself, the EARL500directs the data bus interface logic460to transfer the packet to the output queuing logic440. The output queuing logic440places the packet onto an appropriate output queue for transfer onto the network via the output port217.

The present invention incorporates a technique that may be used to limit the amount of flooding that occurs for a particular virtual local area network (VLAN) in a data network. According to the technique, a limit is established for each VLAN processed by an intermediate node contained in the network. The limit indicates a number of forwarding table entries that may be associated with the VLAN. The intermediate node determines the actual number of entries in the forwarding table associated the VLAN and compares this number with the limit to determine if the number matches the limit. If so, an action is taken which may include limiting the amount of flooding that occurs for that VLAN.

The MAC limit database data structure700is illustratively a table comprising one or more entries710wherein each entry holds information associated with a particular VLAN.FIG. 7is a high-level schematic block diagram of a MAC limit database700that may be advantageously used with the present invention. MAC limit database700is illustratively a table comprising one or more entries710wherein each entry710is associated with a VLAN and contains a VLAN field730, a MAC count field740, a MAC limit field750, an action field760and a status field770. The VLAN field730holds an identifier that identifies the VLAN associated with the entry. The MAC count field holds a value that represents the number of forwarding database entries610in the forwarding database600that is associated with the VLAN. The MAC limit field750holds a value that represents, illustratively, a maximum number of entries610in the forwarding database600that may be associated with the VLAN. The action field760contains an identifier that identifies an action that is taken when the MAC count740matches the MAC limit750. Illustratively, this action may include logging a warning, cease “learning” for the VLAN (e.g., stop associating new entries610with the VLAN), cease flooding packets for the VLAN and/or shutting down the VLAN (e.g., cease forwarding traffic for the VLAN).

The status field770holds a status associated with the VLAN that represents the state of the VLAN. Illustratively, this state includes a “shut down” state, a “no learning” state, a “no flooding” state and an “active” state. The “shut down” state indicates the intermediate node has shut down the VLAN and is not forwarding traffic for the VLAN. The “no learning” state indicates the intermediate node is not adding new entries to the forwarding database600for the VLAN. The “no flooding” state indicates the intermediate node is not flooding traffic onto the VLAN and the “active” state indicates the intermediate node is forwarding traffic for the VLAN.

The MAC limit process534monitors the forwarding database600, maintains the MAC count740for each VLAN represented in the MAC limit database700and takes action if the MAC count740for a VLAN matches the MAC limit750established for that VLAN.FIGS. 8A–Bare a flow diagram of a sequence of steps that may be used to monitor the forwarding database600, update the MAC limit database700and take action, if necessary, in accordance with the inventive technique. The sequence begins at Step805and proceeds to Step810where processing engine520initializes timer522to expire at predetermined intervals that are, illustratively, 3-minute intervals. Next, at Step815, engine520initializes the entries710in the MAC limit database700with information for the various VLANs processed by intermediate node200. Illustratively, the contents of the MAC count field740of the entries710are set to zero and the VLAN730, MAC limit750and action760fields of the entries710are initialized with information generated from predetermined data configured in node200by e.g., a network administrator.

At Step820, engine520performs a check to determine if the timer522has expired. If not, the sequence returns to Step820. Otherwise, the sequence proceeds to Step825where engine520accesses the first entry610in the forwarding database600. At Step830, engine520determines if the entry610is “valid” by examining the valid field620of the entry610to determine if it contains e.g., a one. If not, the sequence proceeds to Step850. Otherwise, at Steps832and835, engine520locates the entry710in the MAC limit database700associated with the VLAN640of the forwarding database entry610and determines if the MAC count740of the VLAN associated with the forwarding database entry610matches the MAC limit750for that VLAN by e.g., comparing the content of the entry's MAC count field740with the content of the entry's MAC limit field750. If there is no match, the sequence proceeds to Step840where the content of the MAC count field840is updated, illustratively, by adding one to the field's content and replacing the content with the results. The sequence then proceeds to Step850.

If, however, the VLAN entry's MAC count740matches the entry's MAC limit750, the sequence proceeds to Step845where engine520performs the action indicated by the entry's action field760. Illustratively, as noted above, this action may include logging the condition as a message in a system log accessible to the intermediate node200, disabling learning for the VLAN, disabling flooding of data packets for the VLAN and/or halting all traffic for the VLAN by shutting it down. Moreover, engine520updates the content of the status field770associated with the VLAN to indicate the actions taken. For example, if the action taken includes shutting down the VLAN, the engine520updates the status770to indicate “shut down.” Likewise, if the action taken includes disable flooding and/or disable learning, the engine updates the status770to indicate “no flooding” and/or “no learning,” respectively.

At Step850(FIG. 8B), engine520accesses the next forwarding database entry610and, at Step855, checks the entry610to determine if the entry610is the last entry in the database600. If so, the sequence proceeds to Step895where the sequence ends; otherwise, the sequence returns to Step830.

FIGS. 9A–Bare a flow chart of a sequence of steps that may be used to configure the EARL500to acquire and process a packet in accordance with the inventive technique. The sequence begins at Step905and proceeds to Step910where a packet is acquired by an input port215and is eventually transferred to the input interface logic510. Next, at Step915, engine520determines if the status770of the VLAN associated with the packet indicates the VLAN is shut down. Illustratively, “the VLAN associated with a packet” is a VLAN associated with the input port217on which the VLAN was acquired. Alternatively, the packet may be associated with a VLAN associated with a VLAN tag contained in the packet or with a source address contained in the packet. If the VLAN associated with the packet is shut down, the sequence proceeds to Step965(FIG. 9B) where the packet is dropped (discarded). The sequence then ends at Step995.

If the VLAN's status770does not indicate the VLAN is shut down, the sequence proceeds to Step920where the MAC limit entry710for the VLAN associated with the packet is located. Next, at Steps925and930, engine520compares a source address contained in the packet with the MAC addresses630contained in the forwarding database600to determine if an entry610contains a MAC address630that matches the source address contained in the packet. If so, the sequence proceeds to Step945(FIG. 9B). Otherwise, the sequence proceeds to Step935where engine520determines if learning is disabled for the packet's VLAN by examining the status field770associated with the VLAN to determine if it indicates “no learning.” If so, the sequence proceeds to Step945. If not, the sequence proceeds to Step940where engine520generates a forwarding database entry610that contains the packet's source address, VLAN, port and line card information. Specifically, engine520places the packet's source address and an identifier that identifies the VLAN associated with the packet in the MAC address field630and VLAN field640, respectively, of an available (invalid) entry610in the forwarding database600. In addition, engine520illustratively places identifiers that identify the line card and the port on the line card where the packet was acquired in the line card field660and port field650of the entry610, respectively. Engine520then sets the content of the entry's valid field620to indicate the entry610is valid (e.g., sets the field's content to a one).

At Steps945and950, the destination address is compared with the MAC addresses630contained in the forwarding database600to determine if the destination address matches the MAC address630of an entry610contained in the database600. If so, the sequence proceeds to Step955where the packet is forwarded in a conventional manner using information contained in the matching entry610; e.g., the packet is forwarded to the port and line card400indicated by the port field650and line card field660of the matching entry610. The sequence then ends at Step995.

If a matching entry610is not found, the sequence proceeds to Step960where engine520determines if flooding is disabled for the packet's VLAN by examining the status770associated with the VLAN to determine if it indicates “no flooding.” If so, the sequence proceeds to Step965, where the packet is dropped (discarded). Otherwise, the sequence proceeds to Step970where the packet is flooded. The sequence then ends at Step995.

It should be noted that although various data structures described in the illustrated embodiment described herein are illustrated as tables, other types of data structures, such as linked lists or arrays, may be used to implement these data structures.

It should be further noted that the inventive technique may be implemented in hardware, software (e.g., firmware) or in a combination of hardware and software. For example, a hardware implementation may implement the data structures, such as the forwarding database600and MAC limit database700in hardware CAMs and the functions performed by the processing engine520in one or more hardware state machines. Moreover, a software implementation may implement the databases as software-defined data structures and various functions performed by the hardware as software functions or routines.