Abstract
In optical networks regenerators have to be placed on lightpaths in order to regenerate the signal. In addition, grooming enables the use of the same regenerator by several lightpaths. In this work we consider the problem of minimizing the number of regenerators used in traffic grooming in optical networks. We deal with the case in which a regenerator has to be placed at every internal node of each lightpath. Up to g (the grooming factor) lightpaths can use the same regenerator. Starting from the 4-approximation algorithm of [7] that solves this problem for a path topology, we provide an approximation algorithm with the same approximation ratio for the ring and tree topologies. We present also a technique based on matching that leads to the same approximation ratio in tree topology and can be used to obtain approximation algorithms in other topologies. We provide an approximation algorithm for general topology that uses this technique.
This work was partially supported by the Israel Science Foundation grant No. 1249/08, by British Council Grant UKTELHAI09, and by the PRIN 2008 research project COGENT (COmputational and GamE-theoretic aspects of uncoordinated NeTworks), funded by the Italian Ministry of University and Research.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Chen, S., Ljubic, I., Raghavan, S.: The regenerator location problem. Networks 55(3), 205–220 (2010)
Dor, D., Tarsi, M.: Graph decomposition is np-complete: A complete proof of holyer’s conjecture. SIAM Journal on Computing 26(4), 1166–1187 (1997)
Edmonds, J.: Paths, trees, and flowers. Canad. J. Math. 17, 449–467 (1965)
Fedrizzi, R., Galimberti, G.M., Gerstel, O., Martinelli, G., Salvadori, E., Saradhi, C.V., Tanzi, A., Zanardi, A.: A Framework for Regenerator Site Selection Based on Multiple Paths. In: Prooceedings of IEEE/OSA Conference on Optical Fiber Communications (OFC) (to appear, 2010)
Fedrizzi, R., Galimberti, G.M., Gerstel, O., Martinelli, G., Salvadori, E., Saradhi, C.V., Tanzi, A., Zanardi, A.: Traffic Independent Heuristics for Regenerator Site Selection for Providing Any-to-Any Optical Connectivity. In: Proceedings of IEEE/OSA Conference on Optical Fiber Communications (OFC) (to appear, 2010)
Flammini, M., Marchetti-Spaccamela, A., Monaco, G., Moscardelli, L., Zaks, S.: On the complexity of the regenerator placement problem in optical networks. IEEE/ACM Transactions on Networking (to appear, 2010)
Flammini, M., Monaco, G., Moscardelli, L., Shachnai, H., Shalom, M., Tamir, T., Zaks, S.: Minimizing total busy time in parallel scheduling with application to optical networks. Theoretical Computer Science 411(40-42), 3553–3562 (2010)
Flammini, M., Monaco, G., Moscardelli, L., Shalom, M., Zaks, S.: Approximating the traffic grooming problem with respect to adms and oadms. In: Luque, E., Margalef, T., Benítez, D. (eds.) Euro-Par 2008. LNCS, vol. 5168, pp. 920–929. Springer, Heidelberg (2008)
Flammini, M., Monaco, G., Moscardelli, L., Shalom, M., Zaks, S.: Optimizing regenerator cost in traffic grooming. Technical report, Faculty of Computer Science, Technion (September 2010), http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2010/CS/CS-2010-16
Kim, S.W., Seo, S.W.: Regenerator placement algorithms for connection establishment in all-optical networks. IEE Proceedings Communications 148(1), 25–30 (2001)
Mertzios, G.B., Sau, I., Shalom, M., Zaks, S.: Placing regenerator in optical networks: New model, hardness results and algorithms. In: Gavoille, C. (ed.) ICALP 2010, Part II. LNCS, vol. 6199, pp. 333–344. Springer, Heidelberg (2010)
Pachnicke, S., Paschenda, T., Krummrich, P.M.: Physical Impairment Based Regenerator Placement and Routing in Translucent Optical Networks. In: Optical Fiber Communication Conference and Exposition and The National Fiber Optic Engineers Conference (Optical Society of America, paper OWA2) (2008)
Sriram, K., Griffith, D., Su, R., Golmie, N.: Static vs. dynamic regenerator assignment in optical switches: models and cost trade-offs. In: Workshop on High Performance Switching and Routing (HPSR), pp. 151–155 (2004)
Winkler, P., Zhang, L.: Wavelength assignment and generalized interval graph coloring. In: SODA, pp. 830–831 (2003)
Yang, X., Ramamurthy, B.: Dynamic routing in translucent WDM optical networks. In: Proceedings of the IEEE International Conference on Communications (ICC), pp. 955–971 (2002)
Yang, X., Ramamurthy, B.: Sparse Regeneration in Translucent Wavelength-Routed Optical Networks: Architecture, Network Design and Wavelength Routing. Photonic Network Communications 10(1), 39–53 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Flammini, M., Monaco, G., Moscardelli, L., Shalom, M., Zaks, S. (2010). Optimizing Regenerator Cost in Traffic Grooming. In: Lu, C., Masuzawa, T., Mosbah, M. (eds) Principles of Distributed Systems. OPODIS 2010. Lecture Notes in Computer Science, vol 6490. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17653-1_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-17653-1_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17652-4
Online ISBN: 978-3-642-17653-1
eBook Packages: Computer ScienceComputer Science (R0)