Algorithms for distributing telecommunication traffic on a multiple-ring SONET-based network

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

We examine a problem arising in the assignment of telecommunication traffic to a set of synchronous optical network (SONET) rings. Prior SONET design algorithms determine node-to-ring assignments while concurrently prescribing an assignment of traffic to the rings. However, due to uncertain voice and data demand among client nodes, it may become necessary to revise the planned routing scheme once the true values of this data are realized. We develop a minimum cost flow algorithm for the case in which demands may be split across multiple rings, and provide a transformation to a maximum flow problem for specially structured data. The case in which each demand pair may be routed on only one ring is proven to be NP-hard, and we accordingly provide a powerful heuristic and an effective standard valid inequality generation scheme to optimally solve this problem within reasonable computational limits. The effectiveness of our approach is demonstrated on a set of randomly generated test data.

Original languageEnglish (US)
Pages (from-to)659-672
Number of pages14
JournalEuropean Journal of Operational Research
Volume154
Issue number3
DOIs
StatePublished - May 1 2004
Externally publishedYes

Keywords

  • Integer programming
  • Network flows
  • Synchronous optical network
  • Telecommunications

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint Dive into the research topics of 'Algorithms for distributing telecommunication traffic on a multiple-ring SONET-based network'. Together they form a unique fingerprint.

  • Cite this