Ph.D Thesis | |

Ph.D Student | Salom Mordohay |
---|---|

Subject | Optimal Design Problems for Optical Networks |

Department | Department 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 2*g* paths. The approximation ratio of any algorithm is at most 2*g*.

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.