Volume 20, 2001, No. 2

WAVELENGTH ROUTING IN ALL-OPTICAL TREE NETWORKS: A SURVEY

I. CARAGIANNIS, C. KAKLAMANIS, P. PERSIANO   Abstract We study the problem of allocating optical bandwidth to sets of communication requests in all-optical networks that utilize Wavelength Division Multiplexing (WDM). WDM technology establishes communication between pairs of network nodes by establishing transmitter-receiver paths and assigning wavelengths to each path so that no two paths going through the same fiber link use the same wavelength. Optical bandwidth is the number of distinct wavelengths. Since state-of-the-art technology allows for a limited number of wavelengths, the engineering problem to be solved is to establish communication between pairs of nodes so that the total number of wavelengths used is minimized; this is known as the wavelength routing problem. In this paper, we survey recent advances in bandwidth allocation in tree-shaped WDM all-optical networks: We present hardness results and lower bounds for the general problem and the special case of symmetric communication. We give the main ideas of deterministic greedy algorithms and study their limitations. We demonstrate how we can achieve optimal and nearly-optimal bandwidth utilization in networks with wavelength converters using simple algorithms. We also present recent results about the use of randomization for wavelength routing.

 

HARDNESS RESULTS AND EFFICIENT APPROXIMATIONS FOR FREQUENCY ASSIGNMENT PROBLEMS: RADIO LABELLING AND RADIO COLORING

D. A. FOTAKIS, S. E. NIKOLETSEAS, V. G. PAPADOPOULOU, P. G. SPIRAKIS   Abstract The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters, exploiting frequency reuse while keeping signal interference to acceptable levels. The FAP is usually modeled by variations of graph coloring. In this work we first survey the variations of the FAP and then we study two (similar but still different) frequency assignment problems: radio labelling and radiocoloring. For radio labelling, we prove that the problem is NP-complete for general graphs and we provide efficient NC approximation algorithms. We also give a polynomial time algorithm computing an optimal radio labelling for planar graphs, thus showing that radio labelling is in P for planar graphs. On the other hand, we prove that radiocoloring remains NP-complete even for planar graphs and we provide an efficient 2-ratio approximation algorithm. We also present a fully polynomial randomized approximation scheme for computing the number of different radiocolorings of planar graphs.

 

ON EFFICIENCY OF PATH SYSTEMS INDUCED BY ROUTING AND COMMUNICATION SCHEMES

Peter RUŽIČKA   Abstract Communication problems are studied as simple directed path systems satisfying given communication requests in point-to-point networks. Efficiency measures of these path systems such as congestion, dilation, compactness and buffer-size are analyzed. We focus on some recent algorithmic developments and novel techniques for the design of efficient communication schemes. Related open problems and an overview of several related research directions are also given.

 

DESIGN ISSUES IN ATM AND OPTICAL NETWORKS

Shmuel ZAKS   Abstract In this paper, graph-theoretic models are described that are of use in studies of designs for ATM networks and for optical networks. Although these models share a basic framework, the problems studied, and the parameters under concern, are not identical. The differences stem from the constraints imposed by the two different technologies, and their perspective applications. For ATM networks, a short summary of the virtual path layout problem is given, and some results are discussed. A detailed description is given for the use of duality and high dimensional geometry in deriving and analyzing optimal designs for chain and ring networks. Regarding optical networks the wavelength assignment problem and the ring partition problem are described, together with few recent results.

 

Volume 20, 2001, No. 2