NDLI: Placing regenerators in optical networks to satisfy multiple sets of requests

Content Provider	ACM Digital Library
Author	Zaks, Shmuel Shalom, Mordechai Mertzios, George B. Sau, Ignasi
Copyright Year	2013
Abstract	The placement of regenerators in optical networks has become an active area of research during the last few years. Given a set of lightpaths in a network $\textit{G}$ and a positive integer $\textit{d},$ regenerators must be placed in such a way that in any lightpath there are no more than $\textit{d}$ hops without meeting a regenerator. The cost function we consider is given by the total number of regenerators placed at the nodes, which we believe to be a more accurate estimation of the real cost of the network than the number of locations considered in the work of Flammini et al. (IEEE/ACM Trans. Netw., vol. 19, no. 2, pp. 498-511, Apr. 2011). Furthermore, in our model we assume that we are given a finite set of $\textit{p}$ possible traffic patterns (each given by a set of lightpaths), and our objective is to place the minimum number of regenerators at the nodes so that each of the traffic patterns is satisfied. While this problem can be easily solved when $\textit{d}$ = 1 or $\textit{p}$ = 1, we prove that for any fixed d, p ≥ 2, it does not admit a PTAS, even if $\textit{G}$ has maximum degree at most 3 and the lightpaths have length $\textit{O(d)}.$ We complement this hardness result with a constant-factor approximation algorithm with ratio $(\textit{dċp}).$ We then study the case where $\textit{G}$ is a path, proving that the problem is polynomial-time solvable for two particular families of instances. Finally, we generalize our model in two natural directions, which allows us to capture the model of Flammini et al. as a particular case, and we settle some questions that were left open therein.
Starting Page	1870
Ending Page	1879
Page Count	10
File Format	PDF
ISSN	10636692
DOI	10.1109/TNET.2012.2186462
Volume Number	20
Issue Number	6
Journal	IEEE/ACM Transactions on Networking (TON)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-12-01
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Approximation algorithms Hardness of approximation Optical networks Overprovisioning Regenerators
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering Computer Networks and Communications Software Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests

On the complexity of the regenerator placement problem in optical networks

Complexity of wavelength assignment in optical network optimization

On the Complexity of the Regenerator Placement Problem in Optical Networks

On New Approaches of Assessing Network Vulnerability: Hardness and Approximation

Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests (2010)

Approximation algorithms for many-to-many traffic grooming in optical WDM networks

Approximation Algorithms for Many-to-Many Traffic Grooming in Optical WDM Networks

Placing regenerators in optical networks to satisfy multiple sets of requests (2012).

Placing regenerators in optical networks to satisfy multiple sets of requests

Similar Documents

Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests

On the complexity of the regenerator placement problem in optical networks

Complexity of wavelength assignment in optical network optimization

On the Complexity of the Regenerator Placement Problem in Optical Networks

On New Approaches of Assessing Network Vulnerability: Hardness and Approximation

Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests (2010)

Approximation algorithms for many-to-many traffic grooming in optical WDM networks

Approximation Algorithms for Many-to-Many Traffic Grooming in Optical WDM Networks

Placing regenerators in optical networks to satisfy multiple sets of requests (2012).

Placing regenerators in optical networks to satisfy multiple sets of requests