Systems and methods for assigning colors to nodes of a subgraph

In one embodiment, a method includes generating a subgraph from a dependency graph. The subgraph includes one or more potential paths between an event interest node and an event generator node of the dependency graph. The method also includes activating the event interest node and assigning, in response to activating the event interest node, a color to nodes along the one or more potential paths of the subgraph from the event interest node to the event generator node. The method further includes modifying the event generator node and modifying, in response to modifying the event generator node, one or more of the nodes along the one or more potential paths of the subgraph from the event generator node to the event interest node.

TECHNICAL FIELD

This disclosure generally relates to assigning colors to nodes, and more specifically to systems and methods for assigning colors to nodes of a subgraph.

BACKGROUND

A software representation of network nodes typically forms a dependency chain or a directed acyclic graph. In certain instances, a network event may update a node in this graph, which requires modifying the dependent nodes. The dependent nodes may be modified by using specialized code that is included in each intermediate node of the graph. However, vigilant code reviews are required to capture any additional intermediate nodes that may be added in the future.

DESCRIPTION OF EXAMPLE EMBODIMENTS

Overview

According to an embodiment, a router includes one or more processors and one or more computer-readable non-transitory storage media coupled to the one or more processors. The one or more computer-readable non-transitory storage media include instructions that, when executed by the one or more processors, cause the router to perform operations including generating a subgraph from a dependency graph. The subgraph includes one or more potential paths between an event interest node and an event generator node of the dependency graph. The operations also include activating the event interest node and assigning, in response to activating the event interest node, a color to nodes along the one or more potential paths of the subgraph from the event interest node to the event generator node. The operations further include modifying the event generator node and modifying, in response to modifying the event generator node, one or more of the nodes along the one or more potential paths of the subgraph from the event generator node to the event interest node.

In certain embodiments, generating the subgraph from the dependency graph occurs during a compile time. In some embodiments, assigning the color to the nodes along the one or more potential paths of the subgraph occurs during a run time. Activating the event interest node may include configuring a feature on the router. The color may be a label indicating that the node is subject to tracking.

In certain embodiments, the operations include deleting the event interest node, modifying the event generator node, and deleting, in response to deleting the event interest node and modifying the event generator node, the color from the nodes along the one or more potential paths of the subgraph from the event generator node to the event interest node. In some embodiments, modifying the event generator node includes one of the following: changing a next-hop, changing a virtual output queueing (VOQ) identification, changing an equal-cost multi-path (ECMP) routing, or changing a link aggregation group (LAG). In certain embodiments, the operations further include defining relationships between a plurality of nodes of the dependency graph and generating a plurality of subgraphs from the dependency graph. Each of the plurality of subgraphs may include the event generator node and a unique event interest node.

According to another embodiment, a method includes generating a subgraph from a dependency graph. The subgraph includes one or more potential paths between an event interest node and an event generator node of the dependency graph. The method also includes activating the event interest node and assigning, in response to activating the event interest node, a color to nodes along the one or more potential paths of the subgraph from the event interest node to the event generator node. The method further includes modifying the event generator node and modifying, in response to modifying the event generator node, one or more of the nodes along the one or more potential paths of the subgraph from the event generator node to the event interest node.

According to yet another embodiment, one or more computer-readable non-transitory storage media embody instructions that, when executed by a processor, cause the processor to perform operations including generating a subgraph from a dependency graph. The subgraph includes one or more potential paths between an event interest node and an event generator node of the dependency graph. The operations also include activating the event interest node and assigning, in response to activating the event interest node, a color to nodes along the one or more potential paths of the subgraph from the event interest node to the event generator node. The operations further include modifying the event generator node and modifying, in response to modifying the event generator node, one or more of the nodes along the one or more potential paths of the subgraph from the event generator node to the event interest node.

Technical advantages of certain embodiments of this disclosure may include one or more of the following. Certain embodiments of this disclosure assign colors to nodes of a subgraph upon activation (e.g., creation) of an event interest node and delete the colors from the nodes of the subgraph upon deactivation (e.g., removal) of the event interest node, which preserves network resources. In certain embodiments, rather than deleting the colors from nodes at the time the event interest node is deactivated, the event generator node “lazy deletes” the color from each colored node when another graph traversal occurs, which provides for better forwarding convergence. In some embodiments, only a few lines of code (e.g., JavaScript Object Notation (JSON) code) are required to assign and delete colors from the nodes, which allows for fast and accurate deployment.

