Title:

Flow Trees: A Lower Bound Computation Tool with Applications to Rearrangeable Multihop Lightwave Network Optimization

Author(s):

Yener, Bulent
Boult, Terrance E.

Date:

1994

Type:

Technical reports

Department:

Computer Science

Permanent URL:

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

Series:

Columbia University Computer Science Technical Reports

Part Number:

CUCS-006-94

Publisher:

Department of Computer Science, Columbia University

Publisher Location:

New York

Abstract:

This paper presents a new method for computing the lower bounds for multihop network design problems which is particularly well suited to optical networks. More specifically, given N stations each with d transceivers and pairwise average traffic values of the stations, the method provides a lower bound for the combined problem of finding optimum (i) allocation of wavelengths to the stations to determine a configuration, and (ii) routing of the traffic on this configuration while minimizing congestion - defined as the maximum flow assigned on any link. The lower bounds can be computed in time polynomial in the network size. Consequently, the results in this work yield a tool which can be used in (i) evaluating the quality of heuristic design algorithms, and (ii) determining a termination criteria during minimization. The lower bound computation is based on first building flow trees to find a lower bound on the total flow, and then distributing the total flow over the links to minimize the congestion.

Subject(s):

Computer science

Item views:

35

Metadata:

description

View | Download