Diverse routing in optical mesh networks

作者：Hu JQ^*

来源：IEEE Transactions on Communications, 2003, 51(3): 489-494.

DOI：10.1109/TCOMM.2003.809779

• communication system routing
• complexity theory
• optical fiber communication
• protection
• wavelength division multiplexing (WDM)

In this paper, we study the diverse routing problem in optical mesh networks. We use a general framework based on shared risk link groups to model the problem. We prove that the diverse routing problem is indeed NP-complete, a result that has been conjectured by several researchers previously. In fact, we show that even the fiber-span-disjoint paths problem, a special case of the diverse routing problem, is also NP-complete. We then develop an integer linear programming formulation and show through numerical results that it is a very viable method to solve the diverse routing problem for most optical networks found in many applications which typically have no more than a few hundred nodes and fiber spans.

• 出版日期2003-3