چندپخشی قابل اطمینان سلسله مراتبی: تجزیه و تحلیل عملکرد و جایگذاری بهینه پروکسی

This paper studies the use of multicast together with proxy nodes for reliably disseminating data from a single source to a large number of receivers. In order to achieve reliability, data must be retransmitted in case of loss either by the source or by special network nodes, called proxies. Each proxy is responsible for reliably delivering the data to a subgroup it is assigned. The multicast tree is partitioned into subgroups that form a hierarchy rooted at the source, hence the term hierarchical reliable multicast. The performance of this approach strongly depends on the topology and the loss characteristics of the underlying tree and the location of proxies. In the first part of the paper, we study the processing and bandwidth performance of such a reliable multicast dissemination given the tree and the placement of proxies. In the second part of the paper, we develop dynamic programming algorithms that give a placement of a fixed number of proxies on an arbitrary tree that minimizes the bandwidth used for reliable transfer. The first algorithm provides an optimal solution to the multicast proxies location problem in polynomial time, in the number of nodes and proxies. The second is an approximation algorithm that gives a solution with cost within a chosen precision from the optimal, in an improved running time. An optimal and an approximate solution are also provided for the proxies location problem if unicast is used for transmissions. Applications of this dynamic programming approach to related problems are discussed.

Data dissemination applications such as the distribution of newspapers or multimedia component, as well as the updates of stock quotes, software and web caches require reliable data transfer from one source to many receivers of potentially huge number and wide geographical distribution. In this paper, we study the use of multicast for serving such one-to-many applications. IP multicast naturally fits such applications by constructing the multicast routing tree that allows the source to reach all receivers. The well-known strengths of IP multicast are that it saves network bandwidth by duplicating the packets only where it is necessary and that it allows for dynamic membership in a way transparent to the source. However, IP multicast provides only a best effort delivery, while applications do have reliability requirements. A large number of reliable multicast (RM) protocols have been developed in the last decade mainly for the purpose of ensuring reliability at the transport layer and also for ensuring some congestion control in the network, issues similar to those addressed by TCP. In this paper, we focus on the reliability aspect. Receivers send feedback about whether they received the data packets or not and the source retransmits the packets until all receivers get them. RM protocols face a number of well-known problems, inherent to the nature of the one-to-many communication model, especially for large numbers of receivers. Feedback implosion occurs when large groups send feedback without duplicate suppression, thus unnecessarily wasting bandwidth, overwhelming the source with processing and increasing the latency in the delivery of data. Another inherent problem is the exposure [21] (also called the crying baby problem [7]): parts of the tree that experience high loss, expose the rest of the tree to unnecessary retransmissions. The drop-to-zero problem occurs when receivers with poor capabilities force the rest of the group to adjust at the slowest rate. One successful approach that deals with the above problems is the hierarchical proxies approach, which we call hierarchical reliable multicast(HRM). This approach partitions the multicast delivery tree into subgroups that form a hierarchy rooted at the source. Each subgroup has a representative, called proxy, which keeps copies of data packets, collects the feedback from the receivers in the subgroup and locally retransmits the packets, if needed. Feedback implosion is limited because each proxy handles a smaller size of subgroup. Limiting the feedback and the retransmissions locally saves bandwidth and limits the exposure of the good parts of the tree. The recovery latency is reduced as repairs come from a proxy located close to the point of loss. Large numbers of receivers may join the group in this hierarchical scalable way. The performance of such hierarchical schemes, strongly depends on the underlying tree topology and its loss characteristics, and on the selection of proxies. In this paper, we study two problems: the performance evaluation of a tree given a placement of proxies and the optimal placement of proxies. The structure of the rest of the paper is as follows. In Section 2 we discuss work in this area and how our work relates to it. In Section 3 we present our model for HRM. The performance evaluation of an entire multicast tree is reduced to evaluating the performance of every subgroup, in Section 4. The performance measures considered are the work at the source (Section 4.1) and the network bandwidth (Section 4.2) needed for reliable transfer. Section 5 studies the optimal placement of a fixed number of proxies on the multicast tree in order to minimize a total bandwidth measure, for multicast and unicast transmissions in 5.1 and 5.2, respectively. In Section 5.1(1), we give an algorithm that provides an optimal placement for the multicast problem. In Section 5.2(2), we give an approximation algorithm for the multicast problem too. An example of the approximation algorithm using a realistic topology and MBONE measurements is given in Section 5.3(3). Also algorithms to find both the optimal and an approximation are given in Section 5.2 for the unicast case. Possible applications of the dynamic programming approach to related problems are discussed in Section 5.3. Section 6 concludes the paper.

In this paper, we studied the Hierarchical Reliable Multicast problem. In the first part of the paper we partitioned an entire group into subgroups and evaluated the performance of each subgroup in terms of two appropriate measures. In the second part, we studied the problem of optimal placement of proxies in order to minimize a bandwidth cost function. An optimal and an approximation algorithm were given for both the multicast and the unicast problem. We focused on the multicast case, which had not been solved before as an optimization problem. We also applied our algorithm on a realistic example obtained from MBONE measurements. We outlined how our approach can be applied to a variety of related problems.