Vol 4 No 2 (2009)
Articles

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

Jérôme Palaysi
LIRMM, Univ. Montpellier 2, CNRS
Olivier Cogis
LIRMM, Univ. Montpellier 2, CNRS
Guillaume Bagan
LIRMM, Univ. Montpellier 2, CNRS
Published September 16, 2009
Keywords
  • minimum load routing,
  • minimum path colouring,
  • all-optical networks,
  • mesh,
  • 1-turn-routing,
  • approximation algorithms
  • ...More
    Less
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

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.