Sparse telephone gateway for internet telephony

Yiu-Wing Leung*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

2 Citations (Scopus)
11 Downloads (Pure)


Internet telephony is promising for long-distance calls. To serve the general public, a service provider can operate a telephone gateway in each servicing city to bridge the local telephone network and the Internet, so that users can use telephones or mobile phones to access these telephone gateways for long-distance calls. The service provider should serve many cities to attain good service coverage but it is costly to operate telephone gateways in all of these cities. In this paper, we propose a sparse telephone gateway configuration to serve many cities cost-effectively. Using this configuration, if the service provider serves N cities, it operates telephone gateways in only M cities where M < N. If a telephone gateway is available in a city, users in this city access this gateway for service; otherwise, they access the gateway in a nearby city through inter-city calls for service. It is necessary to optimize the sparse telephone gateway configuration to achieve the best cost-effectiveness. We formulate this problem in which the expected revenue is maximized, prove that it is NP-hard, and design an efficient two-stage heuristic algorithm to solve it. Numerical results show that the sparse telephone gateway configuration is more cost-effective than the existing configuration.

Original languageEnglish
Pages (from-to)150-164
Number of pages15
JournalComputer Networks
Issue number1
Early online date20 Sept 2009
Publication statusPublished - 15 Jan 2010

Scopus Subject Areas

  • Computer Networks and Communications

User-Defined Keywords

  • Internet telephony
  • Telephone gateway
  • Cost and revenue
  • Optimization


Dive into the research topics of 'Sparse telephone gateway for internet telephony'. Together they form a unique fingerprint.

Cite this