KMSharing: The Framework and Space Abstraction for Efficient Data Sharing at the Network Edge

Edge storage promises to be crucial for edge computing infrastructure, which enables users to access data within a low delay from widespread storage nodes at the network edge. The key challenge is how to integrate massive geographically distributed weak edge nodes to form an efficient storage system, enabling users to launch data operations from any node or retrieve the desired data across the entire distributed system. To address this data-sharing problem, researchers from both the traditional peer-to-peer (P2P) overlay networking and emerging edge computing fields have proposed some decentralized indexing mechanisms. However, existing studies lack insightful descriptions and analyses about the nature of the data-sharing problem at the network edge. It motivates us to rethink the edge data-sharing framework and provide the problem reformulation for analyzing the limitations of existing schemes. We reveal that the existing data-sharing schemes fail in complex network topologies which can be regarded as high-dimensional network spaces beyond the representation of low-dimensional Euclidean spaces or other existing hash spaces. A better space abstraction is an urgent need to alleviate the performance degradation due to the dimensional mismatch between network spaces and virtual spaces. To fill this gap, this paper proposes the Kautz metric space, a novel space abstraction extended from Kautz graphs, where the coordinates and the metric are defined as Kautz strings and Kautz distances (i.e., the shortest distances in undirected Kautz graphs), respectively. We design a dynamic programming algorithm to directly compute the Kautz distances. Then, we propose KMSharing, an efficient edge data-sharing scheme: both nodes and data are represented in a Kautz metric space, where the Kautz distance of any two Kautz strings reflects the network delay of the corresponding nodes. The workflow of KMSharing consists of three core components: the virtual address allocation represents edge nodes in the Kautz metric space; the data-to-node mapping ensures the uniqueness of target nodes; and forwarding table construction ensures the data delivery. Theoretical analyses confirm that KMSharing ideally achieves <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {O}\left ({{ \tau }}\right)$ </tex-math></inline-formula> network delays, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {O}\left ({{ \log N }}\right)$ </tex-math></inline-formula> overlay hops, and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {O}\left ({{ 1 }}\right)$ </tex-math></inline-formula> forwarding entries in an N-node edge system with the network radius <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\tau $ </tex-math></inline-formula>, while the successive ensuring data delivery. Its worst-case network delay <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {O}\left ({{ \tau \log N }}\right)$ </tex-math></inline-formula> is also much better than <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\mathcal {O}\left ({{ \tau N^{\alpha } }}\right)},\alpha \mathrm {\in }(0,1)$ </tex-math></inline-formula>, the worst case of the baselines using Euclidean spaces. Evaluation on various network topologies also shows that our KMSharing effectively reduces network delays and indexing costs than existing data-sharing schemes.