Sparse and limited wavelength conversion in all-optical tree networks

We study the problem of assigning a minimum number of colors to directed pa ths (dipaths) of a tree, so that any two dipaths that share a directed edge of the tree are not assigned the same color. The problem has applications to wavelength routing in WDM all-optical tree networks, an important engine ering problem. Dipaths represent communication requests, while colors corre spond to wavelengths that must be assigned to requests so that multiple use rs can communicate simultaneously through the same optical fiber. Recent wo rk on wavelength routing in trees has studied a special class of algorithms which are called greedy,. Although these algorithms are simple and impleme ntable in a distributed setting, it has been proved that there are cases wh ere a bandwidth utilization of 100% is not possible. Thus, in this work, we relax the constraints of the original engineering problem and use devices called wavelength converters that are able to convert the wavelength assign ed to a segment of a communication request to another wavelength that will be assigned to some other segment of the same request. The trade-off of the use of wavelength converters is increased cost and complexity; so, our aim is to use converters that have relatively simple functionality. We study t he performance of greedy deterministic algorithms in tree-shaped all-optica l networks that support wavelength conversion. We study both the case of sp arse conversion and limited conversion. By sparse we mean that converters h ave full conversion capabilities and the objective is to minimize the numbe r of converters employed. On the other hand, in limited conversion, we assu me that converters with limited conversion capabilities are placed at each non-leaf node of the tree. By limited, we mean that converters are simple a ccording to either their wavelength degree or their size. Our results show that using converters of either low degree or small size, we can beat the k nown lower bounds and improve bandwidth utilization. In some cases we even achieve optimal bandwidth utilization. For the construction of the converte rs, we use special classes of graphs such as expanders, dispersers and dept h-two superconcentrators, Explicit constructions are known for most of the graphs used in this paper. (C) 2001 Elsevier Science B.V. All rights reserv ed.