Topology reconstruction using time series data in telecommunication networks

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

We consider Hybrid fiber-coaxial (HFC) networks in which data is transmitted from a root node to a set of customers using a series of splitters and coaxial cable lines that make up a tree. The physical locations of the components in a HFC network are always known but frequently the cabling is not. This makes cable faults difficult to locate and resolve. In this study we consider time series data received by customer modems to reconstruct the topology of HFC networks. We assume that the data can be translated into a series of events, and that two customers sharing many connections in the network will observe many similar events. This approach allows us to use maximum parsimony to minimize the total number of character-state changes in a tree based on observations in the leaf nodes. Furthermore, we assume that nodes located physically close to each other have a larger probability of being closely connected. Hence, our objective is a weighted sum of data distance and physical distance. A variable-neighborhood search heuristic is presented for minimizing the combined distance. Furthermore, three greedy heuristics are proposed for finding an initial solution. Computational results are reported for both real-life and synthetic network topologies using simulated customer data with various degrees of random background noise. We are able to reconstruct large topologies with a very high precision.
Original languageEnglish
JournalNetworks
Volume83
Issue number2
Pages (from-to)408-427
ISSN0028-3045
DOIs
Publication statusPublished - 2024

Keywords

  • Dynamic programming
  • Maximum parsimony
  • Network reconstruction
  • Phylogenetic trees
  • Telecommunication networks
  • Variable neighborhood search

Fingerprint

Dive into the research topics of 'Topology reconstruction using time series data in telecommunication networks'. Together they form a unique fingerprint.

Cite this