Date of Award

2004

Publication Type

Master Thesis

Degree Name

M.Sc.

Department

Computer Science

Keywords

Computer Science.

Supervisor

Bandyopadhyay, S.

Rights

info:eu-repo/semantics/openAccess

Abstract

Finding an optimum routing scheme, so that a given logical topology for a wavelength routed WDM network handles all traffic requirements in an efficient manner, is an important problem in optical network design. One major design objective is to minimize the congestion of the network, defined as the traffic on the logical link which has the maximum traffic. This is known to be a hard problem taking an enormous amount of time even for moderate sized networks and is intractable for larger networks. The approach we have outlined is that of obtaining an approximate solution to the problem rather than an exact solution. We have developed three closely related approximate algorithms to solve this problem. These three algorithms significantly improved the running time for finding the minimum congestion. We based our approach on the approximation fraction multi-commodity algorithm by Lisa Fleischer [F99] to calculate the primal and dual solutions for the linear program to solve the multi-commodity flow problem. We have compared our algorithm with the standard linear program solution obtained using CPLEX. The experiments show that our algorithms require, on the average, only less than 10% of the time CPLEX uses for networks with 25 nodes or less. Our algorithms perform well for larger networks which CPLEX cannot handle.Dept. of Computer Science. Paper copy at Leddy Library: Theses & Major Papers - Basement, West Bldg. / Call Number: Thesis2004 .L85. Source: Masters Abstracts International, Volume: 43-03, page: 0884. Advisers: Subir Bandyopadhyay; Arunita Jackel. Thesis (M.Sc.)--University of Windsor (Canada), 2004.

Download

Share

COinS