| Application Layer Multicast (ALM) has attracted more and more research community's attention due to the increasing prevalence of group communication applications in the Internet and the hardness in the deployment of IP multicast. While the migration of multicast function from routers to hosts has the potential to address most problems associated with IP multicast, it also faces many new challenges. In an ALM tree, when a parent node quits or fails, all its descendent nodes must adjust their locations, which leads to the interruption of multicast connections. This problem is called stability problem of ALM, and it may impact the continuity of multicast data transmission and then degrade user experience severely. Therefore, it is necessary to improve the quality of ALM service by enhancing the stability. This thesis focuses on the design of approaches to enhancing the stability of ALM.In this thesis, we first analyze the root causes for the stability problem and propose the criterion for evaluating the stability of ALM. We analyze the factors which affect the ALM stability. The factors include the node leaving frequency, the affected region of node leaving event, and the time used to recover ALM tree after node leaves. Accordingly, we categorize the techniques to enhance the stability of ALM into three classes: reducing the node leaving frequency, reducing the affected region of node leaving event, and shortening the time used to recover ALM tree after node leaves. Based on the classification, all the techniques of stability enhancement are overviewed and compared. Aiming at addressing some of shortcomings in current techniques, this thesis makes an in-depth study on the techniques of enhancing the stability of ALM. The remaining contributions of the thesis are as follows.The key to the performance of ALM is the construction algorithm for multicast tree. However, the current research has not given a clear definition of the problem with the goal of optimizing the stability of ALM. To define this problem clearly, we propose the Instantaneous Stability Degree Model (ISDM), which characterizes the stability of ALM tree in a moment of multicast session and defines the criterion to evaluate the instantaneous stability of ALM tree. An approach that takes advantage of the statistical properties of member's join-leave behavior is proposed to evaluate the relative leaving probability of ALM node. Based ISDM, the DDSD (the Degree- and Delay-bounded maximum Stability Degree ALM tree) problem and its degenerated DSD (the Delay-bounded maximum Stability Degree ALM tree) problem are presented and proved to be NP-Hard. Therefore, we propose two kinds of algorithms which include a centralized algorithm (DDSD-H) and a distributed algorithm (DSD-D). Our simulations demonstrate that our proposed algorithms can efficiently reduce the average affected region of node leaving event during the whole ALM session. Node failure detection is the prerequisite of the recovery of partitioned multicast tree caused by node failures. And the performance of failure detection is critical to shorten the time used to recover ALM tree. We can use two measures to improve the performance of failure detection, one is to design efficient failure detection scheme, and the other is to optimize the approach to configuring the parameter for failure detection scheme. For the former, we propose a Cooperative-Probe based failure detection Scheme (CPS), in which the detecting ring of each node is formed by its parent node and child nodes. The information about probe loss is shared among the nodes in each detecting ring. For the later, as the current parameter configuration approaches are difficult to adapt to the diversity with respect to the performance requirements, we propose a node-impact-degree based parameter configuration model. Then a Hierarchical Parameter Configuration (HPC) approach is proposed by applying the model. By utilizing the HPC approach to configuring parameter appropriately, CPS can reduce both the detecting time and the probability of false positive.Usually, once the node failures are detected, the remaining process of reconstructing ALM tree is the same as the one after node quitting. And quickening the reconstruction process of ALM tree is important to shorten the time used to recover ALM tree after node leaves. The proactive policy is effective in reconstructing ALM tree compared to reactive policy, but all the current studies are limited in the context of unstructured ALM tree. Therefore, we extend the proactive policy to ALM tree which is based on Chord DHT and propose a backup-path scheme with which each node pre-calculates a backup path for itself. When the non-leaf node leaves, all its child nodes can switch to the respective backup path immediately. Moreover, we develop the ChordM-FR protocol, which is derived from Chord and adopts the backup-path scheme. Our simulations demonstrate that the ChordM-FR can reconstruct ALM tree about 2.5 times faster on average than the ChordM-SR which adopts the reactive policy in reconstructing multicast tree.The proxy-based ALM is a technique to enhance stability of ALM by reducing the node leaving frequency and reducing the affected region of node leaving event. However, in the traditional ALM forwarding process, if end-host is to send data packets to N different receivers, then the N copies of each packet have to be sent from host memory to Network Interface Card (NIC) buffer, making poor use of the limited bandwidth and computing resource. To address this problem, we propose a hardware-based multicast forwarding scheme, by which the CPU overhead and the number of times that data packets are copied from host memory to NIC buffer are reduced dramatically. Theoretical analysis indicates that the new scheme can notably decrease the multicast delay and improve the service capability of ALM proxies. We modified the NIC driver and added some corresponding APIs to network protocol stack to implement the proposed scheme. Experimental results show the feasibility and validity of this scheme.
|
PDF Full Text Request