Premium
Compression and expansion in graphs using overlays
Author(s) -
Khan Bilal,
Bhutani Kiran R.
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20411
Subject(s) - overlay network , overlay , computer science , computer network , scalability , distributed computing , bandwidth (computing) , network topology , node (physics) , the internet , engineering , structural engineering , database , world wide web , programming language
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. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 58(1), 36–42 2011