Certain embodiments of this disclosure include systems and methods for network parent node tracking that dynamically adjusts to multiple levels of hierarchy. For example, tracking may be maintained if a network event changes a recursive route to a non-recursive route (or vice versa). In some embodiments, the network parent node tracking does not scale with a number of routes. For example, if only a few routes track a particular interface or LAG, changes at the root level will only reach the few routes that have registered for changes.

In certain embodiments of this disclosure, to ensure accuracy in the graph traversal, ownership of the logic is within dynamically generated code. For example, a dependency graph may be dynamically generated during every code compilation so that if a developer changes the dependency chain, no code change is required to maintain accuracy. Since the ownership of the graph traversal accuracy does not belong to any forwarding feature owner, the modularity of the code base is increased.

Example Embodiments

This disclosure describes systems and methods for assigning colors to nodes of a subgraph.FIG.1shows an example system for assigning colors to nodes of a subgraph.FIG.2shows an example dependency graph that may be used by the system ofFIG.1, andFIG.3shows an example subgraph that may be generated from the dependency graph ofFIG.2.FIG.4shows an example run-time topology of the subgraph ofFIG.3prior to activation of an event interest node, andFIG.5shows an example run-time topology of the subgraph ofFIG.3after activation of the event interest node.FIG.6shows an example method for assigning colors to nodes of a subgraph.FIG.7shows an example computer system that may be used by the systems and methods described herein.

FIG.1illustrates an example system100for assigning colors to nodes of a subgraph. System100or portions thereof may be associated with an entity, which may include any entity, such as a business or company that assigns colors to nodes of a subgraph. The components of system100may include any suitable combination of hardware, firmware, and software. For example, the components of system100may use one or more elements of the computer system ofFIG.7. System100ofFIG.1includes a network110, nodes120, and a graph generator130.

Network110of system100is any type of network that facilitates communication between components of system100. Network110may connect one or more components of system100. This disclosure contemplates any suitable network. One or more portions of network110may include an ad-hoc network, an intranet, an extranet, a virtual private network (VPN), a local area network (LAN), a wireless LAN (WLAN), a wide area network (WAN), a wireless WAN (WWAN), a metropolitan area network (MAN), a portion of the Internet, a portion of the Public Switched Telephone Network (PSTN), a cellular telephone network, a combination of two or more of these, or other suitable types of networks. Network110may include one or more networks. Network110may be any communications network, such as a private network, a public network, a connection through Internet, a mobile network, a WI-FI network, etc. One or more components of system100may communicate over network110. Network110may include a core network (e.g., the Internet), an access network of a service provider, an internet service provider (ISP) network, and the like.

Nodes120of system100are connection points within network110that receive, create, store and/or send traffic along a path. Nodes120may include one or more endpoints and/or one or more redistribution points that recognize, process, and forward traffic to other nodes120. Nodes120may include virtual and/or physical network nodes. In certain embodiments, one or more nodes120include data equipment such as routers, servers, switches, bridges, modems, hubs, printers, workstations, and the like.

Nodes120of system100include event generator nodes122, event interest nodes124, intermediate nodes126, and excluded nodes128. Event generator nodes122represent nodes120that indicate the state of a network function element such as a next hop or queue availability. Event interest nodes124represent nodes120that indicate a network service state availability for the network function state. Intermediate nodes126represent nodes120along a potential path between event generator nodes122and event interest nodes124. In certain embodiments, intermediate nodes126are assigned a color upon activation of an associated event interest node124. Excluded nodes128represent nodes122that are not part of any potential path between event generator nodes122and event interest nodes124. In certain embodiments, excluded nodes128are not assigned a color upon activation of an associated event interest node124. One or more nodes120within network110may receive traffic from other components of network110. For example, intermediate nodes126may receive traffic from event generator nodes122, event interest nodes124may receive traffic from intermediate nodes126, and so on.

