19.5 Solution Considerations

The light trail design is a challenging problem for the following reasons.

First, in order to use a wavelength fully, one would like to groom near full-wavelength capacity traffic onto the wavelength. This is similar to a normal traffic grooming problem, which is often formulated as a knapsack problem and is known to be an NP-complete problem. However, it might be infeasible to simply set up a light trail for any set of traffic requests that add up to C. For example, given that d ₁₂ + d ₁₃ + d ₁₆ = C, it might not be possible to establish the desired light trail due to the physical hop-length constraint. As a matter of fact, the light trail hop-length limit introduces complexity to the problem.

Secondly, the ILP formulation of the light trail design problem is similar to the bin packing problem [157], which is an NP-hard problem. However, if light trails are treated as the bins and elements in the given traffic matrix as the items in the bin packing problem, this problem differs from a normal bin packing problem due to a potential physical route constraint that an item cannot be put in any of the given bins, but only a subset of the bins. More specifically, an s-d pair can be assigned to the routes that satisfy: (i) nodes s and t belong to the route and (ii) node s