Optimal Path Calculation for Multi-ring Based Packet–Optical Transport Networks

Hyuncheol Kim
Namseoul university, Cheonan, Korea
E-mail: hckim@nsu.ac.kr

Received 26 June 2024; Accepted 13 July 2024

Abstract

Multi-domain optical transport networks are inherently non-interoperable and require integrated orchestration and path provisioning mechanisms at the network-wide level. Moreover, ensuring the network’s survivability is a critical issue. While the MPLS-TP (multi-protocol label switching-transport profile) defines various protection and recovery mechanisms as standards, it does not address methods for calculating and selecting protection and recovery paths. Therefore, an algorithm is needed to calculate and set up paths to ensure quick protection and recovery across the entire integrated network, minimizing conflicts in protection and recovery at the packet optical integrated network level. In this paper, we proposed an algorithm that calculates and sets a path that enables rapid protection and recovery in an MPLS-TP network composed of a multi-ring-mesh topology. To this end, this study proposes the concept of a transparent node (T-node) for calculating link-disjoint SPF (shortest path first) in a multi-ring network with dual or more rings. A T-node is a node in a ring with more than a dual ring and indicates that the node has been used once in route calculation. Therefore, during path calculation, a T-node can be used as a source node and an intermediate node but not as a destination node.

Keywords: MPLS-TP, protection and recovery, optimal path calculation.

1 Introduction

