Patent Publication Number: US-10771332-B2

Title: Dynamic scheduling of network updates

Description:
PRIORITY APPLICATION 
     This patent application is a continuation application of, and claims priority to, co-pending, commonly owned U.S. patent application Ser. No. 14/298,794, entitled “DYNAMIC SCHEDULING OF NETWORK UPDATES”, filed on Jun. 6, 2014, which is incorporated herein by reference in its entirety. 
    
    
     BACKGROUND 
     As electronic services (e.g., search services, electronic mail services, social networking services, cloud computing services, etc.) continue to expand, providers of the electronic services operate networks of devices to provide the electronic services. A provider or a manager of a network maintains the network by continuously updating inter-connected devices within the network. However, network service interruptions and/or failures often occur when implementing a network update across multiple devices at least because the network update is unable to adapt to run-time differences related to an amount of time it takes individual devices to apply and complete an update. For example, an update to a first device may take a longer amount of time than expected (e.g., more than an average amount of time) because of a current load on hardware resources of the first device. In another example, an update to the first device may not be completed at all. Consequently, an update to a second device may be affected by the unsuccessful or delayed update to the first device, and therefore, the network may experience a service interruption or a failure. 
     SUMMARY 
     The techniques and/or systems described herein are configured to determine a set of update operations to transition a network from an observed network state to a target network state and to generate an update dependency graph used to dynamically schedule the set of update operations based on constraint(s) defined to ensure reliability of the network during the transition. The techniques and/or systems dynamically schedule the set of update operations based on feedback. For example, the feedback may include an indication that a previously scheduled update operation has been delayed, has failed, or has been successfully completed. 
     In various embodiments, an update dependency graph may include multiple orderings in which a set of update operations can be scheduled. For instance, a first ordering may be associated with a first subset of update operations and a second ordering may be associated a second subset of update operations. At least one update operation may be included in both the first subset of update operations and the second subset of update operations such that it can be dynamically scheduled based on the first ordering or the second ordering. Stated another way, at least one update operation may be a child update operation that depends on successful completion of one of multiple parent update operations, e.g., a first parent update operation included in the first ordering or a second parent update operation included in the second ordering. 
     This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The detailed description is presented with reference to accompanying figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The use of the same reference numbers in different figures indicates similar or identical items. 
         FIG. 1  illustrates an example diagram showing a network update service configured to dynamically schedule individual update operations of a network update on a network, in accordance with various embodiments. 
         FIG. 2  illustrates an example diagram showing an environment that describes components of one or more devices configured to implement the network update service, in accordance with various embodiments. 
         FIG. 3  illustrates an example diagram showing changes made to transition at least part of a network from an observed network state to a target network state, in accordance with various embodiments. 
         FIG. 4  illustrates an example diagram showing an update dependency graph generated based on the changes of  FIG. 3 , in accordance with various embodiments. 
         FIG. 5  illustrates an example process that generates an update dependency graph to transition a state of a network from an observed network state to a target network state, in accordance with various embodiments. 
         FIG. 6  illustrates an example process that uses an update dependency graph to dynamically schedule individual update operations that comprise a network update, in accordance with various embodiments. 
         FIG. 7  illustrates an example diagram showing a state transition from an observed network state to a target network state for a portion of a network that forwards traffic, in accordance with various embodiments. 
         FIG. 8  illustrates an example diagram showing an update dependency graph generated based on the state transition of  FIG. 7 , in accordance with various embodiments. 
         FIG. 9  illustrates an example diagram showing a circular dependency in an update dependency graph, in accordance with various embodiments. 
         FIG. 10  illustrates an example process that schedules operation updates of a circular dependency in an update dependency graph, in accordance with various embodiments. 
     
    
    
     DETAILED DESCRIPTION 
     The techniques and/or systems described herein implement a network update service configured to generate an update dependency graph associated with update operations that transition (e.g., move) a state of a network from an observed network state to a target network state. The network update service uses the update dependency graph to dynamically schedule individual update operations so the network update can be implemented. The network update service generates the update dependency graph based on one or more constraints that are defined to ensure that implementation of the network update is reliable (e.g., reduces a chance that a network interruption or a network failure occurs). Using the update dependency graph, the network update service may dynamically schedule the individual update operations that comprise the network update based on feedback received from the devices in the network. 
     Stated another way, the update dependency graph may be a guide or navigational tool used by the network update service to dynamically select, during run-time, one or more next or subsequent update operations to implement based on received feedback associated with previously implemented update operations. For instance, the feedback may indicate that (i) an individual update operation has failed and not been successfully completed, (ii) an individual update operation has been delayed and not yet completed (e.g., but has not failed), or (iii) an individual update operation has been successfully completed. Based on the feedback received, the network update service may access and use the update dependency graph to dynamically identify and schedule a next update operation. 
     A first conventional approach to updating a network includes a “one shot” approach that determines a set of differences between an observed state of a network and a target state of a network and applies the differences to the relevant devices all at once or all at the same time (e.g., hence the terminology “one shot”). This conventional one shot approach to updating a network requires that updates to individual devices within the network are successfully completed at the same time. However, in most cases, device updates do not occur at the same time at least because the devices take different amounts of time to implement an update due to different hardware capabilities, different control loads on device resources, communication latencies (e.g., remote procedure call (RPC) delays), etc. Consequently, the conventional “one shot” approach is not reliable or safe at least because an update to a second device may depend on a successfully completed update to a first device in order to ensure network reliability and safety. If the update to the first device takes longer to implement than the update to the second device (i.e., the updates do not occur at the same time), or if the update to the first device is delayed or fails, the network may operate within a “transient” time period between a time when a successful update to the second device is completed and a later time when the update to the first device is eventually completed (e.g., five second transient time period, ten second transient time period, thirty second transient time period, a minute transient time period, etc.). Transient time periods often lead to network interruptions or failures such as routing loops, black holes, and/or congestion. Thus, while the conventional “one shot” approach attempts to implement a network update efficiently or all at once, it is unable to ensure that the network update is implemented reliably and safely. 
     A second conventional approach to updating a network improves reliability and safety, but is inefficient. This second conventional approach is a multi-step approach to updating a network where the network update is divided into different steps and the steps are statically ordered as part of fixed schedule that is predetermined before the update to the network begins. For example, after generating the fixed schedule, the second conventional approach may implement a first predetermined step of the network update (e.g., update a first device), wait for an indication that the first predetermined step was successfully completed, then implement a second predetermined step of the network update (e.g., update a second device), wait for an indication that the second predetermined step was successfully completed, then implement a third predetermined step of the network update, and so forth until the whole network update is completed. While the second conventional approach may improve reliability and safety of the network update, it is inefficient and slow because the fixed schedule is incapable of adapting to run-time conditions. For example, if an issue arises and completion of the first predetermined step is unsuccessful or is delayed, then subsequent predetermined steps in the fixed schedule are either unable to be implemented or must wait to be implemented. In some instances, a delayed or failed first predetermined step may be referred to as a straggler step. Or a device associated with a delayed or failed first predetermined step may be referred to as a straggler device. In many cases, by the time the straggler steps and/or the straggler devices catch up (e.g., an update is eventually completed successfully), the subsequent predetermined steps in the fixed schedule may be irrelevant (e.g., old updates, not meaningful, etc.). Thus, while being reliable and safe, the conventional approach that statically orders steps as part of a fixed schedule is also inefficient at least because it does not allow the fixed schedule to be modified, e.g., to account for a straggler step and/or a straggler device. 
     The network update service described herein is configured to implement a dynamic scheduling approach to implementing a network update. The network update service generates and uses an update dependency graph to dynamically schedule various update operations that comprise the network update. Put another way, the network update service is configured to access the update dependency graph after the network update has already begun to select and schedule a next update operation based on received feedback associated with update operations have already been scheduled (e.g., network update run-time conditions). 
     Unlike the “one shot” conventional approach discussed above, the update operations discussed herein are not all initiated at the same time. Furthermore, unlike the “static order” conventional approach above, the update operations discussed herein are not part of a fixed schedule that is predetermined before the network update is started. Rather, the update dependency graph may include various orderings of update operations and the network update service may dynamically schedule update operations based on one or more of the orderings after considering received feedback. For example, if a problem or a road-block arises along a first ordering and the network update service determines, e.g., at run-time, that an update operation that is part of the first ordering is delayed or has failed, then the network update service can use the update dependency graph to identify a second ordering and dynamically find an acceptable way to continue the network update even in light of a delayed or failed update operation. Therefore, one or more yet to be scheduled update operations that depend on the delayed or failed update operation, and that consequently cannot be scheduled via the first ordering, may be able to be scheduled in accordance with dependencies defined in a second ordering. 
     The network update service generates the update dependency graph based on dependencies resulting from defined constraints. In various embodiments, nodes of the update dependency graph correspond to update operations and edges between the nodes represent dependencies between the update operations (e.g., a first update operation is to be implemented before a second update operation). In various embodiments, nodes of the update dependency graph correspond to resource availability of a network element (e.g., a device or a communication path) such as link bandwidth availability and/or memory availability. 
     In various implementations, the network update service may define the constraints based on network consistency properties. To be consistent, a network update has to comply with, or not violate, properties established to protect the network from an interruption or a failure. A first example property may be a loop freedom property indicating that packets communicated in the network should not loop. A second example property may be a congestion freedom property indicating that traffic communicated via a link between two devices cannot exceed a predetermined and/or maximum capacity. Consequently, constraints may be defined based on these example properties and the constraints may impose dependencies on an order in which update operations can be implemented. For instance, a constraint may be defined to ensure that an update operation that brings a new flow to a link must occur after an update operation that removes an existing flow from the link (e.g., if the link cannot support both flows simultaneously due to a resource capacity limitation). Accordingly, the network update service is configured to use the update dependency graph to dynamically schedule a next update operation while respecting dependencies established based on defined constraints. 
       FIG. 1  illustrates an example diagram  100  that includes a network update service  102  configured to dynamically schedule individual update operations of a network update on a network  104 . The network  104  may comprise a variety of devices  106  and communications paths  108 . A communication path  108  may be associated with a direct link that connects two devices or may comprise an indirect link that connects two devices in which traffic is communicated via at least one intermediary device located between the two devices. In one implementation, a communication path  108  may comprise a communication tunnel established through, or for, two or more devices  106 . 
     In various embodiments, the network  104  being managed may be a large production network such as a data-center network (DCN), an Internet service provider (ISP) network, an enterprise network (e.g., a cloud service) or any other administrative domain that may be under control of an entity (e.g., an entity that operates and maintains devices executing the network update service  102 ). The devices  106  may be physical network devices such as a switching device (a switch), a routing device (a router), a gateway device (a gateway), a bridging device (a network bridge), a hub device (a network hub), a firewall device, a network address translator device (a NAT), a multiplexing device (a multiplexer), a wireless access point device (a WAP), a proxy server device, a file server device, a database server device, a storage device, etc. The devices  106  may also be end-user devices capable of connecting to the network  104 . For instance, an end-user device may comprise a mobile or portable device such as a smart phone, a cellular phone, a personal digital assistant (PDA), an electronic book device, a laptop computing device, a tablet computing device, a personal media player device, etc. Or, an end-user device may comprise a stationary device such as a desktop computing device, a gaming console device, a digital video recording device (a DVR), a set top box device, etc. Therefore, the network  104  may comprise tens, hundreds or thousands of devices connected to one another to comprise a domain or an administrative network. 
     When updating the network  104 , the network update service  102  is configured to determine changes  110  that transition a state of a network from an observed network state  112  to a target network state  114 . As used herein, the “state” of a network  104  is dependent on the states of individual devices  106  and/or individual communication paths  108  within the network  104 . In various implementations, an individual device  106  or an individual communication path  108  may have one or more state variables and at any given time a state variable may be any one of various values. In various embodiments, a state variable is defined as a component of a device  106  or a communication path  108  for which a value can be read and/or written (e.g., a controllable value that can be changed from an observed value to a target value desired that is different than the observed value). Accordingly, a change  110  may be associated with changing a state variable from a first value to a second value. A change to a state variable may be a direct change such that the first value is changed to a second value. Or, a change to a state variable may be an indirect change such that the first value to a second value via an intermediate value that is neither the first value nor the second value. 
     For example, a device  106  may comprise a power state variable that indicates whether the device  106  is powered on or powered off. Thus, a first value for the power state variable may indicate the device  106  is powered on and a second value for the power state variable may indicate the device  106  is powered off. These different values can be read from the device  106  (e.g., observed) and/or written to the device  106 . In another example, a device  106  may comprise a routing state variable that indicates one of various communication paths for which a device  106  is to use to transmit data (e.g., an ingress switching device). Thus, a first value for the routing state variable may indicate the device  106  is to transmit data (e.g., a traffic flow) to another device in the network using a first communication path and a second value for the routing state variable may indicate the device  106  is to transmit data to the other device in the network using a second communication path that is different than the first communication path. 
     In various embodiments, the target network state  114  may be generated based on state variable value changes requested and/or proposed by various applications  116 ( 1 ) . . .  116 (N). An application (e.g., one of  116 ( 1 ) . . .  116 (N)) may be responsible for managing and controlling a particular aspect or function of the network  104  so that the network  104  operates efficiently and reliably. In various embodiments, the particular aspect or function of the network  104  managed and controlled by an individual application (e.g., one of  116 ( 1 ) . . .  116 (N)) may be associated with a single device  106  and/or a single communication path  108  of the network  104  or a subset of the devices  106  and/or a subset of communication paths  108  of the network (e.g., a particular type of devices such as switching devices). 
     An application (e.g., one of  116 ( 1 ) . . .  116 (N)) may be classified as a routing management application that manages switch forwarding rules for the devices  106  (e.g., switching devices) and/or the communication paths  108  of the network  104 . For example, a traffic-engineering application may be a routing management application that is configured to steer traffic along different communication paths  108  (e.g., a communication tunnel established through/for two or more devices  106 ) to improve network utilization and/or ensure that performance requirements are satisfied. In another example, a server load balancing application may be a routing management application that divides (e.g., equally) a communication load (e.g., traffic) across devices (e.g., a group of servers processing requests for data). 
     An application (e.g., one of  116 ( 1 ) . . .  116 (N)) may be classified as an infrastructure management application that manages the network infrastructure of devices  106  and/or communication paths  108  of the network  104 . For example, a power management application may be an infrastructure management application that is configured to turn a switching device or off at any given time in order to mitigate a failure or save energy. In another example, a switch upgrade application may be an infrastructure management application that is responsible for installing a new operating system (i.e., firmware) on a switching device. 
     The applications described above are provided herein as example applications, and it is contemplated that other applications developed to control an aspect or a function of a network may also benefit from the techniques and/or systems described in this document. 
     In various embodiments, the network update service  102  may determine the changes  110  by calculating differences between the observed network state  112  and the target network state  114 . The calculated differences may be the differences between one or more observed state variable values and one or more corresponding desired state variable values to be written to the network  104 . Put another way, given the observed network state  112  and the target network state  114  as inputs, the network update service  102  may compute a set of update operations based on the changes  110 . Then, the network update service  102  is configured to generate an update dependency graph  118  based on one or more defined constraints  120 . For instance, the network update service  102  is configured to determine dependencies between update operations based on the constraints and generate one or more acceptable and reliable orderings that inter-link the update operations. 
     The constraints  120  may be defined by an entity operating the network update service  102 , an entity being served by the network  104 , and/or one of the applications  116 ( 1 ) . . .  116 (N). As discussed above, the constraints  120  may be defined in light of properties and/or policies configured to ensure that the network  104  operates reliably, safely and efficiently. For example, consistency related properties may include, but are not limited to, one or more of (i) a black hole freedom property that ensures that communication units (e.g., data packets) are not dropped at a device (e.g., a switching device), (ii) a loop freedom property that ensures that communication units are not looped within the network; (iii) a packet coherence property that ensures that communication units are not transmitted in the network based on a mix of an old routing instruction (e.g., that is part of an observed network state) and a new routing instruction (e.g., that is part of the target network state), (iv) a congestion freedom property that ensures that the routing of communication units within the network do not cause congestion (e.g., a link is not congested due to exceeding a bandwidth limitation), and (v) a memory overload that ensures that available memory resources at a device is sufficient to meet memory needs associated with a target state. 
     The update dependency graph  118  is comprised of multiple nodes and edges. In various embodiments, the nodes of the update dependency graph  118  may be operation type nodes. An operation node represents an update operation to be scheduled, the update operation being associated with one or more changes to be written to the network  104  (e.g., a new value proposed by an application). For example, an operation node may be associated with a change to a traffic routing state variable at a switching device (e.g., an addition, deletion or modification of a traffic forwarding rule that moves traffic flow from a first communication path to a second communication path). A second type of node includes a resource node that may be associated with resource availability at one or more devices. For example, a resource node may indicate an amount of available memory based on a current memory load or an amount of available communication bandwidth based on a current load. 
     An edge between two operation nodes in the update dependency graph  118  represents an operation dependency between two update operations to be implemented and thereby signals that a first update operation (e.g., a parent update operation of a parent node) is to be implemented before a second update operation (e.g., a child update operation of child node that depends upon successful completion the parent update operation). An edge between a resource node and an operation node in the update dependency graph  118  represents a resource dependency. For instance, an edge that starts at an operation node and ends at, or leads to, a resource node may have an associated label indicating an amount of the resource that will be freed or become available (e.g., resource available for use) after the update operation represented by the operation node at which the edge starts is successfully completed. An edge that starts at a resource node and ends at, or leads to, an operation node may have an associated label indicating an amount of available resource required before an update operation being represented by the operation node at which the edge ends can be implemented (e.g., resource needed for consumption). In various embodiments, the update dependency graph  118  may solely include operation nodes if no resource constraints are defined (e.g., a constraint defined based on a congestion freedom property). In other embodiments, the update dependency graph  118  may include operation nodes and resource nodes. 
     Once generated, the update dependency graph  118  may comprise multiple acceptable and reliable orderings which can be followed to implement the network update. Stated another way, the network update service  102  may be provided with various ways to navigate the update dependency graph  118 . Therefore, the network update service  102  is able to dynamically, e.g., based on run-time conditions, select a next update operation to schedule. 
     For example, if successful completion of an update operation is delayed or stalled and subsequent update operations along a first ordering depend upon the delayed or stalled update operation, then the network update service  102  may access the update dependency graph  118  to identify a second ordering (e.g., a different route or solution in the graph) that does not include the delayed or stalled update operation but still leads to the subsequent update operations. Thus, the network update service  102  uses the update dependency graph  118  to dynamically find a way around (e.g., an alternative ordering) the delayed or stalled update operation so the subsequent update operations can still be scheduled. Thus, the network update service  102  described herein does not use a fixed schedule to implement the network update. Rather, as long as the network update service  102  maintains the update dependency graph  118  based on computed changes  110  that transition a state of a network from the observed network state  112  to the target network state  114 , the network update service  102  can implement a network update more efficiently while also ensuring the network update is safe and reliable. 
     The network update service  102  is configured to use the update dependency graph  118  to dynamically schedule update operations based on feedback  122  received from the network  104 . The feedback  122  may be explicit feedback provided by elements (e.g., devices  106 ) of the network  104  which may include an indication that (i) an update operation has been successfully completed (e.g., on time, within a predetermined amount of time), (ii) the update operation has not yet been completed but is still being in the process of being implemented (e.g., the update is delayed, will not be completed in a predetermined or expected amount of time), or (iii) the update operation has failed and cannot be successfully completed. The feedback  122  may also, or alternatively, be implied feedback such that the network update service  102  monitors the progress of individual update operations and observes whether the update operation has been successfully or unsuccessfully completed or whether the update operation has been delayed (e.g., not completed with an expected or predetermined amount of time). 
     Based on the feedback  122 , the network update service  102  can use the update dependency graph  118  to select a next update operation and dynamically schedule  124  the next update operation so that the network update can continue. Accordingly, the network update service  102  implements a more efficient and reliable approach to updating a network or a part of a network at least because it determines multiple reliable orderings (e.g., that respect dependencies) in which the network update can be implemented and it uses the orderings to dynamically select a next operation update to be implemented in light of feedback  122  received from the network (e.g., a switching device is currently delayed in implementing an already scheduled update operation). 
       FIG. 2  is a diagram showing an example environment  200  that implements the network update service  102  described above. In various embodiments, the network update service  102  may be implemented via one or more devices  202 . A device  202  may comprise a stationary device such as a desktop computing device, a server computing device, or the like. A device  202  may alternatively comprise a mobile or portable device such as a laptop computing device, a tablet computing device, a smart phone device, a cellular phone device, a personal digital assistant (PDA) device, an electronic book device, or the like. 
     The device(s)  202  include the network update service  102  configured to implement the techniques described herein. A device  202  may individually and separately include one or more processor(s)  204  and memory  206 . The processor(s)  204  may be a single processing unit or a number of units, each of which could include multiple different processing units. The processor(s)  204  may include a microprocessor, a microcomputer, a microcontroller, a digital signal processor, a central processing unit (CPU), a graphics processing unit (GPU), a security processor etc. Alternatively, or in addition, some or all of the techniques described herein can be performed, at least in part, by one or more hardware logic components. For example, and without limitation, illustrative types of hardware logic components that can be used include a Field-programmable Gate Array (FPGA), an Application-specific Integrated Circuit (ASIC), an Application-specific Standard Products (ASSP), a state machine, a Complex Programmable Logic Device (CPLD), other logic circuitry, a system on chip (SoC), and/or any other devices that perform operations based on instructions. Among other capabilities, the processor(s)  204  may be configured to fetch and execute computer-readable instructions stored in the memory  206 . 
     The memory  206  may include one or a combination of computer-readable media. As used herein, “computer-readable media” includes computer storage media and communication media. 
     Computer storage media includes volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer-readable instructions, data structures, program modules, or other data. Computer storage media includes, but is not limited to, phase change memory (PRAM), static random-access memory (SRAM), dynamic random-access memory (DRAM), other types of random access memory (RAM), read only memory (ROM), electrically erasable programmable ROM (EEPROM), flash memory or other memory technology, compact disk ROM (CD-ROM), digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium that can be used to store information for access by a device. 
     In contrast, communication media includes computer-readable instructions, data structures, program modules, or other data in a modulated data signal, such as a carrier wave. As defined herein, computer storage media does not include communication media. 
     The memory  206  may include an operating system that is configured to manage hardware and services within and coupled to a device for the benefit of other modules, components and devices. In some instances, at least part of the network update service  102  may be implemented within, or by, the operating system. 
     The network update service  102  includes one or more of a graph generating module  208  and a scheduling module  210 . As used herein, the term “module” is intended to represent example divisions of the software for purposes of discussion, and is not intended to represent any type of requirement or required method, manner or organization. Accordingly, while various “modules” are discussed, their functionality and/or similar functionality could be arranged differently (e.g., combined into a fewer number of modules, broken into a larger number of modules, etc.). Further, while certain functions and modules are described herein as being implemented by software and/or firmware executable on one or more processors across one or more devices, in other embodiments, any or all of the modules may be implemented in whole or in part by hardware (e.g., as an ASIC, a specialized processing unit, etc.) to execute the described functions. In other instances, the functions and/or modules are implemented as part of a device driver, firmware, and so on. 
     The graph generating module  208  is configured to determine and/or receive the changes  110  that move a state of the network  104  from the observed network state  112  to the target network state  114 . For example, the changes  110  may be associated with calculated differences and a calculated difference may include instruction or commands that change a state variable value from an observed value to a desired value may (e.g., a device-specific instruction or command). As discussed above, the change may be a direct change or an indirect change and a specific update operation may be associated with an operation node in the update dependency graph  118 . Therefore, the graph generating module  108  generates and maintains the update dependency graph  118  based on the changes  110  and stores the updating dependency graph  118  in an update dependency graph store  212 . Moreover, the graph generating module  208  generates the update dependency graph  118  based on defined constraints  120  stored in a constraints store  214 . As discussed above, the constraints  120  may be defined by one or more of an entity operating the network update service  102 , an entity being served by the network  104  (e.g., if different than the entity operating the network update service  102 ), or a developer of one of the applications  116 ( 1 ) . . .  116 (N). 
     The scheduling module  210  is configured to receive the feedback  122  from the network and dynamically, e.g., based on run-time conditions, schedule  124  one or more subsequent or next update operations via the state dependency graph  118 . In various embodiments, the scheduling module  210  may use any one of a variety of scheduling algorithms to dynamically schedule the update operations. The use of a scheduling algorithm may depend on resources allocated to the network update service  102  to implement the network update. In one implementation, the scheduling module  210  may implement a critical path scheduling algorithm to implement a network update. In accordance with the critical path scheduling algorithm, the scheduling module  210  is configured to calculate path lengths (e.g., a length of an ordering) and identify a longest critical path. The scheduling module  210  is then configured to prioritize the scheduling of update operations associated with nodes that are part of a longest critical path so that an overall amount of time to implement the network update is minimized. That is, the scheduling module  210  may continually work to shorten the longest critical path by dynamically scheduling update operations associated with nodes on the longest critical path. An example critical-path scheduling algorithm is provided later in this document. Moreover, other scheduling algorithms may also be used to dynamically schedule the network update using the update dependency graph. 
     Upon successful completion of an update operation associated with an operation node in the update dependency graph, the scheduling module  210  may be configured to remove the operation node from the update dependency graph at least because it no longer is associated with an update operation to be implemented. 
     In various embodiments, a device  202  includes one or more communication unit(s)  216 . The communication unit(s)  216  may be configured to facilitate a wired and/or wireless connection to one or more networks (e.g., network  104 ), applications  116 ( 1 ) . . .  116 (N) operated by various service or content providers, and/or other devices. Therefore, the communication unit(s)  216  may implement one or more of various communications or network connection protocols. 
       FIG. 3  is a diagram  300  illustrating changes to be made to transition at least part of a network from an observed network state  302  to a target network state  304 . The diagram  300  shows data traffic flows between devices  306 ( 1 ) . . .  306 ( 5 ) (e.g., a set of network switching devices that comprise part of a network in this example). In this example, a resource constraint is defined to limit a communication or traffic load of each direct link between two devices to a maximum or threshold capacity (e.g., ten units in this example). An example unit for a communication or traffic flow may be Gbps (gigabits per second). Thus, the graph generating module  208  is configured to generate an update dependency graph so that the changes can be made in one of various orders without violating a defined constraint. In the example of  FIG. 3 , communication tunnels have already been established, and therefore, moving a traffic flow from a first communication path to a second communication path can be implemented by updating an ingress switching device (e.g., a state variable of the ingress switching device). 
     In the observed network state  302 , a first traffic flow  308 ( 1 ) shows five units representing observed traffic flow from device  306 ( 1 ) to device  306 ( 5 ) via device  306 ( 4 ). A second traffic flow  308 ( 2 ) shows five units representing observed flow from device  306 ( 2 ) to device  306 ( 5 ) via device  306 ( 1 ). A third traffic flow  308 ( 3 ) shows ten units (e.g., the maximum allowed capacity) representing observed flow from device  306 ( 3 ) to device  306 ( 5 ) via device  306 ( 2 ). A fourth traffic flow  308 ( 4 ) shows five units representing observed flow from device  306 ( 4 ) to device  306 ( 5 ) via device  306 ( 1 ). 
     In the target network state  304 , the first traffic flow  308 ( 1 ) of the observed network state  302  has been moved to a target first traffic flow  310 ( 1 ) that shows five units flowing from device  306 ( 1 ) directly to device  306 ( 5 ). The second traffic flow  308 ( 2 ) of the observed network state  302  has been moved to a target second traffic flow  310 ( 2 ) that shows five units flowing from device  306 ( 2 ) directly to device  306 ( 5 ). The third traffic flow  308 ( 3 ) of the observed network state  302  has been moved to a target third traffic flow  310 ( 3 ) that shows ten units flowing from device  306 ( 3 ) directly to device  306 ( 5 ). And the fourth traffic flow  308 ( 4 ) of the observed network state  302  has been moved to a target fourth traffic flow  310 ( 4 ) that shows five units flowing from device  306 ( 4 ) directly to device  306 ( 5 ). 
     Since the various switching devices  306 ( 1 ) . . .  306 ( 5 ) in  FIG. 3  are likely to apply the traffic flow updates at different times, a one shot approach that simultaneously issues all the update operations/commands to the various switching devices  306 ( 1 ) . . .  306 ( 5 ) at the same time is likely to cause congestion on at least some direct links (e.g., exceed the ten unit capacity). For example, if device  306 ( 1 ) successfully completes the update operation that moves flow  308 ( 1 ) to target flow  310 ( 1 ) before device  306 ( 2 ) successfully completes the update operation that moves flow  308 ( 2 ) to target flow  310 ( 2 ) and before device  306 ( 4 ) successfully completes the update operation that moves flow  308 ( 4 ) to target flow  310 ( 4 ), then the load or bandwidth demand on the direct link between device  306 ( 1 ) and  306 ( 5 ) will be fifteen units and will exceed the ten unit maximum capacity defined by a resource constraint. This causes congestion within the network. 
     To ensure that the maximum capacity of a link (e.g., ten units in the example of  FIG. 3 ) is not exceeded when implementing the changes in  FIG. 3 , the graph generating module  208  is configured to generate the example update dependency graph  400  of  FIG. 4 . 
     The circle nodes in the update dependency graph  400  of  FIG. 4  represent operation nodes. The rectangle nodes in the update dependency graph  400  of  FIG. 4  represent resource nodes that indicate available resources (e.g., available link bandwidth). A label on an edge that starts at an operation node and ends at, or leads to, a resource node indicates the amount of resource that is freed or released after an update operation associated with the operation node at which the edge starts is successfully completed. A label on an edge that starts at a resource node and ends at, or leads to, an operation node indicates the amount of available resources required to perform the update operation associated with the operation node at which the edge ends (e.g., resources consumed by the update operation). 
     Accordingly, in the observed network state  302  of  FIG. 3 , the link between device  306 ( 2 ) and device  306 ( 5 ) has “zero” available bandwidth, as indicated via resource node  402  of the example update dependency graph  400 . Moving the observed traffic flow  308 ( 3 ) to the target traffic flow  310 ( 3 ), as indicated via operation node  404 , releases ten units to the link between device  306 ( 2 ) and device  306 ( 5 ) and the edge from operation node  404  to resource node  402  is labeled to indicate the released resources (e.g., ten units). Furthermore, operation node  406  indicates that the observed traffic flow  308 ( 2 ) is to be moved to the target flow  310 ( 2 ) subsequent to moving the observed traffic flow  308 ( 3 ) to the target traffic flow  310 ( 3 ). The edge from resource node  402  to operation node  406  is labeled to indicate that five units are required to implement the update operation of operation node  406  (e.g., five available units between device  306 ( 2 ) and device  306 ( 5 ) are needed). 
     Moving on, resource node  408  indicates that the link between device  306 ( 1 ) and device  306 ( 5 ) has “zero” available bandwidth in the observed state. Moving the observed traffic flow  308 ( 2 ) to the target traffic flow  310 ( 2 ), as indicated via operation node  406 , releases five units to the link between device  306 ( 1 ) and device  306 ( 5 ) and the edge from operation node  406  to resource node  408  is labeled to indicate the released resources. Furthermore, moving the observed traffic flow  308 ( 4 ) to the target traffic flow  310 ( 4 ), as indicated via operation node  410 , also releases five units to the link between device  306 ( 1 ) and device  306 ( 5 ) and the edge from operation node  410  to resource node  408  is labeled to indicate the released resources. 
     Furthermore, operation node  412  indicates that the observed traffic flow  308 ( 1 ) is to be moved to the target flow  310 ( 1 ) after either an update operation associated with one of operations nodes  410  or  406  is successfully completed. The edge from resource node  408  to operation node  412  is labeled to indicate that five units are required to implement the operation of operation node  412  (e.g., five available units between device  306 ( 1 ) and device  306 ( 5 ) are needed). 
     Given the update dependency graph  400  in  FIG. 4 , the scheduling module  210  can dynamically schedule the update operations while also ensuring that link congestion is avoided. For instance, the schedule module  210  may determine that moving observed traffic flow  308 ( 3 ) to target traffic flow  310 ( 3 ) and moving observed traffic flow  308 ( 4 ) to target traffic flow  310 ( 4 ) do not depend on other update operations. Thus, the update operations represented by operation nodes  404  and  410  can be scheduled immediately and/or in parallel without violating a network congestion property. After the operation associated with operation node  404  is completed, the scheduling module  210  can schedule the operation associated with operation node  406 . Finally, the scheduling module  210  can dynamically schedule the update operation associated with operation node  412  after determining, e.g., based on feedback, that either one of the update operation associated with node  406  or the update operation associated with node  410  is successfully completed. 
     As seen in the example described with respect to  FIG. 3  and  FIG. 4 , the scheduling module  210  can use an update dependency graph to dynamically schedule update operations based on feedback received from the network and in any one of various orders. For example, the scheduling module  210  may determine that the update operation associated with operation node  410  is a straggler update operation that is stalled or delayed, and thus, the scheduling module  210  is aware that the update operation associated with operation node  412  can alternatively be implemented after the update operation associated with operation node  406  is successfully completed (e.g., because enough resources are released to satisfy the resources needed). Accordingly, the operation node  412  (e.g., a child node) may be implemented after a first ordering of update operations (e.g., parent operation nodes  404  and  406 ) is successfully completed or after a second ordering of update operation(s) (e.g., parent operation node  410 ) is successfully completed. 
     In the “static ordering” conventional approach discussed above, operation node  412  may have been a subsequent step in a fixed schedule that had to wait until the update operation associated with operation node  410  is completed. For example, the fixed schedule that cannot be changed after the network update begins may have required that: the observed flow  308 ( 3 ) is moved to target flow  310 ( 3 ) first, the observed flow  308 ( 2 ) is moved to target flow  310 ( 2 ) second, the observed flow  308 ( 4 ) is moved to target flow  310 ( 4 ) third, and only then can the observed flow  308 ( 1 ) be moved to target flow  310 ( 1 ). 
     Therefore, the update dependency graph provides scheduling flexibility such that the scheduling module  210  can still move observed flow  308 ( 1 ) to target flow  310 ( 1 ) even if there is a failure or delay associated with one of operation nodes  406  or  410 . In some instances, to improve network update efficiency, the scheduling module  210  may dynamically schedule operation node  412  in response to determining that one of operation nodes  406  and  410  is completed faster than expected. 
     The example update dependency graph  400  is provided herein as an example only, and it is understood that update dependency graphs may include many more nodes and dependencies based on (i) a number of changes to be made to move a state of a network from an observed state to a target state and/or (ii) a number of constraints defined. 
       FIGS. 5, 6 and 10  illustrate example processes individually depicted as a logical flow graph, which represents a sequence of operations that can be implemented in hardware, software, firmware, or a combination thereof. In the context of software, the operations represent computer-executable instructions that, when executed by one or more processors, configure a computing device to perform the recited operations. Generally, computer-executable instructions include routines, programs, objects, components, data structures, and the like that configure a computing device to perform particular functions or implement particular abstract data types. In some embodiments, any or all of the operations may be implemented in whole or in part by hardware (e.g., as an ASIC, a specialized processing unit, etc.) to execute the described functions. In some instances, the functions and/or modules are implemented as part of an operating system. In other instances, the functions and/or modules are implemented as part of a device driver, firmware, and so on. 
     The order in which the operations are described in an example process is not intended to be construed as a limitation, and any number of the described operations can be combined in any order and/or in parallel to implement an example process. 
       FIG. 5  illustrates an example process  500  that determines changes to transition a state of a network from an observed network state to a target network state. The example operations in  FIG. 5  may be described with reference to the modules, components and/or elements illustrated in any one of  FIGS. 1-4 . 
     At  502 , the graph generating module  208  may determine an observed network state. For example, the observed network state may include one or more observed state variable values of a network (e.g., network  104 ). The observed network state may be stored and/or updated over time (e.g., in accordance with a periodic observing schedule). Accordingly, the graph generating module  208  may access a data store to determine the observed network state or the graph generating module  208  may receive the observed network state e.g., from a network observing service or network observing entity. 
     At  504 , the graph generating module  208  may determine a target network state. For example, the target network state may comprise, or be generated based on, one or more changes to the observed network state. For example, applications (e.g., applications  116 ( 1 ) . . .  116 (N)) tasked with managing a particular network function, may request or propose changes to one or more state variable values. The changes may indicate a desire to transition (e.g., move) a state variable value from an observed value to a target value (e.g., directly or indirectly). The target network state may be stored and/or updated over time (e.g., in accordance with a periodic or continuous network updating schedule). Accordingly, the graph generating module  208  may access a data store to determine the target network state or the graph generating module  208  may receive the target network state, e.g., from a service or entity that generates the target network state. 
     At  506 , the graph generating module  208  may determine update operations (e.g., a set of update operations) to transition a state of the network from the observed network state to the target network state. The update operations may be associated with the changes proposed or requested by the applications  116 ( 1 ) . . .  116 (N), for example. The update operations may comprise update instructions and/or commands to be issued to a device in the network to change one or more state variable values from an observed value to a target value. 
     At  508 , the graph generating module  208  may receive or access one or more constraints. As discussed above, the constraints may be defined to ensure reliability of the network. For example, the constraints may be defined to ensure that a network state transition complies with one or more consistency properties, as discussed above. 
     At  510 , the graph generating module  208  may generate an update dependency graph based on the update operations and the constraints. The update dependency graph may define various acceptable orderings in which the update operations can be dynamically scheduled. The orderings ensure that defined constraints are not violated, and therefore, the network state transition is reliable and safe. Moreover, since various orderings may be defined, the network state transition may be more efficient because if a first ordering stalls (e.g., a straggler device or a straggler operation is encountered along the first ordering), then the update dependency graph provides a second ordering in which the network state transition can continue. 
     The example process  500  may continually be implemented as part of an on-going network management and maintenance service. Thus, the observed network state and/or the target network state may continue to change, and therefore, the update dependency graph is generated and/or maintained to reflect updated changes that transition a state of the network from the observed network state to the target network state. 
       FIG. 6  illustrates an example process  600  that uses an update dependency graph to dynamically schedule individual update operations that comprise a network update. The example operations in  FIG. 6  may be described with reference to the modules, components, elements and/or operations illustrated in any one of  FIGS. 1-5 . 
     At  602 , the scheduling module  210  may determine one or more starting nodes within an update dependency graph. The starting nodes are associated with update operations that may be scheduled first, to implement a network update. In various embodiments, the starting nodes may be determined based on critical path scheduling in which a longest path through the update dependency graph is determined. 
     At  604 , the scheduling module  210  begins scheduling update operations based on the starting nodes. For example, the scheduling module  210  may begin scheduling update operations in accordance with one or more orderings. 
     At  606 , the scheduling module  210  receives feedback indicating successful, unsuccessful (e.g., failed) or delayed completion of a previously scheduled update operation (e.g., an update operation associated with a starting node). 
     At  608 , the scheduling module  210  may access the update dependency graph to dynamically schedule one or more subsequent update operations based on the feedback. For example, if the feedback indicates that the previously scheduled update operation has failed or is delayed, then the scheduling module  210  may use the update dependency graph to select for scheduling an update operation that does not depend on successful completion of the failed or delayed update operation. The previously scheduled update operation may be part of a first ordering in the update dependency graph and the selected update operation may be part of a second ordering in the update dependency graph. The scheduling module  210  continues to iteratively perform operations  606  and  608 . For example, the scheduling module  210  continues to iteratively perform operations  606  and  608  until a transition from an observed network state to a target network state is completed. 
     The discussion provided below describes implementations where the network update service  102  transitions the network from an observed network state to a target network state in association with tunnel-based forwarding and/or weighted cost multi-path (WCMP) forwarding. 
     For purposes of the discussion provided herein, a network G (e.g., at least a portion of network  104 ), may comprise a set of switching devices, S, and a set of direct links, L, where a direct link connects two switching devices. A flow f represents data communicated, e.g., via an established tunnel, from an ingress switching device, s i , to an egress switching device, s j , with traffic volume t f . The network may use a path set P f  to carry traffic (e.g., may also be referred to as a tunnel set). Thus, the forwarding state of f may be defined as R f ={r f,p |p ∈ P f } where r f,p  is the traffic load of f on path p. The network state NS can then be represented as the combined state of all flows such that NS={R f |f ∈ F}. Relative weights may be set at an ingress switching device to determine how the flow is split, or divided, amongst multiple paths or tunnels. 
     As an illustrative example,  FIG. 7  shows at least part of a network  700 , e.g., configured to communicate data units (e.g., data packets, Gbps, etc.), that transitions from an observed network state  702  to a target network state  704 . The network  700  includes five switching devices,  706 ( 1 ) . . .  706 ( 5 ), (e.g., these may also be referred to herein as individual switching devices s 1 , s 2 , s 3 , s 4 , s 5 ). The observed network state  702  has a flow (a flow is represented by a dashed line) across a first path, p 1 ,  708 , and a second path, p 2 ,  710 , with five data units of traffic flowing along each of the first path, p 1 ,  708  and the second path, p 2 ,  710  (e.g., shown a “5” in  FIG. 7 ). In the example of  FIG. 7 , it follows that the traffic volume t f =10, the path set P f ={p 1 =s 1 s 2 s 3 s 5 , p 2 =s 1 s 2 s 5 }, and the forwarding state for f is R f ={r f,p1 =5, r f,p2 =5}.  FIG. 7  also illustrates that the target network state  704  of the network  700  has a flow across a same first path, p 1 ,  708  and a new third path, p 3 ,  712 . The target network state  704  does not include the old second path, p 2 ,  710  from the observed network state  702 . 
     The network update service  102  may use the representations in the preceding paragraph in association with tunnel-based forwarding that may be used in Wide-Area Networks (WANs), for example. The network update service  102  may also use the representations in the preceding paragraph in association with WCMP forwarding that may be used in data center networks (DCNs), for example. 
     In tunnel-based forwarding, a flow may be forwarded by multiple paths. The ingress switching device (e.g., switching device  706 ( 1 )/s 1  in  FIG. 7 ) may (i) match incoming traffic to the flow, e.g., based on data packet headers, and (ii) split the incoming traffic across the multiple paths based on weights. Before forwarding a data packet along a path, the ingress switching device may tag the data packet with a path identifier. Subsequent switching devices (e.g., switching devices  706 ( 2 )/s 2  and  706 ( 3 )/s 3  along the first path, p 1 ,  708 ) may forward the data packets based on the path identifier and an egress switching device (e.g., switching device  706 ( 5 )/s 5  in  FIG. 7 ) may remove the path identifier after the data packet arrives. Thus, for tunnel-based forwarding P f  is the set of paths (or tunnels) and the weight of a path is r f,p /t f  (e.g., five divided by ten in  FIG. 7  or 50% weight for each of the first path, p 1 ,  708  and the second path, p 2 ,  710 ). 
     In WCMP forwarding, switching devices at every hop along a path may match packet headers and split flows over one or more next hops with set weights. Shortest-path and equal cost multi-path (ECMP) forwarding are example types of WCMP forwarding. For WCMP forwarding, the network update service  102  may calculate a traffic rate of the flow on link l using Equation (1) as follows:
 
 r   f   l =Σ l∈p,p∈P     f      r   f,p   equ. (1)
 
     Then at switch s i , the weight for a next hop s j  may be determined using Equation (2) as follows:
 
 w   i,j   =r   f   l     ij   /Σ l∈L     i      r   f   l   equ. (2)
 
     Here l ij  is the link from s i  to s j  and L i  is the set of links starting at s i . For example, in the observed network state  702  of  FIG. 7 , w 1;2 =1, w 1;4 =0, w 2;3 =0.5, and w 2;5 =0.5. 
     As discussed above, the network update service  102  may be configured to receive, as an input, a current (e.g., observed) network state, NS c , a target network state, NS t , and one or more constraints associated with one or more consistency properties. The network update service  102  can then determine (e.g., compute) a set of update operations (e.g., based on changes  110 ) that transition a state of the network from the current network state NS c  (e.g.,  702  in  FIG. 7 ) to the target state NS t  (e.g.,  704  in  FIG. 7 ) and inter-link the update operations to build an update dependency graph so that the constraints are not violated when a network update is implemented. Therefore, the state transition is reliable and safe. 
     For these example data forwarding implementations, in addition to operation nodes and resource nodes, the graph generating module  208  may be configured to include path nodes in an update dependency graph. A path node may further organize an update dependency graph by grouping update operations and/or link capacity resources that are associated with an individual path. A path node can connect to operation nodes and/or resource nodes. An edge from an operation node to a path node can be an operation dependency or a resource dependency. As part of the scheduling process, a path node that releases link resources may have an associated “committed” label that indicates an amount of traffic that is moving away from the path as a network transitions from the observed network state to the target network state. After the traffic is moved away, the committed label may be used to update an amount of available resources. 
       FIG. 8  illustrates an example update dependency graph  800  generated for tunnel-based forwarding based on the state transition shown in  FIG. 7 . The graph generating module  208  may generate the update dependency graph  800  based on constraints defined to ensure black hole freedom for a network. In various embodiments, the constraints may indicate that (i) a new path is to be fully established before an ingress switching device applies traffic to the new path, and (ii) all traffic is removed from a path to be deleted before the path is removed from any downstream switching device. 
     The graph generating module  208  may generate the update dependency graph  800  based on the constraints specified in the preceding paragraph as follows. For each flow f, using NS c  and NS t , the graph generating module  208  may determine paths to be added and/or to be deleted and may generate a path node for each added and/or deleted path. Then, the graph generating module  208  may generate an operation node for individual hops and add an edge from (i) an operation node to the path node or (ii) from the path node to an operation node, thereby indicating that a path is added or deleted at a switching device. The graph generating module  208  may generate an operation node that changes the path weights so that the weights correspond to those specified in the NS t  at the ingress switching device. To ensure black hole freedom, the graph generating module  208  may add an edge from each path node that adds a new tunnel to the operation node that changes the path weights. Further, the graph generating module  208  may add an edge from the operation node that changes the path weights to each path node that deletes an old path. 
     As discussed above with respect to  FIG. 7 , the path weights on the first path, p 1 ,  708  and the second path, p 2 ,  710  of the observed network state  702  are 0.5 and 0.5 respectively. In the target network state  704 , a path is added (e.g., the third path, p 3 ,  712 ) and a path is deleted (e.g., the second path, p 2 ,  710 ) and the path weights are changed to 0.5 on the first path, p 1 ,  708  and 0.5 on the third path, p 3 ,  712 . 
     To generate the update dependency graph  800  for this transition, the graph generating module  208  may generate a path node  802 , e.g., triangle node corresponding to the second path, p 2 ,  710 , which is a path to be deleted via the state transition of  FIG. 7 . The graph generating module  208  may also generate a path node  804 , e.g., triangle node corresponding to the third path, p 3 ,  712 , which is a path to be added via the state transition of  FIG. 7 . The graph generating module  208  may further generate: operation node  806  associated with operation A specified in Table 1 below, operation node  808  associated with operation B specified in Table 1 below, operation node  810  associated with operation C specified in Table 1 below, operation node  812  associated with operation D specified in Table 1 below, operation node  814  associated with operation E specified in Table 1 below, operation node  816  associated with operation F specified in Table 1 below, and operation node  818  associated with operation G specified in Table 1 below. 
     
       
         
           
               
               
               
             
               
                   
                 TABLE 1 
               
               
                   
                   
               
               
                   
                 INDEX 
                 OPERATION 
               
               
                   
                   
               
             
            
               
                   
                 A 
                 Add p 3  at s 1   
               
               
                   
                 B 
                 Add p 3  at s 4   
               
               
                   
                 C 
                 Add p 3  at s 5   
               
               
                   
                 D 
                 Change weight at s 1   
               
               
                   
                 E 
                 Delete p 2  at s 1   
               
               
                   
                 F 
                 Delete p 2  at s 2   
               
               
                   
                 G 
                 Delete p 2  at s 5   
               
               
                   
                   
               
            
           
         
       
     
     As seen in Table 1, the graph generating module  208  generates the update dependency graph  800  so that a new path p 3  (e.g., path node  804 ) is fully established after operations A, B, and C associated with operation nodes  806 ,  808 , and  810  are successfully completed. The update dependency graph  800  then indicates that the path weights at s 1  (e.g., switching device  706 ( 1 )) can be switched (e.g., via operation D corresponding to node  812 ) so the traffic is removed before deleting the old path p 2  (e.g., via operations E, F, and G associated with operation nodes  814 ,  816 , and  818 , respectively). As shown in the update dependency graph  800 , the graph generating module  208  defines dependencies by adding: (i) edges from the operation nodes  806 ,  808 , and  810  that add a path to the corresponding path node  804 , and (ii) edges to the operation nodes  814 ,  816 , and  818  that delete a path from the corresponding path node  802 . The graph generating module  208  also defines a dependency by adding an edge from the path node  804  to the weight-changing operation node  812  and from the weight-changing operation node  812  to the path node  802 . 
     In addition to the constraints discussed above with respect to tunnel-based forwarding, resource constraints may also be defined (e.g., a maximum link capacity, a maximum memory capacity of a switching device, etc.). In various embodiments, the resource constraints may cause the update dependency graph  800  in  FIG. 8  to have resource nodes (e.g., rectangle nodes). The resource nodes in  FIG. 8  are labeled to indicate a current amount of available resources. 
     For example, resource node  820  indicates that the link between s 1  and s 4  in the observed network state  702  of  FIG. 7  has ten available (e.g., free) units. Similarly, resource node  822  indicates that the link between s 4  and s 5  in the observed network state  702  of  FIG. 7  has ten available (e.g., free) units. The edge from resource node  820  to path node  804  is labeled to indicate that five units are required to add the third path p 3    712 . The edge from resource node  822  to path node  804  is also labeled to indicate that five units are required to add the third path p 3    712 . 
     Furthermore, the edge from path node  802  to resource node  824  and resource node  826  are labeled to indicate, upon the deletion of path p 2 , that five units are released to (i) the link between s 1  and s 2  (which has zero availability in the observed network state as indicated via resource node  824 ) and (ii) the link between s 2  and s 5  (which has five units available in the observed network state as indicated via resource node  826 ). As discussed above, the indications may be referred to as a committed label indicating an amount of traffic moving away from the path. 
     The graph generating module  208  furthers adds a label on the edge from path node  804  to operation node  812  (e.g., operation D which changes path weights at s 1 ) to indicate that five units of traffic are added via path node  804 . Furthermore, the label on the edge from operation node  812  to path node  802  indicates that five units of traffic are removed via path node  802 . 
     For resource nodes associated with memory of a device (e.g., a switching device), the graph generating module  208  may add an edge from a resource node to an operation node if the associated update operation consumes memory at a device and the graph generating module  208  labels the edge with a weight indicating the amount of memory consumed by the update operation. Conversely, the graph generating module  208  may add an edge from an operation node to a resource node if the associated update operation releases memory at the device and the graph generating module  208  labels the edge with a weight indicating the amount of memory released. 
     In WCMP forwarding, the graph generating module  208  may determine weight change operations for each flow to be updated based on the transition from the NS c  to NS t . The graph generating module  208  generates dependency edges between these weight change operations based on constraints associated with a packet coherence network consistency property. 
     Example Algorithm 1 may be used by the graph generating module  208  to generate the example update dependency graph to ensure packet coherence (e.g., in a WCMP Network). In example Algorithm 1, an old version number represents an old routing rule that may be part of the NS c  and a new version number represents a new routing rule that may be part of the NS t . 
     
       
         
           
               
             
               
                   
               
               
                 ALGORITHM 1 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
            
               
                   
                 - 
                 v 0 : old version number 
               
               
                   
                 - 
                 v 1 : new version number 
               
            
           
           
               
               
               
            
               
                   
                 1: 
                 for each flow f do 
               
            
           
           
               
               
               
            
               
                   
                 2: 
                 s* = GetIngressSwitch(f) 
               
               
                   
                 3: 
                 o* = GenRuleModifyOp(s*, v 1 ) 
               
               
                   
                 4: 
                 for s i  ∈ GetAllSwitches(f) − s* do 
               
            
           
           
               
               
               
            
               
                   
                 5: 
                 if s i  has multiple next-hops then 
               
            
           
           
               
               
               
            
               
                   
                 6: 
                 o 1  = GenRuleInsertOp(s i , v 1 ) 
               
               
                   
                 7: 
                 o 2  = GenRuleDeleteOp(s i , v 0 ) 
               
               
                   
                 8: 
                 Add edge from o 1  to o* 
               
               
                   
                 9: 
                 Add edge from o* to o 2   
               
               
                   
                   
               
            
           
         
       
     
     Using example Algorithm 1, an ingress switching device is configured to tag each data packet with a version number and downstream switching devices handle data packets based on the version number. This ensures that each data packet either is routed according to the old routing rule or the new routing rule (i.e., the data packet is not routed based on a mix of rules). Example Algorithm 1 generates three types of operations: a first type in which an ingress switching device tags data packets with the new version number and uses new weights (Line 3 of example Algorithm 1); a second type in which downstream switching devices have rules for handling the data packets with the new version number and new weights (Line 6 of example Algorithm 1); and a third type in which downstream switching devices delete rules for the old version number (Line 7 of example Algorithm 1). Accordingly, packet coherence is ensured if the first type of operations specified above occur after the second type of operations specified above (Line 8 of example Algorithm 1) and if the third type of operations specified above occur after the first type of operations (Line 9 of example Algorithm 1). Line 5 of example Algorithm 1 is an example optimization specifying that no changes may be required at switching devices that have only one next hop for the flow in both the old and new routing rules. 
     After an update dependency graph is generated and/or updated to reflect update operations associated with the changes  110 , the scheduling module  210  uses the update dependency graph to implement the network update (e.g., issue update instructions and/or commands for various devices to carry out the update operations). The update dependency graph may provide multiple different acceptable orderings in which to implement a network update so that the constraints are not violated, and different orderings may be associated with different completion times (e.g., an amount of time it takes to complete a set of update operations in an ordering). Therefore, in various embodiments, the scheduling module  210  is configured to identify an ordering within the update dependency graph that likely will take the longest amount of time to complete and initiate the scheduling of the identified ordering to minimize this longest amount of time. This may be referred to as critical path scheduling. 
     To implement critical path scheduling, the scheduling module  210  may use example Algorithm 2, provided herein: 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 2 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
            
               
                   
                 1: 
                 while true do 
               
            
           
           
               
               
               
            
               
                   
                 2: 
                 UpdateGraph(G) 
               
               
                   
                 3: 
                 Calculate CPL for every node 
               
               
                   
                 4: 
                 Sort nodes by CPL in decreasing order 
               
               
                   
                 5: 
                 for unscheduled operation node O i  ∈ G do 
               
            
           
           
               
               
               
            
               
                   
                 6: 
                 if CanScheduleOperation(O i ) then 
               
            
           
           
               
               
               
            
               
                   
                 7: 
                 Schedule O i   
               
            
           
           
               
               
               
            
               
                   
                 8: 
                 Wait for time t or for all scheduled operations to finish 
               
               
                   
                   
               
            
           
         
       
     
     The symbols and/or variables in example Algorithm 2 are specified as follows in Table 2: 
     
       
         
           
               
               
               
             
               
                   
                 TABLE 2 
               
               
                   
                   
               
               
                   
                 Symbol 
                 Description 
               
               
                   
                   
               
             
            
               
                   
                 O i   
                 Operation Node i 
               
               
                   
                 R j   
                 Resource Node j 
               
               
                   
                 R j .free 
                 Free Capacity of R j   
               
               
                   
                 P k   
                 Path Node k 
               
               
                   
                 P k .committed 
                 Traffic that is Moving Away from Path k 
               
               
                   
                 l ij   
                 Edge Weight from Node i to Node j 
               
               
                   
                   
               
            
           
         
       
     
     Since resource nodes and/or path nodes in the update dependency graph may be used to express constraints, the scheduling module  210  assigns a weight w=0 to the resource nodes and/or path nodes when calculating critical paths. Conversely, the scheduling module  210  assigns a weight w=1 to operation nodes and calculates a critical path length CPL i  for each node i in an update dependency graph shown in Equation (3) as follows: 
     
       
         
           
             
               
                 
                   
                     C 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     P 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       L 
                       i 
                     
                   
                   = 
                   
                     
                       w 
                       i 
                     
                     + 
                     
                       
                         max 
                         
                           j 
                           ∈ 
                           
                             children 
                             ⁡ 
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                       
                       ⁢ 
                       
                         C 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         P 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           L 
                           j 
                         
                       
                     
                   
                 
               
               
                 
                   equ 
                   . 
                   
                       
                   
                   ⁢ 
                   
                     ( 
                     3 
                     ) 
                   
                 
               
             
           
         
       
     
     In various embodiments, he scheduling module  210  may implement a topological sort of the nodes in the update dependency graph and then iterate over the nodes to calculate CPL i  using Equation (3) in a reverse topological order. This can be implemented efficiently in linear time. 
     Therefore, the scheduling of update operations may be implemented based on example Algorithm 2. For example, each time the scheduling module  210  commences scheduling, the scheduling module  210  may first update the update dependency graph by removing completed update operations and/or edges in the update dependency graph that may be associated with resources that are no longer bottlenecked (Line 2 in example Algorithm 2). Then the scheduling module  210  calculates a CPL for individual nodes (Line 3 in example Algorithm 2) and sorts the nodes in decreasing order of CPL (Line 4 in example Algorithm 2). The scheduling module  210  subsequently iterates over operation nodes and schedules the operation nodes if their operation dependencies and/or resource dependencies are satisfied (Lines 6 and 7 in example Algorithm 2). Finally, the scheduling module  210  may wait for a period of time or for the scheduled update operations to be completed before it begins a next round (Line 8 in example Algorithm 2). 
     In various embodiments, the scheduling module  210  implements critical path scheduling for an update dependency graphs that is a directed acyclic graph (DAG) such that it is free of circular dependencies. Example Algorithm 3 and example Algorithm 4 provided herein show pseudo code for scheduling update operations for the specific implementation of tunnel-based forwarding discussed above. 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 3 - CanScheduleOperation(O i ) 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
            
               
                 // Add tunnel operation node 
               
            
           
           
               
               
            
               
                  1: 
                 if O i .isAddTunnelOp( ) then 
               
            
           
           
               
               
            
               
                  2: 
                 if O i .hasNoParents( ) then 
               
            
           
           
               
               
            
               
                  3: 
                 return true 
               
            
           
           
               
               
            
               
                  4: 
                 R j  ← parent(O i ) // AddTunnelOp only has 1 parent 
               
               
                  5: 
                 if R j .free ≥ l ji  then 
               
            
           
           
               
               
            
               
                  6: 
                 R j .free ←R j .free − l ji   
               
               
                  7: 
                 Delete edge Rj → O i   
               
               
                  8: 
                 return true 
               
            
           
           
               
               
            
               
                  9: 
                 return false 
               
            
           
           
               
            
               
                 // Delete tunnel operation node 
               
            
           
           
               
               
            
               
                 10: 
                 if O i .isDelTunnelOp( ) then 
               
            
           
           
               
               
            
               
                 11: 
                 if O i .hasNoParents( ) then 
               
            
           
           
               
               
            
               
                 12: 
                 return true 
               
            
           
           
               
               
            
               
                 13: 
                 return false 
               
            
           
           
               
            
               
                 // Change weight operation node 
               
            
           
           
               
               
            
               
                 14: 
                 total ← 0 
               
               
                 15: 
                 canSchedule ← false 
               
               
                 16: 
                 for path node P j  ∈ parents(O i ) do 
               
            
           
           
               
               
            
               
                 17: 
                 available ← l ji   
               
               
                 18: 
                 if P j .hasOpParents( ) then 
               
            
           
           
               
               
            
               
                 19: 
                 available ← 0 
               
            
           
           
               
               
            
               
                 20: 
                 else 
               
            
           
           
               
               
            
               
                 21: 
                 for resource node R k  ∈ parents(P j ) do 
               
            
           
           
               
               
            
               
                 22: 
                 available ← min(available, l kj , R k .free) 
               
            
           
           
               
               
            
               
                 23: 
                 for resource node R k  ∈ parents(P j ) do 
               
            
           
           
               
               
            
               
                 24: 
                 l kj  ← l kj  − available 
               
               
                 25: 
                 R k .free ← R k .free − available 
               
            
           
           
               
               
            
               
                 26: 
                 total ← total + available 
               
               
                 27: 
                 l ji  ← l ji  − available 
               
            
           
           
               
               
            
               
                 28: 
                 if total &gt; 0 then 
               
            
           
           
               
               
            
               
                 29: 
                 canSchedule ← true 
               
            
           
           
               
               
            
               
                 30: 
                 for path node Pj ∈ children(O i ) do 
               
            
           
           
               
               
            
               
                 31: 
                 P j .committed ← min(l ij , total) 
               
               
                 32: 
                 l ij  ← l ij  − P j .committed 
               
               
                 33: 
                 total ← total − P j .committed 
               
            
           
           
               
               
            
               
                 34: 
                 return canSchedule 
               
               
                   
               
            
           
         
       
     
     Example Algorithm 3 determines if an update operation O i  is ready to be scheduled and also updates the resource levels for resource nodes and/or path nodes accordingly. If O i  is a path (e.g., tunnel) addition operation, the scheduling module  210  can schedule O i  either if it has no parent nodes (Lines 2 and 3 in example Algorithm 3) or if its parent resource node indicates enough available (e.g., free) resource (Lines 4-8 in example Algorithm 3). If O i  is a path deletion operation, the scheduling module  210  can schedule O i  if it has no parent nodes s (Lines 11 and 12 in example Algorithm 3). In various embodiments, path deletion operations do not have resource nodes as parent nodes because they release resources (e.g., memory resources, link resources, etc.). 
     If O i  is a weight change operation, the scheduling module  210  gathers free capacities on the paths where traffic increases and moves traffic to them (Lines 14-34 in example Algorithm 3). The scheduling module  210  then iterates over each parent path node and obtains the available resources of the path (Lines 16-27 in example Algorithm 3). This relates to the amount of traffic capable of being moved to the path. The scheduling module  210  then sums up the paths into a total amount of traffic the scheduling module  210  can move for this flow (Line 26 in example Algorithm 3). Lastly, the scheduling module  210  iterates over child path nodes (Line 30-33 in example Algorithm 3) and decreases “P j .committed” traffic on path represented by P j  (Line 31 in example Algorithm 3). 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 4 - UpdateGraph(G) 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
            
               
                  1: 
                 for finished operation node O i  ∈ G do 
               
            
           
           
               
               
            
               
                   
                 // Finish add tunnel operation node 
               
               
                  2: 
                 if O i .isAddTunnelOp( ) then 
               
            
           
           
               
               
            
               
                  3: 
                 Delete O i  and all its edges 
               
            
           
           
               
               
            
               
                   
                 // Finish delete tunnel operation node 
               
               
                  4: 
                 else if O i .isDelTunnelOp( ) then 
               
            
           
           
               
               
            
               
                  5: 
                 R j  ← child(O i ) 
               
               
                  6: 
                 R j .free ← R j .free + l ij   
               
               
                  7: 
                 Delete O i  and all its edges // DelTunnelOp only has 1 child 
               
            
           
           
               
               
            
               
                   
                 // Finish change weight operation node 
               
               
                  8: 
                 else 
               
            
           
           
               
               
            
               
                  9: 
                 for path node P j  ∈ children(O i ) do 
               
            
           
           
               
               
            
               
                 10: 
                 for resource node R k  ∈ children(P j  ) do 
               
            
           
           
               
               
            
               
                 11: 
                 l jk  ← l jk  − P j .committed 
               
               
                 12: 
                 R k .free ← R k .free + P j .committed 
               
               
                 13: 
                 if l jk  = 0 then 
               
            
           
           
               
               
            
               
                 14: 
                 Delete edge P j  → R k   
               
            
           
           
               
               
            
               
                 15: 
                 P j .committed ← 0 
               
               
                 16: 
                 if l ij  = 0 then 
               
            
           
           
               
               
            
               
                 17: 
                 Delete P j  and its edges 
               
            
           
           
               
               
            
               
                 18: 
                 for path node P i  ∈ parents(O i ) do 
               
            
           
           
               
               
            
               
                 19: 
                 if l ji  = 0 then 
               
            
           
           
               
               
            
               
                 20: 
                 Delete P j  and its edges 
               
            
           
           
               
               
            
               
                 21: 
                 if O i .hasNoParents( ) then 
               
            
           
           
               
               
            
               
                 22: 
                 Delete O i  and its edges 
               
            
           
           
               
               
            
               
                 23: 
                  for resource node R i  ∈ G do 
               
            
           
           
               
               
            
               
                 24: 
                  if R i .free ≥ Σ j  l ij  then 
               
            
           
           
               
               
            
               
                 25: 
                  R i .free ← R i .free − Σ j  l ij   
               
               
                 26: 
                  Delete all edges from R i   
               
               
                   
               
            
           
         
       
     
     Example Algorithm 4 updates the update dependency graph before scheduling based on update operations that finished in the last round of updating the network. For instance, the scheduling module  210  receives the completed update operations and updates related nodes in the update dependency graph (Lines 1-22 in example Algorithm 4). If the operation node adds a path, the scheduling module  210  deletes the operation node and its edges (Lines 2 and 3 in example Algorithm 4). If the operation node deletes a path, then rule space is freed and the scheduling module  210  updates the resource node (Lines 5 and 6 in example Algorithm 4) and deletes the operation node (Line 7 in example Algorithm 4). If the operation node changes a weight, for each child path node, the scheduling module  210  releases resources to links (Lines 11 and 12 in example Algorithm 4) and deletes the edge if the resources are released (Lines 13 and 14 in example Algorithm 4). Then the scheduling module  210  resets the amount of traffic that is moving away from this path, P j .committed, to zero (Line 15 in example Algorithm 4). Once the scheduling module  210  has moved the traffic away from this path, the scheduling module  210  deletes the path node (Lines 16 and 17 in example Algorithm 4). Similarly, the scheduling module  210  checks the parent path nodes (Lines 18-20 in example Algorithm 4). If the scheduling module  210  has moved all the traffic into a path, the scheduling module  210  deletes the path node (Lines 19 and 20 in example Algorithm 4). If the parent path nodes are removed, the weight change for this flow has finished and the scheduling module  210  removes it from the update dependency graph (Line 22 in example Algorithm 4). After updating the update dependency graph with completed update operations, the scheduling module  210  checks the resource nodes (Lines 23-26 in example Algorithm 4) and deletes edges from resources that are not bottlenecked (Line 24-26 in example Algorithm 4). 
     In various embodiments, an update dependency graph may include a circular dependency. For instance, due to a defined resource constraint, dependencies between a group of nodes (e.g., a group with two or more operation nodes) maybe create a circle and as a result the critical path may become infinite. Moreover, a circular dependency may cause a scheduling deadlock that halts progress of a network update. 
       FIG. 9  illustrates an example diagram  900  where a circular dependency may occur in an update dependency graph. That is, a first operation node  902 , upon implementation, may release resources to a resource associated with a first resource node  904  but may require that a resource associated with a second resource node  906  have enough available resources before being implemented. However, an update operation associated with a second operation node  908  may require that the resource associated with the first resource node  904  have enough available resources before being implemented and the aforementioned resource may not have sufficient resource availability until the update operation associated with update operation node  902  is completed. Moreover, the resource associated with the second resource node  906  may not be able to provide available resources to operation node  902  until operation node  908  is completed. Thus, a circular dependency results. 
     In embodiments where an update dependency graph comprises one or more circular dependencies, the scheduling module  210  may be configured to (i) determine that a circular dependency occurs in the update dependency graph and (ii) represent the circular dependency as a single logical node  910  in the update dependency graph. Thus, the scheduling module  210  may be configured to schedule the logical node  910  as part of a DAG, e.g., using example Algorithm 2 provided above. 
     In some instances, the logical node  910  may be referred to as a strongly connected component (SCC) that is a sub-part of an update dependency graph where each inclusive node has a path to other nodes included in the SCC. If an SCC is represented as logical node in the update dependency graph, then the scheduling module  210  can calculate CPLs as discussed above and implement critical path scheduling. In some instances, an SCC may be associated with multiple circular dependencies. For example, two or more circular dependencies may overlap such that at least one node (e.g., an operation node) may be an intersecting node that is part of two or more circular dependencies. Therefore, the scheduling module  210  may schedule update operations for a first circular dependency and then use the intersecting node to schedule update operations for at least a second circular dependency. 
     In various embodiments, when calculating CPLs, the scheduling module  210  may use a number of operation nodes included in an SCC (e.g., the number is two in  FIG. 9 ) as a weight for the corresponding logical node. Consequently, the scheduling module  210  may be configured to evaluate a weight so that orderings that include larger SCCs (e.g., more operation nodes) will be preferred. 
     As an example, the scheduling module  210  may implement two modifications to incorporate SCCs into DAG scheduling. First, the “for” loop at line 5 of Algorithm 2 iterates over all nodes in a virtual update dependency graph (e.g., an update dependency graph with one or more circular dependencies individually represented as a logical node). When a node is selected and if it is a single node, the scheduling module  210  may directly call CanScheduleOperation(O i ). If the selected node is a logical node (e.g., logical node  910 ), the scheduling module  210  may iterate over the operation nodes in an SCC and call the functions accordingly. 
     In some implementations, the scheduling module  210  may use a centrality approach to decide an order of the iteration. Using the centrality approach, the scheduling module  210  identifies a central node (e.g., the intersecting node mentioned above) of an SCC that may be part of multiple circular dependencies, and the scheduling module  210  may schedule the central node early in the update process so that update operations from multiple circular dependencies can be implemented and the SCC can be scheduled and/or completed more efficiently. 
     The second modification implemented by the scheduling module  210  relates to when path nodes consume link resources or tunnel add operations consume switch resources. This consumption of resources can be implemented via nodes that either (i) are in the same SCC as the path nodes or tunnel add operations consuming the resources, or (ii) are independent nodes (not in any SCC). This heuristic helps prevent deadlocks caused by allocating resources to nodes outside the SCC. 
     Therefore, with the scheduling algorithm above (e.g., Algorithm 2), the scheduling module  210  can solve SCCs. However, in some cases, the scheduling module  210  may still encounter deadlocks in which case no operations in the SCC can progress. This may occur because (i) the scheduling algorithm may be unable to find a feasible solution among the various orderings and may become stuck, or (2) a feasible solution may not exist even if the target state is a valid state. 
     In various implementations, the scheduling module  210  may resolve deadlocks by reducing flow rates (e.g., by introducing rate limiters). Reducing flow rates frees up link resources on a path which allows removal of a tunnel. In turn, switching device memory resources may be freed and this allows some of the operations that were previously deadlocked, e.g., due to unavailable resources, to be completed. As a result of rate limiters, the scheduling algorithm  210  may implement an update operation partially, e.g., using a fraction of a total amount of resources required to implement the update operation wholly. 
     Example Algorithm 5 shows a procedure to resolve deadlocks for tunnel-based networks. The parameter k* determines a maximum number of flows that the scheduling module  210  rate limits each time and the scheduling module  210  controls the tradeoff between a time to resolve the deadlock and an amount of throughput loss. 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 5 - Rate Limits (SCC, k*) 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
            
               
                   
                 1: 
                 O* ← weight change nodes ∈ SCC 
               
               
                   
                 2: 
                 for i=0; i&lt;k* &amp;&amp; O* ≠ Ø; i+ + do 
               
            
           
           
               
               
               
            
               
                   
                 3: 
                 O i  ← O*.pop( ) 
               
               
                   
                 4: 
                 for path node P j  ∈ children(O i ) do 
               
            
           
           
               
               
            
               
                   
                  // f i  is the corresponding flow of O i   
               
            
           
           
               
               
               
            
               
                   
                 5: 
                 Rate limit flow f i  by l ij  on path P j   
               
            
           
           
               
               
               
            
               
                   
                 6: 
                 for resource node R k  ∈ children(P j ) do 
               
            
           
           
               
               
               
            
               
                   
                 7: 
                 R k .free ← R k .free + l ij   
               
            
           
           
               
               
               
            
               
                   
                 8: 
                  Delete P j  and its edges 
               
               
                   
                   
               
            
           
         
       
     
     The scheduling module  210  iterates over up to k* weight change nodes in the SCC, each of which corresponds to a flow (Lines 2-8 in example Algorithm 5). The order of iteration may be based on the centrality approach discussed above. For each weight change node O i , the scheduling module  210  iterates over children path nodes P j . The scheduling module  210  reduces a rate on P j  by l ij  (Line 5 in example Algorithm 5) and accordingly increases the free resources of links on the path (Lines 6-7 in example Algorithm 5). The scheduling module  210  then deletes P j  from the graph (line 8 in example Algorithm 5). 
       FIG. 10  illustrates an example process  1000  that schedules operation updates of a circular dependency in an update dependency graph. The example operations in  FIG. 10  may be described with reference to the modules, components and/or elements illustrated in any one of  FIGS. 1-9 . 
     At  1002 , the scheduling module  210  may determine that a circular dependency (e.g., a SCC) occurs between two or more operation nodes in an update dependency graph. The update dependency graph may also include resource nodes and/or path nodes. 
     At  1004 , the scheduling module  210  represents the circular dependency as a single logical node (e.g., node  910 ). By representing the circular dependency as a single logical node then the update dependency graph may become a DAG. 
     At  1006 , when the single logical node is scheduled to be implemented, the scheduling module  210  selects, as a circular dependency starting point, an operation node (e.g., node  902  or node  908 ) from the operation nodes in the circular dependency. In accordance with the centrality approach discussed above, the scheduling module  210  may be configured to identify and select an intersecting node as the circular dependency starting point. 
     At  1008 , the scheduling module  210  uses the circular dependency starting point to implement update operations associated with the other operation nodes in the circular dependency or in multiple circular dependencies that overlap via the intersecting node. 
     CONCLUSION 
     Although the present disclosure may use language that is specific to structural features and/or methodological acts, the invention is not limited to the specific features or acts described herein. Rather, the specific features and acts are disclosed as illustrative forms of implementing the invention.