Improved Access to Optical Bandwidth in Trees

Abstract

We present improved bounds for efficient bandwidth allocation in a WDM optical network whose topology is that of a directed tree of fiber-optic links. The problem of bandwidth allocation is modeled as a coloring problem, where each path in a set of communication requests must be assigned a color (representing a wavelength) in such a way that no two paths using the same link in the same direction are assigned the same color. Letting L be the largest number of paths using any directed link, we show that for an arbitrary set of paths, 7L=4 colors are sufficient to route all paths. This improves an upper bound of 15L=8 due to Mihail, Kaklamanis and Rao [8]. In addition, we show that a family of problem instances given by Mihail, Kaklamanis and Rao [8] to establish a worst-case lower bound of 3L=2 for the problem can in most cases be colored with only 5L=4 colors (technically, d5L=4e). Finally, we show that in all cases 5L=4 colors are in fact necessary for this family of instances, yield...