In this paper the multiple routing path problem in wide area Wavelength Division Multiplexing (WDM) networks is considered, which is to find K edge-disjoint lightpaths/semi-lightpaths from a source to a destination such that the K paths meet some specified optimization objectives if they exist. Two versions of the problem are studied One is to minimize the total cost of the K paths. Another is to minimize the cost of the maximum cost path among the K paths. An efficient algorithm for the first version is proposed, which takes O (kK (kn + m + n log(kn))) time and delivers an exact solution, where n, m, and k are the number of nodes, links and wavelengths in the network. The second version of the problem is shown to be NP-hard, and an approximate algorithm for it is devised, delivering an approximate solution that is K times the optimum, where K ≥ 2.
展开▼
机译：本文考虑了广域波分复用（WDM）网络中的多路由路径问题，该问题是查找从源到目的地的K条边缘不相交的光路/半光路，以使K条路径满足某些指定的优化目标如果存在。研究了该问题的两种版本，一种是使K条路径的总成本最小化。另一个是使K条路径中最大成本路径的成本最小化。针对第一个版本，提出了一种有效的算法，该算法花费O（kK（kn + m + n log（kn）））时间并提供精确的解决方案，其中n，m和k是节点，链路和波长的数量在网络中。问题的第二个版本显示为NP难解的，并为此设计了一种近似算法，提供的近似解是最优值的K倍，其中K≥2。
展开▼
