An Incremental Procedure for Improving Path Assignment in a Telecommunications Network

A fundamental problem in the design and management of a telecommunications network is that of determining an optimal routing pattern for a given set of origin-destination demand pairs. In addition, reliability considerations may require provisioning a set of backup paths to protect the working trac against network failures. In the literature, the problem of nding an optimal routing for a network with xed link capacities and a list of point-to-point demands (origin-destination pairs), each with a set of candidate routing paths has been referred to as the path-assignment problem. There are three versions of this problem that correspond to the type of network protection required (no protection, dedicated protection, and shared protection). The solution to those models can be used to determine an initial design for a new network. Over time, however, changes in the demand pattern and/or upgrades to the network equipment may create a situation in which the working and/or backup paths are sub-optimal. For network managers who are reluctant to make wholesale changes to an established and reliable routing assignment, a complete modication to obtain an optimal assignment that uses fewer network resources is viewed as highly risky. This investigation presents a new procedur