传送网路由规划关键算法研究

发布时间：2018-06-13 04:01

本文选题：光网络 + RWA　；参考：《电子科技大学》2014年硕士论文

【摘要】：随着网络技术和服务的不断演进和革新,各种应用层出不穷,内容出现爆发式增长,传送网承载的流量迅猛增长,为了缓解或根治传送网的压力,人们把目光转向了网络架构升级或重构,于是涌现了一股以CCN为代表的内容中心网络和以OpenFlow协议为代表的SDN网络的研究热潮。然而,无论是内容中心网络还是SDN网络,传送网的路由规划都是解决问题的关键之一。对业务的路由规划将直接影响到传送网的业务接纳能力和资源利用能力。本文以SDN下的PCE系统作为切入点来研究光网络作为传送网(OTN)的路由规划问题。光网络的路由规划,需考虑光网络自身的约束,主要有波长连续性和光参损耗。所谓的波长连续性是指同一光路在其所经过的光纤链路上须使用同一波长;光参损耗是指任意业务节点对间建立连接须克服光信号在传输过程中出现的非线性衰减。文献中把光网络下的路由问题称为RWA,近二十年内提出了大量静态和动态RWA算法,其中不乏优秀的建模,例如波长分层图模型,然而大部分RWA算法并未考虑光节点的波长转换能力以及光参损耗约束。本文针对不同的业务下发场景,提出了解决上述多约束的有路通路由算法和最优中继分配算法。针对离散到达的新业务,本文提出了自下而上和自上而下两种解决方案。与传统的RWA算法相似,自下而上的解决方案采用在物理拓扑上直接计算前K条备选最短路,然后顺序对备选路进行多约束条件地校验,最后进行波长资源分配;自上而下的解决方案通过预处理光参损耗约束生成可达表,利用可达表构造虚拓扑,在虚拓扑上进行选路并最终实现物理路由映射和波长资源分配。波长资源分配采用First-fit策略。本文通过实验对自下而上和自上而下的解决方案进行对比,选择了性能更优的自上而下的解决方案来设计有路通路由算法。针对网络故障生成的重路由业务,本文提出了最优中继分配算法,是一种多目标算法,试图通过合理分配中继资源达到低阻塞率、少使用中继资源的目标。通过业务类型分析,将原问题分解为单中继、双中继和多中继分配三个子问题。针对前两个子问题分别提出了构建单中继互斥模型从而转换为二部图的最大匹配问题和构建分层配对关系模型从而转换为最大配对最大匹配问题的最优算法,并分析了算法的时间复杂度;对于多中继分配子问题,给出了近优解算法。通过和有路通路由算法对比,最优中继分配算法能有效减少业务阻塞,提高资源利用率。
[Abstract]:With the continuous evolution and innovation of network technology and service, various applications emerge in endlessly, the content appears explosive growth, the traffic of transport network increases rapidly, in order to alleviate or cure the pressure of transmission network, People have turned their eyes to upgrading or reconstructing the network architecture, so there is a wave of research on CCN and SDN represented by OpenFlow protocol. However, routing planning of transport networks is one of the key problems in both content-centric networks and SDN networks. Routing planning will directly affect the transport network's ability to accept services and utilize resources. In this paper, the PCE system under SDN is used as the starting point to study the routing planning problem of optical network as transport network (OTNN). The routing planning of optical networks needs to consider the constraints of optical networks, including wavelength continuity and optical parameter loss. The so-called wavelength continuity means that the same wavelength must be used in the optical link through which the same optical path must be used, and the optical parameter loss means that the nonlinear attenuation of the optical signal in the transmission process must be overcome when the connection between any service node is established. In the literature, the routing problem in optical networks is called RWA. In the last 20 years, a large number of static and dynamic RWA algorithms have been proposed, among which there are many excellent models, such as wavelength layering graph model. However, most RWA algorithms do not take into account the wavelength conversion ability and optical parameter loss constraints of optical nodes. In this paper, we propose a multi-constraint routing algorithm and an optimal relay allocation algorithm for different traffic scenarios. In this paper, two solutions, bottom-up and top-down, are proposed for new discrete arrival services. Similar to the traditional RWA algorithm, the bottom-up solution directly calculates the first K alternative shortest path on the physical topology, then verifies the alternative path with multiple constraints sequentially, and finally carries out wavelength resource allocation. The top-down solution generates reachable tables by pre-processing optical parameter loss constraints, constructs virtual topologies by using reachable tables, selects paths on virtual topologies and finally implements physical routing mapping and wavelength resource allocation. First-fit strategy is used in wavelength resource allocation. In this paper, the bottom-up and top-down solutions are compared through experiments, and a top-down solution with better performance is selected to design the routing algorithm. For the rerouting services generated by network faults, this paper proposes an optimal relay allocation algorithm, which is a multi-objective algorithm, which attempts to achieve the goal of low blocking rate and less use of relay resources through rational allocation of relay resources. By analyzing the service types, the original problem is decomposed into three sub-problems: single relay, double relay and multi-relay assignment. For the first two sub-problems, the optimal algorithm for constructing a single relay mutex model to convert to a bipartite graph and a hierarchical pairing relationship model for the maximum matching problem are proposed, respectively. The time complexity of the algorithm is analyzed, and the near optimal solution algorithm is given for the multi-relay assignment subproblem. Compared with the routing algorithm, the optimal relay allocation algorithm can effectively reduce traffic congestion and improve resource utilization.
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TN929.1

【参考文献】