Optimization algorythms for WDM optical networks

随着带宽密集型网络应用的巨大增长，对数据网络上的带宽的需求也在迅速增加。波分复用（WDM）光网络提供了满足信息网络需求的有前途的基础设施，并已被广泛用作因特网、城域网和大容量局域网中的骨干网。WDM网络的方法和技术已成为学术界和工业界的重点研究领域。为了在WDM网络上实现通信应用，需要算法来决定用于路由的光路，以及在应用中复用低速率业务需求以共享光路。WDM网络研究的一个总体目标是确定实现给定连通性所需的资源，作为网络规模和网络节点功能的函数。基本的优化问题，为这个目标是最小化的资源，实现一个给定的通信应用程序，并最大限度地提高网络的性能受到给定的资源。这些优化问题的最优解通常是NP难的。以往的求解算法大多是基于整数线性规划或自组织规划，解的质量不能得到保证。如何设计出能保证问题解质量的算法是一个非常重要但又具有挑战性的问题。在这个项目中，我们使用新的方法来开发有效的算法，保证性能的优化问题。一种新的方法是探索树/分支分解为基础的算法。我们希望开发出高效的算法，为目标优化问题提供更好的质量保证，并建立新的通用方法来解决网络中的硬优化问题。本研究的成果可望显著提高WDM网络的性能，为今后WDM网络的设计和运营提供坚实的基础。该研究还有望为加拿大学术界和工业界培养和培养一批高素质的人才。

With the tremendous growth of bandwidth-intensive networking applications, the demand for bandwidth over data networks is increasing rapidly. Wavelength division multiplexing (WDM) optical networks provide promising infrastructures to meet the information networking demand and have been widely used as backbone networks in the Internet, metropolitan area networks, and high-capacity local area networks. Methodologies and technologies for WDM networks have been becoming key research areas for both academia and industry. To realize communication applications on WDM networks, algorithms are needed to decide light paths for routing and to multiplex low-rate traffic demands in the applications to share the light paths. A general goal in the study of WDM networks is to determine the resources required to achieve a given connectivity as a function of network size and functionality of network nodes. Fundamental optimization problems for this goal are to minimize the resources for realizing a given communication application and to maximize the performance of a network subject to the given resources. It is usually NP-hard to find optimal solutions for those optimization problems. Most previous algorithms for the problems are based on the integer linear programming or ad hoc heuristics and the quality of solutions is not guaranteed. It is extreme importance but challenging to design algorithms which proive solutions with guaranteed quality for those problems. With this proposed project, we use new approaches to develop efficient algorithms with guaranteed performances for the optimization problems. One novel approach to be explored is the tree/branch-decompositions based algorithms. We expect to develop efficient algorithms which provide solutions with much better guaranteed quality for the targeted optimization problems and establish new general approaches for tackling hard optimization problems in networking. The outcome of the research is expected to significantly improve the performances and provide solid foundation for the future design and operation of WDM networks. The research is also expected to train and produce a number of high qualifiied personnel for Canadian academia and industry.