A Practical RWA Algorithm Based on Lookup Table for Edge Disjoint Paths

Springer-Verlag Lecture Notes in Computer Science, vol. 2713, pp. 138-147, Jun. 2003 (SCI)

Myung Hee Kim, Hyunseung Choo, Byung Ho Yae, and JongHyun Lee


Routing and wavelength assignment (RWA) problem is an important issue in optical transport networks based on wavelength division multiplexing (WDM) technique. It is typically solved using a combination of linear programming and graph coloring, or path selection based graph algorithms. Such methods are either complex or make extensive use of heuristics. In this paper we propose a novel and efficient approach which basically obtains the maximum edge disjoint paths (EDPs) for each source-destination demand pair. And those EDPs obtained are stored in Lookup Table and used for the update of weight matrix. Routes are determined in order by the weight matrix for the demand set. The comprehensive computer simulation shows that the proposed algorithm uses similar or fewer number of wavelengths with significantly less execution time than bounded greedy approach (BGA) for EDP [2] which is currently known to be effective in practice.





View Full Text