Chinese Journal of Computers   Full Text
  TitleA Scheduling Algorithm on Symmetric Fiber Trees with Tunable ADMs
  AuthorsZHOU Feng-Feng1),2) XU Yin-Long1),2) CHEN Guo-Liang1),2)
  Address1)(Department of Computer Science & Technology, University of Science & Technology of China, Hefei 230027)
2)(National High Performance Computing Center at Hefei, Hefei 230027)
  Year2005
  IssueNo.5(774781)
  Abstract &
  Background
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.1Opt+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.1Opt+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.1Opt+0.8+L)/Opt, where L is the load of the request set on the tree.

keywords all-optical networks wavelength division multiplexing(WDM) tunable add/drop multiplexer scheduling approximation ratio

background The project mainly focuses on the designing and analyzing of the algorithms for the combinatorial optimization problems in all optical networks, etc. This group is interested in the routing and wavelength assignment problems, the scheduling problems, and the MAC-layer protocol designing in all optical networks. They have published more than ten research papers in the domestic and foreign peer-reviewed journals and conferences. This paper considered the job scheduling problem on the directed fiber trees with one tunable ADMs per node, which is important in the theory and the practice.