On the complexity of the regenerator placement problem in optical networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of the regenerator placement problem in optical networks

Full text

Pdf (423 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures table of contents

Calgary, AB, Canada

SESSION: Graph labeling/coloring table of contents

Pages 154-162

Year of Publication: 2009

ISBN:978-1-60558-606-9

Authors

Michele Flammini	University of L'Aquila, L'Aquila, Italy
Alberto Marchetti Spaccamela	University of Rome, Rome, Italy
Gianpiero Monaco	University of L'Aquila, l'Aquila, Italy
Luca Moscardelli	University of Chieti-Pescara, Pescara, Italy
Shmuel Zaks	Technion, Haifa, Israel

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 30, Downloads (12 Months): 64, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1583991.1584035 What is a DOI?

ABSTRACT

Placement of regenerators in optical networks has attracted the attention of recent research works in optical networks. In this problem we are given a network, with an underlying topology of a graph G, and with a set of requests that correspond to paths in G. There is a need to put a regenerator every certain distance, because of a decrease in the power of the signal. In this work we investigate the problem of minimizing the number of locations to place the regenerators. We present analytical results regarding the complexity of this problem, in four cases, depending on whether or not there is a bound on the number of regenerators at each node, and depending on whether or not the routing is given or only the requests are given (and part of the solution is also to determine the actual routing). These results include polynomial time algorithms, NP-complete results, approximation algorithms, and inapproximability results.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Giorgio Ausiello , M. Protasi , A. Marchetti-Spaccamela , G. Gambosi , P. Crescenzi , V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
	2	C. A. Brackett, A. S. Acampora, J. Sweitzer, G. Tangonan, M. T. Smith, W. Lennon, K.-C. Wang, R.H. Hobbs. A scalable multiwavelength multihop optical network: a proposal forresearch on all-optical networks. Journal of Lightwave Technology, 11(5), pp. 736--753, 1993.
	3	Ioannis Caragiannis , Christos Kaklamanis , Panagiotis Kanellopoulos, Energy-Efficient Wireless Network Design, Theory of Computing Systems, v.39 n.5, p.593-617, September 2006 [doi>10.1007/s00224-005-1204-8]
	4	S. Chen and S. Raghavan. The Regenerator Location Problem. In Proceedings of the International Network Optimization Conference (INOC 2007).
	5	V. Chvatal. A greedy heuristic for the set-covering problem. Math. Oper. Res., 4(3), pp. 233--235, 1979.
	6	T. Erlebach and S. Stefanakos. Wavelength Conversion in All-Optical Networks with Shortest-Path Routing. Algorithmica, 43(1--2), pp. 43--61, 2005.
	7	Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
	8	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	9	Sudipto Guha , Samir Khuller, Improved methods for approximating node weighted Steiner trees and connected dominating sets, Information and Computation, v.150 n.1, p.57-74, April 10, 1999 [doi>10.1006/inco.1998.2754]
	10	Jon Kleinberg , Amit Kumar, Wavelength conversion in optical networks, Journal of Algorithms, v.38 n.1, p.25-50, Jan. 2001 [doi>10.1006/jagm.2000.1137]
	11	S. W. Kim and S. W. Seo. Regenerator placement algorithms for connection establishment in all-optical networks. IEEE Proceedings Communications, 148(1), pp. 25--30, 2001.
	12	S. Pachnicke, T. Paschenda and P. M. Krummrich. Physical Impairment Based Regenerator Placement and Routing in Translucent Optical Networks. Proceedings of the Optical Fiber communication/National Fiber Optic Engineers Conference,(OFC/NFOEC 2008), pp. 1--3, 2008.
	13	B. Ramamurthy, H. Feng, D. Datta, J. P. Heritage and B. Mukherjee. Transparent vs. opaque vs. translucent wavelength-routed optical networks. Proceedings of the Optical Fiber Communication Conference and the International Conference on Integrated Optics and Optical Fiber Communication, (OFC/IOOC 99), pp. 59--61, 1999.
	14	C. V. Saradhi and S. Zaks. Placement of regenerators in optical networks. In preparation.
	15	K. Sriram, D. Griffith, R. Su and N. Golmie. Static vs. dynamic regenerator assignment in optical switches: models and cost trade-offs. Proceedings of the Workshop on High Performance Switching and Routing, (HPSR 2004), pp. 151--155, 2004.
	16	Gordon Wilfong , Peter Winkler, Ring routing and wavelength translation, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.333-341, January 25-27, 1998, San Francisco, California, United States
	17	X. Yang and B. Ramamurthyn. Sparse Regeneration in Translucent Wavelength-Routed Optical Networks: Architecture, Network Design and Wavelength Routing. Photonic Network Communications, 10(1), pp. 39--53, 2005.
	18	X. Yang and B. Ramamurthy. Dynamic routing in translucent WDM optical networks. Proceedings of the IEEE International Conference on Communications (ICC 2002),pp. 2796--2802, 2002.