Ondashline routing in all-optical networks Export

@article{citeulike:4177211, abstract = {The paper deals with ondashline routing in wavelength division multiplexing (WDM) optical networks. A sequence of requests arrives over time, each is a pair of nodes to be connected by a path. The problem is to assign a wavelength and a path to each pair, so that no two paths sharing a link are assigned the same wavelength. The goal is to minimize the number of wavelengths used to establish all connections. Raghavan and Upfal (Proc. 26th Annual Symp. on Theory of Computing, 1994, pp. 133–143) considered the off-line version of the problem, which was further studied in Aumann and Rabani (Proc. 6th ACM-SIAM Symp. on Discrete Algorithms, 1995, pp. 567–576), Kaklamanis and Persiano (Proc. 4th Annual European Symp. on Algorithms, Lecture Notes in Computer Science, vol. 1136, Springer, Berlin, 1996, pp. 460–470), Mihail et al. (Proc. 36th IEEE Annual Symp. on Foundations of Computer Science, 1995, pp. 548–557), Rabani, (Proc. 37th Annual Symp. on Foundations of Computer Science, 1996, pp. 400–409). For a line topology, the problem is the well-studied interval graph coloring problem. Ondashline algorithms for this problem have been analyzed in Kierstead and Trotter (Congr. Numer. 33 (1981) 143–153). We consider trees, trees of rings, and meshes topologies, previously studied in the off-line case. We give ondashline algorithms with competitive ratio O ( log n ) for all these topologies. We give a matching Ω( log n ) lower bound for meshes. We also prove that any algorithm for trees cannot have competitive ratio better than Ω( log n / log log n ). We also consider the problem where every edge is associated with parallel links. While in WDM technology, a fiber link requires different wavelengths for every transmission, space division multiplexing technology allows parallel links for a single wavelength, at an additional cost. Thus, it may be beneficial in terms of network economics to combine between the two technologies (this is indeed done in practice). For arbitrary networks with Ω( log n ) parallel links we give an ondashline algorithm with competitive ratio O ( log n ).}, author = {Bartal, Y.}, citeulike-article-id = {4177211}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/S0304-3975(99)00025-0}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S0304-3975(99)00025-0}, day = {28}, doi = {10.1016/S0304-3975(99)00025-0}, issn = {03043975}, journal = {Theoretical Computer Science}, keywords = {oblivious}, month = {June}, number = {1-2}, pages = {19--39}, posted-at = {2009-03-15 02:46:41}, priority = {2}, title = {Ondashline routing in all-optical networks}, url = {http://dx.doi.org/10.1016/S0304-3975(99)00025-0}, volume = {221}, year = {1999} }

TY - JOUR ID - citeulike:4177211 L3 - citeulike-article-id:4177211 N2 - The paper deals with ondashline routing in wavelength division multiplexing (WDM) optical networks. A sequence of requests arrives over time, each is a pair of nodes to be connected by a path. The problem is to assign a wavelength and a path to each pair, so that no two paths sharing a link are assigned the same wavelength. The goal is to minimize the number of wavelengths used to establish all connections. Raghavan and Upfal (Proc. 26th Annual Symp. on Theory of Computing, 1994, pp. 133–143) considered the off-line version of the problem, which was further studied in Aumann and Rabani (Proc. 6th ACM-SIAM Symp. on Discrete Algorithms, 1995, pp. 567–576), Kaklamanis and Persiano (Proc. 4th Annual European Symp. on Algorithms, Lecture Notes in Computer Science, vol. 1136, Springer, Berlin, 1996, pp. 460–470), Mihail et al. (Proc. 36th IEEE Annual Symp. on Foundations of Computer Science, 1995, pp. 548–557), Rabani, (Proc. 37th Annual Symp. on Foundations of Computer Science, 1996, pp. 400–409). For a line topology, the problem is the well-studied interval graph coloring problem. Ondashline algorithms for this problem have been analyzed in Kierstead and Trotter (Congr. Numer. 33 (1981) 143–153). We consider trees, trees of rings, and meshes topologies, previously studied in the off-line case. We give ondashline algorithms with competitive ratio O ( log n ) for all these topologies. We give a matching Ω( log n ) lower bound for meshes. We also prove that any algorithm for trees cannot have competitive ratio better than Ω( log n / log log n ). We also consider the problem where every edge is associated with parallel links. While in WDM technology, a fiber link requires different wavelengths for every transmission, space division multiplexing technology allows parallel links for a single wavelength, at an additional cost. Thus, it may be beneficial in terms of network economics to combine between the two technologies (this is indeed done in practice). For arbitrary networks with Ω( log n ) parallel links we give an ondashline algorithm with competitive ratio O ( log n ). IS - 1-2 JF - Theoretical Computer Science SN - 03043975 EP - 39 TI - Ondashline routing in all-optical networks VL - 221 SP - 19 KW - oblivious AU - Bartal, Y PY - 1999/06/28/ UR - http://dx.doi.org/10.1016/S0304-3975(99)00025-0 ER -