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 traffic against network failures. In the literature, the problem of finding an optimal routing for a network with fixed 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 modification to obtain an optimal assignment that uses fewer network resources is viewed as highly risky. The investigation presents a new procedure to take a given feasible, but sub-optimal design and improve it by making a series of incremental improvements each of which only changes a small number of path assignments. Network managers view this strategy as much less risky since only a few customers are affected by any one change. Test cases that require no protection, dedicated protection, and shared protection were examined in an empirical analysis. For all cases, near-optimal solutions were achieved irrespective of the quality of the given sub-optimal starting solutions.