On the Optimal Monitor Placement for Inferring Additive Metrics of Interested Paths

Rongwei Yang; Cuiying Feng; Luning Wang; Weiwei Wu; Kui Wu; Jianping Wang; Yinlong Xu

doi:10.1109/INFOCOM.2018.8486423

On the Optimal Monitor Placement for Inferring Additive Metrics of Interested Paths

Rongwei Yang, Cuiying Feng, Luning Wang, Weiwei Wu, Kui Wu, Jianping Wang, Yinlong Xu

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

13 Citations (Scopus)

Abstract

In the "network-as-a-service" paradigm, network operators have a strong need to know the metrics of critical paths running services to their users/tenants. However, it is usually prohibitive to directly measure the metrics of all such paths due to the measuring overhead. A practical solution is to use network tomography to infer the metrics of such paths based on observations from a small number of monitoring nodes. This problem is termed as path identifiability problem, a new problem that largely differs from existing link identifiability problems. we show that the new problem is harder than link identifiability problems, in the sense that fewer monitors are required for identifying the metrics of given paths than for identifying the metrics of links along the paths. To solve the problem, we develop sufficient and necessary conditions for the identifiability of a given set of interested paths, and design an efficient algorithm that deploys the minimum number of monitors. Experiments show a saving of up to 40% fewer monitors that guarantee the identifiability of a given set of paths.

Original language	English
Title of host publication	IEEE INFOCOM 2018
Subtitle of host publication	IEEE Conference on Computer Communications
Publisher	IEEE
Pages	2141-2149
Volume	2018-April
ISBN (Print)	9781538641286
DOIs	https://doi.org/10.1109/INFOCOM.2018.8486423
Publication status	Published - Apr 2018
Event	37th IEEE International Conference on Computer Communications (IEEE INFOCOM 2018) - Honolulu, United States Duration: 15 Apr 2018 → 19 Apr 2018 http://infocom2018.ieee-infocom.org/ http://infocom2018.ieee-infocom.org/program/main-technical-program

Publication series

Name	IEEE Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM
Publisher	IEEE
ISSN (Print)	0743-166X

Conference

Conference	37th IEEE International Conference on Computer Communications (IEEE INFOCOM 2018)
Country/Territory	United States
City	Honolulu
Period	15/04/18 → 19/04/18
Internet address	http://infocom2018.ieee-infocom.org/ http://infocom2018.ieee-infocom.org/program/main-technical-program

Research Keywords

Communication Network
Monitor Placement
Network Tomography

Access Output

10.1109/INFOCOM.2018.8486423

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Yang, R., Feng, C., Wang, L., Wu, W., Wu, K., Wang, J., & Xu, Y. (2018). On the Optimal Monitor Placement for Inferring Additive Metrics of Interested Paths. In IEEE INFOCOM 2018: IEEE Conference on Computer Communications (Vol. 2018-April, pp. 2141-2149). Article 8486423 (IEEE Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM). IEEE. https://doi.org/10.1109/INFOCOM.2018.8486423

@inproceedings{f8fa24430d70425f8c158041e0b97971,

title = "On the Optimal Monitor Placement for Inferring Additive Metrics of Interested Paths",

abstract = "In the {"}network-as-a-service{"} paradigm, network operators have a strong need to know the metrics of critical paths running services to their users/tenants. However, it is usually prohibitive to directly measure the metrics of all such paths due to the measuring overhead. A practical solution is to use network tomography to infer the metrics of such paths based on observations from a small number of monitoring nodes. This problem is termed as path identifiability problem, a new problem that largely differs from existing link identifiability problems. we show that the new problem is harder than link identifiability problems, in the sense that fewer monitors are required for identifying the metrics of given paths than for identifying the metrics of links along the paths. To solve the problem, we develop sufficient and necessary conditions for the identifiability of a given set of interested paths, and design an efficient algorithm that deploys the minimum number of monitors. Experiments show a saving of up to 40% fewer monitors that guarantee the identifiability of a given set of paths.",

keywords = "Communication Network, Monitor Placement, Network Tomography",

author = "Rongwei Yang and Cuiying Feng and Luning Wang and Weiwei Wu and Kui Wu and Jianping Wang and Yinlong Xu",

year = "2018",

month = apr,

doi = "10.1109/INFOCOM.2018.8486423",

language = "English",

isbn = "9781538641286",

volume = "2018-April",

series = "IEEE Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM",

publisher = "IEEE",

pages = "2141--2149",

booktitle = "IEEE INFOCOM 2018",

address = "United States",

note = "37th IEEE International Conference on Computer Communications (IEEE INFOCOM 2018) ; Conference date: 15-04-2018 Through 19-04-2018",

url = "http://infocom2018.ieee-infocom.org/, http://infocom2018.ieee-infocom.org/program/main-technical-program",

}

