Efficient routing in optical networks

ABSTRACT

This 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.

REFERENCES

• 1: S. Arora , T. Leighton , B. Maggs, On-line algorithms for path selection in a nonblocking network, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.149-158, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100232]
• 2: ~BARRY, R. A., AND HUMBLET, P.A., 1992. Bounds on the number of wavelengths needed in WDM ~ networks. In LEOS'92 Summer Topical Meeting Digest. pp. 21-22.
• 3: ~BARRY, R. A., AND HUMBLET, P.A. 1993. An all-optical non-blocking M x M switchless connector ~with O(X/M log M) wavelengths and without wavelength changers. Electron Lett. 29, 1252-1254.
• 4: ~BARRY, R. A., AND HUMBLET, P. A. 1994. On the number of wavelengths and switches in ~all-optical networks. IEEE Trans. Commun. 42, 2/3/4, 583-591.
• 5: ~BENE~, V. E. 1962. Heuristic remarks and mathematical problems regarding the theory of ~switching systems. Bell Syst. Tech. J. 41, 1201-1247.
• 6: Allan Borodin , Prabhakar Raghavan , Baruch Scheiber , Eli Upfal, How much can hardware help routing?, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.573-582, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167237]
• 7: ~CHEUNG, N. K., Nosu, K., AND WINZER, G. (EDS.) 1990. IEEE JSAC: Special Issue on Dense WDM ~Networks, vol. 8, IEEE, New York.
• 8: Paul Feldman , Joel Friedman , Nicholas Pippengers, Wide-sense nonblocking networks, SIAM Journal on Discrete Mathematics, v.1 n.2, p.158-173, May 1988 [doi>10.1137/0401018]
• 9: ~GREEN, P.E. 1992. Fiber-Optic Networks. Prentice-Hall, Engelwood Cliffs, N.J.
• 10: ~HALL, P. 1935. On the representatives of subsets. J. London Math. Soc. 10,(1), 26-30.
• 11: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 12: Rajesh Kumar Pankaj, Architectures for linear lightwave networks, Massachusetts Institute of Technology, Cambridge, MA, 1992
• 13: Gerard R. Pieris , Galen H. Sasaki, A linear lightwave Benes network, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.441-445, Aug. 1993 [doi>10.1109/90.251896]
• 14: ~RAMASWAMI, R. 1993. Multi-wavelength lightwave networks for computer communication, IEEE ~ Communications Magazine, 31, 2, 78-88
• 15: Avi Wigderson , David Zuckerman, Expanders that beat the eigenvalue bound: explicit construction and applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.245-251, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167163]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
      G.2.2 Graph Theory

General Terms:
Algorithms

Keywords:
optical networks, routing, wavelength assignment