# Serial Combination Optimization Method of Packet Transport Network

Authors: Chunzhi Wang; Zaoning Wang; Xing Li; Sha Guan; Ruoxi Wang
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Packet transport network (PTN) has problems such as waste of resources and low network stability due to the excessive complexity of the existing network or improper network architecture design. The optimization of the transport networks can not only make the network structure more reasonable but also reduce all kinds of unexpected scenarios in the network operation, improving the network efficiency and reducing the failure rate. This research will be optimized from three aspects. (1) In order to solve the problem of the same active and standby routing in the existing network, an optimization algorithm for the same active and standby routing of LSP is proposed. The essence of the optimization algorithm is to search the existing routing using theK-shortest path (KSP) between two network nodes as protection routing for LSP protection. (2) Aiming at the link with a high CIR bandwidth occupancy rate, a method is completed without adding optical fibers and other physical resources; an optimization method for the committed information rate bandwidth occupancy rate based on the KSP algorithm is proposed. (3) When the PTN ring formation rate is low, the security of the PTN is seriously reduced. In order to solve the problem of low ring formation rate in the network, this paper proposes a ring formation rate optimization scheme for PTN access layer equipment based on network elements accounting income. Through the experimental verification on the mobile PTN in one city, Hubei Province, the combination optimization method can improve the network LSP protection rate by 24%, the CIR bandwidth occupancy rate is reduced by 13.82%, and the nonring forming rate was reduced by 17.9%. This method improved network stability, reducing the risk of failure in service transportation effectively.


---

## Body

## 1. Introduction

In recent years, with the continuous advancement of informatization construction, information technology has been widely used and information networks have been rapidly popularized. As an optical network capable of high-efficiency transmission of IP, PTN has received great attention from major operators and has been deployed on a large scale. The emergence of PTN technology has completely changed the position of TDM as the core in the network. PTN is supported by packet switching and QoS. It can fully accept all the important networks that have appeared, and it completely maintains the core spirit of the transport network technology. There is no doubt that PTN, as the successor of SDH transport network, will play a cornerstone role in network basic services. At the same time, this puts forward higher requirements for the PTN structure, and the optimization of the PTN is also facing huge challenges. It is mainly reflected in the optimization and improvement of the operating quality of the existing network [1–3]; this article details PTN and OTN. LDP is a self-defined signaling control protocol based on MPLS. It is mainly responsible for dividing FEC through traditional IP, generating labels and sending labels to preestablished neighbor routes, while waiting for messages from neighbor routes. Finally, an LSP is established [4]; LSP is introduced in this article.It is very important to ensure the reliability of service transmission and the safe and stable operation of the network, which can improve the user experience. Therefore, operators generally deploy complete protection mechanisms for PTNs [5]; PTN protection mechanism is introduced in this article, but it did not point out how to optimize the PTN protection mechanism. In order to ensure that the service is not interrupted, when the active route of the LSP that transmits the service fails, the system needs to automatically switch the service to the standby path. However, due to various reasons such as construction period, geographical constraints, and investment income, there are still problems with the same routing in the network. In LSP, once the physical active and standby paths fail at the same routing location, or the optical fiber forming the logical ring network is damaged, the active path and the standby path (also called the protection path) will be interrupted at the same time. This will cause the actual standby to fail and cause service transmission to fail. Literature [6] first introduces the three-tier architecture of the software-defined network to the PTN to optimize the complex and bloated PTN architecture and other issues. This article constructs a mathematical model of the multiconstrained optimal path and proposes an improved ant colony algorithm to improve the efficiency and accuracy of the algorithm in searching for the optimal path in the network. Then, optimize the LSP active and standby routing problem. In the PTN, when the CIR bandwidth occupancy rate of a link is too high, information may be blocked during transmission, which may cause information loss; literature [7] proposes a method based on capacity expansion to optimize the problem of excessive CIR bandwidth occupancy. However, the economic cost of doing so is high and requires a lot of physical equipment support. In this article, a packet transport network recovery system based on failure pattern under examination of transmission quality is proposed. But it did not point out how to solve the problem of excessive CIR bandwidth occupancy. If too many network elements are not looped in PTN, during network operation, whether the equipment is ringed has a huge impact on network stability. Nonlooped equipment may affect the transmission of a large number of mobile services when a single point line or equipment failure occurs. Making the network into a loop as much as possible has become an important operation to improve network security; literature [8] only points out the problems caused by the low ring formation rate and does not provide a solution.TheK-shortest path problem is the expansion and deformation of the shortest path problem. In the 1950s, Hoffinan and Pavley first proposed it. There are many ways to solve the K-shortest path problem, among which the well-known algorithms are the Yen algorithm, Epstein algorithm, and so on; literature [9] details two K-shortest path problems. The Yen algorithm is mainly aimed at the shortest path problem of A without a self-loop link graph. The core idea of the algorithm is to use the method of deviating path to solve. With the proposal of the algorithm for solving this problem, new ideas and development opportunities have been brought to network resource allocation, road planning, and network structure optimization [10].Soorki and Rostami proposed a coordinated switching method between different layers to achieve business standby in the event of multiple points of failure in view of the difficulty of business standby [11]. However, the contribution of this article to LSP optimization is not very large, and the problem of excessively high LSP active/standby routing rate still exists. On the basis of a detailed assessment of the network failure risk, Hongbin proposed a method to optimize existing network resources and improve performance by using existing resources [8]; the method in the article improved resource utilization in the network. Wang et al. studied the abnormal data transmission path switching method of the network big data. Firstly, the output end of the abnormal transmission path was determined, and then, through the design of the path switching unit, the abnormal transmission path switching of the network big data was realized [12]. Wang and Li proposed a load-balanced shortest path routing algorithm for the serial high-speed input-output (SRIO) network depth-first search distribution path nonoptimal problem [13]. Wang et al. proposed a paving material transportation path planning of railway hub based on the KSP algorithm [14].The research mentioned above has improved the network status to a certain extent, but in the process of implementation, most of them still rely on worker experience.In the following, we investigated the same routing problem in the existing network and propose a new idea, that is, an optimization algorithm for the same active and standby routing of label switching path based on KSP, without increasing physical resources, through the KSP algorithm finds the available standby path, and replace the original standby path. Aiming at the problem of excessive CIR bandwidth occupancy, this article proposes to use the KSP algorithm to find the shortest path between the source/sink node NEs of the original link and then switch the original service transmission path to the path provided by the KSP algorithm, in order to reduce the CIR bandwidth occupancy rate of the original link. This method is completed without adding optical fibers and other physical resources. Aiming at the problem of low equipment ring formation rate, it is proposed to switch services by calculating the NE accounting income without adding optical fiber and other physical resources, so that more NEs are in the ring, and the ring formation rate in the network is improved.The remainder of this paper is as follows. The next part will introduce the network mechanism of PTN that includes the standby mechanism of PTN, committed information rate (CIR), and equipment ring formation rate. Section3 introduces the KSP algorithm and describes the application of the improved KSP algorithm in this article in detail. Section 4 introduces the innovation of this article, that is, to solve the optimization solution of LSP active and standby routing and CIR bandwidth occupancy rate that is too high, introduce how to improve the looping rate of equipment in the network, and analyze the applicability of the solution. Section 5 shows and analyzes the experimental results, specifically the comparison before and after optimization of LSP, CIR, and ring formation rate. Finally, conclusion and outlook are given by Section 6.