Graph generator130of system100is a component that generates dependency graphs132and subgraphs134using nodes120of network110. Graph generator130may identify the relationships between nodes120based on user input. For example, a user of graph generator130may define the relationships between nodes120using an encoding scheme (e.g., JSON). Graph generator130may identify event generator nodes122and event interest nodes124from nodes120based on user input. For example, a user of graph generator130may define event generator nodes122and event interest nodes124using an encoding scheme (e.g., JSON).

In certain embodiments, during compile time, graph generator130of system100automatically generates code that is used to build dependency graphs132and subgraphs134. Graph generator130may identify all potential paths between event generator node122and each event interest node124. In some embodiments, graph generator130writes global constants in a general-purpose, procedural computer programming language (e.g., C, C++, etc.). The global constants may take into account all relationships between nodes120of dependency graph132.

In some embodiments, during run time, one or more nodes120are activated (e.g., created or enabled) and form relationships with other nodes120depending on the rules generated by graph generator130during compile time. When a particular event interest node124is activated and linked to other nodes120, that particular event interest node124will traverse, from event interest node124to event generator node122, all potential paths leading up to event generator node122and assign a color to each node120along all potential paths. Activating event interest node124may include creating event interest node124, configuring a feature (e.g., an Encapsulated Remote Switched Port Analyzer (ERSPAN) feature) on a network component (e.g., a router, a server, etc.), and the like. The color is a label for node120that indicates colored node120is subject to tracking.

When event generator node122is modified (e.g., changed, updated, etc.), event generator node122will traverse, from event generator node122to event interest node124, all paths leading up to event interest node124and modify one or more of nodes120that have been assigned the color. In certain embodiments, the modification to event generator node122causes a depth first search (DFS) traversal of dependency graph132to all event interest nodes124. Modifying event generator node122may include one or more of the following: changing a next-hop, changing a VOQ identification, changing an ECMP routing, or changing a LAG, etc.

If event interest node124is deactivated (e.g., deleted, removed, or disabled), event generator node122deletes the colors from nodes120assigned the color by deactivated event interest node124. In certain embodiments, rather than deleting the colors from nodes120at the time event interest node124is deactivated, event generator node122“lazy deletes” the color from each colored node120the next time event generator node122is modified. For example, event generator node122may delete the color from each colored node120when another walk occurs and event generator node122discovers that event interest node124is no longer present. In some embodiments, event generator node122traverses, from event generator node122to event interest node124, all paths that have been colored by event interest node124and deletes the colors from all colored nodes120during the path traversal. Once the colors have been deleted from nodes120, further modifications to event generator node122will not cause any graph traversal. In certain embodiments, a lazy delete pruning algorithm is used to lazy delete the colors from each colored node122.

Dependency graphs132of system100represent relationships between nodes120of system100. Each dependency graph132includes a single event generator node122(i.e., the root node), multiple event interest nodes124(i.e., the leaf nodes), and multiple intermediate nodes126located along the potential paths between event generator node122and each event interest node124. Each dependency graph132shows all potential paths between event generator node122and each event interest nodes124.

Subgraphs134of system100are generated from dependency graphs132. Each subgraph134represents all potential paths between event generator node122of dependency graph132and one unique event interest node124of dependency graph132. For example, a first subgraph134may show all potential paths between event generator node122and a first event interest node124of dependency graph132, a second subgraph134may show all potential paths between event generator node122and a second event interest node124of dependency graph132, a third subgraph134may show all potential paths between event generator node122and a third event interest node124of dependency graph132, and so on.

In certain embodiments, subgraphs134are dynamically created as a result of the colored paths. For example, first subgraph134may be dynamically created as nodes120associated with first event interest node124are assigned a first color (e.g., orange), second subgraph134may be dynamically created as nodes120associated with second event interest node124are assigned a second color (e.g., green), third subgraph134may be dynamically created as nodes120associated with third event interest node124are assigned a third color (e.g., yellow), and so on. In certain embodiments, once event interest node124is deactivated (e.g., deleted or disabled), its associated subgraph134is pruned (e.g., deleted) so that no further resources are wasted.

