Title:

Logical Embeddings for Minimum Congestion Routing in Lightwave Networks

Author(s):

Yener, Bulent
Boult, Terrance E.

Date:

1993

Type:

Technical reports

Department:

Computer Science

Permanent URL:

http://hdl.handle.net/10022/AC:P:12337

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:

100

Metadata:

description

View | Download