Enhanced Tube-Based Sampling for Accurate Network Distance Measurement with Minimal Sampling Scheduling Overhead

The surge in demand for latency-sensitive services has propelled network distance measurement to the forefront of networking research. Utilizing the low-rank structure of full network data, the tensor completion method can efficiently estimate network distance from partially sampled distance data measured from a small set of node pairs. However, its performance is affected by sampling algorithm limitations, including unreliability and high overhead in dynamic networks. To tackle these challenges, we propose tube-based sampling as an alternative to point-based sampling, utilizing a partition-based algorithm to incorporate randomness for improved reliability. Additionally, we introduce a Tube Length Identification Algorithm to dynamically adjust tube length based on network status, balancing scheduling overhead reduction with estimation accuracy. Experimental results on three real network distance datasets, compared against 13 baseline algorithms, demonstrate the high accuracy and low scheduling overhead of our approach.

I. Introduction

As network applications continue to flourish, the demand for latency-sensitive services is on the rise. Many internet applications require shorter delays, such as overlay routing, peer-to-peer file sharing, and content delivery networks. These stringent requirements have thrust the accuracy of network distance measurement into a critical spotlight. Network distance, typically gauged by the round-trip times (RTT) between two nodes, is vital for optimizing the performance of various applications. For instance, in a Content Delivery Network (CDN), having precise network distance information for all node pairs enables the system to direct users to the nearest server, ensuring the fastest possible access to content.