Ph.D Thesis

Ph.D StudentSalom Mordohay
SubjectOptimal Design Problems for Optical Networks
DepartmentDepartment of Computer Science
Supervisor PROFESSOR EMERITUS Shmuel Zaks


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. Information travels along a path, called lightpath. We assume optical routers with no wavelength conversion, thus a lightpath uses the same wavelength on all the edges. A communication request should be assigned a path and a wavelength in order to be transmitted. Two paths sharing an edge should get distinct wavelengths, otherwise the information they carry interferes.

The ADM minimization (MINADM) problem became of interest in the late 1990's: Information enters and leaves a lightpath 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 l , then they may share an ADM operating at wavelength l at node v. An ADM may be shared by at most two lightpaths. Therefore 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 number of edges. In our work we present a 10/7+e-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 an associated bandwidth which is a multiple of some basic unit, thus represented by an integer. The bandwidth of a wavelength is g times this unit, where g is the grooming factor. A coloring is valid if for each edge e and wavelength l, the sum of the bandwidths of the paths using e and colored l is at most g. In these settings an ADM may serve at most  2g paths. The approximation ratio of any algorithm 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.