Technical Report PHD-2006-03

TR#:PHD-2006-03
Class:PHD
Title: Optimal Design Problems for Optical Network
Authors: Mordechai Shalom
Supervisors: Shmuel Zaks
PDFPHD-2006-03.pdf
Abstract: Third generation optical networks, also known as all-optical networks, enable us to transmit information in several wavelength ranges within a single fiber, independent of each other, and to route information at communication nodes without the need of examining its contents. Therefore, information travels from its source to its destination at the speed of light along a path called lightpath. We assume optical routers with no wavelength conversion, thus a lightpath uses the same wavelength on all the edges.

In single-hop communication a communication request from a node s to a node t should be assigned a path from s to t and a wavelength (color) in order to be transmitted, whereas in multi-hop communication it is assigned a sequence of paths (hops) each of which is assigned a wavelength independently. The problem of assigning paths and wavelengths to requests is called the WRA (Wavelength Routing and Assignment) problem. When the path assignment is already known, it is termed WLA (Wavelength Assignment) problem. Two paths sharing an edge should get distinct wavelengths, otherwise the information they carry interferes.

Most of the problems we discuss in our work are NP-Hard, therefore we are mainly interested in approximation algorithms.

The ADM minimization (MINADM) problem became of interest in the late 1990's. Information enters a lightpath at its source and leaves it at its destination via equipment called ADMs. A lightpath uses an ADM at each endpoint. Obviously 2 |P| ADMs are sufficient for |P| paths. If two lightpaths with a common endpoint v get the same wavelength $\lambda$, then they may share an ADM operating at wavelength $\lambda$ at node v. An ADM may be shared by at most two lightpaths. Therefore the minimum required number of ADMs is |P|, and the approximation ratio of any algorithm for this problem is at most 2.

The ring topology is important in communication networks because it provides protection for one failure with minimum edges. In our work we present a (10/7+\epsilon)-approximation algorithm for the MINADM problem in ring networks. We present also an improved analysis of an algorithm for general topology.

A communication request has a bandwidth which is an integer multiple of some basic unit of bandwidth. It is presented by an integer. The bandwidth supplied by a wavelength is $g$ times this basic unit, where $g$ is an integer called the grooming factor. A coloring is valid if for each edge e and wavelength \lambda, the sum of the bandwidths of the paths using e and colored \lambda is at most g. This family of problems is termed traffic grooming problems. An ADM may service at most 2g paths, g at each side. Therefore the approximation ratio of any algorithm for this problem is at most 2g.

In our work we present an efficient architecture in terms of number of ADMs used, for uniform all-to-all traffic in ring networks and multi-hop communication, using the bandwidth of the fiber optimally.

We also present an O(log g)-approximation algorithm for ring networks, general traffic, single-hop communication and any grooming factor. The algorithm is usable in any topology, whereas our analysis holds in the ring topology.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2006/PHD/PHD-2006-03), rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2006
To the main CS technical reports page

Computer science department, Technion