In operation, during compile time, graph generator130of system100generates dependency graph132, which shows the relationships between nodes120of network110. Dependency graph132includes all potential paths from event generator node122to a plurality of event interest nodes124. Graph generator130then generates individual subgraphs134for each event interest node124of dependency graph132. Each subgraph134includes all potential paths between event generator node122and the particular event interest node124of each subgraph134. During run time, a first event interest node124is activated (e.g., created). Upon its activation, first event interest node124traverses all potential paths from first event interest node124to event generator node122and assigns a color (e.g., green) to all nodes120along all potential paths. When event generator node122is modified (e.g., updated), event generator node122traverses all nodes120that have been assigned the color and propagates the modifications to all colored nodes120. As such, system100allows for graph traversal only when event interest node124has been activated.

AlthoughFIG.1illustrates a particular arrangement of network110, nodes120, and graph generator130, this disclosure contemplates any suitable arrangement of network110, nodes120, and graph generator130. For example, graph generator130may operate on one or more nodes120of system100. AlthoughFIG.1illustrates a particular number of networks110, nodes120, and graph generators130, this disclosure contemplates any suitable number of networks110, nodes120, and graph generators130. For example, system100may include more or less than one graph generator130.

FIG.2illustrates an example dependency graph132that may be used by system100ofFIG.1. In certain embodiments, dependency graph132is generated by graph generator130ofFIG.1during compile time. Dependency graph132includes nodes120. Nodes120include event generator node122, event interest node124, and intermediate nodes126. While dependency graph132ofFIG.2illustrates a single event interest node124, any node120of dependency graph132other than event generator node122may represent an event interest node124. Dependency graph132shows all potential paths from event generator node122to event interest node124. Intermediate nodes126represent nodes120along the potential paths between event generator node122and event interest node124.

AlthoughFIG.2illustrates a particular arrangement of nodes120, event generator node122, event interest node124, and intermediate nodes126for dependency graph132, this disclosure contemplates any suitable arrangement of nodes120, event generator node122, event interest node124, and intermediate nodes126for dependency graph132. For example, nodes120of dependency graph132may be arranged in a different order. AlthoughFIG.2illustrates a particular number of nodes120, event generator nodes122, event interest nodes124, intermediate nodes126, and dependency graphs132, this disclosure contemplates any suitable number of nodes120, event generator nodes122, event interest nodes124, intermediate nodes126, and dependency graphs132. For example,FIG.2may include more than one dependency graph132.

FIG.3illustrates an example subgraph134that may be generated from dependency graph132ofFIG.2. Subgraph134shows all potential paths between event generator node122and event interest node124ofFIG.1. In certain embodiments, subgraph134is generated by graph generator130ofFIG.1during compile time. Subgraph134includes event generator nodes122, event interest node124, and intermediate nodes126. Whereas dependency graph132ofFIG.2shows all potential paths between event generator node122and a plurality of event interest nodes124, subgraph134ofFIG.3shows all potential paths between event generator node122and a particular event interest node124. Intermediate nodes126represent nodes120of subgraph134along the potential paths between event generator node122and event interest node124.

AlthoughFIG.3illustrates a particular arrangement of nodes120, event generator node122, event interest node124, and intermediate nodes126for subgraph134, this disclosure contemplates any suitable arrangement of nodes120, event generator node122, event interest node124, and intermediate nodes126for subgraph134. For example, nodes120of subgraph134may be arranged in a different order. AlthoughFIG.3illustrates a particular number of nodes120, event generator nodes122, event interest nodes124, intermediate nodes126, and subgraphs134, this disclosure contemplates any suitable number of nodes120, event generator nodes122, event interest nodes124, intermediate nodes126, and subgraphs134. For example,FIG.3may include more than one subgraph134(e.g., a different subgraph134for each event interest node124of dependency graph132ofFIG.2).

