Submarine Cable System Optimization

海底光纜系統優化

Student thesis: Doctoral Thesis

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Awarding Institution
Supervisors/Advisors
Award date14 Oct 2022

Abstract

Submarine cables are an important part of the Internet infrastructure, carrying more than 99% of the world's international data transmission. Today, submarine cable systems are vital to the global economy and are a driving force for sustainable economic growth worldwide.

The cost of submarine cable construction is currently estimated at around $24,000 per kilometer, resulting in high prices for large-scale submarine cable systems. Investments in submarine cables in the next five years are estimated at about $9.4 billion. Cable path planning does not just seek to minimize the cost of cable, it must consider the cable survivability under various possible events, including earthquakes, heavy fishing activities, and specific legal requirements.

In addition to considering the cost of and risk to cable systems, another important issue for a cable system design is latency. As technology advances, more and more devices and applications are latency-sensitive, requiring stringent Quality of Service (QoS) and low latency, such as high-frequency trading. Therefore, the cable systems serving these applications require low latency, e.g., high-frequency trading, online games, and remote surgery.

Submarine cable path planning and cable system design are currently based on human knowledge and experience. This way cannot guarantee the optimal cable path and cable system. Automated methods can be helpful for manual cable systems design. These methods are based on real data for cable system design on the Earth's surface by an automated procedure to minimize both construction costs and risks while considering the latency requirement between pairs of nodes.

Firstly, we approximate the Earth’s surface as a triangulated manifold in an irregular 2-dimensional (2D) manifold in a 3-dimensional (3D) Euclidean space. We provide an optimized cable path planning solution for a spanning tree-topology network in the triangulated manifold with an application to the planning of submarine cable networks. This solution is based on total cost minimization, where the individual cable costs are assumed to be linear in the length of the corresponding submarine cables, subject to latency constraints between pairs of nodes. These latency constraints limit the cable length between any pair of nodes. Our method combines the Fast Marching Method (FMM) and a new Integer Linear Programming (ILP) formulation for Minimum Spanning Trees (MSTs) where there are constraints between pairs of nodes.

Next, we focus on minimizing the weighted cost of the cable system (cable laying cost, design level, and repair rate) together with additional costs to enhance cable resilience. And incorporates the overall cost of branching units (again including material, construction, and laying) and the choice of submarine cable landing stations, where such a station can be anywhere on the coast in a connected region. These are important issues for the economics of cable laying and significantly change the model and the optimization process. For the problem of designing trunk-and-branch tree topology cable networks, we pose it as a variant of the Steiner tree problem, but one in which the Steiner nodes can vary in number while incurring a penalty. We refer to it as the weighted Steiner node problem. The optimal solution is achieved in polynomial time using dynamic programming. Unlike earlier work, the path planning optimization problem considered here extends to the more realistic provision of region-to-region connectivity.

Then, beyond the ILP problem considered before, we provide an optimized cable path planning solution which we call Lagrangian Fast Marching (LAFM), for the most popular submarine cable system topology, i.e., trunk-and-branch, on the undersea surface of the earth modeled by a triangulated 2D manifold in a 3D Euclidean space. We formulate the problem of a cable system design as a Steiner minimal tree problem, where Steiner nodes model the branching units (BU). Our objective is to minimize the total cost of the cable system; this total cost is defined to include both actual cable and BU costs — including laying — as well as a measure of risk associated with the location and topography. We minimize this total cost while imposing latency constraints limiting the length of cable between specified pairs of nodes. As most BUs in practice are Y-shaped, each Steiner node is assumed to have three branches, in accord once with the theory of Steiner trees, at least in the Euclidean plane. We discuss methodological ideas related to the general problem and provide two algorithms, LAFM I and LAFM II, to solve the constrained optimization problem. We have proved that LAFM I can find the optimal solution for cable systems with one latency constraint. We also show that LAFM II provides a solution with provable bounds for problems with multiple latency constraints. Numerical results show that the LAFM method outperforms the Simulated Annealing algorithm in terms of cable system optimization solutions.

Finally, we illustrate the importance of data density in achieving high-quality submarine cable paths and systems planning. We describe future challenges of obtaining the required level of high-density data to achieve high-quality automated path planning over thousands of kilometers and the challenge of the scalability of the algorithms that use such highly-dense data. Our vision of the mutual interworking and collaboration between cable system designers and software designers of automatic solutions is also presented.

    Research areas

  • Submarine cable system, submarine manifold, Steiner minimal tree, latency constraints, Lagrangian