Approximable 1-Turn Routing Problems in All-Optical Mesh Networks

Authors

  • Jérôme Palaysi LIRMM, Univ. Montpellier 2, CNRS
  • Olivier Cogis LIRMM, Univ. Montpellier 2, CNRS
  • Guillaume Bagan LIRMM, Univ. Montpellier 2, CNRS

Keywords:

minimum load routing, minimum path colouring, all-optical networks, mesh, 1-turn-routing, approximation algorithms

Abstract

In all-optical networks, several communications can be transmitted through the same fiber link provided that they use different wavelengths. The MINIMUM ALL-OPTICAL ROUTING problem (given a list of pairs of nodes standing for as many point to point communication requests, assign to each request a route along with a wavelength so as to minimize the overall number of assigned wavelengths) has been paid a lot of attention and is known to be N P–hard. Rings, trees and meshes have thus been investigated as specific networks, but leading to just as many N P–hard problems. This paper investigates 1-turn routings in meshes (paths are allowed one turn only). We first show the MINIMUM LOAD 1-TURN ROUTING problem to be N P–hard but 2-APX (more generally, the MINIMUM LOAD k-CHOICES ROUTING problem is N P–hard but k-APX), then that the MINIMUM 1-TURN PATHS COLOURING problem is 4-APX (more generally, any d-segmentable routing of load L in a hypermesh of dimension d can be coloured with 2d(L−1)+1 colours at most). >From there, we prove the MINIMUM ALL-OPTICAL 1-TURN ROUTING problem to be APX.

Downloads

Published

2009-09-16

How to Cite

Palaysi, J., Cogis, O., & Bagan, G. (2009). Approximable 1-Turn Routing Problems in All-Optical Mesh Networks. Algorithmic Operations Research, 4(2), Pages 95 – 101. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/4177

Issue

Vol. 4 No. 2 (2009)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.