FIG.4illustrates an example run-time topology400of subgraph134ofFIG.3prior to activation of event interest nodes124. Pre-activation run-time topology400includes event generator node122, event interest nodes124(i.e., event interest node124aand event interest node124b), intermediate nodes126(i.e., intermediate nodes126a,126b,126c,126d,126e,126f, and126g), and excluded nodes128(i.e., excluded nodes128a,128b,128c, and128d). Intermediate nodes126of pre-activation run-time topology400are part of the potential path illustrated in subgraph134ofFIG.3. Intermediate nodes126represent nodes120that can be activated for path coloring. Excluded nodes128of pre-activation run-time topology400are not part of any potential path to event generator node122and therefore cannot be activated. In run-time topology400ofFIG.4, event interest nodes124have not been activated (e.g., created or enabled). When event interest nodes124are not activated, modifications (e.g., changes, updates, etc.) to event generator node122will not propagate back to intermediate nodes126.

AlthoughFIG.4illustrates a particular arrangement of event generator node122, event interest nodes124, intermediate nodes126, and excluded nodes128for pre-activation run-time topology400, this disclosure contemplates any suitable arrangement of event generator node122, event interest nodes124, intermediate nodes126, and excluded nodes128for pre-activation run-time topology400. For example, event interest node124b may include multiple paths to event generator node122. AlthoughFIG.4illustrates a particular number of event generator nodes122, event interest nodes124, intermediate nodes126, and excluded nodes128for pre-activation run-time topology400, this disclosure contemplates any suitable number of event generator nodes122, event interest nodes124, intermediate nodes126, and excluded nodes128for pre-activation run-time topology400. For example,FIG.4may include more or less than two event interest nodes124, more or less than seven intermediate nodes126, and/or more or less than four excluded nodes128.

FIG.5illustrates an example run-time topology500of subgraph134ofFIG.3after activation of event interest node124a. Post-activation run-time topology500includes event generator node122, event interest nodes124(i.e., event interest node124aand event interest node124b), intermediate nodes126(i.e., intermediate nodes126a,126b,126c,126d,126e,126f, and126g), and excluded nodes128(i.e., excluded nodes128a,128b,128c, and128d). Intermediate nodes126of post-activation run-time topology500are part of the potential path illustrated in subgraph134ofFIG.3. Intermediate nodes126represent nodes120that can be activated for path coloring. Excluded nodes128of post-activation run-time topology500are not part of any potential path to event generator node122and therefore cannot be activated. In post-activation run-time topology500ofFIG.5, event interest node124ahas been activated (e.g., enabled, created, etc.).

In response to the activation of event interest node124a, intermediate nodes126a,126b,126d, and126falong the path from event interest node124ato event generator node122are assigned a color (e.g., green), which allows for tracking between event interest node124aand event generator node122. In certain embodiments, event interest node124aassigns the color to intermediate nodes126during a forward walk to event generator node122. After intermediate nodes126have been assigned the color, modifications (e.g., changes, updates, etc.) to event generator node122propagate back to intermediate nodes126a,126b,126d, and126f. However, modifications to event generator node122will not propagate back to intermediate nodes126c,126e, and126gsince event interest node124bhas not been activated.

AlthoughFIG.5illustrates a particular arrangement of event generator node122, event interest nodes124, intermediate nodes126, and excluded nodes128for post-activation run-time topology500, this disclosure contemplates any suitable arrangement of event generator node122, event interest nodes124, intermediate nodes126, and excluded nodes128for post-activation run-time topology500. For example, in certain embodiments, event interest node124bmay be activated in addition to or in lieu of the activation of event interest node124a. AlthoughFIG.5illustrates a particular number of event generator nodes122, event interest nodes124, intermediate nodes126, and excluded nodes128for post-activation run-time topology500, this disclosure contemplates any suitable number of event generator nodes122, event interest nodes124, intermediate nodes126, and excluded nodes128for post-activation run-time topology500. For example,FIG.5may include more or less than two event interest nodes124, more or less than seven intermediate nodes126, and/or more or less than four excluded nodes128.

FIG.6shows an example method600for assigning colors to nodes of a subgraph. Method600begins at step605. At step610, a graph generator (e.g., graph generator130ofFIG.1) of a system (e.g., system100ofFIG.1) generates a dependency graph (e.g., dependency graph132ofFIG.2) using nodes of a network (e.g., nodes120of network110ofFIG.1). The graph generator generates the graph during compile time. The dependency graph includes all potential paths between an event generator node (e.g., event generator node122ofFIG.1) and a plurality of event interest nodes (e.g., event interest nodes124ofFIG.1). Method600then moves from step610to step615.

