Suggested Citation:
Chuah, Chen-Nee, Yueyue Fan, Ram Keralapura (2006) Optimal Strategy for Graceful Network Upgrade. INM 06 Proceedings of the 2006 SIGCOMM Workshop on Internet Network Management, 83 - 88

One of the critical aspects of network management that has not received much attention is network upgrade. This paper addresses the question of “how to add new nodes and links into an operational network in a graceful manner so that the perceived network performance from the perspective of existing customers does not deteriorate?”. We propose a two-phase framework to find the optimal upgrade strategy: first, deciding what nodes should be added and how they should be connected to existing topology, and second, deciding the ideal sequence to add these new nodes and links. We formulate the first phase as a non-linear optimization problem and the second phase as a multistage dynamic programming problem. Through a numerical example, we show the feasibility of this framework and demonstrate the advantages of our multistage approach in determining an ideal upgrade sequence. The results also highlight the significance of incorporating network performance (for ex, service availability) into the two-phase framework to achieve minimal impact to existing customers.

Keywords: Graceful Network Upgrade, Multi-Stage Network Upgrade