AbstractThis paper studies the problem of dedicating routes to connections in optical networks. In optical networks, the vast bandwidth available in an optical fiber is utilized by partitioning it into several channels, each at a different optical wavelength. A connection between two nodes is assigned a specific wavelength, with the constraint that no two connections sharing a link in the network can be assigned the same wavelength. This paper considers optical networks with and without switches, and different types of routing in these networks. It presents optimal or near-optimal constructions of optical networks in these cases and algorithms for routing connections, specifically permutation routing for the networks constructed here.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Preliminary versionA preliminary version of these results was presented in: Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, and Madhu Sudan. Efficient routing and scheduling algorithms for optical networks. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 412-423, Arlington, Virginia, 23-25 January 1994.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.1 [Discrete Mathematics]: Combinatorics; G.2.2 [Discrete Mathematics]: Graph Theory
General Terms: Algorithms
Additional Key Words and Phrases: Optical networks, routing, wavelength assignment
Selected papers that cite this one
- Philip D. MacKenzie and Vijaya Ramachandran. ERCW PRAMs and optical communication. Theoretical Computer Science, 196(1-2):153-180, 6 April 1998.
- Aravind Srinivasan. Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems. In 38th Annual Symposium on Foundations of Computer Science, pages 416-425, Miami Beach, Florida, 20-22 October 1997. IEEE.
Selected references
- Sanjeev Arora, Tom Leighton, and Bruce Maggs. On-line algorithms for path selection in a nonblocking network (extended abstract). In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 149-158, Baltimore, Maryland, 14-16 May 1990.
- Allan Borodin, Prabhakar Raghavan, Baruch Schieber, and Eli Upfal. How much can hardware help routing? (extended abstract). In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 573-582, San Diego, California, 16-18 May 1993.
- Avi Wigderson and David Zuckerman. Expanders that beat the eigenvalue bound: Explicit construction and applications. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 245-251, San Diego, California, 16-18 May 1993.