A HEURISTIC-PROCEDURE FOR LEASING CHANNELS IN TELECOMMUNICATIONS NETWORKS

Rapid advances in computing and communications technology have made di stributed computing an attractive alternative for geographically dispe rsed organizations. A telecommunication sub-network forms the backbone of these distributed systems. in general, this paper focuses on the a ssignment of communication channel capacities in the presence of time variant usage patterns. Specifically, we concentrate on long-range cap acity planning for organizations that construct networks by leasing co mmunication channels from telecommunication companies. We formulate th e capacity assignment problem as a 0-1 integer program that seeks to m inimize total leasing cost subject to communication delay restrictions . Unlike previous models that include a single-system wide-average del ay constraint, our model allows the flexibility of specifying delay re strictions by communicating node pairs. We propose an efficient heuris tic, and a Lagrangian relaxation based procedure to obtain performance guarantees on the solution obtained from the heuristic.