ABSTRACT
Contents 24.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578 24.2 Overview of Conventional RWA Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580
24.2.1 Fixed Shortest Path Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580 24.2.2 Alternate Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581
24.2.2.1 Alternate Shortest Path Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581 24.2.2.2 Fixed-Paths Least Congestion Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 582
24.2.3 Adaptive Unconstrained Routing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583 24.3 Adaptive Ant-Based Routing Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583
24.3.1 Network Model and Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583 24.3.2 New Routing Table Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584 24.3.3 Ant’s Foraging and Routing Table Updating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584
24.3.3.1 Data Collected by Ants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585 24.3.3.2 Routing Table Updating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586 24.3.3.3 Ant Movement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587
24.3.4 Smart Updating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587 24.3.5 Selection of Path and Wavelength . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587
24.4 Alternate Ant-Based Routing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589 24.4.1 Motivation of Ant-Based Alternate Routing Approach . . . . . . . . . . . . . . . . . . . . . . . . 589 24.4.2 Twin Routing Table Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589
24.4.3 Ant’s Foraging and Routing Tables Updating. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590 24.4.3.1 P-Route Table Updating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590
24.4.4 Connection Setup. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590 24.5 Numerical Results and Discussions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 591
24.5.1 Simulation Results for ABR Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593 24.5.1.1 Parameters Setting and Tuning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593 24.5.1.2 Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596
24.5.2 Simulation Results for HABR Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598 24.5.2.1 Setting of the Number of Alternate Routes . . . . . . . . . . . . . . . . . . . . . . . . . 598 24.5.2.2 Tuning Number of Ants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599 24.5.2.3 Blocking Probability Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599 24.5.2.4 Number of Required Wavelengths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601
24.6 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602 24.6.1 ABR Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602
24.6.1.1 Computation Times for Route Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602 24.6.1.2 Size of Routing Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603 24.6.1.3 Control Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604 24.6.1.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607
24.6.2 HABR Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607 24.6.2.1 Computation Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607 24.6.2.2 Routing Tables’ Size and Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 608
24.7 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 609 24.7.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 609 24.7.2 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 609
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 609
24.1 Introduction All-optical networks using wavelength-division multiplexing (WDM) technology are promising infrastructure for the future Internet [1]. In such networks, data are switched and routed in all-optical domain via lightpaths. The Routing and Wavelength Assignment (RWA) problem is one of the most important issues in optical WDM networks; it involves determining routes and wavelengths to establish lightpaths for connection requests. In optical networks without wavelength converters, the same wavelength must be assigned on every link of a lightpath; this referred to as the wavelength-continuity constraint. The RWA problem can be generally classified into two types: static and dynamic RWA. In a static RWA problem, network topology and connectionestablishing requirements are given in advance, and the problem is to find a solution that satisfies certain optimizing conditions, such as minimizing the number of wavelengths or maximizing the total number of lightpaths that can be established. A dynamic RWA problem involves the online establishment of lightpaths for connection requests that arrive dynamically. The static RWA problem is proved as a NP-hard problem [2]. The dynamic RWA problem is much more difficult to solve, therefore heuristics algorithms are usually employed to solve it.
