【作者】 王豪；

【导师】 郭薇；

【作者基本信息】 上海交通大学 ， 通信与信息系统， 2009， 硕士

【摘要】 随着信息技术的发展和信息化程度的不断加深,人们对通信的容量、速度、质量以及服务种类等要求也越来越高,光通信技术靠其巨大的潜力――带宽资源庞大、损耗低、信号传输突变小、功率低等,而日益成为产业界和学术界关注的热点。而分布式计算以及实时系统的发展也对含大数据量的文件在光网络中的传输提出了更高的要求,它关系到大量分布在不同地理位置的文件的汇集,同时也会影响到系统中数据的存储以及系统的性能,因此如何在最短的时间内对需要传输的大量文件完成传输汇聚是现代网络发展中需要重点研究的课题之一。本文中,我们主要研究了波长路由WDM光网络中的大文件传输问题,即需要传输的含大量数据的文件按一定的分布随机到达网络,我们的目标是希望这些文件能在最短的时间内完成传输汇聚工作以提高系统的性能。基于这样的问题,我们在分析了与之相关的路由与波长分配以及文件调度问题的基础上,提出了相应的启发式算法来求解所研究的光网络中含时间约束的大文件传输问题。因为我们所研究的问题是NP-hard的,求解它的最优解的计算复杂度非常的高,所以一般的启发式算法只能求出它的一个可行解却无法求出它的最优解。为了进一步分析研究的需要,我们在提出的启发式算法的基础上,结合与通信网络相关的图论和排队论的知识抽象出了所研究问题的数学模型,然后运用拉格朗日松弛结合次梯度优化的求解方法计算出了问题最优值的一个下界。最后,我们给出了基于Java的仿真结果。首先,仿真对比验证了所提出的各种启发式算法对于求解我们所研究问题性能的优劣性;然后,对比了拉格朗日松弛算法求得的下界和启发式算法求得的可行解,从结果中可以看出拉格朗日松弛的方法求得的解优于启发式算法的解,并由拉格朗日相关理论可知这个值的确是我们所研究问题的最优解的一个下界,它为我们进一步的研究和分析提供了依据。更多还原

【Abstract】 With the development of information technology and the deepening of information degree, the requests of the capacity and the quality and variety of quality for communication are become higher. For its huge potentials in enormous bandwidth resource, lower loss and power etc, the optical communication technology has become a research hotspot in the industry and academia. On the other hand, the high developments of distributed computing and real time systems have given higher requirements for the large files transmitting in optical networks. This transfers process often involved the aggregating of files included large scale data which distributed in different locations and it will affect the data store and the performance of systems, so how to minimize the time that needed to complete the huge number of large files transfers is one of the subjects need to be solved in the development of modern networks.In this paper, we mainly research the problem of large files transfer with time constraints in WDM wavelength-routed optical network. That is, the file need to be transferred arrived in network with some distributing and our purpose is expect these large files can complete the transfers process as soon as possible, which can improve the systems’performance. Based on this problem, we first analysis the routing and wavelength assignment (RWA) problem and the file scheduling problem, which are related to the solving of our problem. And then, we proposed some effective heuristic algorithms to solve our large files transmitting problem.Since our research problem is a NP-hard problem, the computational complexity for the optimal solution is very high and general heuristic algorithms can only get some feasible solutions for it. For the sake of further analysis, firstly, we use the knowledge of graph and queuing theory to abstract our study problem and obtain its mathematic model. Secondly, we acquired the lower bound of our problem’s optimal solution using the method of subgradient algorithm based on Lagrange Relaxation, which will help us to further analyze the research problem and the heuristic algorithms proposed to solve the problem.In order to compare the performance of algorithms proposed to solve our research problem, a Java-based simulator is also proposed. By simulation, we can find that the Subgradient algorithm based on LR can get better results of the file transmitting time than the heuristic algorithms, and with the theorem of Lagrangian Bounding Principle we can know that value get by the LR method is a lower bound on the optimal value.更多还原