On Minimizing Network Wide Node Update Time

In the maintenance of communication networks, nodes often need to be rebooted or brought off line for software updates, configuration updates or hardware maintenance. ISPs often run the same protocols and use equipment from the same vendor network-wide, increasing the probability that a maintenance window will be network wide. Some of the updates can be critical where we have to update fast, for example, updates against network viruses. This paper presents an algorithm that utilizes a priori knowledge of network traffic demand to minimize the rebooting time of the entire network, under the constraint that only a designated percentage of the network traffic volume be affected. The algorithm uses the fact that closely related routers that need to be upgraded can be done simultaneously to minimize network wide affected traffic. By closely related we mean nodes that send traffic to each other more than their other neighbor nodes. We use a gravity traffic model over a real network topology collected from Rocketfeul measurements to simulate our experiments. Performance results show a significant improvement in terms of overall upgrade time and scalability which indicates the properties of an efficient solution with respect to minimizing impact on network traffic.