## 2. PTN Mechanism

In the PTN networking solution, in order to prevent network failures caused by failure of single-homing uplink, dual-homing uplink is adopted at the access layer, convergence layer, and core layer to improve the security of the network. The convergence layer that adopts the network is mainly ring network, and various services are carried on bare fiber. In order to ensure network security and high reliability, the network is mainly based on meshes and supplemented by ring behaviors to ensure the scheduling and landing of various services across backbone nodes. QoS meets the different needs of various applications by classifying, monitoring, and dredging traffic, solves the problems of message loss, delay, and jitter, can provide different levels of service quality, and ensures the quality of service carrying. Among them, optimizing the same active and standby routing of LSP and reducing the CIR bandwidth occupancy rate is very important to improve the stability of the PTN. The schematic diagram of the PTN is shown in Figure1.Figure 1
PTN networking diagram.The standby methods in the PTN mainly include LSP standby (also known as linear protection) and ring network protection. They are described in detail in paper [15]. This paper only discusses LSP protection.The LSP protection in the PTN uses a dedicated end-to-end protection structure to protect an MPLS-TP connection. When the working path fails, all services on the working path are converted to the standby path for transmission. This paper is optimized for 1 : 1 LSP protection.


### 2.1. LSP Protection

The LSP protection in the PTN uses a dedicated end-to-end protection structure to protect a path connection. When the active routing fails, all services on the path are converted to the protection routing for transmission.It is assumed in Figure2 that communication needs to be performed at start NE to end EN. Usually, the preferred working path is the active path in Figure 2. Below the active routing, the service transmission link is start NE → B → C → D → E → end NE. If the link fails at any node of B → C → D → E, the network will automatically enable linear protection and switch the standby routing, and the path will become start NE → G → H → I → J → end NE. This ensures that even when the active routing fails, dedicated line services can run smoothly [5].Figure 2
Schematic diagram of PTN LSP protection.


### 2.2. Committed Information Rate

The committed information rate (CIR) refers to the information transfer rate under normal conditions on a specific virtual circuit scheduled on the network. The CIR bandwidth occupancy rate of each link equals total link bandwidth occupancy/link bandwidth capacity. When the CIR bandwidth occupancy rate of the link is greater than 80%, congestion may occur during information transmission, which may cause some frames sent by users to be discarded. Therefore, in order to improve user experience and ensure the reliability of service transmission and the safe and stable operation of the network, it is generally required that the link CIR bandwidth occupancy rate in the PTN should not exceed 80%. In reality, due to various reasons such as errors in network deployment by staff, there are still links in the transmission network with a CIR bandwidth occupancy rate greater than 80%, resulting in poor network operation stability. However, there is little research on the problem of excessive CIR bandwidth occupancy.


### 2.3. Equipment Ring Formation Rate

In the network operation process, whether the equipment is looped has a huge impact on the stability of the network. When a single-point line or equipment failure occurs, a device that does not form a loop may affect whether a large number of mobile services can be successfully transmitted. Putting the NEs on the ring as much as possible has become an important operation to improve network security. In the process of PTN configuration, most of the access layer devices will form a ring. The condition of the ring is that there are at least 2 completely nonrepetitive paths, which are finally connected to the convergence layer devices. However, there will still be a small number of access layer devices that are not in a ring, and there will be a long chain phenomenon, which will affect a large number of services when the network is turbulent.When the mobile PTN is deployed, it generally adopts a three-layer networking mode of core layer, convergence layer, and access layer. As shown in Figure3, the devices between NE A and NE B in the access layer form a ring, and other devices connected to the ring form a long chain. When communicating between devices in a ring, if a device fails, services can be transmitted through the other end of the loop. When a device on the long chain fails, it will cause service transmission to fail. In order to improve the stability and reliability of service transmission, it is required to make as many devices as possible to the ring and to increase the ring formation rate of devices in the network.Figure 3
PTN three-layer networking mode.


## 2.1. LSP Protection

The LSP protection in the PTN uses a dedicated end-to-end protection structure to protect a path connection. When the active routing fails, all services on the path are converted to the protection routing for transmission.It is assumed in Figure2 that communication needs to be performed at start NE to end EN. Usually, the preferred working path is the active path in Figure 2. Below the active routing, the service transmission link is start NE → B → C → D → E → end NE. If the link fails at any node of B → C → D → E, the network will automatically enable linear protection and switch the standby routing, and the path will become start NE → G → H → I → J → end NE. This ensures that even when the active routing fails, dedicated line services can run smoothly [5].Figure 2
Schematic diagram of PTN LSP protection.


## 2.2. Committed Information Rate

