A controller device manages a plurality of network devices. The controller device includes one or more processing units configured to receive an upgrade request; obtain a redundancy model indicating network device redundancies or service redundancies; determine, based on the upgrade request and the redundancy model, an update graph having nodes each representing one of the network devices or one of the services, the update graph also having at least one edge that connects two of the nodes and that indicates the network redundancy or the service redundancy; determine, based on the update graph including the at least one edge, an update schedule for performing an update of software for the network devices that ensures availability for the first network device or second network device or availability for the service; and update the software of each of the network devices according to the update schedule.