Performing scalable network upgrades

1. A method for upgrading a network, the method comprising:

receiving a request to upgrade a network comprising a plurality of network devices providing connectivity for a set of servers;

receiving a network topology of the network, the network topology represented as a topology graph;

performing network upgrade comprising, repeating:

selecting a network device for upgrading;

evaluating a set of upgrade criteria, each upgrade criterion based on a relation between the selected network device and one or more other network devices currently being upgraded, the set of upgrade criteria including an upgrade criterion indicating whether another network device directly connected to the selected network device is currently being upgraded;

determining whether to upgrade the selected network device based on a result of evaluation of the set of upgrade criteria; and

performing one of (1) upgrading the selected network device or (2) delaying upgrade of the selected network device based on the result of evaluation of the set of upgrade criteria and completing the upgrade of the selected network device after the delay; and

determining whether the network upgrade completed successfully.

2. The method of claim 1 , wherein the set of upgrade criteria further includes an upgrade criterion that indicates that two network devices are not upgraded simultaneously if any of the two network devices has a neighboring network device with incomplete topology information.

3. The method of claim 1 , wherein the set of upgrade criteria further includes an upgrade criterion that indicates that a network device is not upgraded if upgrading the network device will remove from service, more than a threshold percentage of viable paths to a portion of the network.

4. The method of claim 1 , further comprising:

adding a representation of each of the plurality of network devices to a queue, wherein selecting a network device for upgrading comprising selecting a network device from front of the queue.

5. The method of claim 4 , wherein delaying upgrade of the selected network device comprises adding the representation of the selected network device to end of the queue.

6. The method of claim 1 , wherein determining whether the network upgrade completed successfully comprises:

determining a pre-snapshot comprising attributes representing a state of the network before network upgrade;

determining a post-snapshot comprising attributes representing a state of the network after network upgrade; and

comparing the pre-snapshot and the post-snapshot to determine whether upgrade of one or more network devices failed.

7. The method of claim 6 , wherein each of the pre-snapshot and the post-snapshot comprises attributes based on status of physical interfaces of each of the plurality of network devices.

8. The method of claim 6 , further comprising:

receiving an expectations specification specifying relations between value of an attribute of a snapshot before upgrade and after upgrade, wherein comparing the pre-snapshot and the post-snapshot is based on the expectations specification.

9. A computer readable non-transitory storage medium storing instructions, the instructions when executed by one or more computer processors cause the one or more computer processors to perform steps comprising:

receiving a request to upgrade a network comprising a plurality of network devices providing connectivity for a set of servers;

receiving a network topology of the network, the network topology represented as a topology graph;

performing network upgrade comprising, repeating:

selecting a network device for upgrading;

evaluating a set of upgrade criteria, each upgrade criterion based on a relation between the selected network device and one or more other network devices currently being upgraded, the set of upgrade criteria including an upgrade criterion indicating whether another network device directly connected to the selected network device is currently being upgraded;

determining whether to upgrade the selected network device based on a result of evaluation of the set of upgrade criteria; and

performing one of (1) upgrading the selected network device or (2) delaying upgrade of the selected network device based on the result of evaluation of the set of upgrade criteria and completing the upgrade of the selected network device after the delay; and

determining whether the network upgrade completed successfully.

10. The computer readable non-transitory storage medium of claim 9 , wherein the set of upgrade criteria further includes an upgrade criterion that indicates that two network devices are not upgraded simultaneously if any of the two network devices has a neighboring network device with incomplete topology information.

11. The computer readable non-transitory storage medium of claim 9 , wherein the set of upgrade criteria further includes an upgrade criterion that indicates that a network device is not upgraded if upgrading the network device will remove from service, more than a threshold percentage of viable paths to a portion of the network.

12. The computer readable non-transitory storage medium of claim 9 , wherein the instructions further cause the one or more computer processors to perform steps comprising:

adding a representation of each of the plurality of network devices to a queue, wherein selecting a network device for upgrading comprising selecting a network device from front of the queue.

13. The computer readable non-transitory storage medium of claim 12 , wherein delaying upgrade of the selected network device comprises adding the representation of the selected network device to end of the queue.

14. The computer readable non-transitory storage medium of claim 9 , wherein instructions for determining whether the network upgrade completed successfully, further cause the one or more computer processors to perform steps comprising:

determining a pre-snapshot comprising attributes representing a state of the network before network upgrade;

determining a post-snapshot comprising attributes representing a state of the network after network upgrade; and

comparing the pre-snapshot and the post-snapshot to determine whether upgrade of one or more network devices failed.

15. The computer readable non-transitory storage medium of claim 14 , wherein each of the pre-snapshot and the post-snapshot comprises attributes based on status of physical interfaces of each of the plurality of network devices.

16. The computer readable non-transitory storage medium of claim 14 , wherein the instructions further cause the one or more computer processors to perform steps comprising:

receiving an expectations specification specifying relations between value of an attribute of a snapshot before upgrade and after upgrade, wherein comparing the pre-snapshot and the post-snapshot is based on the expectations specification.

17. A computer-implemented system for upgrading a network, the system comprising:

one or more computer processors; and

a computer readable non-transitory storage medium storing instructions, the instructions when executed by the one or more computer processors cause the one or more computer processors to perform steps comprising:

receiving a request to upgrade a network comprising a plurality of network devices providing connectivity for a set of servers;

receiving a network topology of the network, the network topology represented as a topology graph;

performing network upgrade comprising, repeating:

selecting a network device for upgrading;

evaluating a set of upgrade criteria, each upgrade criterion based on a relation between the selected network device and one or more other network devices currently being upgraded, the set of upgrade criteria including an upgrade criterion indicating whether another network device directly connected to the selected network device is currently being upgraded;

determining whether to upgrade the selected network device based on a result of evaluation of the set of upgrade criteria; and

performing one of (1) upgrading the selected network device or (2) delaying upgrade of the selected network device based on the result of evaluation of the set of upgrade criteria and completing the upgrade of the selected network device after the delay; and

determining whether the network upgrade completed successfully.

18. The computer-implemented system of claim 17 , wherein instructions for determining whether the network upgrade completed successfully further cause the one or more computer processors to perform steps comprising:

determining a pre-snapshot comprising attributes representing a state of the network before network upgrade;

determining a post-snapshot comprising attributes representing a state of the network after network upgrade; and

comparing the pre-snapshot and the post-snapshot to determine whether upgrade of one or more network devices failed.

19. The computer-implemented system of claim 17 , wherein the set of upgrade criteria further includes an upgrade criterion that indicates that two network devices are not upgraded simultaneously if any of the two network devices has a neighboring network device with incomplete topology information.

20. The computer-implemented system of claim 17 , wherein the set of upgrade criteria further includes an upgrade criterion that indicates that a network device is not upgraded if upgrading the network device will remove from service, more than a threshold percentage of viable paths to a portion of the network.