Graceful Network Operations

A significant fraction of network events (such as topology or route changes) and the resulting performance degradation stem from premeditated network management and operational tasks. This paper introduces a general class of Graceful Network Operation (GNO) problems, where the goal is to discover the optimal sequence of operations that progressively transition the network from its initial to a desired final state while minimizing the overall performance disruption. We investigate two specific GNO problems: (a) Link Weight Reassignment Scheduling (LWRS) studies the optimal ordering of link weight updates to migrate from an existing to a new link weight assign- ment, and (b) Link Maintenance Scheduling (LMS) looks at how to schedule link deactivations and subsequent reactivations for maintenance purposes. LWRS and LMS are both combinatorial optimization problems. We use dynamic programming to find the optimal solutions when the problem size is small, and leverage Ants Colony Optimization to get near-optimal solutions for large problem sizes. Our simulation study reveals that judiciously ordering network operations can achieve significant performance gains. Our GNO solution framework is generic and applies to similar problems with different operational contexts, underlying network protocols or mechanisms, and performance metrics. I. INTRODUCTION The Internet has been an enabling technology for mission- critical applications and services such as Voice over IP, VPNs, e-commerce applications, and multimedia streaming. Such applications rely upon consistent Quality of Service (QoS) provisioning by Internet Service Providers (ISPs), with five-nines availability (99.999% uptime) becoming the norm rather than the exception. The end-to-end perceived QoS can potentially be affected due to the dynamic nature of the networks. For instance, network topology may change due to transient router/link outages or long-term network engineering. Furthermore, protocol configuration parameters may be altered to migrate from one setting to another. Ideally, QoS guarantees should persist across such dynamic conditions. Some of these dynamic changes are inadvertent e.g., ones due to faulty interfaces, router crashes, and accidental fiber cuts. However, other changes ensue from deliberate and pre- meditated actions of network operators (e.g., routine main- tenance). A failure characterization study of the Sprint IP backbone (1) observed that planned maintenance activities account for more than 20% of transient failures. Other studies (2) have also observed the prevalence of such planned main- tenance activities. Premeditated network tasks also include network upgrade activities such as adding new routers to the network and overhauling link capacity. Another example of a premeditated network task is migrating an existing OSPF (3) or IS-IS (4) 1 link weight assignment to a new assignment that has been optimized based upon the most up-to-date traffic matrix estimates. In the case of premeditated tasks, network operators have the prerogative to decide the sequence of atomic operations that comprise such a task. This paper introduces a general class of problems referred to as Graceful Network Operation (GNO) problems, which typically involve migrating a network from its initial state to a final state by executing a series of atomic operations. Each of these operations may cause some performance disruption that is a function of the network's state. The GNO problem is to discover the sequence of operations that progressively transition the network to the final state while minimizing the overall disruption. This paper looks at two specific GNO problems, as described below.