Optimal wavelength routing on directed fiber trees. (English) Zbl 0933.68155
Summary: We present a polynomial-time greedy algorithm that assigns proper wavelengths to a set of requests of maximum load \(L\) per directed fiber link on a directed fiber tree using at most \(5/3L\) wavelengths. This improves previous results of (*) P. Raghavan and E. Upfal [Proc. Ann. ACM Symp. on theory of computing STOC, 1994, pp. 134-143], (**) M. Mihail, C. Kaklamanis and S. Rao [Proc. 36th IEEE Symp. on Foundations of Computer Science, 1995, pp. 548-557], C. Kaklamanis and P. Persiano [Proc. Algorithms – ESA 96, Lect. Notes Comput. Sci. 1136, 460-470], V. Kumar and E. J. Schwabe [Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms SODA, 1997, pp. 437-444]. We also prove that no greedy algorithm can in general use less than 5/3L wavelengths for a set of requests of load L in a directed fiber tree, and thus our algorithm is optimal in the class of greedy algorithms which includes the algorithms presented in (*) (**).
References:
| [1] | Aggarwal, A.; Bar-Noy, A.; Coppersmith, D.; Ramaswami, R.; Schieber, B.; Sudan, M., Efficient routing and scheduling algorithms for optical networks, (Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms SODA (1994)), 412-423 · Zbl 0874.68018 |
| [2] | C. Berge, Graphs, North-Holland, Amsterdam.; C. Berge, Graphs, North-Holland, Amsterdam. · Zbl 0566.05001 |
| [3] | Bermond, J. C.; Gargano, L.; Perennes, S.; Rescigno, A. A.; Vaccaro, U., Efficient collective communication in optical networks, (Proc. 23rd Internat. Coll. on Automata, Languages and Programming ICALP. Proc. 23rd Internat. Coll. on Automata, Languages and Programming ICALP, LNCS, 1099 (1996)), 574-585 · Zbl 1045.90502 |
| [4] | Cheung, K. W., IEEE JSAC: Special Issue on Dense WDM Networks, vol. 8 (1990) |
| [5] | Erlebach, T.; Jansen, K., Scheduling of virtual connections in fast networks, (Proc. 4th Parallel Systems and Algorithms Workshop PASA ’96 (1996), World Scientific: World Scientific Singapore), 13-32 |
| [6] | Erlebach, T.; Jansen, K., Call scheduling in trees, rings and meshes, (Proc. 30th Hawaii Internat. Conf. on System Sciences HICSS-30, vol. 1 (1997)), 221-222 |
| [7] | Green, P. E., Fiber Optic Communication Networks (1992), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ |
| [8] | C. Kaklamanis, P. Persiano, Efficient wavelength routing on directed fiber trees, in: Proc. Algorithms - ESA 96, Lecture Notes in Computer Science, 1136, pp. 460-470.; C. Kaklamanis, P. Persiano, Efficient wavelength routing on directed fiber trees, in: Proc. Algorithms - ESA 96, Lecture Notes in Computer Science, 1136, pp. 460-470. · Zbl 1379.68014 |
| [9] | Kumar, V.; Schwabe, E. J., Improved access to optical bandwidth in trees, (Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms SODA (1997)), 437-444 · Zbl 1321.68388 |
| [10] | Mihail, M.; Kaklamanis, C.; Rao, S., Efficient access to optical bandwidth, (Proc. 36th IEEE Symp. on Foundations of Computer Science (1995)), 548-557 · Zbl 0938.68522 |
| [11] | Minoli, D., (Telecommunications Technology Handbook (1991), Artech House) |
| [12] | Raghavan, P.; Upfal, E., Efficient routing in all-optical networks, (Proc. 26th Ann. ACM Symp. on Theory of Computing STOC (1994)), 134-143 · Zbl 1345.90038 |
| [13] | Alexander; Bondurant; Byrne; Chan; Finn; Gallager; Glance; Haus; Humblet; Jain; Kaminiw; Karol; Kennedy; Kirby; Le; Saleh; Schofield; Shapiro; Shankar; Thomas; Williamson; Milson, A precompetitive consortium on wide-band all-optical networks, IEEE J. Lightwave Technol., 11, 5/6, 714-735 (1993) |
| [14] | Chung, G. K., ONTC-ARPA Technology Development Group, Experimental Demonstration of a Reconfigurable WDM/ATM/SONET Multiwavelength Network Testbed, (OFC Optical Fiber Conf.. OFC Optical Fiber Conf., San Jose CA (January 1993)) |
| [15] | ONTC-ARPA; Brackett; Acampora; Sweitzer; Tangonan; Smith; Lennon; Wang; Hobbs, A scalable multiwavelength multihop optical network: a proposal for research in all-optical networks, IEEE J. Lightwave Technol., 11, 5/6, 736-753 (1993) |
| [16] | Lu; Roorda; Coathup; Gruber; Ashton; Leeson; Boutilier: BNR/Northern Telecom; Bala; Brackett; Cordell; Goldstein; Goodman; Chung; Mihail; Winkler: Bellcore; Acampora; Stern; Zhang; Kovaacevic; Brown; Guo; Jagannath; Jiang, Columbia University, Final Phase I Report, 25-76 (August 1994) |
| [17] | Pankaj, R., Architectures for Linear Lightwave Networks, (Ph.D. Thesis (1992), Department of Electrical Engineering and Computer Science, MIT: Department of Electrical Engineering and Computer Science, MIT Cambridge MA) |
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.
