Abstract
We present a heuristic for solving the discrete maximum-minimum (maxmin) rates
for dense WDM- (DWDM-) based optical subnetworks. Discrete maxmin allocation is
proposed here 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 (NP is the class that a nondeterministic Turing machine
accepts in polynomial time). The heuristic proposed here is tested against all
possible networks such that |Γ + Ω| ≤ 10, where Γ and Ω
are the set of links and the set of flows of the network, respectively. From
1,084,112 possible networks, the heuristic produces the exact lexicographic
solutions with 99.8% probability. Furthermore, for 0.2% cases in which the solutions
are nonoptimal, 99.8% of these solutions are within the minimal possible distance
from the true lexicographic optimal solutions.
© 2002 Optical Society of America
PDF Article
More Like This
Cited By
You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.
Contact your librarian or system administrator
or
Login to access Optica Member Subscription