Minimizing Wait Latency in Periodic P2P Hypercube Gossiping
Philipp Berndt · 2012
Owed to its regular structure and rich interweaving, facilitating simple and efficient dissemination and aggregation of data, the hypercube is an effective and popular interconnection network for parallel and distributed computing. Its short paths make it suitable for latency critical real-time applications such as live streaming or estimation of system state vectors, including object tracking or real-time business intelligence. However, latency not only depends on the communication complexity of the network topology and network delay but also on the scheduling of each node's periodic transmissions, referred to as timing mode. Existing timing modes targeting the reduction of latency in periodic hypercube gossiping are limited to node local optimization. In this paper, we investigate a novel global wait latency minimization approach named Crossing Mode. To this end, we analyze the conditions that induce wait latency in its predecessor Chained Mode and show how the problem of determining optimal transmission times can be reduced to a mixed integer linear programming (MILP) problem. For evaluation, we integrated Crossing Mode into a P2P emulator. Results show a reduction of mean wait latency by 35% and more. Yet with growing network sizes, the effort of solving the MILP problem becomes impracticable.