The committed information rate (CIR) refers to the information transfer rate under normal conditions on a specific virtual circuit scheduled on the network. The CIR bandwidth occupancy rate of each link equals total link bandwidth occupancy/link bandwidth capacity. When the CIR bandwidth occupancy rate of the link is greater than 80%, congestion may occur during information transmission, which may cause some frames sent by users to be discarded. Therefore, in order to improve user experience and ensure the reliability of service transmission and the safe and stable operation of the network, it is generally required that the link CIR bandwidth occupancy rate in the PTN should not exceed 80%. In reality, due to various reasons such as errors in network deployment by staff, there are still links in the transmission network with a CIR bandwidth occupancy rate greater than 80%, resulting in poor network operation stability. However, there is little research on the problem of excessive CIR bandwidth occupancy.


## 2.3. Equipment Ring Formation Rate

In the network operation process, whether the equipment is looped has a huge impact on the stability of the network. When a single-point line or equipment failure occurs, a device that does not form a loop may affect whether a large number of mobile services can be successfully transmitted. Putting the NEs on the ring as much as possible has become an important operation to improve network security. In the process of PTN configuration, most of the access layer devices will form a ring. The condition of the ring is that there are at least 2 completely nonrepetitive paths, which are finally connected to the convergence layer devices. However, there will still be a small number of access layer devices that are not in a ring, and there will be a long chain phenomenon, which will affect a large number of services when the network is turbulent.When the mobile PTN is deployed, it generally adopts a three-layer networking mode of core layer, convergence layer, and access layer. As shown in Figure3, the devices between NE A and NE B in the access layer form a ring, and other devices connected to the ring form a long chain. When communicating between devices in a ring, if a device fails, services can be transmitted through the other end of the loop. When a device on the long chain fails, it will cause service transmission to fail. In order to improve the stability and reliability of service transmission, it is required to make as many devices as possible to the ring and to increase the ring formation rate of devices in the network.Figure 3
PTN three-layer networking mode.


## 3. KSP Algorithm Model

TheK-shortest path problem is a generalization of the shortest path problem by seeking a shorter path between the source node and the terminal node of the network. K-shortest path (KSP) problems usually include two types: restricted K-shortest path problems and unrestricted K-shortest path problems. Restricted requirements require that the shortest path set does not contain loops, and unrestricted has no restriction on the shortest path set obtained. This article needs to require the available path between the original network element and the sink network element, which is a restricted multipath problem, that is, a KSP problem with a limited loop. The commonly used algorithm for solving the restricted acyclic KSP problem is the deviation path algorithm based on the shortest path Dijkstra algorithm, also known as Yen’s algorithm. Yen’s algorithm adopts the deviated path algorithm idea in the recursive method and is suitable for the structure of directed acyclic graphs with nonnegative weight edges [16].


### 3.1. Dijkstra Algorithm Model

The Dijkstra algorithm (Dijkstra) is the shortest path algorithm from one vertex to the other vertices, and it solves the shortest path problem in the graph. The main feature of Dijkstra’s algorithm is that it starts from the starting point and adopts the strategy of the greedy algorithm. Each time, it traverses to the adjacent node of the vertex that is closest to the starting point and has not been visited, until it expands to the end point. The algorithm steps are as follows:Step 1. Determine the network graphG=V,E according to the fiber connection status between the network elements. If there is a fiber connection between every two network elements in the figure, the edge weight is 1, and if there is no fiber connection, the edge weight is infinite. The adjacency matrix W is established, and Wij is used to represent the fiber connection status from network element i to network element j. Set S is used to record the visited network elements of the shortest path, and set U is used to record the unvisited network elements of the shortest path. Use disx to record the sum of the shortest path edge weights from the starting network element V0 to the network element Vx, that is, the shortest number of hops between V0 and Vx.Step 2. If the NE satisfies formula (1), add NE j to the visited NE set S and delete NE j from the unvisited NE set U.
(1)disj<=mindisi,Vi∈V−S.Step 3. Compare the sum of the edge weights from the start NEV0 to the NE Vx and the edge weights from the NE Vx to the end NE Vt with the sum of the edge weights from the start NE V0 to the end NE Vt. If the former is less than the latter, then update dist to the sum of the shortest path edge weight disx and the edge weight value Wxt, as shown in
(2)Ifdisx+Wxt<dist,dist=disx+Wxt.Step 4. Determine whether the setU is empty. If it is empty, output the set S as the shortest path. If it is not empty, go to Step 2 to continue execution.The simulated network topology and its corresponding adjacency matrix are shown in Figure4.Figure 4
Simulation network topology and adjacency matrix.


### 3.2. Improved Model of the KSP Algorithm

Yen’s algorithm uses the Dijkstra algorithm to find the shortest path between two points and then calculates the otherK−1 shortest paths in turn on this basis. When finding Pi+1, all nodes on Pi except the terminal node Vt are regarded as deviating nodes and calculate the shortest path from each deviating node to the end node and then concatenate it with the path from the starting node V0 to the deviating node Vx on Pi to form a candidate path and then obtain the shortest deviating path.This paper seeks theKK=5 shortest path between two NEs. Specific steps are as follows:Step 1. Use setP to record the first K-shortest paths, set B to record candidate paths, and both B and P are initially empty, and i represents the number of paths in set P. The Dijkstra algorithm is used to solve the shortest path p from the source v0 to the sink vt, and the shortest path P is sequentially stored in the set P.Step 2. Remove then nodes on the ith shortest path Pi except for the node at the end NE Vt, in turn as the deviation point Vj=j=1,2,.,n−1.Step 3. Use the above Dijkstra algorithm to sequentially calculate the shortest pathH from the deviation point to the end NE Vt.Step 4. Place the path composed of the path from the start NEV0 to the deviation point Vj in the ith shortest path P and the deviation path H=j=1,2,.,n−1 in the candidate route set B.Step 5. Take the path with the smallest path weight in the candidate path setB as Pi+1, put it in the first KSP set P, and delete the path from set B.Step 6. Determine whether the numberi of paths in the set P is less than K, and whether the set B is not empty. If it is, transfer to Step 2. If not, output the first KSP sets.Step 7. Extract the first path in the set of the firstK-shortest paths, and determine whether the same route occurs with the original main path. If not, replace the original backup path with this path, if so, compare the second path, and so on.


