PAINT: Path Aware Iterative Network Tomography for Link Metric Inference

Leyang Xue, Mahesh K. Marina, Geng Li, Kai Zheng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Understanding link-level performance is key to assuring the quality of cloud-based and OTT services, optimal path selection, robust network operations and beyond. However, direct measurement of each link not only incurs high overhead at the Internet-scale but also is infeasible due to lack of access to network measurement information beyond AS boundaries and functional limitations at relay nodes. Although network tomography is well suited, existing approaches are insufficient due to their unrealistic assumptions with respect to stability, controllability, and visibility. Motivated by this, we propose PAINT, an online iterative algorithm that estimates and refines link-level performance metrics based on path-level measurement. In PAINT, the link metrics are iteratively estimated by minimizing their least square error (LSE) and calibrated based on the comparison of weight between the estimated shortest paths (SPs) and best-known paths from end-to-end path measurements. The key insight is that when there is inconsistency between these paths, then weights of links on the estimated SP are likely misestimated, triggering a further round of estimation to refine the estimated link metrics. Evaluation of PAINT, focusing on link delay estimation, using four different real network topologies and two real-world measurement datasets (including one we collected) shows that relative to existing approaches, it yields up to 3x gain in absolute link delay estimation accuracy and improves decisions dependent on link delay estimation by up to 5x in relative error.
Original languageEnglish
Title of host publicationProceedings of the 30th IEEE International Conference on Network Protocols
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages12
ISBN (Electronic)978-1-6654-8234-9
ISBN (Print)978-1-6654-8235-6
Publication statusPublished - 14 Nov 2022
EventThe 30th IEEE International Conference on Network Protocols - Lexington, United States
Duration: 30 Oct 20222 Nov 2022
Conference number: 30

Publication series

NameIEEE International Conference on Network Protocols (ICNP)
ISSN (Print)1092-1648
ISSN (Electronic)2643-3303


ConferenceThe 30th IEEE International Conference on Network Protocols
Abbreviated titleICNP 2022
Country/TerritoryUnited States
Internet address


Dive into the research topics of 'PAINT: Path Aware Iterative Network Tomography for Link Metric Inference'. Together they form a unique fingerprint.

Cite this