Research On Placement Of Proxies For Hierarchical Reliable Multicast

The use of proxies for local error recovery and congestion control is a scalable technique used to overcome a number of well-known problems in reliable multicast. The idea is that the multicast tree is partitioned into subgroups that form a hierarchy rooted at the source, hence the term Hierarchical Reliable Multicast (HRM). For each subgroup, there is a designated node, called proxy, which is responsible for collecting the feedback from receivers in the subgroup and locally retransmitting the lost packets. The performance of this approach strongly depends on the appropriate partition of the tree and the selection of proxies.In this paper, we focus on the issue of placement proxies for HRM to minimize the bandwidth required for data transfer from a single source to a number of receivers. We achieve our goal by minimizing the number of total link transmissions required for a packet to arrive all receivers correctly. We start by presenting a HRM model with assumptions. Then, we define and compute related performance metrics and study the impact of placement of proxies on reduction of the number of total link transmissions. Further, we convert our goal into an equivalent of maximizing the reduction in the number of total link transmissions incurred by the placement of proxies. We propose an algorithm to attack the problem of optimal partition of a subtree rooted at a proxy to maximize the reduction, achieving an optimal solution for placement of a single proxy. Based on this algorithm, we finally propose our proxy placement algorithm designed in a greedy fashion. It offers optimal solution based on current circumstance and achieves a global suboptimal solution by several local optimal solutions. Simulation results demonstrate that the performance of our algorithm is very close to that of the current best algorithm, and outperforms other heuristic. Moreover, it has a significant benefit in the tradeoff between performance and complexity.