본문 바로가기
  • Home

Independent Set Bin Packing Algorithm for Routing and Wavelength Assignment (RWA) Problem

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2015, 20(1), pp.111-118
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Sang-Un, Lee 1

1강릉원주대학교

Accredited

ABSTRACT

This paper deals with the routing and wavelength assignment problem (RWAP) that decides the bestlightpaths for multiple packet demands for   in optical communication and assigns the minimum numberof wavelengths to given lightpaths. There has been unknown of polynomial-time algorithm to obtain theoptimal solution for RWAP. Hence, the RWAP is classified as NP-complete problem and one can obtain theapproximate solution in polynomial-time. This paper decides the shortest main and alternate lightpath withsame hop count for all    for given network in advance. When the actual demands of communication forparticular multiple packet for  , we decrease the maximum utilized edge into  utilized number usingthese dual-paths. Then, we put these    into -wavelength bins without duplicated edge. This algorithmcan be get the optimal solution within  computational complexity. For two experimental data, the proposed algorithm shows that can be obtain the known optimal solution.

Citation status

* References for papers published after 2022 are currently being built.