Title: A novel graph compression algorithm for data-intensive scientific networks
Authors: Xiao Lin; Haizhou Du; Shenshen Chen
Addresses: Department of Computer Science, School of Electronic and Information Engineering, Tongji University, Shanghai, China ' Department of Computer Science, School of Electronic and Information Engineering, Tongji University, Shanghai, China ' Department of Computer Science, School of Electronic and Information Engineering, Tongji University, Shanghai, China
Abstract: As one of the world's leading scientific and data-intensive computing grids, the worldwide LHC computing grid (WLCG) faces the challenge of improving its computing efficiency and network utilisation. To achieve this goal, WLCG needs an important piece of information: the network topology graphs of participating computing grids. Directly collecting such information from all of the grids, however, would cause high communication overhead and raise many security issues. In this paper, we address these issues by proposing a novel algorithm to compress such a large network topology into a compact, equivalent network topology. We formally define our problem, develop a novel, efficient topology compression algorithm and evaluate its performance using real-world network topologies. Our results show that our algorithm not only achieves a much higher topology compression ratio than state-of-the-art topology transformation algorithms, but also leads to at most 100× reduction in computation time.
Keywords: network topology; data-intensive; compression; shortest path tree; SPT; weighted graph; high performance networking.
DOI: 10.1504/IJHPCN.2019.102348
International Journal of High Performance Computing and Networking, 2019 Vol.14 No.4, pp.425 - 434
Received: 09 Dec 2017
Accepted: 09 Mar 2018
Published online: 23 Sep 2019 *