SCIENCE@home

Graph Filter: Enabling Efficient Topology Calibration

Lailong Luo,Deke Guo,Jia Xu,Xueshan Luo

Published 2019 in IEEE Transactions on Parallel and Distributed Systems

ABSTRACT

The topology of a network may change inevitably, due to dynamic behaviors of nodes and links, and failures of hardware and software. Many protocols and applications must be aware of the up-to-date topology of the underlying network. This triggers the topology calibration problem, which means to deduce those different nodes and links between two topologies. The Bloom filter and its variants are efficient to represent and calibrate two general sets. They, however, fail to represent all links and nodes in a topology simultaneously, and thus remain inapplicable to the topology calibration problem. In this paper, we design the graph filter, a novel space-efficient data structure to record not only the node set but also the link set of any given topology. Accordingly, given two topologies we aim to represent them via two respective graph filters, and thereafter deduce those different links in an invertible manner. To this end, we design three essential operations for graph filter, i.e., encoding, subtracting and decoding. Although such operations are sufficient to solve the topology calibration problem, two challenging issues still remain open. First, the XOR traps which occur with low probability at the encoding stage may result in a few miscalculations at the decoding stage. Thus, we propose another augmented decoding algorithm to lessen the impact of XOR traps via terminating illegal decodings. Second, several different links may form cycles in the worst case; hence, we further design a cycle destruction algorithm to make such different links decodable. We implement the graph filter and the associated topology calibration method. Comprehensive evaluations indicate that our method finishes the topology calibration task efficiently with high probability, incurs the least space overhead, and supports invertible decoding reasonably.

PUBLICATION RECORD

  • Publication year

    2019

  • Venue

    IEEE Transactions on Parallel and Distributed Systems

  • Publication date

    2019-12-01

  • Fields of study

    Computer Science, Engineering

  • Identifiers
    DOI 10.1109/TPDS.2019.2925001
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-29 of 29 references · Page 1 of 1

CITED BY