[DMO] Siv Sørensen: Topology reconstruction using time series data in telecommunication networks

05 April 2023 14:00 till 15:00 - Location: EEMCS Lecture Hall F | Add to my calendar

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 general (non-binary) 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 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 customer data with various degrees of background noise, showing that we are able to reconstruct the topology with a very high precision.