Maxmin lambda allocation for DWDM networks

This paper presents a heuristic for solving the discrete maxmin rates for DWDM-based optical subnetworks. Discrete maxmin allocation is proposed as the preferred way of assigning wavelengths to the flows found to be suitable for lightpath switching. The discrete maxmin optimality condition is shown to be a unifying principle underlying both the continuous maxmin and discrete maxmin optimality conditions. Among the many discrete maxmin solutions for each assignment problem, lexicographic optimal solutions can be argued to be the best in the true sense of "maxmin." However, the problem of finding lexicographic optimal solutions is known to be NP-complete. The heuristic proposed is tested against all possible networks such that |/spl Gamma/|+|/spl Omega/|/spl les/10, where /spl Gamma/ and /spl Omega/ are the set of links and the set of flows of the network, respectively. Out of 1,084,112 possible networks, the heuristic produces the exact lexicographic solutions with 99.8% probability. Furthermore, for 0.2% cases where the solutions are non-optimal, 99.8% of these solutions are within the minimal possible distance from the true lexicographic optimal solutions.