Research Of Flash Dissemination Based On Topology Awareness And Unbiased Sampling

Data dissemination under the Internet environment aims to send data to many nodes across the wide area networks, which is studied and applied in many fields. Flash dissemination, as one paradigm of data dissemination, sends medium-size data to heterogeneous nodes, with the demands of high bandwidth and low end-to-end latency. Flash dissemination is one of future key enabling techniques in many fields, e.g. emergence response, information battlefields. With the help of recent success of overlay techniques, flash dissemination can be practical, by taking advantage of self-organization and high scalability of overlays. However, overlays exhibit distinct characteristics, e.g. heterogeneous and dynamic, which have brought many challenges for flash dissemination. Based on requirements of flash dissemination, this thesis deeply study three basic services for flash dissemination based on overlays, i.e. overlay topology-awareness, overlay sampling and efficient data transfer under heterogeneous and selfish nodes, separately but coherently. The results are listed as follows:Topology-awareness techniques can be used to construct efficient overlays with low latency stretch, and consequently reduce network latencies of the data dissemination process. Network coordinates have been shown to predict the physical network latencies, scalably and reasonably accurately. However, network coordinates must be adaptive and fault-resilient to cope with the heterogeneous and dynamic nature of nodes. This thesis proposes Cocast, a network coordinate prediction anycast service for topology-awareness. Firstly, Cocast provides an anycast-query scheme to forward nodes' requests. Secondly, Cocast adopts a hierarchical network embedding mechanism to predict nodes' coordinates. Thirdly, Cocast synthesizes coordinate predictions by a coordinate fusion filter. Analysis and simulations show that compared with current typical methods, e.g. GNP and Vivaldi, Cocast can distribute anycast-message overhead scalably, be resilient to adversary attacks, predict network coordinates at a faster convergence speed, and adapt to nodes' incremental queries.Overlay sampling, by selecting typical nodes of an overlay, can improve the dynamic adaptations of the overlay and optimize the data transfer paths. Random walks on unstructured overlays can efficiently sample typical nodes. However, to get volumes of uniform-random samples, random-walk based sampling methods need to be scalable and unbiased. Firstly, this thesis formally proves that, with Naive and Metropolis-Hastings methods, even neighboring nodes in the overlay may have large differentiations on forwarding random walk message costs. Then we propose SMARW, a sampling method based on multi-peer adaptive random walk. SMARW adopts a MPRW algorithm to receive tunable number of samples. Besides, SMARW applies an adaptive random walk adjustment process to increase the convergence rate of the unbiased sampling process. Detailed theorical analysis and performance evaluation confirm that SMARW has near-optimal load balancing capability, O(logN) convergence speed for adjustment process, and a higher degree of unbiased sampling level.By efficiently taking full use of heterogeneity of nodes, data transfer techniques can optimize system-wide throughputs, and improve the fairness of the download-bandwidth allocation. Meanwhile, flash dissemination needs to efficiently differentiate heterogeneous and selfish nodes, for the sake of improving system-wide throughputs. By introducing capacity-differentiation for topology construction process and rate control mechanism, this thesis presents CORE, a capacity-differentiation multicast based on resilient network coding. Firstly, CORE adopts an adaptive layering topology construction mechanism based on capacity-differentiation. Secondly, CORE maintains a histogram based flow control scheme for the data transfer process with network coding. Thirdly, CORE applies a distributed rate control algorithm for the fairness of the capacity-differentiation based download-bandwidth allocation. Fourthly, CORE detects and disconnects adversary nodes by incrementally encoded block verification at predefined check points. Analysis and simulations confirm that CORE can efficiently utilize nodes upload capacities, ensure pareto-optimal capacity-differentiation based download-bandwidth allocation, increase system-wide throughputs, and disconnect with adversaries at a low computation overhead. Thus, CORE can support efficient flash dissemination under heterogeneous network environments.