McGill University - School of Computer Science

Computational Geometry Seminar

Everybody is welcome.

DATE:	Wednesday, September 23rd, 1998
TIME:	16:00-17:00 <- note new time
PLACE:	McConnell 320
TITLE:	Optical routing in some networks
SPEAKER:	Dominique Sotteau, CNRS

We consider the problem of routing in networks employing all-optical routing technology. In such networks, information is transmitted as light on fiber-optic lines without being converted to electronic form in between. By using different wavelengths, different messages may use the same line concurrently. However, messages assigned the same wavelength must be assigned edge-disjoint paths. Given a communication pattern in a network, the wavelength routing problem entails the assignment of routes to communication requests, as well as wavelengths to routes. As the cost of an optical network increases with the number of wavelengths used, we must attempt to minimize the total number of wavelengths used by the communication pattern.

Optical networks are generally modeled by directed graphs, and more specifically by symmetric digraphs, that is, a directed graph G with vertex set V(G) and edge set E(G) such that if (x,y) is in E(G), then (y,x) is also in E(G). A request is an ordered pair of nodes (x,y) which corresponds to a message to be sent from x to y. An instance I is a collection of requests. Given an instance I in the network, an optical routing problem is to determine a path through the network, and assign a wavelength, to each request in I so that no two requests whose paths share a link are assigned the same wavelength. Since the cost of an optical switch is proportional to the number of wavelengths it can handle, it is important to determine paths and wavelengths so that the total number of wavelengths required is minimized.

We present some of the theoretical work which has been done on this optical routing problem and show how it may be related to some previous work on forwarding indices of a graph.

Finally we focus on the all-to-all communication pattern in a widely studied family of chordal rings.

This information is available at http://cgm.cs.mcgill.ca/~therese/seminar.
Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to Therese Biedl at therese@cgm.cs.mcgill.ca.