Communication Network Topology Inference via Transfer Entropy

Pranay Sharma, Donald J. Bucci, Swastik K. Brahma, Pramod Kumar Varshney

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

In this work, we consider the problem of inferring links in a communication network, using limited, passive observations of network traffic. Our approach leverages transfer entropy (TE) as a metric for quantifying the strength of the automatic repeat request (ARQ) mechanisms present in next-hop routing links. In contrast with existing approaches, TE provides an information-theoretic, model-free approach that operates on externally available packet arrival times. We show, using discrete event simulation of a wireless sensor network, that the TE based topology inference approach described here is robust to varying degrees of connection quality in the underlying network. Compared to an existing approach which uses the linear regression based formulation of Granger Causality for network topology inference, our approach has better asymptotic time complexity, and shows significant improvement in network reconstruction performance. Our approach, though sub-optimal, also has better time complexity compared to a causation entropy based optimal algorithm proposed in the literature.

Original languageEnglish (US)
JournalIEEE Transactions on Network Science and Engineering
DOIs
StateAccepted/In press - Jan 1 2019

Fingerprint

Telecommunication networks
Entropy
Topology
Discrete event simulation
Linear regression
Wireless sensor networks

Keywords

  • causal inference
  • communication networks
  • Granger Causality
  • network topology inference
  • Transfer entropy

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Computer Networks and Communications

Cite this

Communication Network Topology Inference via Transfer Entropy. / Sharma, Pranay; Bucci, Donald J.; Brahma, Swastik K.; Varshney, Pramod Kumar.

In: IEEE Transactions on Network Science and Engineering, 01.01.2019.

Research output: Contribution to journalArticle

@article{8b078ea36335453dadaebbfd67db5850,
title = "Communication Network Topology Inference via Transfer Entropy",
abstract = "In this work, we consider the problem of inferring links in a communication network, using limited, passive observations of network traffic. Our approach leverages transfer entropy (TE) as a metric for quantifying the strength of the automatic repeat request (ARQ) mechanisms present in next-hop routing links. In contrast with existing approaches, TE provides an information-theoretic, model-free approach that operates on externally available packet arrival times. We show, using discrete event simulation of a wireless sensor network, that the TE based topology inference approach described here is robust to varying degrees of connection quality in the underlying network. Compared to an existing approach which uses the linear regression based formulation of Granger Causality for network topology inference, our approach has better asymptotic time complexity, and shows significant improvement in network reconstruction performance. Our approach, though sub-optimal, also has better time complexity compared to a causation entropy based optimal algorithm proposed in the literature.",
keywords = "causal inference, communication networks, Granger Causality, network topology inference, Transfer entropy",
author = "Pranay Sharma and Bucci, {Donald J.} and Brahma, {Swastik K.} and Varshney, {Pramod Kumar}",
year = "2019",
month = "1",
day = "1",
doi = "10.1109/TNSE.2018.2889454",
language = "English (US)",
journal = "IEEE Transactions on Network Science and Engineering",
issn = "2327-4697",
publisher = "IEEE Computer Society",

}

TY - JOUR

T1 - Communication Network Topology Inference via Transfer Entropy

AU - Sharma, Pranay

AU - Bucci, Donald J.

AU - Brahma, Swastik K.

AU - Varshney, Pramod Kumar

PY - 2019/1/1

Y1 - 2019/1/1

N2 - In this work, we consider the problem of inferring links in a communication network, using limited, passive observations of network traffic. Our approach leverages transfer entropy (TE) as a metric for quantifying the strength of the automatic repeat request (ARQ) mechanisms present in next-hop routing links. In contrast with existing approaches, TE provides an information-theoretic, model-free approach that operates on externally available packet arrival times. We show, using discrete event simulation of a wireless sensor network, that the TE based topology inference approach described here is robust to varying degrees of connection quality in the underlying network. Compared to an existing approach which uses the linear regression based formulation of Granger Causality for network topology inference, our approach has better asymptotic time complexity, and shows significant improvement in network reconstruction performance. Our approach, though sub-optimal, also has better time complexity compared to a causation entropy based optimal algorithm proposed in the literature.

AB - In this work, we consider the problem of inferring links in a communication network, using limited, passive observations of network traffic. Our approach leverages transfer entropy (TE) as a metric for quantifying the strength of the automatic repeat request (ARQ) mechanisms present in next-hop routing links. In contrast with existing approaches, TE provides an information-theoretic, model-free approach that operates on externally available packet arrival times. We show, using discrete event simulation of a wireless sensor network, that the TE based topology inference approach described here is robust to varying degrees of connection quality in the underlying network. Compared to an existing approach which uses the linear regression based formulation of Granger Causality for network topology inference, our approach has better asymptotic time complexity, and shows significant improvement in network reconstruction performance. Our approach, though sub-optimal, also has better time complexity compared to a causation entropy based optimal algorithm proposed in the literature.

KW - causal inference

KW - communication networks

KW - Granger Causality

KW - network topology inference

KW - Transfer entropy

UR - http://www.scopus.com/inward/record.url?scp=85059465008&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85059465008&partnerID=8YFLogxK

U2 - 10.1109/TNSE.2018.2889454

DO - 10.1109/TNSE.2018.2889454

M3 - Article

AN - SCOPUS:85059465008

JO - IEEE Transactions on Network Science and Engineering

JF - IEEE Transactions on Network Science and Engineering

SN - 2327-4697

ER -