COMBINATORIAL OPTIMIZATION IN TELECOMMUNICATIONS

Abstract. Combinatorial optimization problems are abundant in the telecommunications industry. In this paper, we present four real-world telecommunications applications where combinatorial optimization plays a major role. The first problem concerns the optimal location of modem pools for an internet service provider. The second problem deals with the optimal routing of permanent virtual circuits for a frame relay service. In the third problem, one seeks to optimally design a SONET ring network. The last problem comes up when planning a global telecommunications network.

1. Introduction

Combinatorial optimization problems are abundant in the telecommunications industry. In this paper, we present four real-world telecommunications applications where combinatorial optimization plays a major role.

In Section 2, we consider the PoP (point-of-presence) placement problem, an optimization problem confronted by internet access providers. The most common, and potentially least expensive, way for a customer to access the internet is with a modem by making a phone call to a PoP of the provider. It has been conjectured that potential customers are more likely to subscribe to internet access service if they can make a local (free unmetered) phone call to access at least one of the internet provider's PoPs. Given that the number of PoPs that can be deployed is limited by a number of constraints, such as budget and office capacity, one would like to place (or locate) the PoPs in a configuration that maximizes the number of customers than can make local calls to at least one PoP. We call this number of customers the coverage. A greedy randomized adaptive search procedure (GRASP) is used to find solutions to this location problem that, in real-world situations, are shown to be near-optimal.

A Frame Relay (FR) service offers virtual private networks to customers by provisioning a set of permanent (long-term) virtual circuits (PVCs) between customer endpoints on a large backbone network. During the provisioning of a PVC, routing decisions are made either automatically by the FR switch or by the network designer, through the use of preferred routing assignments, without any knowledge of future requests. Over time, these decisions usually cause inefficiencies in the network and occasional rerouting of the PVCs is needed. The new PVC routing scheme is then implemented on the network through preferred routing assignments. Given a preferred routing assignment, the FR switch will move the PVC from its current route to the new preferred route as soon as that move becomes feasible.

Section 3, deals with a GRASP for optimal routing of permanent virtual circuits for a frame relay service.

Survivable telecommunications networks with fast service restauration capability are increasingly in demand by customers whose businesses depend heavily on continuous reliable communications. Businesses such as brokerage houses, banks, reservation systems, and credit card companies are willing to pay higher rates for guaranteed service availability. The introduction of the Synchronous Optical Network (SONET) standard has enabled the deployment of networks having a high level of service availability. In Section 4, we describe an approach for optimal design a SONET ring network.

With the worldwide market liberalization of telecommunications, the international telecommunications environment is changing from the traditional bilateral mode of operation, where each network between pairs of administrations (AT&T and British Telecom, AT&T and France Telecom, British Telecom and France Telecom, etc.) is planned separately, to a more global, alliance-based, environment, where the network needs of several administrations may be planned simultaneously. This allows network planning to be done more in the manner that a single national network is designed, as opposed to many individual networks [6, 3, 24]. In Section 5, we describe a problem that comes up when planning a global telecommunications network.