All-to-all optical routing in chordal rings of degree 4

We consider the problem of routing in networks employing all-optical routin g technology. In such networks, information between nodes of the network is transmitted as light on fiber-optic lines without being converted to elect ronic form in between. We consider switched optical networks that use the w avelength-division multiplexing (or WDM) approach. A WDM network consists o f nodes connected by point-to-point fiber-optic links, each of which can su pport a fixed number of wavelengths. The switches are capable of redirectin g 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 b e 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 wel l as wavelengths to routes so that the number of wavelengths used by the in stance 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 chord al rings. For these networks, we prove exact bounds on the optimal load ind uced 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 us ing at most 1.006 times the lowerbound on the number of wavelengths. The pr evious best approximation algorithm has a performance ratio of 8. Furthermo re, 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.