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, we concentrate on long-range capacity planning for organizations that construct networks by leasing communication channels from telecommunication companies. We 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, our model allows the flexibility of specifying delay restrictions by communicating node pairs. We propose an efficient heuristic, and a Lagrangian relaxation based procedure to obtain performance guarantees on the solution obtained from the heuristic.