Performance evaluation of heuristic algorithms for routing and wavelength assignment in WDM optical networks

Abstract

We evaluate the average-case performance of eight offline heuristic algorithms to solve the routing and wavelength assignment (RWA) problem and the related throughput maximisation (TM) problem in wavelength division multiplexing optical networks. These algorithms are first-fit-decreasing (FFD), first-fit-increasing (FFI), best-fit-decreasing (BFD), best-fit-increasing (BFI), densest-fit-decreasing (DFD), densest-fit-increasing (DFI), random-fit-decreasing (RFD) and random-fit-increasing (RFI). Our experimental performance evaluation is conducted by extensive simulations on a wide range of WDM optical networks, including a mesh network, four real networks and three types of random networks. We find offline RWA algorithms and TM algorithms which perform better than previously studied online algorithms, namely, first-fit (FF), best-fit (BF), densest-fit (DF) and random-fit (RF). In particular, algorithm FFD (BFD, DFD and RFD, respectively) has better performance than algorithm FF (BF, DF and RF, respectively) for RWA, and algorithm FFI (BFI, DFI and RFI, respectively) has better performance than algorithm FF (BF, DF and RF, respectively) for TM.

Keywords:

• average-case performance
• heuristic algorithm
• optical network
• routing
• throughput maximisation
• wavelength assignment
• wavelength division multiplexing

Acknowledgement

Two anonymous reviewers are acknowledged for their constructive comments on improving the presentation of the paper.