## 3.1. Dijkstra Algorithm Model

The Dijkstra algorithm (Dijkstra) is the shortest path algorithm from one vertex to the other vertices, and it solves the shortest path problem in the graph. The main feature of Dijkstra’s algorithm is that it starts from the starting point and adopts the strategy of the greedy algorithm. Each time, it traverses to the adjacent node of the vertex that is closest to the starting point and has not been visited, until it expands to the end point. The algorithm steps are as follows:Step 1. Determine the network graphG=V,E according to the fiber connection status between the network elements. If there is a fiber connection between every two network elements in the figure, the edge weight is 1, and if there is no fiber connection, the edge weight is infinite. The adjacency matrix W is established, and Wij is used to represent the fiber connection status from network element i to network element j. Set S is used to record the visited network elements of the shortest path, and set U is used to record the unvisited network elements of the shortest path. Use disx to record the sum of the shortest path edge weights from the starting network element V0 to the network element Vx, that is, the shortest number of hops between V0 and Vx.Step 2. If the NE satisfies formula (1), add NE j to the visited NE set S and delete NE j from the unvisited NE set U.
(1)disj<=mindisi,Vi∈V−S.Step 3. Compare the sum of the edge weights from the start NEV0 to the NE Vx and the edge weights from the NE Vx to the end NE Vt with the sum of the edge weights from the start NE V0 to the end NE Vt. If the former is less than the latter, then update dist to the sum of the shortest path edge weight disx and the edge weight value Wxt, as shown in
(2)Ifdisx+Wxt<dist,dist=disx+Wxt.Step 4. Determine whether the setU is empty. If it is empty, output the set S as the shortest path. If it is not empty, go to Step 2 to continue execution.The simulated network topology and its corresponding adjacency matrix are shown in Figure4.Figure 4
Simulation network topology and adjacency matrix.


## 3.2. Improved Model of the KSP Algorithm

Yen’s algorithm uses the Dijkstra algorithm to find the shortest path between two points and then calculates the otherK−1 shortest paths in turn on this basis. When finding Pi+1, all nodes on Pi except the terminal node Vt are regarded as deviating nodes and calculate the shortest path from each deviating node to the end node and then concatenate it with the path from the starting node V0 to the deviating node Vx on Pi to form a candidate path and then obtain the shortest deviating path.This paper seeks theKK=5 shortest path between two NEs. Specific steps are as follows:Step 1. Use setP to record the first K-shortest paths, set B to record candidate paths, and both B and P are initially empty, and i represents the number of paths in set P. The Dijkstra algorithm is used to solve the shortest path p from the source v0 to the sink vt, and the shortest path P is sequentially stored in the set P.Step 2. Remove then nodes on the ith shortest path Pi except for the node at the end NE Vt, in turn as the deviation point Vj=j=1,2,.,n−1.Step 3. Use the above Dijkstra algorithm to sequentially calculate the shortest pathH from the deviation point to the end NE Vt.Step 4. Place the path composed of the path from the start NEV0 to the deviation point Vj in the ith shortest path P and the deviation path H=j=1,2,.,n−1 in the candidate route set B.Step 5. Take the path with the smallest path weight in the candidate path setB as Pi+1, put it in the first KSP set P, and delete the path from set B.Step 6. Determine whether the numberi of paths in the set P is less than K, and whether the set B is not empty. If it is, transfer to Step 2. If not, output the first KSP sets.Step 7. Extract the first path in the set of the firstK-shortest paths, and determine whether the same route occurs with the original main path. If not, replace the original backup path with this path, if so, compare the second path, and so on.


## 4. Methods

This article takes 11,261 tunnels in a city as an example. It mainly solves the problem of the same route. The same route can be divided into the same board at the source (that is, the starting network element), the same board at the sink (that is, the terminating network element), and the middle network elements with the same route (including the same network element, the same link, and the same board). The KSP algorithm mainly optimizes the problem of the same route of the intermediate network element, and the problem of the same board of the start (sink) is solved by switching the board to the remaining boards of the network element.


### 4.1. Same Routing Optimization

#### 4.1.1. Start/Sink NE Same Routing Solution Strategy

The start (sink) NE same routing is that the starting node of the active path and the standby path corresponds to the same board. The main reason for this phenomenon in the city’s mobile network is the improper initial configuration of the staff. For this phenomenon, an optimized solution for switching boards is proposed in this article. If there are excess boards in the starting NE, the starting board of the standby path is switched to the excess board to eliminate the problem of the same board at the source. As shown in Figure5, the black solid line represents the original active path, the red solid line represents the original standby path, and the red dashed line represents the modified path. When the starting board of the standby path is switched from board 1 of the starting network node to board 2, the problem that the active path and the standby path are the same board can be eliminated. The time complexity of the start (sink) NE same routing solution is On and the space complexity is O1.Figure 5
Schematic diagram of the start NE the same board.The end NE same routing is that the ending node of the active path and the standby path corresponds to the same board. For this problem, this paper proposes that switched from board 1 of the end NE to board 2, the problem that the active path and the standby path are the same board can be eliminated, as shown in Figure6. At this time, when board 1 on the end NE fails and the active path is unavailable, the service can be switched to the standby path, and the standby path does not pass through board 1. Therefore, service transmission can be completed and the stability of the network is protected.Figure 6
Schematic diagram of the end NE the same board.


#### 4.1.2. Intermediate NE Same Routing Solution Strategy

