1 Network Topology Inference Based on Timing Meta-Data

2025-04-24 0 0 3.67MB 22 页 10玖币

侵权投诉

Network Topology Inference Based on Timing

Meta-Data

Wenbo Du, Member, IEEE, Tao Tan, Haijun Zhang, Senior Member, IEEE,

Xianbin Cao, Senior Member, IEEE, Gang Yan, Member, IEEE,

and Osvaldo Simeone, Fellow, IEEE

Abstract

Consider a processor having access only to meta-data consisting of the timings of data packets and

acknowledgment (ACK) packets from all nodes in a network. The meta-data report the source node of

each packet, but not the destination nodes or the contents of the packets. The goal of the processor is to

infer the network topology based solely on such information. Prior work leveraged causality metrics to

identify which links are active. If the data timings and ACK timings of two nodes – say node 1 and node

2, respectively – are causally related, this may be taken as evidence that node 1 is communicating to node

2 (which sends back ACK packets to node 1). This paper starts with the observation that packet losses

can weaken the causality relationship between data and ACK timing streams. To obviate this problem, a

new Expectation Maximization (EM)-based algorithm is introduced – EM-causality discovery algorithm

(EM-CDA) – which treats packet losses as latent variables. EM-CDA iterates between the estimation

This work was supported in part by the National Key Research and Development Program of China under Grant

2019YFF0301400, in part by the National Natural Science Foundation of China under Grant 61961146005, in part by the

Shuohuang Railway Project under Grant GJNY-19-90. The work of O. Simeone was supported by the European Research

Council (ERC) under the European Union’s Horizon 2020 Research and Innovation Programme (Grant Agreement No. 725731)

and by an EPSRC Open Fellowship.

W. Du, T. Tan and X. Cao are with the School of Electronic and Information Engineering, Beihang University, Beijing

100191, China, with the Key Laboratory of Advanced Technology of Near Space Information System (Beihang University).

(e-mail: wenbodu@buaa.edu.cn; tantao@buaa.edu.cn; xbcao@buaa.edu.cn).

H. Zhang is with Beijing Engineering and Technology Research Center for Convergence Networks and Ubiquitous Services,

University of Science and Technology Beijing, Beijing, China, 100083 (e-mail: haijunzhang@ieee.org).

G. Yan is with School of Physics Science and Engineering, Tongji University, Shanghai 200092, China (e-mail: ee-

gyan@gmail.com).

O. Simeone is with the King’s Communications, Learning, and Information Processing (KCLIP) Laboratory, Department of

Engineering, King’s College London, London WC2R 2LS, U.K. (e-mail: osvaldo.simeone@kcl.ac.uk).

arXiv:2210.05439v1 [eess.SP] 11 Oct 2022

of packet losses and the evaluation of causality metrics. The method is validated through extensive

experiments in wireless sensor networks on the NS-3 simulation platform.

Index Terms

Network topology inference, meta-data, causality metrics, packet loss, expectation maximization.

I. INTRODUCTION

A. Motivation and Overview

Information about the topology of a device-to-device wireless network, e.g., a sensor network,

is essential to implement functionalities such as routing, anomaly detection, and load balance.

In recent years, passive monitoring methods that leverage only observations of network trafﬁc

have received signiﬁcant attention, owing to their cost-effectiveness as compared to active

methods that probe nodes for information [1], [2]. Passive monitoring methods can be “invasive”,

implementing packet inspection techniques like demodulation and decryption [3]; or “non-

invasive”, leveraging only meta-data. Invasive methods can achieve high accuracy, but they

require complex sensors and baseband processors. Non-invasive techniques have the advantage

of requiring only information about the timings of data packet and acknowledgement (ACK)

packets, which is relatively easier to collect and process (see Fig. 1). This paper contributes to

the line of work on passive, non-invasive, network topology estimation.

Fig. 1. An example of a wireless device-to-device network with a set of nodes N={1,2,3,4,5}and a set of directional

links L={(2,1),(3,1),(3,2),(4,3),(4,5)}. The central monitor collects meta-data from the nodes in the form of data and

acknowledgment (ACK) packet timings, based on which it aims to estimate the network topology. Unlike previous work [4],

[5], this paper allows for packet losses, making it more challenging to interpret and use meta-data.

To elaborate, consider, as in Fig. 1, a processor having access only to meta-data consisting of

the timings of data packets and ACK packets from all nodes in a network. The meta-data report

the source node of each packet, but not the destination nodes or the contents of the packets.

The goal of the processor is to infer the network topology based solely on such information.

Reference [6] proposed to leverage causality metrics to identify which links are active. The key

underlying idea is that, if the data timings and ACK timings of two nodes – say node 1 and node

2, respectively – are causally related, this may be taken as evidence that node 1 is communicating

to node 2 (which sends back ACK packets to node 1). The same principle underpins network

discovery in ﬁelds as diverse as biology and sociology [7]–[10].

The causality discovery algorithm (CDA) introduced in [6] was based on Granger causality,

a measure of causal dependence based on auto-regressive modelling [11]. Asymmetric Granger

causality was used in [4], which outperforms GCT at a ﬁner time resolution. Transfer Entropy

(TE) was then adopted for CDA in [5]. TE has the advantage of capturing also non-linear

causality relationships [12]–[14].

This paper starts with the observation that packet losses can weaken the causality relationship

