|
Abstract: |
In this paper we introduce and motivate the static multicast advance reservation (MCAR) problem
for all-optical wavelength-routed WDM networks. Under the advanced reservation traffic model, connection requests
specify their start time to be some time in the future and also specify their holding times.
We investigate the static MCAR problem where the set of advance reservation requests is known ahead of time.
We show the problem is NP-complete, formulate the problem mathematically as an integer linear program,
and develop three efficient heuristics, seqRWA, ISH, and SA, to solve the problem for practical size networks. We also introduce a theoretical lower bound
on the number of wavelengths required. To evaluate our heuristics we compare the results
to the ILP for small networks and run simulations over real-world, large scale networks. We find
the SA heuristic provides close to optimal results compared to the ILP for our smaller
networks, and up to a 33% improvement over seqRWA and up to a 22% improvement
over ISH on realistic networks. SA provides, on average, solutions 1.5-1.8x times the
cost given by our conservative lower bound on large networks. |
