The most congested cutset: deriving a tight lower bound for the chromatic number in the RWA problem

Author

Sharafat, Ahmad R. ; Ma´rouzi, Omid R.

Author_Institution

Dept. of Electr. Eng., Tarbiat Modarres Univ., Tehran, Iran

Volume

8

Issue

7

fYear

2004

fDate

7/1/2004 12:00:00 AM

Firstpage

473

Lastpage

475

Abstract

Routing and wavelength assignment (RWA) is an important issue in the design of routing protocols in an all-optical network. A solution for the RWA problem should determine the least possible number of wavelengths, also known as the chromatic number. In this letter, we introduce the concept of cutset congestion, and show that the congestion of the most congested cutset of a graph representing the network is a tight lower bound for the chromatic number in the RWA problem. In contrast to other existing techniques, our method can be applied to any network and any traffic pattern.

Keywords

directed graphs; optical communication; optical fibre networks; routing protocols; RWA problem; all-optical network; chromatic number; cutset congestion; digraph; point-to-point unidirectional fiber optic link; routing and wavelength assignment; routing protocols; symmetric directed graph; tight lower bound; All-optical networks; Intelligent networks; Interference constraints; Joining processes; Network topology; Optical computing; Routing protocols; Telecommunication traffic; Wavelength assignment; Wavelength routing; All-optical networks; RWA; chromatic number; cutset congestion; routing and wavelength assignment;

fLanguage

English

Journal_Title

Communications Letters, IEEE

Publisher

ieee

ISSN

1089-7798

Type

jour

DOI

10.1109/LCOMM.2004.832765

Filename

1315681