Title page for ETD etd-11162005-111427

Type of Document Dissertation
Author Yi, Tong
Author's Email Address tyi1@lsu.edu
URN etd-11162005-111427
Title Broadcast in Sparse Conversion Optical Networks Using Fewest Converters
Degree Doctor of Philosophy (Ph.D.)
Department Computer Science
Advisory Committee
Advisor Name Title
Sukhamay Kundu Committee Chair
Bert Boyce Committee Member
Donald Kraft Committee Member
Jianhua Chen Committee Member
Stephen Shipman Dean's Representative
  • optical networks
  • broadcast
  • converters usage problem
  • sparse conversion
Date of Defense 2005-10-07
Availability unrestricted
Wavelengths and converters are shared by communication requests in optical networks. When a message goes through a node without a converter, the outgoing wavelength must be the same as the incoming one. This constraint can be removed if the node uses a converter. Hence, the usage of converters increases the utilization of wavelengths and allows more communication requests to succeed. Since converters are expensive, we consider sparse conversion networks, where only some specified nodes have converters. Moreover, since the usage of converters induces delays, we should minimize the use of available converters.

The Converters Usage Problem (CUP) is to use a minimum number of converter so that each node can send messages to all the others (broadcasting). In this dissertation, we study the CUP in sparse conversion networks.

We design a linear algorithm to find a wavelength assignment in tree networks such that, with the usage of a minimum number of available converters, every node can send messages to all the others.

This is a generalization of [35], where each node has a converter. Our algorithm can assign wavelengths efficiently and effectively for one-to-one, multicast, and broadcast communication requests.

A converter wavelength-dominates a node if there is a uniform wavelength path between them. The Minimal Wavelength Dominating Set Problem (MWDSP) is to locate a minimum number of converters so that all the other nodes in the network are wavelength-dominated. We use a linear complexity dynamic programming algorithm to solve the MWDSP for networks with bounded treewidth. One such solution provides a low bound for the optimal solution to the CUP.

  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Yi_dis.pdf 600.82 Kb 00:02:46 00:01:25 00:01:15 00:00:37 00:00:03

Browse All Available ETDs by ( Author | Department )

If you have more questions or technical problems, please Contact LSU-ETD Support.