An Incremental Procedure for Improving Path Assignment
in a Telecommunications Network
Abstract
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. This 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.
Manuscript
PDF: "An Incremental Procedure for Improving
Path Assignment in a Telecommunications Network"
(37 pages, 313 K)
Data and Model Files
olinick@engr.smu.edu