At step615of method600, the graph generator generates a subgraph (e.g., subgraph134ofFIG.3) from the dependency graph. The graph generator generates the subgraph during compile time. The subgraph includes all potential paths between the event generator node and a particular event interest node. In certain embodiments, the graph generator generates a separate subgraph for each event interest node of the dependency graph. Method600then moves from step615to step620.

At step620of method600, the event interest node is activated (e.g., enabled, created, etc.). The event interest node may be activated by enabling a feature on a node of the network. For example, the event interest node may be activated upon the configuration of ERSPAN on a router. Method600then moves from step620to step625, where a color is assigned to one or more nodes along the potential paths of the subgraph during a forward walk from the event interest node to the event generator node. For example, referring toFIG.5, event interest node124amay assign the color green to intermediate nodes126a,126b,126d, and126fas event interest node124atraverses the available paths to event generator node122. In certain embodiments, the activation of the event interest node triggers the forward walk and coloring of the nodes along the paths between the activated event interest node and the event generator node. Method600then moves from step625to step630.

At step630of method600, the system determines whether the event generator node has been modified. Modifications to the event generator node may include changing a next-hop, changing a VOQ identification, changing an ECMP routing, changing a LAG, and the like. If the event generator node has not been modified, method600advances from step630to step640. If the event generator node has been modified, the event generator node propagates the modifications to the colored nodes. For example, referring toFIG.4, event generator node122may back walk along colored intermediate nodes126f,126d,126b, and126ato event interest node124aand propagate the modifications to the colored intermediate nodes. Method600then moves from step635to step640.

At step640of method600, the system determines whether the event interest node has been deactivated (e.g., disabled, deleted, etc.). The event interest node may be deactivated by deleting the event interest node or disabling a feature on the event interest node. For example, referring toFIG.4, event interest node124amay be deactivated upon deleting event interest node124aor disabling the ERSPAN feature on event interest node124a. If the event interest node has not been deactivated, method600advances from step640to step650, where method600ends. If, at step640, the event generator node has been deactivated, method600moves from step640to step645. At step645, the event generator node deletes the colors that have been assigned to the nodes during a back walk from the event generator node to the event interest node. For example, referring toFIG.4, event generator node122may back walk along colored nodes126f,126d,126b, and126aand delete the color from each of these nodes. Method600then moves from step645to step650, where method600ends.

Although this disclosure describes and illustrates an example method600for assigning colors to nodes of a subgraph including the particular steps of the method ofFIG.6, this disclosure contemplates any suitable method600for assigning colors to nodes of a subgraph, including any suitable steps, which may include all, some, or none of the steps of the method ofFIG.6, where appropriate.

Although this disclosure describes and illustrates particular steps of method600ofFIG.6as occurring in a particular order, this disclosure contemplates any suitable steps of method600ofFIG.6occurring in any suitable order. Although this disclosure describes and illustrates particular components, devices, or systems carrying out particular steps of method600ofFIG.6, this disclosure contemplates any suitable combination of any suitable components, devices, or systems carrying out any suitable steps of method600ofFIG.6.

FIG.7illustrates an example computer system700. In particular embodiments, one or more computer systems700perform one or more steps of one or more methods described or illustrated herein. In particular embodiments, one or more computer systems700provide functionality described or illustrated herein. In particular embodiments, software running on one or more computer systems700performs one or more steps of one or more methods described or illustrated herein or provides functionality described or illustrated herein. Particular embodiments include one or more portions of one or more computer systems700. Herein, reference to a computer system may encompass a computing device, and vice versa, where appropriate. Moreover, reference to a computer system may encompass one or more computer systems, where appropriate.

In particular embodiments, computer system700includes a processor702, memory704, storage706, an input/output (I/O) interface708, a communication interface710, and a bus712. Although this disclosure describes and illustrates a particular computer system having a particular number of particular components in a particular arrangement, this disclosure contemplates any suitable computer system having any suitable number of any suitable components in any suitable arrangement.

