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

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

0.00 Avg rating0 Votes
Article ID: iaor20051790
Country: Netherlands
Volume: 154
Issue: 3
Start Page Number: 659
End Page Number: 672
Publication Date: May 2004
Journal: European Journal of Operational Research
Authors:
Keywords: networks, programming: integer
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 these 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.

Reviews

Required fields are marked *. Your email address will not be published.