Flow Trees: A Lower Bound Computation Tool with Applications to Rearrangeable Multihop Lightwave Network Optimization
Bulent Yener; Terrance E. Boult
- Flow Trees: A Lower Bound Computation Tool with Applications to Rearrangeable Multihop Lightwave Network Optimization
Boult, Terrance E.
- Technical reports
- Computer Science
- Permanent URL:
- Columbia University Computer Science Technical Reports
- Part Number:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- 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.
- Computer science
- Item views: