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

Yener, Bulent; Boult, Terrance E.

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.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-006-94
Published Here
January 27, 2012