When the same route appears in the intermediate network node (including the same network node, the same link, and the same board), this paper proposes to use the KSP algorithm to search for available paths in the existing resources and sort them from short to long according to the path. After the path with the same routing occurs, the shorter path is preferred to replace the original standby path, thereby eliminating the phenomenon of the same route between the intermediate network nodes.In Figure7, the active path is as follows: board 1 of the start NE--board 1 of the NE A--board 1 of the NE B--board 1 of the NE C--board 1 of the End NE. The original standby path is as follows: board 2 of the start NE--board 1 of the NE D--board 1 of the NE B--board 1 of the NE E--board 2 of the End NE, the active path and the standby path have the same board card at the intermediate NE B; at this time, the KSP algorithm can be used to find a standby path 1: board 2 of the start NE--board 1 of the NE D--board 1 of the NE E--board 1 of the NE F--board 2 of the End NE. After replacing the original standby path with standby path 1, it successfully solves the problem of the same routing between the active and standby and does not add physical equipment, which improves the utilization rate of existing resources, reduces the probability of the same routing in the network, and improves the service transmission when the active path fails safety.Figure 7
Schematic diagram of intermediate NE the same board.Optimizing a tunnel with active and standby same routing is mainly divided into the following steps:Step 1. Obtain all NEs of the active path and standby path of the tunnel, and determine whether the source/sink end is the same route.Step 2. If the source/sink end is the same route, use the scheme in 3.1 above for optimization.Step 3. If the intermediate NE is the same route, use the scheme mentioned in 3.2 above for optimization.Step 4. Evaluate whether the optimization is successful. The time complexity of the intermediate NE same routing solution isOn2, and the space complexity is O1.The optimization process is shown in Figure8.Figure 8
LSP optimization process.


### 4.2. CIR Bandwidth Occupancy Rate Optimization

This article takes 3580 links in the city’s network as an example to optimize the phenomenon of excessive CIR bandwidth occupancy. The bandwidth occupation of a link is obtained by the accumulation of the CIR values of all the tunnels passing through this link. As shown in Figure9, assuming that there are 3 tunnels passing through the link DE, and the CIR value of each tunnel is 80, 40, and 80, respectively, the CIR bandwidth occupation of the link DE=80+40+80=200.Figure 9
CIR link diagram.When the CIR bandwidth occupancy rate of a link is greater than 80%, this article proposes to find out all the tunnels passing through this link, determine the CIR value of the tunnel and the source and sink NEs, then use the KSP algorithm to find other paths between the source and sink NEs passing through one tunnel, and select a suitable path to replace the original path. The specific steps are as follows:Step 1. Determine link A with CIR bandwidth occupancyrate>80%, select one of them, and assume that its bandwidth occupancy is P.Step 2. Find all the tunnels passing through this link, and sort the tunnel sets according to their CIR values.Step 3. Traverse the tunnel set, select a tunnel with the largest CIR value, and use the KSP algorithm to find the top 10 shortest paths between the source and sink NEs.Step 4. Traverse the 10 paths found in Step 3 one by one.Step 5. Determine whether the CIR bandwidth occupied by each hop link of thispath+theCIRvalue of the above-mentioned tunnel is less than 80%.Step 6. If yes, replace the path of the original tunnel; otherwise, return to Step 4.Step 7. Determine whether the bandwidth occupancy rate of link A (P-tunnel CIR value)/the bandwidth capacity of link A is less than 80% at this time.Step 8. If yes, the link is optimized successfully; otherwise, go back to step 3.The optimization diagram is shown in Figure10. When the CIR bandwidth occupancy rate of the link DE is too high, the original path A-D-E-F of tunnel 1 can be switched to the path A-I-J-F to reduce the bandwidth occupancy rate of the link DE. At this time, it is necessary to ensure that the CIR bandwidth occupancy rate of each link in the path A-I-J-F does not exceed 80%.Figure 10
CIR link optimization diagram.


### 4.3. Equipment Ring Formation Rate Optimization

Taking 2977 NE nodes in the one city’s network as an example, the active solution is to solve the problem of nodes not forming a ring. Known the long single chain information formed by the unlooped NEs and the ring information, according to the existing network structure and possible optical fiber lines, under the premise of satisfying reliability and business segment constraints, a more economical optical fiber connection scheme was determined. Use the structure of the graph to model the PTN transmission network. Each node in the figure represents the access layer NE equipment, and the edge represents the optical fiber connected between the NEs. As shown in Figure11 (left), the NEs in the figure are all access layer devices, in which devices A-B-C-D-E-F form a ring, and device G-H-I is not on the ring, so device G-H-I is a long chain device that does not form a ring. Therefore, it is necessary to optimize this type of long chain equipment so that it is located on the ring as much as possible.Figure 11
Schematic diagram of ring formation.In order to make the long chain on the ring, the method proposed in this paper is shown in Figure11 (right). Assuming that there is an unused fiber between the end of the long chain and the ring NE, the optimization scheme is to first dismantle the ring and then connect the device at the end of the long chain to the nearest node on the original ring near the root end of the long chain, so that all devices are on the same ring, then connect the NE at the end of the long chain to the original ring NE so that all NEs are on the same ring. The black line in Figure 11 (right) represents the line of the existing service, the red line represents the unused fiber, the red fiber may have multiple, and the black dashed line represents the fiber that needs to be broken in the service after optimization.In the current network, there may not be unused fibers at the end of the long chain and the NEs close to the root end of the long chain. At this time, cannot make all the long chain devices on the ring, only as many NEs as possible can be on the ring. Accounting income refers to the concept of income in accounting. It refers to the difference between the realized income and the corresponding expenses from the company’s transactions during the period. This paper introduces this concept to improve the ring formation rate of the network, calculating the number difference between the newly connected long chain NE and the sacrificing original ring NE as the accounting income, so a ring formation rate optimization scheme based on the NEs accounting income is proposed.In the PTN, each long chain may be located on multiple loops, and each loop has multiple NEs. In the process of calculating the accounting income of the NEs, first, abstract all the loops of the long chain as a graph. Using the depth-first search of the graph, traverse with the cross NE as the starting vertex, and calculate the NE information income between each NE of this long chain and each NE on the graph composed of all loops. The calculation formula for accounting income between long chain NEs and ring NEs is shown in(3)G=L_i−R_j+1,whereG is the accounting income of the NE; L_i is the position of the ith NE from the cross NE on the long chain; R_j is the position of the jth NE from the cross NE on the ring. As shown in Figure 12, the maximum value of L_i is 4, and the maximum value of R_j is 3.Figure 12
Schematic diagram of long chain.Use the above method to calculate the accounting income between the NEs L1, L2, L3, L4, and each NE on the ring, and determine whether there is an optical fiber connection between the two NEs. Assuming that there is an optical fiber between the two NEs L1 and R1, if this optical fiber is used to switch the original service, the connection between the crossover NE and the ring NE R1 needs to be disconnected, and connect the long chain NE L1 to the ring. At this time, the ring NE is not sacrificed, and a long chain NE is connected at the same time. Therefore, the NE accounting income of this optical fiber is 1, which is a positive income. The ring formation rate will increase after the optical fiber is used to switch services. The accounting income between each NE on the long chain and each NE on the ring in Figure12 is shown in Table 1.Table 1
Accounting income statement.
R1R2R3/convergence NE BL1101L2210L3321L4432This article is how to findN available optical fibers and select a line from these N available optical fibers to form the most economical and reliable optimization solution.Specific steps are as follows:Step 1. Determine all long chains that are not on the ring to form a long chain set A.Step 2. Traverse the long chain set A, select one of the long chains, and determine which rings the long chain is connected to.Step 3. Determine the position where the long chain NEs and the ring NEs have optical fiber connections.Step 4. Calculate the accounting income of each fiber and arrange it in descending order.Step 5. Select a fiber with the largest income for service switching to achieve the purpose of increasing the loop rate.Step 6. Return to Step 1 until the end of the traversal.


