Optimization algorythms for WDM optical networks

随着带宽密集型网络应用的迅猛发展，数据网络对带宽的需求也在迅速增长。波分复用（Wavelength division multiplexing， WDM）光网络为满足信息网络的需求提供了良好的基础设施，已被广泛用作Internet、城域网和大容量局域网的骨干网。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.