Logical Embeddings for Minimum Congestion Routing in Lightwave Networks

Bulent Yener; Terrance E. Boult

Logical Embeddings for Minimum Congestion Routing in Lightwave Networks
Yener, Bulent
Boult, Terrance E.
Technical reports
Computer Science
Persistent URL:
Columbia University Computer Science Technical Reports
Part Number:
Department of Computer Science, Columbia University
Publisher Location:
New York
The problem considered in this paper is motivated by the independence between logical and physical topology in Wavelength Division Multiplexing WDM based local and metropolitan lightwave networks. This paper suggests logical embeddings of digraphs into multihop lightwave networks to maximize the throughput under nonuniform traffic conditions. Defining congestion as the maximum flow carried on any link, two perturbation heuristics are presented to find a good logical embedding on which the routing problem is solved with minimum congestion. A constructive proof for a lower bound of the problem is given, and obtaining an optimal solution for integral routing is shown to be NP-Complete. The performance of the heuristics is empirically analyzed on various traffic models. Simulation results show that our heuristics perform on the average from a computed lower bound Since this lower bound is not quite tight we suspect that the actual performance is better In addition we show that 5%-20% performance improvements can be obtained over the previous work.
Computer science
Item views
text | xml
Suggested Citation:
Bulent Yener, Terrance E. Boult, 1993, Logical Embeddings for Minimum Congestion Routing in Lightwave Networks, Columbia University Academic Commons, http://hdl.handle.net/10022/AC:P:12337.

Center for Digital Research and Scholarship at Columbia University Libraries | Policies