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 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article