Affiliations: Columbia University Department of Computer Science, NYC, NY 10027, USA, E-mail: [email protected]
Note: [] T. Boult is now with Lehigh University Department of Electrical Engineering and Computer Science, Bethlehem, PA, USA, E-mail: [email protected] work was supported in part by NSF PYI award #IRI-90-57951 with industrial support from IBM and Texas Instruments. Final version of paper prepared while Dr Yener was a visiting Assistant Professor at Northeastern University, Boston, MA.
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.
