All-to-All Optical Routing in Chordal Rings of Degree 4

We consider the problem of routing in networks employing all-optical routing technology. In such networks, information between nodes of the network is transmitted as light on fiber-optic lines without being converted to electronic form in between. We consider switched optical networks that use the wavelength-division multiplexing (or WDM) approach. A WDM network consists of nodes connected by point-to-point fiber-optic links, each of which can support a fixed number of wavelengths. The switches are capable of redirecting incoming streams based on wavelengths, without changing the wavelengths. Different messages may use the same link concurrently if they are assigned distinct wavelengths. However, messages assigned the same wavelength must be assigned edge-disjoint paths. Given a communication instance in a network, the optical routing problem is the assignment of {routes} to communication requests of the instance, as well as wavelengths to routes so that the number of wavelengths used by the instance is minimal. We focus on the all-to-all communication instance I _A in a widely studied family of chordal rings of degree 4, called optimal chordal rings . For these networks, we prove exact bounds on the optimal load induced on an edge for I _A , over all shortest-path routing schemes. We show an approximation algorithm that solves the optical routing problem for I _A using at most 1.006 times the lower bound on the number of wavelengths. The previous best approximation algorithm has a performance ratio of 8. Furthermore, we use a variety of novel techniques to achieve this result, which are applicable to other communication instances and may be applicable to other networks. Received July 22, 1998; revised October 14, 1999.