Error message

  • Warning: Illegal string offset 'tokenized' in addtocal_field_get_value() (line 362 of /var/www/drupal/sites/all/modules/addtocal/addtocal.module).
  • Warning: Illegal string offset 'tokenized' in addtocal_field_get_value() (line 400 of /var/www/drupal/sites/all/modules/addtocal/addtocal.module).
  • Warning: Illegal string offset 'tokenized' in addtocal_field_get_value() (line 362 of /var/www/drupal/sites/all/modules/addtocal/addtocal.module).
  • Warning: Illegal string offset 'tokenized' in addtocal_field_get_value() (line 400 of /var/www/drupal/sites/all/modules/addtocal/addtocal.module).
Home > Node > Optimizing the use of regenerators in optical networks
Optimizing the use of regenerators in optical networks
20 December 2011 - 12:30pm
Ponente(s): 
Professor Shmuel Zaks, Department of Computer Science, Technion, Haifa, Israel
Lugar: 

Room 4.1.F03, Torres Quevedo Building, University Carlos III of Madrid, Avda. Universidad, 30, 28911 Leganes – Madrid

Organización: 
NETCOM Research Group (Telematics Department, University Carlos III of Madrid, Spain); Institute IMDEA Networks (Madrid, Spain)

The placement of regenerators in optical networks has become an active area of research during the last years. Given a set of lightpaths in a network G and a positive integer d, regenerators must be placed in such a way that in any lightpath there are no more than d hops without meeting a regenerator. In the talk I present a few optimization problems that arise within this framework. This is done by considering two cases: a. The cost function is the total number of regenerators placed at the nodes. In addition, we are given set of p possible traffic patterns (each given by a set of lightpaths), and our objective is to place the regenerators at the nodes so that each of the traffic patterns is satisfied separately. We prove that the problem is hard to approximate (it does not admit a PTAS) for any fixed d,p > 1, and show a constant-factor approximation algorithm with ratio ln(d p). These results are from G. Mertzios, I. Sau, M. Shalom and S. Zaks, Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests, ICALP 2010. b. The cost function is the total number of nodes in which the regenerators are placed. In addition, up to g lightpath on any given edge can get the same color (this notion is known as traffic grooming). When the network topology is a path, this problem can be viewed as a scheduling problem: jobs with given start and end times have to be assigned to machines, so that each machine can serve at most g jobs at any given time, and such that the total busy time of the machines is minimized. We present a 4-approximation algorithm for an arbitrary set of lightpaths, and better ratios for some special cases. These results are from M. Flammini, G. Monaco, L. Moscardelli, H. Shachnai, M. Shalom, T. Tamir and S. Zaks, Minimizing Total Busy Time in Parallel Scheduling with Application to Optical Networks, Theoretical Computer Science, 2010.

Who is Shmuel Zaks?
Shmuel Zaks received his BSc (cum laude) and MSc degrees in Mathematics from the Technion, Haifa, Israel, in 1971 and 1972, respectively, and his PhD degree in Computer Science from the University of Illinois at Urbana-Champaign in 1979. He is a Professor in the Department of Computer Science at the Technion, Haifa, Israel, and is the incumbent of the Joan Callner-Miller Chair in Computer Science. Professor Zaks is the author of over 150 journal and conference publications. His research areas include Distributed Computing, Graph and Combinatorial Algorithms, Discrete Mathematics, and Theory of Networking (especially Optical Networks).

Related publications:
Document PDF Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests (201 Kb)
Document PDF Minimizing Total Busy Time in Parallel Scheduling with Application to Optical Networks (150 Kb)