Performance Modeling of Tree Based Overlay Networks

As high-performance systems continue to expand in power and size, scalable mechanisms 
for communication and processing are required. In such contexts, many popular frameworks 
such as MapReduce, MPI and MRNet provide scalable data reduction operations to help to 
fulfill the performance requirements of large-scale distributed systems. The topology 
structures to handle this aggregation may consist simply of a single level with children 
connecting directly to the destination node or may comprise more complex tree topologies. 
Despite their prevalence, the techniques for modeling data aggregation in these tree-based 
overlay networks (TBON) are lacking. This paper addresses this need by introducing an 
extension to the LogP framework specifically targeted at TBON-based data aggregation. Our 
model adheres to the simplicity of the LogP model but leverages structural insights to 
provide a simple yet precise performance estimate. Additionally, our model makes no 
assumptions of the underlying Network Interface Card (NIC) transfer mechanisms or uniformity 
of tree breadth, making it suitable for a wide range of environments. To evaluate our model, 
we compare it to the traditional LogP model for predicting the performance of the Multicast 
Reduction Network (MRNet) framework. We then show how our model can be used to derive 
communication cost for a production tool, the Stack Trace Analysis Tool (STAT).