In particular embodiments, processor702includes hardware for executing instructions, such as those making up a computer program. As an example and not by way of limitation, to execute instructions, processor702may retrieve (or fetch) the instructions from an internal register, an internal cache, memory704, or storage706; decode and execute them; and then write one or more results to an internal register, an internal cache, memory704, or storage706. In particular embodiments, processor702may include one or more internal caches for data, instructions, or addresses. This disclosure contemplates processor702including any suitable number of any suitable internal caches, where appropriate. As an example and not by way of limitation, processor702may include one or more instruction caches, one or more data caches, and one or more translation lookaside buffers (TLBs). Instructions in the instruction caches may be copies of instructions in memory704or storage706, and the instruction caches may speed up retrieval of those instructions by processor702. Data in the data caches may be copies of data in memory704or storage706for instructions executing at processor702to operate on; the results of previous instructions executed at processor702for access by subsequent instructions executing at processor702or for writing to memory704or storage706; or other suitable data. The data caches may speed up read or write operations by processor702. The TLBs may speed up virtual-address translation for processor702. In particular embodiments, processor702may include one or more internal registers for data, instructions, or addresses. This disclosure contemplates processor702including any suitable number of any suitable internal registers, where appropriate. Where appropriate, processor702may include one or more arithmetic logic units (ALUs); be a multi-core processor; or include one or more processors702. Although this disclosure describes and illustrates a particular processor, this disclosure contemplates any suitable processor.

In particular embodiments, memory704includes main memory for storing instructions for processor702to execute or data for processor702to operate on. As an example and not by way of limitation, computer system700may load instructions from storage706or another source (such as, for example, another computer system700) to memory704. Processor702may then load the instructions from memory704to an internal register or internal cache. To execute the instructions, processor702may retrieve the instructions from the internal register or internal cache and decode them. During or after execution of the instructions, processor702may write one or more results (which may be intermediate or final results) to the internal register or internal cache. Processor702may then write one or more of those results to memory704. In particular embodiments, processor702executes only instructions in one or more internal registers or internal caches or in memory704(as opposed to storage706or elsewhere) and operates only on data in one or more internal registers or internal caches or in memory704(as opposed to storage706or elsewhere). One or more memory buses (which may each include an address bus and a data bus) may couple processor702to memory704. Bus712may include one or more memory buses, as described below. In particular embodiments, one or more memory management units (MMUs) reside between processor702and memory704and facilitate accesses to memory704requested by processor702. In particular embodiments, memory704includes RAM. This RAM may be volatile memory, where appropriate. Where appropriate, this RAM may be dynamic RAM (DRAM) or static RAM (SRAM). Moreover, where appropriate, this RAM may be single-ported or multi-ported RAM. This disclosure contemplates any suitable RAM. Memory704may include one or more memories704, where appropriate. Although this disclosure describes and illustrates particular memory, this disclosure contemplates any suitable memory.

In particular embodiments, storage706includes mass storage for data or instructions. As an example and not by way of limitation, storage706may include a hard disk drive (HDD), a floppy disk drive, flash memory, an optical disc, a magneto-optical disc, magnetic tape, or a Universal Serial Bus (USB) drive or a combination of two or more of these. Storage706may include removable or non-removable (or fixed) media, where appropriate. Storage706may be internal or external to computer system700, where appropriate. In particular embodiments, storage706is non-volatile, solid-state memory. In particular embodiments, storage706includes ROM. Where appropriate, this ROM may be mask-programmed ROM, programmable ROM (PROM), erasable PROM (EPROM), electrically erasable PROM (EEPROM), electrically alterable ROM (EAROM), or flash memory or a combination of two or more of these. This disclosure contemplates mass storage706taking any suitable physical form. Storage706may include one or more storage control units facilitating communication between processor702and storage706, where appropriate. Where appropriate, storage706may include one or more storages706. Although this disclosure describes and illustrates particular storage, this disclosure contemplates any suitable storage.

