Patent attributes
A controller device manages a plurality of network devices. The controller device includes one or more processing units configured to receive an upgrade request; determine an upgrade graph having nodes each representing one of the network devices or a network service provided by the network, and also having one or more edges each connecting two of the nodes and representing a network redundancy or service dependency; compute and assign, an edge weight to each edge by combining results of at least one objective function, each of the at least one objective functions having a minimum objective or maximum objective for the network; partition the upgrade graph into a plurality of sub-groups based on the edge weights; determine an upgrade schedule; and upgrade software of each of the plurality of network devices according to the upgrade schedule.