使用可调ADM的对称全光树网上的调度算法

A Scheduling Algorithm on Symmetric Fiber Trees with Tunable ADMs

波分复用技术可以显著提高光传输网络的带宽,是未来主干网的核心技术之一.工作波长可调节的加载/下载复用器(ADM)是实现该技术的主要光学器件之一,研究使用可调ADM的全光网络上的任务调度问题具有重要的理论和应用价值.该文研究了在每个节点放置一个可调ADM的对称全光树网上的任务调度问题,首先证明了它是NP完全的,接着给出了星形网络上的近似算法及其性能分析.最后,将一般树网上任务调度问题规约为星形网络上相同的问题,得到了一个2×(1.1×Opt+0.8+L)/Opt近似算法.

This paper studies the scheduling problem on directed fiber trees with one tunable ADM per node, which is important in the theory and the practice. First, the scheduling problem is reduced to a special case of the edge coloring problem on an undirected graph. Since the edge coloring problem on an undirected graph is NP-complete, the scheduling problem is also NP-complete. Then the special case on the all optical star networks is reduced to the edge coloring problem on an undirected graph, and an 1.1×Opt+0.8 approximation algorithm is got, where Opt is the optimal result. For the case on a general tree network, the scheduling problem of the requests that pass through, arrive at, or leave from the root node of the tree is reduced to the special case on the star networks, and an 1.1×Opt+0.8 approximation algorithm is also got. The other nodes are then processed recursively. The performance is proved to be no worse than 2×(1.1×Opt+0.8+L)/Opt, where L is the load of the request set on the tree.