1993 Reports
Logical Embeddings for Minimum Congestion Routing in Lightwave Networks
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.
Subjects
Files
- cucs-008-93.pdf application/pdf 278 KB Download File
More About This Work
- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-008-93
- Published Here
- January 25, 2012