The PTN (packet transport network)/POTN (packet optical transport network) aims to simplify the transport network architecture by integrating traditional transport networks (WDM: wavelength division multiplexing), packet networks, and circuit networks (OTN (optical transport network) and TDM (time division multiplexing) into a single platform, and it is evolving towards an intelligent transport network based on a transport SDN (software defined network). Additionally, with the exponential increase in traffic traversing optical circuit packet integrated networks, ensuring network survivability has become a critical issue. A single failure in the optical fiber or network element (NE) comprising the optical circuit packet integrated network can affect an enormous number of upper-layer sessions. This triggers numerous alarm messages and protection/restoration procedures at the upper layers simultaneously, potentially imposing a significant burden on the network [1, 2].

Furthermore, while the MPLS-TP (multi-protocol label switching-transport profile) defines various protection and recovery mechanisms as standards to ensure network survivability, it does not address methods for calculating and selecting protection and recovery paths. Therefore, an algorithm is needed to calculate and set up paths that can ensure quick protection and recovery across the entire integrated network, minimizing conflicts in protection and recovery at the level of the optical circuit packet integrated network [3–5].

In this paper, we propose an algorithm that calculates and sets a path that enables rapid protection and recovery in an MPLS-TP network composed of a multi-ring-mesh topology. To this end, this study proposes the concept of a transparent node (T-node) for calculating the link-disjoint SPF (shortest path first) in a multi-ring network with dual or more rings. A T-node is a node in a ring with more than a dual ring and indicates that the node has been used once in route calculation. Therefore, during path calculation, a T-node can be used as a source node and an intermediate node but not as a destination node.

2 Multi-Protocol Label Switching – Transport Profile

• Fault management: MPLS-TP includes tools for rapid fault detection and isolation, such as continuity check (CC), connectivity verification (CV), and remote defect indication (RDI). These tools enable operators to identify and address faults quickly, thereby minimizing service interruptions.

• Performance monitoring: Operators continuously monitor performance metrics such as frame loss, delay, and delay variation to ensure compliance with QoS parameters. This monitoring helps proactively manage network performance and address issues before they affect end-users.

• Loopback and link trace: Loopback functions test the bidirectional integrity of paths, while link trace procedures help map packets’ paths through the network. These diagnostic tools are essential for troubleshooting and ensuring the correct configuration of network paths.

• Alarm suppression and aggregation: MPLS-TP supports alarm suppression and aggregation mechanisms to prevent alarm flooding. These features ensure network operations enhance efficiency by raising and managing only pertinent alarms.

2.1 Protection and Recovery Mechanisms

The MPLS-TP incorporates advanced protection and recovery mechanisms to ensure high network availability and resilience. These mechanisms are designed to minimize service disruption in the event of network failures and include [9–11]:

• 1+1 Protection: In 1+1 protection, identical traffic is sent over two disjoint paths simultaneously. The receiving node continuously monitors both paths and selects the better-quality signal. This method offers near-instantaneous failover, typically within 50 milliseconds, ensuring minimal service interruption.

• 1:1 Protection: This approach involves primary and secondary (backup) paths. Under normal conditions, traffic flows over the primary path, but it switches to the backup path if a failure occurs. This method balances bandwidth efficiency with rapid recovery times.

• Ring protection: The MPLS-TP supports ring topologies, which are common in metro and access networks. Ring protection mechanisms, such as ITU-T G.8032 ethernet ring protection switching (ERPS), enable fast traffic rerouting within the ring in the event of a failure, ensuring high availability.

• Path and segment recovery: MPLS-TP allows end-to-end path recovery and segment recovery. This granularity in recovery options enables precise fault isolation and minimizes the impact on unaffected network segments, enhancing overall network robustness.

Figure 1 Typical PTN/POTN network architecture and traffic flow.

3 Proposed Link Disjoint SPF

Typically, the PTN/POTN consists of local networks connecting to regional networks via point-to-point links centered around dual mesh backbone networks (Backbone 1/2), as illustrated in Figure 1. In such configurations, the node-disjoint SPF calculation assumes that all network rings are structured as a single ring, thus failing to reflect multi-ring architecture. Simply excluding nodes in a multi-ring structure where a single node has multiple links results in deleting all links in both directions. Consequently, the node disjoint SPF calculation method calculates an SPF path dividing north and south, as shown in Figure 2.

Furthermore, node disjoint SPF is not the shortest path in the strict sense. For instance, consider calculating the node SPF between nodes s $^{'}$ and d3 $^{'}$ in Figure 2. In this case, the ring SPF becomes B-H-C, and s $^{'}$ first finds the shortest path to f and h, the interconnect nodes of ring B-H, and the path between s $^{'}$ -f is selected. Subsequently, to prevent node duplication, the node-disjoint SPF method deletes all links related to node h, such as f-h, g-h, and h-t. Therefore, following s $^{'}$ -e-f, d-b-i-k-m-o-q-s-u, and u-w-y-d $^{'}$ 3 become the node disjoint SPF.

Figure 2 Problem with node disjoint SPF calculation.

However, if the link disjoint regulation is applied instead of the node disjoint condition, the two disjoint links between f and h can be used in the path calculation. For instance, if backbone ring one establishes the path f-h-t in Figure 2, then backbone ring two can establish the path h-t-u. Consequently, path costs can be significantly lower than node-disjoint SPF, achieving the actual minimum cost for shortest path calculation. This study introduces the concept of transparent nodes (T-nodes) for the link-disjoint SPF calculation in multi-ring networks. A T-node is a node in a ring with more than a dual ring and indicates that the node has been used once in route calculation. Therefore, T-nodes can be used as source and intermediate nodes when calculating a route but cannot be used as destination nodes.

3.1 Proposed Two-Link Disjoint SPF Calculation

The two-link disjoint SPF refers to two paths that do not share any links except for the source and destination nodes. The path calculation method may vary depending on the source-destination location when calculating a two-node disjoint SPF.

1. Traffic within the local network (as illustrated in Figure 1 (1))

2. Traffic between local networks via metro networks (as illustrated in Figure 1 (2))

3. Inter-local network traffic via backbone/metro networks (as illustrated in Figure 1 (3).

To calculate the two-link disjoint SPF, proceed in the following order. This sequence ensures the calculation of two effective link-disjoint SPFs, optimizing network resilience and performance.

1. Determine the ring SPF.

2. Filter out the rings that are not part of the ring SPF.

3. If the ring SPF traverses the backbone network, divide the network into two segments based on the backbone: ‘source node to backbone access node’ and ‘destination node to backbone access node.’ Calculate the paths within these segments.

4. Determine the shortest path (e.g., SPF) to the access node to the second ring (backbone ring) constituting the ring SPF. In this case, the metric value is based on link speed, bandwidth, remaining bandwidth, link utilization, and node sharing.

5. Select this path as part of the first link disjoint SPF.

6. From the identified access node in the backbone, calculate the shortest path to the next ring’s access node.

7. Add the path as part of the link disjoint SPF.

8. Change all nodes belonging to the path to T-nodes. A T-node can be used as a source or transit node but not as a destination node.

9. From the current access node, calculate the shortest path to either the next ring’s access node or the destination node.

10. Add the path as part of the link disjoint SPF.

11. Repeat steps 9 and 10 until reaching the ring that includes the destination node.

12. Filter out all links used in the path.

13. If the ring SPF traverses the backbone network, connect the backbone access nodes within the calculated two paths to form the final route.

The process of calculating the link-disjoint SPF between s $^{'}$ and d3 $^{'}$ in Figure 3 follows. The rings to which the source node s $^{'}$ and destination node d3 $^{'}$ belong are determined as B and F, respectively. Consequently, the ring SPF between rings B and F, as shown in Figure 4, is B-H-F. They filter out the remaining rings that are not part of B, H, and F, which results in the network configuration depicted in Figure 5.

Next, calculate the shortest path from the source node (s $^{'}$ ) in the first ring (B) of the ring SPF to the interconnect nodes (f or h) in the second ring (H) of the ring SPF. In this case, the s $^{'}$ -e-f path becomes the shortest path with cost 3. The cost of all other possible paths from s $^{'}$ to f or h is greater than 3. Therefore, as shown in Figure 5 (1), the path s $^{'}$ -e-f is selected as part of the first node SPF.

Figure 3 Link disjoint SPF between s $^{'}$ -d3 $^{'}$ – initial network.

Figure 4 Ring SPF for calculating the s $^{'}$ -d3 $^{'}$ path.

Figure 5 Link disjoint SPF between s $^{'}$ -d3 $^{'}$ – initial stages.

Subsequently, select the next set of rings on the ring SPF, namely H and F, as shown in Figure 5. Choose f as the starting node for ring H and calculate the shortest path to the interconnect nodes (q or s) between rings H and F. As shown in Figure 5 (2), the shortest path identified is f-h-t-u-s with a cost of 6. Furthermore, f-h-t-u-s becomes the next part of the node disjoint SPF following s $^{'}$ -e-f.

Figure 6 Link disjoint SPF between s $^{'}$ -d3 $^{'}$ – final stages.

Subsequently, change all nodes belong to the path to T-nodes, as shown in Figure 6 (3). A T-node can be used as a source or transit node but not as a destination node. Following this, compute the shortest path for s-d3 $^{'}$ , as shown in Figure 6 (4). The shortest path identified is s-t-y-d3 $^{'}$ with a cost of 6. Also, s-t-y-d3 $^{'}$ becomes the last part of the link disjoint SPF.

Figure 7 Second link disjoint SPF between s $^{'}$ -d3 $^{'}$ .

Afterward, as shown in Figure 7, to calculate the second link disjoint SPF, the first link disjoint SPF, s $^{'}$ -e-f-h-t-u-s-t-y-d3 $^{'}$ path, is filtered. To calculate the second link disjoint SPF, first, an interconnect node (first calculate the shortest path to f or h). As shown in Figure 7 (1), the s $^{'}$ -d1 $^{'}$ -g-h path becomes the shortest path with cost 6. The cost of all other possible paths from s $^{'}$ to f or h is greater than 6. Therefore, the path s $^{'}$ -d1 $^{'}$ -g-h is selected as part of the second link SPF. Afterward, the shortest path from node h to the interconnect nodes q and s of ring F is calculated. In this case, because s is a T-node, it cannot be selected as the destination node, so the shortest path between h-q is found.

The shortest path between h-q is h-t-u-s-q, and the cost is 6. The T-node h is the source node, and T-nodes t, u, and s are used as transit nodes. Therefore, the f-h, h-t, t-u, and t-s sections are sections where the link disjoint SPF is set using all dual links. Finally, find the shortest path in the q-d3 $^{'}$ section as shown in Figure 7 (3). The shortest path in the q-d3 $^{'}$ section is q-r-d3 $^{'}$ , and the cost is 3. Figure 7 shows that the final second link disjoint SPF becomes s $^{'}$ -d1 $^{'}$ -g-h-t-u-s-q-r-d3 $^{'}$ .

Figure 8 Calculation of the link disjoint path via the backbone network.

Figure 8 illustrates the method for calculating the path (s $^{'}$ -d3 $^{'}$ ) via the backbone network. Calculating a path via the backbone network involves three main steps: first, obtaining the node-disjoint SPF up to (s $^{'}$ -i or h) as depicted in Figure 8 (1), second, obtaining the node-disjoint SPF up to (d3 $^{'}$ -k or p) as shown in Figure 8 (2), and third, connecting (i or h) with (k or p) to bridge the regional and backbone networks. These nodes serve as access points linking the regional networks with the backbone.

Using the previously described method for obtaining node-disjoint SPFs, we first establish the node-disjoint SPF up to (s $^{'}$ -i or h). This results in the path s $^{'}$ -a-c-i depicted in Figure 8 (1). Similarly, obtaining the node-disjoint SPF up to (d3 $^{'}$ - k or p) yields the path d3 $^{'}$ -j-n-k shown in Figure 8 (2). Finally, combining the s $^{'}$ -a-c-i path with the d3 $^{'}$ -j-n-k path via the backbone network connection allows for linking i and k, as illustrated in Figure 8 (3). Therefore, the final node-disjoint SPF for (s $^{'}$ -d3 $^{'}$ ) is s $^{'}$ -a-c-i-k-n-j-d3 $^{'}$ .

4 Conclusion

The MPLS-TP stands out as a robust, scalable, and reliable transport technology that meets the demanding requirements of modern carrier-grade networks. Its architecture, enriched with comprehensive OAM capabilities and sophisticated protection and recovery mechanisms, ensures high service availability and operational efficiency. While the MPLS-TP (multi-protocol label switching-transport profile) defines various protection and recovery mechanisms as standard, it does not address methods for calculating and selecting protection and recovery paths. In this paper, we proposed an algorithm that calculates and sets a path that enables rapid protection and recovery in an MPLS-TP network composed of a multi-ring-mesh topology. To this end, this study proposes the concept of a transparent node (T-node) for calculating the link disjoint SPF (shortest path first) in a multi-ring network with dual or more rings. A T-node is a node in a ring with more than a dual ring and indicates that the node has been used once in route calculation. Therefore, during path calculation, a T-node can be used as a source node and an intermediate node but not as a destination node.

Acknowledgments

Funding for this paper was provided by Namseoul University.

References

[1] S. Waleed, M. Faizan, M. Iqbal and M. I. Anis, Demonstration of Single Link Failure Recovery using Bellman Ford and Dijkstra Algorithm in SDN, pp. 0–30.

[2] L. Yang, D. Li and dan R. Tan, “Research on the Shortest Path Solution Method of Interval Valued Neutrosophic Graphs Based on the Ant Colony Algorithm”, IEEE Access, vol. 8, pp. 88717–88728, 2020.

[3] S. Khan, S. Anjum, U. A. Gulzari, T. Umer and B. S. Kim, “Bandwidth-Constrained Multi-Objective Segmented Brute-Force Algorithm for Efficient Mapping of Embedded Applications on NoC Architecture”, IEEE Access, vol. 6, pp. 11242–11254, 2017.

[4] W. Xia, C. Di, H. Guo and dan S. Li, “Reinforcement Learning Based Stochastic Shortest Path Finding in Wireless Sensor Networks”, IEEE Access, vol. 7, pp. 157807–157817, 2019.

[5] Y. Li, Z. L. Zhang and dan D. Boley, “From shortest-path to all-path: The routing continuum theory and its applications”, IEEE Trans. Parallel Distrib. Syst., vol. 25, no. 7, pp. 1745–1755, 2014.

[6] C. W. Ahn dan and R. S. Ramakrishna, “A genetic algorithm for shortest path routing problem and the sizing of populations”, IEEE Trans. Evol. Comput., vol. 6, no. 6, pp. 566–579, 2002.

[7] O. Cosma, P. C. Pop and dan I. Zelina, “An effective genetic algorithm for solving the clustered shortest-path tree problem”, IEEE Access, vol. 9, pp. 15570–15591, 2021.

[8] M. K. M. Ali dan and F. Kamoun, Neural Networks for Shortest Path Computation and Routing in Computer Networks, vol. 4, no. 6, 1993.

[9] M. Huynh, S. Goose, P. Mohapatra and dan R. Liao, “RRR: Rapid Ring Recovery Submillisecond Decentralized Recovery for Ethernet Ring”, IEEE Trans. Comput., vol. 60, no. 11, pp. 1561–1570, 2011.

[10] M. Tsubokawa, “Reliability Evaluation for Distributed PONs with Ring and Tree Topologies”, IEEE/OSA J. Opt. Commun. Network, vol. 4, no. 10, pp. 790–798, 2012.

[11] Q. E. Muftikhali, A. Y. Danar, A. Kusumawati and dan S. Hidayat, “Algoritma Genetika dalam Menentukan Rute Optimal Topologi Cincin pada WAN”, J. Teknol. Inf. dan Ilmu Komput., vol. 4, no. 1, pp. 62, 2017.

Biography

Hyuncheol Kim received his Ph.D. degree in the Department of Information Engineering from Sungkyunkwan University, Korea, in 2005. From 1992 to 2002, he was senior engineer in Electronics and Telecommunications Research Institute (ETRI), Daejon, Korea. He has been a professor in the Department of Computer Science in Namseoul University, Korea. His research interests include cloud computing, next generation network and embedded computing systems.