Compression and expansion in graphs using overlays

Bilal Khan, Kiran R. Bhutani

Research output: Contribution to journalArticle

Abstract

In this article, we describe how to construct physical computer network topologies, which can support the establishment of overlays that reduce or increase the distances between nodes. Reducing pairwise distances (i.e., compression) implies that the overlay enjoys significantly lower inter-node latencies compared to the ambient physical network; such an overlay can be used to implement a "high-performance mode" for disaster situations in which network responsiveness is of critical importance. On the other hand, increasing pairwise distances (i.e., expansion) implies that the overlay exhibits significantly higher internode latencies compared to the ambient physical network; such an overlay can be used to implement a brief "dilated state" in networks that have been infected by a malicious worm, where slowing down the infection spread allows greater time for antidote generation. We show that it is possible to design physical networks which support overlays whose logical link bandwidth is equal to the physical link bandwidth while providing arbitrarily high compression or expansion. We also show that it is possible to "grow" such networks over time in a scalable way, that is to say, it is possible to retain the compression/expansion properties while augmenting the network with new nodes, by making relatively small adjustments to the physical and overlay network structure.

Original languageEnglish (US)
Pages (from-to)36-42
Number of pages7
JournalNetworks
Volume58
Issue number1
DOIs
StatePublished - Aug 2011

Keywords

  • compression
  • diameter
  • expansion
  • graphs embeddings
  • overlays

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Compression and expansion in graphs using overlays'. Together they form a unique fingerprint.

  • Cite this