Network topology optimisation for data aggregation using multiple paths
Soham Das, Sartaj K. Sahni · International Journal of Metaheuristics · 2015
In this paper, we develop algorithms for the data aggregation problem which arises in the context of big data applications that employ the MapReduce operation. For the case when source racks can send their data to the aggregator using multiple paths, we show that an aggregation tree topology that minimises aggregation time can be constructed in a polynomial time. We also consider the problem of constructing aggregation trees that minimise total network traffic subject to the primary constraints that the aggregation time is minimised. The heuristics for this problem is presented and the experiments show that allowing multiple paths reduces aggregation time by up to 99% related to the aggregation trees constructed using the LPT rule. This reduction in aggregation time, however, comes with up to 35% increase in total network traffic when the racks have more than two optical links and up to 98% increase in total network traffic when each rack has two optical links.