In particular embodiments, communication interface710includes hardware, software, or both providing one or more interfaces for communication (such as, for example, packet-based communication) between computer system700and one or more other computer systems700or one or more networks. As an example and not by way of limitation, communication interface710may include a network interface controller (NIC) or network adapter for communicating with an Ethernet or other wire-based network or a wireless NIC (WNIC) or wireless adapter for communicating with a wireless network, such as a Wi-Fi network. This disclosure contemplates any suitable network and any suitable communication interface710for it. As an example and not by way of limitation, computer system700may communicate with an ad hoc network, a personal area network (PAN), a LAN, a WAN, a MAN, or one or more portions of the Internet or a combination of two or more of these. One or more portions of one or more of these networks may be wired or wireless. As an example, computer system700may communicate with a wireless PAN (WPAN) (such as, for example, a BLUETOOTH WPAN), a Wi-Fi network, a Wi-MAX network, a cellular telephone network (such as, for example, a Global System for Mobile Communications (GSM) network, a 3G/Universal Mobile Telecommunications Service (UMTS) network, a LTE network, or a 5G network), or other suitable wireless network or a combination of two or more of these. Computer system700may include any suitable communication interface710for any of these networks, where appropriate. Communication interface710may include one or more communication interfaces710, where appropriate. Although this disclosure describes and illustrates a particular communication interface, this disclosure contemplates any suitable communication interface.

In particular embodiments, bus712includes hardware, software, or both coupling components of computer system700to each other. As an example and not by way of limitation, bus712may include an Accelerated Graphics Port (AGP) or other graphics bus, an Enhanced Industry Standard Architecture (EISA) bus, a front-side bus (FSB), a HYPERTRANSPORT (HT) interconnect, an Industry Standard Architecture (ISA) bus, an INFINIBAND interconnect, a low-pin-count (LPC) bus, a memory bus, a Micro Channel Architecture (MCA) bus, a Peripheral Component Interconnect (PCI) bus, a PCI-Express (PCIe) bus, a serial advanced technology attachment (SATA) bus, a Video Electronics Standards Association local (VLB) bus, or another suitable bus or a combination of two or more of these. Bus712may include one or more buses712, where appropriate. Although this disclosure describes and illustrates a particular bus, this disclosure contemplates any suitable bus or interconnect.

The scope of this disclosure encompasses all changes, substitutions, variations, alterations, and modifications to the example embodiments described or illustrated herein that a person having ordinary skill in the art would comprehend. The scope of this disclosure is not limited to the example embodiments described or illustrated herein. Moreover, although this disclosure describes and illustrates respective embodiments herein as including particular components, elements, feature, functions, operations, or steps, any of these embodiments may include any combination or permutation of any of the components, elements, features, functions, operations, or steps described or illustrated anywhere herein that a person having ordinary skill in the art would comprehend. Furthermore, reference in the appended claims to an apparatus or system or a component of an apparatus or system being adapted to, arranged to, capable of, configured to, enabled to, operable to, or operative to perform a particular function encompasses that apparatus, system, component, whether or not it or that particular function is activated, turned on, or unlocked, as long as that apparatus, system, or component is so adapted, arranged, capable, configured, enabled, operable, or operative. Additionally, although this disclosure describes or illustrates particular embodiments as providing particular advantages, particular embodiments may provide none, some, or all of these advantages. The embodiments disclosed herein are only examples, and the scope of this disclosure is not limited to them. Particular embodiments may include all, some, or none of the components, elements, features, functions, operations, or steps of the embodiments disclosed herein. Embodiments according to the disclosure are in particular disclosed in the attached claims directed to a method, a storage medium, a system and a computer program product, wherein any feature mentioned in one claim category, e.g. method, can be claimed in another claim category, e.g. system, as well. The dependencies or references back in the attached claims are chosen for formal reasons only. However, any subject matter resulting from a deliberate reference back to any previous claims (in particular multiple dependencies) can be claimed as well, so that any combination of claims and the features thereof are disclosed and can be claimed regardless of the dependencies chosen in the attached claims. The subject-matter which can be claimed comprises not only the combinations of features as set out in the attached claims but also any other combination of features in the claims, wherein each feature mentioned in the claims can be combined with any other feature or combination of other features in the claims. Furthermore, any of the embodiments and features described or depicted herein can be claimed in a separate claim and/or in any combination with any embodiment or feature described or depicted herein or with any of the features of the attached claims.