This paper considers the combined problem of finding allocation ofwavelengths to the stations (configuration) and finding the associatedrouting of the traffic to minimize congestion (the amount of maximumflow on any link). This work presents efficient algorithms for computingboth upper and lower bounds on the congestion. The upper bounds-toobtain approximate solutions of this problem-are based modification oftwo heuristics (i) variable depth local search, and (ii) simulatedannealing. A more significant contribution is a lower bound computationbased on building flow trees to find a lower bound on the total flow,and then distributing the total flow over the links provide a lowerbound on the congestion. This technique yields a tool which can be usedin evaluating the quality of heuristic algorithms, and determining atermination criteria during minimization. This technique can be appliedto other problems with flow-based objectives. Performance of theheuristics is analysed, and compared via simulation studies. It is shownthat the heuristics perform on the average, within 20% of the computedlower bound, and 15% better than the previous methods to solve thisproblem
展开▼