## 4.1. Same Routing Optimization

### 4.1.1. Start/Sink NE Same Routing Solution Strategy

The start (sink) NE same routing is that the starting node of the active path and the standby path corresponds to the same board. The main reason for this phenomenon in the city’s mobile network is the improper initial configuration of the staff. For this phenomenon, an optimized solution for switching boards is proposed in this article. If there are excess boards in the starting NE, the starting board of the standby path is switched to the excess board to eliminate the problem of the same board at the source. As shown in Figure5, the black solid line represents the original active path, the red solid line represents the original standby path, and the red dashed line represents the modified path. When the starting board of the standby path is switched from board 1 of the starting network node to board 2, the problem that the active path and the standby path are the same board can be eliminated. The time complexity of the start (sink) NE same routing solution is On and the space complexity is O1.Figure 5
Schematic diagram of the start NE the same board.The end NE same routing is that the ending node of the active path and the standby path corresponds to the same board. For this problem, this paper proposes that switched from board 1 of the end NE to board 2, the problem that the active path and the standby path are the same board can be eliminated, as shown in Figure6. At this time, when board 1 on the end NE fails and the active path is unavailable, the service can be switched to the standby path, and the standby path does not pass through board 1. Therefore, service transmission can be completed and the stability of the network is protected.Figure 6
Schematic diagram of the end NE the same board.


### 4.1.2. Intermediate NE Same Routing Solution Strategy

When the same route appears in the intermediate network node (including the same network node, the same link, and the same board), this paper proposes to use the KSP algorithm to search for available paths in the existing resources and sort them from short to long according to the path. After the path with the same routing occurs, the shorter path is preferred to replace the original standby path, thereby eliminating the phenomenon of the same route between the intermediate network nodes.In Figure7, the active path is as follows: board 1 of the start NE--board 1 of the NE A--board 1 of the NE B--board 1 of the NE C--board 1 of the End NE. The original standby path is as follows: board 2 of the start NE--board 1 of the NE D--board 1 of the NE B--board 1 of the NE E--board 2 of the End NE, the active path and the standby path have the same board card at the intermediate NE B; at this time, the KSP algorithm can be used to find a standby path 1: board 2 of the start NE--board 1 of the NE D--board 1 of the NE E--board 1 of the NE F--board 2 of the End NE. After replacing the original standby path with standby path 1, it successfully solves the problem of the same routing between the active and standby and does not add physical equipment, which improves the utilization rate of existing resources, reduces the probability of the same routing in the network, and improves the service transmission when the active path fails safety.Figure 7
Schematic diagram of intermediate NE the same board.Optimizing a tunnel with active and standby same routing is mainly divided into the following steps:Step 1. Obtain all NEs of the active path and standby path of the tunnel, and determine whether the source/sink end is the same route.Step 2. If the source/sink end is the same route, use the scheme in 3.1 above for optimization.Step 3. If the intermediate NE is the same route, use the scheme mentioned in 3.2 above for optimization.Step 4. Evaluate whether the optimization is successful. The time complexity of the intermediate NE same routing solution isOn2, and the space complexity is O1.The optimization process is shown in Figure8.Figure 8
LSP optimization process.


## 4.1.1. Start/Sink NE Same Routing Solution Strategy

The start (sink) NE same routing is that the starting node of the active path and the standby path corresponds to the same board. The main reason for this phenomenon in the city’s mobile network is the improper initial configuration of the staff. For this phenomenon, an optimized solution for switching boards is proposed in this article. If there are excess boards in the starting NE, the starting board of the standby path is switched to the excess board to eliminate the problem of the same board at the source. As shown in Figure5, the black solid line represents the original active path, the red solid line represents the original standby path, and the red dashed line represents the modified path. When the starting board of the standby path is switched from board 1 of the starting network node to board 2, the problem that the active path and the standby path are the same board can be eliminated. The time complexity of the start (sink) NE same routing solution is On and the space complexity is O1.Figure 5
Schematic diagram of the start NE the same board.The end NE same routing is that the ending node of the active path and the standby path corresponds to the same board. For this problem, this paper proposes that switched from board 1 of the end NE to board 2, the problem that the active path and the standby path are the same board can be eliminated, as shown in Figure6. At this time, when board 1 on the end NE fails and the active path is unavailable, the service can be switched to the standby path, and the standby path does not pass through board 1. Therefore, service transmission can be completed and the stability of the network is protected.Figure 6
Schematic diagram of the end NE the same board.