between data and ACK timing streams. To obviate this problem, a new Expectation Maximization

(EM)-based algorithm is introduced – EM-causality discovery algorithm (EM-CDA) – which

treats packet losses as latent variables.

B. Related Work

Active probing is a traditional method used in wireless topology inference, whereby informa-

tion is collected from neighboring nodes [15], [16]. In such methods, a subset of “privileged”

nodes usually performs the probing task [17]. While these schemes can potentially infer accu-

rately the functional network without location information, the energy cost associated with active

methods is a critical drawback.

As for passive schemes, references [18], [19] exploit spectral coherence to infer the network

topology, but this approach tends to detect spurious links. In [20], [21], multivariate Hawkes

processes, a parametric formulation of packet arrival statistics, is considered to recover the

network topology. These solutions are model-based, and hence operate under strict assumptions

on the valid of the model. CDA-based passive topology inference methods currently provide

state-of-the-art results for passive topology inference. Apart from the papers reviewed in the

previous subsection, the authors of [22] leverage blind source separation to improve the problem

caused by interference. The work [23] considers an equidistant missing-data problem based on

Granger causality. Nonetheless, the problem of missing observations caused by packet loss is

still an open issue, which can result in a signiﬁcant drop in inference accuracy [4]–[6], [24].

C. Main Contributions

Addressing the need for passive topology inference techniques that are robust to packet losses,

this paper introduces EM-CDA. The main contributions of this paper can be summarized as

follows.

•We formulate the problem of network topology inference as the maximum likelihood

problem of estimating existing network links in the presence of latent variables representing

packet losses. EM-CDA is derived as a tractable approximation of the resulting EM

algorithm. Accordingly, EM-CDA iterates between the estimation of packet losses and

the evaluation of causality metrics based on the estimated missing packets.

•EM-CDA is validated through experiments in the wireless network on the NS-3 simulation

platform, demonstrating that EM-CDA can improve the detection probability and false

alarm probability rate of CDA ranging from 4% to 12% under a variety of practical

conditions.

The rest of this paper is organized as follows. The wireless network scenario and system

model are described in Section II. The state-of-the-art causality discovery algorithm (CDA) for

wireless network topology inference is presented in Section III. EM-CDA scheme is introduced

in Section IV. In Section V, numerical results are given to demonstrate the performance of the

proposed algorithm. Finally, the paper is concluded in Section VI.

II. SYSTEM MODEL AND PROBLEM SETUP

In this section, we describe the setting under study in which, as illustrated in Fig. 1, a central

monitor collects meta-data about packet timings from the nodes of a network in order to infer

the network topology. In this paper, unlike [4], [5], we allow packet losses to occur on the

communication links. This creates additional challenges in relating the timings of data and

control (acknowledgment) packets, motivating the novel estimation algorithm introduced in the

next section.

A. Setting

Consider the problem of estimating the topology of a network consisting of a set N=

{1,2, ..., N}of Nnodes and of a set L=(i, j)i, j ∈ N of M≤N(N−1) directional links.

The presence of a link (i, j)∈ L with i, j ∈ N and i6=jindicates that node icommunicates

with node j.

As in [4], [5], we assume that a central monitor collects meta-data in the form of transmission

timestamps reporting the time instants at which data packets or acknowledgments (ACKs) are

sent by each node within a given time window. Only timing meta-data is collected, and hence the

monitor is only aware of packet timings, and not of the intended destination of any given packet.

Successful transmission of a data packet from one node to another causes the transmission of

an ACK from the receiving node to the transmitting one. ACKs are assumed to be much shorter

than data packets and not subject to data losses.

B. Data Transmission and Channel Model

The observation period Tis discretized into Kequal time slots of duration Ts=T/K, which

are indexed by integer k∈ K ={1,2, ..., K}. To describe the timing information recorded by

node i∈ N , two integer-valued time sequences YD

i[k]and YA

i[k]are introduced, corresponding

to data packets and ACKs, respectively. The data packet timing sample YD

i[k]equals the number

of data packets sent by node iin time slot k. In a similar way, the timing information sample

i[k]for ACK packets equals the number of ACK packets sent by node iin time slot k. We

collect the data timing information across all time slots for node iin the K×1vector

i=YD

i[1], Y D

i[2], ..., Y D

i[K]T,(1)

and the ACK timing information in the K×1vector

i=YA

i[1], Y A

i[2], ..., Y A

i[K]T.(2)

The data and ACK timing series for node ican be expressed as the sum of individual

contributions corresponding to the distinct communication links stemming from node i. To

elaborate, we deﬁne the per-link binary sequences

i,j [k] = 





1if a data packet is sent on link (i, j)in time slot k,

0otherwise,

(3)

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1NetworkTopologyInferenceBasedonTimingMeta-DataWenboDu,Member,IEEE,TaoTan,HaijunZhang,SeniorMember,IEEE,XianbinCao,SeniorMember,IEEE,GangYan,Member,IEEE,andOsvaldoSimeone,Fellow,IEEEAbstractConsideraprocessorhavingaccessonlytometa-dataconsistingofthetimingsofdatapacketsandacknowledgment(ACK)packetsf...

展开>> 收起<<

1 Network Topology Inference Based on Timing Meta-Data.pdf

共22页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

1 Network Topology Inference Based on Timing Meta-Data

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: