Abstract:
We propose to use a layered graph approach, which has been previously proposed for unicasting, to have a more general, realistic and flexible model of an all-optical multifiber network for multicasting. This new presentation enables us to state the problem of all-optical multicasting with sparse light splitting and wavelength conversion restrictions so that it is formulated as an original Mixed Integer Linear Programming (MILP). The MILP formulation is solved by CPLEX which finds the optimal solution within a given precision and it also gives a lower bound by relaxing the integrality constraints. However, it is possible to solve MILP problems to optimality only for small networks and number of sessions, since the problem is NP-hard. Therefore, we also propose three different heuristics (LAMA, SLAM and C-FWA) for larger problems and dynamic multicasting requests. Extensive computational experiments demonstrate that LAMA and SLAM perform close to the optimal and better than their competitor (M-ONLY) for all metrics. However, LAMA and SLAM work better than their alternatives, since we jointly optimize routing and fiber-wavelength assignment phases compared to the other candidates which attack to the problem by decomposing two phases. Experiments show that important metrics are adversely affected by the separation of routing and fiber wavelength assignment. SLAM, which is the scalable version of LAMA, performs close or better to LAMA. Finally, we also propose a new fiber wavelength assignment strategy (Ex-Fit in C-FWA) which uses wavelength and fiber conversion resources more effectively than the First Fit.
