Research On Key Algorithms Of Routing Planning In Transport Networks

With the evolution and innovation of technology and services of networks, there appear variety of applications which leads to the explosive growth of content and the demand of transport network carrying traffic increase rapidly. In order to relieve pressure on the transport network, people turned to look at upgrade or re-structure of the network infrastructure, therefore there emerge one wave of craze research on content center network on behalf of CCN and the one on SDN network on behalf of openflow protocol. However, as to either content center network or SDN network, transport network routing planning is one of the keys to solve the problem. The routing planning of traffic demands will significantly influence the acceptable of demands and resource utilization in the networks. In this paper, we use SDN-based PCE system as a starting point to study routing planning under OTN.Optical network routing planning requires taking many constraints in consideration, mainly the wavelength continuity and optical parametric loss. The so-called wavelength continuity means the demand in the same optical path through the fiber link, it is required to use the same wavelength; Optical parameter loss means the demand between any pair of nodes to establish a connection that required to overcome the non-linear attenuation of the optical signal occurring during transmission. Optical network routing problem called RWA in literature, which is proposed a number of static and dynamic RWA algorithm for nearly twenty years, and many of them were excellent model, such as the wavelength of the hierarchical graph model. However, most of the RWA algorithms do not consider the node with capability of converting wavelength and the optical parametric loss constraints. In this paper, we propose PAS(Path Arrived Success) algorithm and ORA(Optimal Relay Allocation) algorithm with multi-constrained to deal with different scenarios.For discrete reaching new demands, this paper presents a bottom-up solution and a top-down one. The bottom-up solution is similar to the traditional RWA algorithm using pre-calculated directly on the physical topology of alternative shortest K, then as the sequence of multi-constraint alternative way to check, finally allocating wavelength resources; the top-down solution is done through preprocessing optical parametric loss constraint to generate the reachable table, and then creating virtual topology, selecting a route on the virtual topology, ultimately mapping the physical routing and allocating wavelength resources. We apply the First-fit strategy in Wavelength resource allocation. By comparing the experiments by the bottom-up and top-down solutions, we chose the better performance of the top-down solution to design PAS routing algorithm.For rerouting demands generated by network failures, this paper presents the ORA algorithm, which is a multi-objective algorithm, trying to rationally allocating relay resources to achieve low blocking rate, less use of resources. By analyzing type of demands, we decompose relay allocation into three sub-problems, i.e. single relay, dual relay and multi-relay allocation. For the single relay sub-problem, we propose a single relay exclusive model to convert into a bipartite graph of maximum matching problem; for the dual-relay sub-problem, we propose dual-relay allocation algorithm, to construct a hierarchical paired relationship graph to get optimal combination maximum matching; for multi-relay allocation sub-problem, an approximate optimal solution algorithm is given. By comparing the PAS algorithm, the ORA algorithm can effectively reduce blocking operations and improve resource utilization.