Yang, R, Feng, C, Wang, L, Wu, W, Wu, K , Wang, J & Xu, Y 2018, On the Optimal Monitor Placement for Inferring Additive Metrics of Interested Paths. in IEEE INFOCOM 2018: IEEE Conference on Computer Communications. vol. 2018-April, 8486423, IEEE Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM, IEEE, pp. 2141-2149, 37th IEEE International Conference on Computer Communications (IEEE INFOCOM 2018), Honolulu, Hawaii, United States, 15/04/18. https://doi.org/10.1109/INFOCOM.2018.8486423

On the Optimal Monitor Placement for Inferring Additive Metrics of Interested Paths. / Yang, Rongwei; Feng, Cuiying; Wang, Luning et al.
IEEE INFOCOM 2018: IEEE Conference on Computer Communications. Vol. 2018-April IEEE, 2018. p. 2141-2149 8486423 (IEEE Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - On the Optimal Monitor Placement for Inferring Additive Metrics of Interested Paths

AU - Yang, Rongwei

AU - Feng, Cuiying

AU - Wang, Luning

AU - Wu, Weiwei

AU - Wu, Kui

AU - Wang, Jianping

AU - Xu, Yinlong

PY - 2018/4

Y1 - 2018/4

N2 - In the "network-as-a-service" paradigm, network operators have a strong need to know the metrics of critical paths running services to their users/tenants. However, it is usually prohibitive to directly measure the metrics of all such paths due to the measuring overhead. A practical solution is to use network tomography to infer the metrics of such paths based on observations from a small number of monitoring nodes. This problem is termed as path identifiability problem, a new problem that largely differs from existing link identifiability problems. we show that the new problem is harder than link identifiability problems, in the sense that fewer monitors are required for identifying the metrics of given paths than for identifying the metrics of links along the paths. To solve the problem, we develop sufficient and necessary conditions for the identifiability of a given set of interested paths, and design an efficient algorithm that deploys the minimum number of monitors. Experiments show a saving of up to 40% fewer monitors that guarantee the identifiability of a given set of paths.

AB - In the "network-as-a-service" paradigm, network operators have a strong need to know the metrics of critical paths running services to their users/tenants. However, it is usually prohibitive to directly measure the metrics of all such paths due to the measuring overhead. A practical solution is to use network tomography to infer the metrics of such paths based on observations from a small number of monitoring nodes. This problem is termed as path identifiability problem, a new problem that largely differs from existing link identifiability problems. we show that the new problem is harder than link identifiability problems, in the sense that fewer monitors are required for identifying the metrics of given paths than for identifying the metrics of links along the paths. To solve the problem, we develop sufficient and necessary conditions for the identifiability of a given set of interested paths, and design an efficient algorithm that deploys the minimum number of monitors. Experiments show a saving of up to 40% fewer monitors that guarantee the identifiability of a given set of paths.

KW - Communication Network

KW - Monitor Placement

KW - Network Tomography

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

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85056156957&origin=recordpage

U2 - 10.1109/INFOCOM.2018.8486423

DO - 10.1109/INFOCOM.2018.8486423

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9781538641286

VL - 2018-April

T3 - IEEE Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM

SP - 2141

EP - 2149

BT - IEEE INFOCOM 2018

PB - IEEE

T2 - 37th IEEE International Conference on Computer Communications (IEEE INFOCOM 2018)

Y2 - 15 April 2018 through 19 April 2018

ER -

Yang R, Feng C, Wang L, Wu W, Wu K , Wang J et al. On the Optimal Monitor Placement for Inferring Additive Metrics of Interested Paths. In IEEE INFOCOM 2018: IEEE Conference on Computer Communications. Vol. 2018-April. IEEE. 2018. p. 2141-2149. 8486423. (IEEE Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM). doi: 10.1109/INFOCOM.2018.8486423

On the Optimal Monitor Placement for Inferring Additive Metrics of Interested Paths

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this