A heuristic procedure for leasing channels in telecommunications networks

Rapid advances in computing and communications technology have made distributed computing an attractive alternative for geographically dispersed organizations. A telecommunication sub-network forms the backbone of these distributed systems. In general, this paper focuses on the assignment of communication channel capacities in the presence of time variant usage patterns. Specifically, the authors concentrate on long-range capacity planning for organizations that construct networks by leasing communication channels from telecommunication companies. They formulate the capacity assignment problem as a 0-1 integer program that seeks to minimize total leasing cost subject to communication delay restrictions. Unlike previous models that include a single-system wide-average delay constraint, the present model allows the flexibility of specifying delay restrictions by communicating node pairs. The authors propose an efficient heuristic, and a Lagrangean relaxation based procedure to obtain performance guarantees on the solution obtained from the heuristic.