MCR: Structure-aware overlay-based latency-optimal greedy relay search

Fu, Yongquan; Biersack, Ernst W
IEEE/ACM Transactions on Networking, Vol.25, N°5, October 2017

Geo-distributed network applications typically use relays to process and forward timely messages among clients. The state-of-the-art approaches greedily locate a relay that is closer to clients based on an overlay that favors neighbors in the immediate vicinity of the current node. Unfortunately, as clients are unknown a priori, the optimal relay is generally outside of the immediate vicinity of the current node. Consequently, the search process often terminates at a poor local minimum. In this paper, we address these challenges by designing and implementing a distributed relay-search system called MCR. In order to accurately locate a relay closer to clients, by observing that the latency space exhibits a proximity clustering phenomenon where nodes in the same cluster are typically within close proximity, we propose an overlay called MCRing that is aware of global proximity clusters. In order to scale well under dynamic relays, we maintain the proximity clusters via a gossiping-based clustering process. Furthermore, we propose a series of algorithms to accurately locate a relay that is closer to clients and satisfies the load constraints. We prove that the relay-search process achieves close to optimal results based on a doubling dimension-based analysis in an inframetric model. Finally, extensive evaluation via simulation and PlanetLab experiments shows that MCRing is able to locate near-optimal relays.

Digital Security
Eurecom Ref:
© 2017 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.