Home

Logical Embeddings for Minimum Congestion Routing in Lightwave Networks

Bulent Yener; Terrance E. Boult

Title:
Logical Embeddings for Minimum Congestion Routing in Lightwave Networks
Author(s):
Yener, Bulent
Boult, Terrance E.
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
Series:
Columbia University Computer Science Technical Reports
Part Number:
CUCS-008-93
Publisher:
Department of Computer Science, Columbia University
Publisher Location:
New York
Abstract:
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.
Subject(s):
Computer science
Item views:
123
Metadata:
text | xml

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services | Terms of Use