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.