×

Wavelength routing of uniform instances in all-optical rings. (English) Zbl 1177.90248

Summary: We consider the problem of routing uniform communication instances in switched optical rings that use wavelength-division multiplexing technology. A communication instance is called uniform if it consists exactly of all pairs of nodes in the graph whose distance is equal to one from a specified set \(S= \{d_1,d_2,\dots,d_k\}\). When \(k=1\) or 2, we prove necessary and sufficient conditions on the values in \(S\) relative to n for the optimal wavelength index to be equal to the optimal load in the ring \(R_n\). When \(k=2\), we show that for any uniform instance specified by \(\{d_1,d_2\}\), there is an optimal wavelength assignment on the ring \(R_n\), if \(n>(d_1/q-2)d_1+ (d_1/q-1)d_2\), where \(q= \text{GCD}(d_1,d_2)\). For general \(k\) and \(n\), we show a \((\frac32)\)-approximation for the optimal wavelength index; this is the best possible for arbitrary \(S\). We also show that an optimal assignment can always be obtained provided \(n\) is large enough compared to the values in \(S\).

MSC:

90B80 Discrete location and assignment
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aggarwal, A.; Bar-Noy, A.; Coppersmith, D.; Ramaswami, R.; Schieber, B.; Sudan, M., Efficient routing in optical networks, JACM, 46, 6, 973-1001 (1996) · Zbl 0885.68083
[2] Beauquier, B.; Bermond, J.-C.; Gargano, L.; Hell, P.; Perennes, S.; Vaccaro, U., Graph problems arising from wavelength-routing in all-optical networks, (Proceedings of the Second Workshop on Optics and Computer Science (WOCS), part of IPPS (April 1997))
[3] Bracket, C., Dense wavelength division multiplexing networks: principles and applications, IEEE J. Selected Areas Commun., 8, 948-964 (1990)
[4] Cheung, N.; Nosu, K.; Winzer, G., An introduction to the special issue on dense WDM networks, IEEE J. Selected Areas Commun., 8, 945-947 (1990)
[5] F. Comellas, M. Mitjana, L. Narayanan, J. Opatrny, Wavelength routing of uniform instances in tori, Proceedings of Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 1893, Springer, Berlin, 2000, pp. 285-294.; F. Comellas, M. Mitjana, L. Narayanan, J. Opatrny, Wavelength routing of uniform instances in tori, Proceedings of Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 1893, Springer, Berlin, 2000, pp. 285-294. · Zbl 0996.90017
[6] Erlach, T.; Jansen, K., Scheduling of virtual connections in fast networks, (Proceedings of the Fourth Workshop on Parallel Systems and Algorithms (1996)), 13-32
[7] Fabrega, J.; Zaragoza, M., Fault tolerant routings in double fixed-step networks, Discrete Appl. Math., 78, 1-3, 61-74 (1997) · Zbl 0890.68099
[8] M. Fiol, J. Yebra, M. Fiol, Grafos y teselaciones del plano, Actas III JAEM, Spain, 1983, pp. 69-77.; M. Fiol, J. Yebra, M. Fiol, Grafos y teselaciones del plano, Actas III JAEM, Spain, 1983, pp. 69-77.
[9] Mihail, M.; Kaklamanis, C.; Rao, S., Efficient access to optical bandwidth, (FOCS (1995)), 548-557 · Zbl 0938.68522
[10] Narayanan, L.; Opatrny, J., Compact routing in chordal rings of degree four, Algorithmica, 23, 76-99 (1999) · Zbl 0918.68038
[11] Narayanan, L.; Opatrny, J., Wavelength routing of uniform instances in all-optical rings, (Proceedings of ARACNE 2000 (2000), Carleton Scientific Press), 203-214
[12] Narayanan, L.; Opatrny, J.; Sotteau, D., All-to-all optical routing in chordal rings of degree four, (Proceedings of the Symposium on Discrete Algorithms (1999)), 695-703 · Zbl 1052.68517
[13] J. Opatrny, Uniform multi-hop all-to-all optical routings in rings, Theor. Comput. Sci. 297 (1-3) (2003) 385-397.; J. Opatrny, Uniform multi-hop all-to-all optical routings in rings, Theor. Comput. Sci. 297 (1-3) (2003) 385-397. · Zbl 1046.68024
[14] Tucker, A., Coloring a family of circular arcs, SIAM J. Appl. Math., 29, 493-502 (1975) · Zbl 0312.05105
[15] Wong, C. K.; Coppersmith, D., A combinatorial problem related to multimode memory organizations, JACM, 21, 392-402 (1974) · Zbl 0353.68039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.