Optimal Tree Topology for a Submarine Cable Network with Constrained Internodal Latency

Abstract

This article provides an optimized cable path planning solution for a tree-Topology network in an irregular 2D manifold in a 3D Euclidean space, with an application in the planning of submarine cable networks. Our solution method is based on total cost minimization, where the individual cable costs are assumed to be linear to 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 (MST) where there are constraints between pairs of nodes. F..