Abstract
In an optical network, wavelength-division multiplexing permits multiple messages to be sent along the same link in the network by transmitting each message using a distinct wavelength. In such a network, the action of establishing a connection between two nodes entails choosing a route in the network between the nodes and then assigning to the connection, a wavelength for each link in the chosen route. We will consider problems concerning the minimum number of wavelengths sufficient to establish a set of connections. In a wavelength-selective (WS) network, the assigned wavelengths for any given connection must be the same throughout the chosen route. In contrast, for a wavelength-interchanging (WI) network the assigned wavelengths for each link in the route may differ. We show that for an important class of networks, namely ring networks of n nodes with clockwise and counterclockwise links between each neighboring pair of nodes on the ring, the minimum number, k n, of wavelengths that suffice to allow simultaneously all possible connections is the same for either case. In particular, for both WS and WI networks, it is shown that k n=(n 2−1)/8 if n is odd, k n=n 2/8 if n is even and divisible by 4 and k n=n 2/8+1/2 if n is even but not divisible by 4.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
A. Aggarwal, A. Bar-Noy, D. Coppersmith, R. Ramaswami, B. Schieber, and M. Sudan. Efficient routing and scheduling algorithms for optical networks. In Proceedings of SODA, pages 412–423, 1994.
S. B. Alexander, R. S. Banderant, D. Byrne, V. W. S. Chan, S. G. Finn, R. Gallager, B. S. Glance, H. A. Haus, P. Humblet, R. Jain, I. P. Kaminow, M. Karol, R. S. Kennedy, A. Kirby, H. Q. Le, A. M. Saleh, B. A. Schofield, J. H. Shapiro, N. K. Shankaranarayanan, R. E. Thomas, R. C. Williamson, and R. W. Wilson. A precompetitive consortium on wide-band all-optical networks. Journal of Lightwave Technology, 11(5/6):714–735, May/June 1993.
M. C. Brain and P. Cochrane. Wavelength routed optical networks using coherent transmission. In Proceedings of ICC, volume 1, pages 26–31, 1988.
I. Chlamtac, A. Ganz, and G Karmi. Lightpath communications: An approach to high bandwidth optical wan's. IEEE Transactions on Communications, 40(7):1171–1182, July 1992.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., San Francisco, CA, 1979.
P. E. Green. Fiber-Optic Networks. Prentice-Hall, Cambridge, MA, 1992.
G. Jeong and E. Ayanoglu. Comparison of wavelength-interchanging and wavelength-selective cross-connects in multiwavelength all-optical networks. Technical Report BLO113430-950927-29TM, AT&T Bell Laboratories, 1995.
K-C. Lee and V. O. K. Li. Routing and switching in a wavelength convertible optical network. In Proceedings of IEEE INFOCOM, volume 2, pages 578–585, 1993.
K. Sato, S. Okamoto, and H. Hadama. Network performance and integrity enhancement with optical path layer technologies. IEEE Journal on Selected Areas of Communications, 12(1):159–170, January 1994.
D. W. Smith and G. R. Hill. Optical processing in future coherent networks. In Proceedings of GLOBECOM, volume 2, pages 678–683, 1987.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wilfong, G. (1996). Minimizing wavelengths in an all-optical ring network. In: Asano, T., Igarashi, Y., Nagamochi, H., Miyano, S., Suri, S. (eds) Algorithms and Computation. ISAAC 1996. Lecture Notes in Computer Science, vol 1178. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0009511
Download citation
DOI: https://doi.org/10.1007/BFb0009511
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62048-8
Online ISBN: 978-3-540-49633-5
eBook Packages: Springer Book Archive