## 4.1.2. Intermediate NE Same Routing Solution Strategy

When the same route appears in the intermediate network node (including the same network node, the same link, and the same board), this paper proposes to use the KSP algorithm to search for available paths in the existing resources and sort them from short to long according to the path. After the path with the same routing occurs, the shorter path is preferred to replace the original standby path, thereby eliminating the phenomenon of the same route between the intermediate network nodes.In Figure7, the active path is as follows: board 1 of the start NE--board 1 of the NE A--board 1 of the NE B--board 1 of the NE C--board 1 of the End NE. The original standby path is as follows: board 2 of the start NE--board 1 of the NE D--board 1 of the NE B--board 1 of the NE E--board 2 of the End NE, the active path and the standby path have the same board card at the intermediate NE B; at this time, the KSP algorithm can be used to find a standby path 1: board 2 of the start NE--board 1 of the NE D--board 1 of the NE E--board 1 of the NE F--board 2 of the End NE. After replacing the original standby path with standby path 1, it successfully solves the problem of the same routing between the active and standby and does not add physical equipment, which improves the utilization rate of existing resources, reduces the probability of the same routing in the network, and improves the service transmission when the active path fails safety.Figure 7
Schematic diagram of intermediate NE the same board.Optimizing a tunnel with active and standby same routing is mainly divided into the following steps:Step 1. Obtain all NEs of the active path and standby path of the tunnel, and determine whether the source/sink end is the same route.Step 2. If the source/sink end is the same route, use the scheme in 3.1 above for optimization.Step 3. If the intermediate NE is the same route, use the scheme mentioned in 3.2 above for optimization.Step 4. Evaluate whether the optimization is successful. The time complexity of the intermediate NE same routing solution isOn2, and the space complexity is O1.The optimization process is shown in Figure8.Figure 8
LSP optimization process.


## 4.2. CIR Bandwidth Occupancy Rate Optimization

This article takes 3580 links in the city’s network as an example to optimize the phenomenon of excessive CIR bandwidth occupancy. The bandwidth occupation of a link is obtained by the accumulation of the CIR values of all the tunnels passing through this link. As shown in Figure9, assuming that there are 3 tunnels passing through the link DE, and the CIR value of each tunnel is 80, 40, and 80, respectively, the CIR bandwidth occupation of the link DE=80+40+80=200.Figure 9
CIR link diagram.When the CIR bandwidth occupancy rate of a link is greater than 80%, this article proposes to find out all the tunnels passing through this link, determine the CIR value of the tunnel and the source and sink NEs, then use the KSP algorithm to find other paths between the source and sink NEs passing through one tunnel, and select a suitable path to replace the original path. The specific steps are as follows:Step 1. Determine link A with CIR bandwidth occupancyrate>80%, select one of them, and assume that its bandwidth occupancy is P.Step 2. Find all the tunnels passing through this link, and sort the tunnel sets according to their CIR values.Step 3. Traverse the tunnel set, select a tunnel with the largest CIR value, and use the KSP algorithm to find the top 10 shortest paths between the source and sink NEs.Step 4. Traverse the 10 paths found in Step 3 one by one.Step 5. Determine whether the CIR bandwidth occupied by each hop link of thispath+theCIRvalue of the above-mentioned tunnel is less than 80%.Step 6. If yes, replace the path of the original tunnel; otherwise, return to Step 4.Step 7. Determine whether the bandwidth occupancy rate of link A (P-tunnel CIR value)/the bandwidth capacity of link A is less than 80% at this time.Step 8. If yes, the link is optimized successfully; otherwise, go back to step 3.The optimization diagram is shown in Figure10. When the CIR bandwidth occupancy rate of the link DE is too high, the original path A-D-E-F of tunnel 1 can be switched to the path A-I-J-F to reduce the bandwidth occupancy rate of the link DE. At this time, it is necessary to ensure that the CIR bandwidth occupancy rate of each link in the path A-I-J-F does not exceed 80%.Figure 10
CIR link optimization diagram.


## 4.3. Equipment Ring Formation Rate Optimization

Taking 2977 NE nodes in the one city’s network as an example, the active solution is to solve the problem of nodes not forming a ring. Known the long single chain information formed by the unlooped NEs and the ring information, according to the existing network structure and possible optical fiber lines, under the premise of satisfying reliability and business segment constraints, a more economical optical fiber connection scheme was determined. Use the structure of the graph to model the PTN transmission network. Each node in the figure represents the access layer NE equipment, and the edge represents the optical fiber connected between the NEs. As shown in Figure11 (left), the NEs in the figure are all access layer devices, in which devices A-B-C-D-E-F form a ring, and device G-H-I is not on the ring, so device G-H-I is a long chain device that does not form a ring. Therefore, it is necessary to optimize this type of long chain equipment so that it is located on the ring as much as possible.Figure 11
Schematic diagram of ring formation.In order to make the long chain on the ring, the method proposed in this paper is shown in Figure11 (right). Assuming that there is an unused fiber between the end of the long chain and the ring NE, the optimization scheme is to first dismantle the ring and then connect the device at the end of the long chain to the nearest node on the original ring near the root end of the long chain, so that all devices are on the same ring, then connect the NE at the end of the long chain to the original ring NE so that all NEs are on the same ring. The black line in Figure 11 (right) represents the line of the existing service, the red line represents the unused fiber, the red fiber may have multiple, and the black dashed line represents the fiber that needs to be broken in the service after optimization.In the current network, there may not be unused fibers at the end of the long chain and the NEs close to the root end of the long chain. At this time, cannot make all the long chain devices on the ring, only as many NEs as possible can be on the ring. Accounting income refers to the concept of income in accounting. It refers to the difference between the realized income and the corresponding expenses from the company’s transactions during the period. This paper introduces this concept to improve the ring formation rate of the network, calculating the number difference between the newly connected long chain NE and the sacrificing original ring NE as the accounting income, so a ring formation rate optimization scheme based on the NEs accounting income is proposed.In the PTN, each long chain may be located on multiple loops, and each loop has multiple NEs. In the process of calculating the accounting income of the NEs, first, abstract all the loops of the long chain as a graph. Using the depth-first search of the graph, traverse with the cross NE as the starting vertex, and calculate the NE information income between each NE of this long chain and each NE on the graph composed of all loops. The calculation formula for accounting income between long chain NEs and ring NEs is shown in(3)G=L_i−R_j+1,whereG is the accounting income of the NE; L_i is the position of the ith NE from the cross NE on the long chain; R_j is the position of the jth NE from the cross NE on the ring. As shown in Figure 12, the maximum value of L_i is 4, and the maximum value of R_j is 3.Figure 12
Schematic diagram of long chain.Use the above method to calculate the accounting income between the NEs L1, L2, L3, L4, and each NE on the ring, and determine whether there is an optical fiber connection between the two NEs. Assuming that there is an optical fiber between the two NEs L1 and R1, if this optical fiber is used to switch the original service, the connection between the crossover NE and the ring NE R1 needs to be disconnected, and connect the long chain NE L1 to the ring. At this time, the ring NE is not sacrificed, and a long chain NE is connected at the same time. Therefore, the NE accounting income of this optical fiber is 1, which is a positive income. The ring formation rate will increase after the optical fiber is used to switch services. The accounting income between each NE on the long chain and each NE on the ring in Figure12 is shown in Table 1.Table 1
Accounting income statement.
R1R2R3/convergence NE BL1101L2210L3321L4432This article is how to findN available optical fibers and select a line from these N available optical fibers to form the most economical and reliable optimization solution.Specific steps are as follows:Step 1. Determine all long chains that are not on the ring to form a long chain set A.Step 2. Traverse the long chain set A, select one of the long chains, and determine which rings the long chain is connected to.Step 3. Determine the position where the long chain NEs and the ring NEs have optical fiber connections.Step 4. Calculate the accounting income of each fiber and arrange it in descending order.Step 5. Select a fiber with the largest income for service switching to achieve the purpose of increasing the loop rate.Step 6. Return to Step 1 until the end of the traversal.


## 5. Experimental Results

Since the staff did not consider the need to avoid the phenomenon of same active and standby routing when initial configuration of the city’s mobile network, resulting in a large number of LSP same active and standby routing problems in the city’s mobile network, the evaluation results show that same routing rate in one city’s mobile network (number of tunnels on the network that have same route/total number of tunnels) is as high as 24.4%. This paper studies the problem and proposes an optimization algorithm for the same active and standby routing of label switching path based on KSP. Due to unreasonable resource allocation, the CIR bandwidth occupancy rate is too high. The evaluation result shows that the unqualified rate of CIR bandwidth occupancy reaches 19.8%. This paper proposes a method for optimizing the bandwidth occupancy rate of the committed information rate based on the KSP algorithm. Set up the adjacency matrix with each NE in the one city’s mobile network as the node, and whether there is fiber connection between the NEs as the weight. The KSP algorithm is used to search the first 5 paths between the two NEs on the basis of the adjacency matrix. Choose one path that does not cause the same routing as the original active path to replace the original standby path. After optimizing the one city’s mobile network by the above scheme, the same routing rate is reduced to 6.5%, a decrease of 17.9%; its running time is about 30 minutes. Using the KSP algorithm to find other paths between the source and sink NEs passing through the link, part of the tunnel on the link is switched to the path provided by the KSP algorithm, so that the link CIR bandwidth occupancy rate is reduced. After optimizing the CIR of the city’s mobile network based on the above solution, the unqualified rate of CIR bandwidth occupancy is reduced to 5.98%, which is a decrease of 13.82% and the running time is about 19 minutes. Regarding the low looping rate of NEs, the optimization scheme based on accounting income proposed in this paper reduces the nonring rate from the original 34% to 19%, which is a decrease of 15%, and the running time is about 12 minutes.The comparison before and after the experiment is shown in Tables2–4.Table 2
LSP experimental results.
Number of tunnelsNumber of same routesNormal number of same routesSame route rateBefore modify11,2612751851024.4%After modify11,26174010,5126.5%Table 3
CIR experimental results.
Number of linksNumber of CIR failuresCIR failure rateBefore modify358070819.8%After modify35802145.98%Table 4
Ring formation rate experimental results.
Number of NEsNumber of nonring NEsNonring rateBefore modify3000101234%After modify300056519%It shows that the PTN optimization algorithm proposed in this paper is feasible. It can not only reduce the same active and standby routing rate in the network and increase the qualified rate of CIR bandwidth occupation and NE ring formation rate but also improve the utilization rate of network resources and ensure the stability and reliability of the network.


## 6. Conclusion

In order to solve the problem of standby failure caused by the LSP active and standby same routing in the PTN, this paper proposes an LSP active and standby same routing optimization algorithm based on the KSP. It provides a reference for improving the standby efficiency of LSP and reducing the transmission failure in PTN. Aiming at the link with a high CIR bandwidth occupancy rate, this paper proposes an optimization method for the committed information rate bandwidth occupancy rate based on the firstK-shortest path (KSP) algorithm. In order to solve the problem of low ring formation rate in the network, this paper proposed a ring formation rate optimization scheme for PTN access layer equipment based on NEs accounting income. Through this algorithm, we optimized the one city’s mobile PTN and reduced the same routing rate of the city’s network by 17.9%. The CIR bandwidth occupancy rate is reduced by 13.82%. The nonring forming rate was reduced by 15%. The optimization method proposed in this article is also applicable to PTN optimization in other regions. It improved the resource utilization rate of city’s network, further improves the security, stability, and reliability of service transmission in the network, and makes the optimization quality of PTN reach a new level.However, the solution proposed in this paper still has shortcomings. For example, when the number of network elements is small and the idle resources are small, it is difficult for the KSP algorithm to find a suitable path to replace the original path. That is, there is no other available path between the start and end NEs; it still cannot solve the problem of the active and standby same routing, and CIR problem also.



---

*Source: 5495425-2021-10-18.xml*