Several organizations have built multiple datacenters connected via dedicated wide area networks over which large inter-datacenter transfers take place. This includes tremendous volumes of bulk multicast traffic generated as a result of data and content replication. Although one can perform these transfers using a single multicast forwarding tree, that can lead to poor performance as the slowest receiver on each tree dictates the completion time for all receivers. Using multiple trees per transfer each connected to a subset of receivers alleviates this concern. The choice of multicast trees also determines the total bandwidth usage. To further improve the performance, bandwidth over dedicated inter-datacenter networks can be carved for different multicast trees over specific time periods to avoid congestion and minimize the average receiver completion times. In this paper, we break this problem into the three sub-problems of partitioning, tree selection, and rate allocation. We present an algorithm called QuickCast which is computationally fast and allows us to significantly speed up multiple receivers per bulk multicast transfer with control over extra bandwidth consumption. We evaluate QuickCast against a variety of synthetic and real traffic patterns as well as real WAN topologies. Compared to performing bulk multicast transfers as separate unicast transfers, QuickCast achieves up to @math reduction in mean completion times while at the same time using @math the bandwidth. Also, QuickCast allows the top @math of receivers to complete between @math to @math faster on average compared with when a single forwarding multicast tree is used for data delivery.
Various techniques have been proposed to make multicasting reliable including the use of coding and receiver (negative or positive) acknowledgments. Experiments have shown that using positive ACKs does not lead to ACK implosion for medium scale (sub-thousand) receiver groups @cite_58 . TCP-XM @cite_37 allows reliable delivery by using a combination of IP multicast and unicast for data delivery and re-transmissions. MCTCP @cite_57 applies standard TCP mechanisms for reliability. Another approach is for receivers to send NAKs upon expiration of some inactivity timer @cite_19 . NAK suppression has been proposed to address implosion which can be applied by routers @cite_7 . Forward Error Correction (FEC) has been used to reduce re-transmissions @cite_19 and improve the completion times @cite_13 examples of which include Raptor Codes @cite_38 and Tornado Codes @cite_52 . These techniques can be applied complementary to QuickCast.
@cite_38 @cite_37 @cite_7 @cite_52 @cite_57 @cite_19 @cite_58 @cite_13
2120679453 1539914100 2161342511 2537090207 2240045799 2162111441
In recent years, much work has been done on attempting to scale multicast data transmission to hundreds or thousands of receivers. There are, however, many situations where an application might involve transmission to just ten or twenty sites. Using multicast for this type of application can provide significant benefits including reduced load on the transmitter an overall reduction in network traffic, and consequently shorter data transfer times. In this project, we are investigating how partial or incomplete multicast can be exploited alongside reliable unicast to improve both speed and efficiency of data transfers while maintaining reliability. The approach taken is to combine unicast with multicast by modifying TCP to support multicast transfers, and run this modified TCP engine over UDP as a userspace transport protocol. We describe the work to date on the design and implementation, and provide experimental results from our tests across both local and wide area networks. This paper presents a novel loss recovery scheme, active reliable multicast (ARM), for large scale reliable multicast. ARM is "active" in that routers in the multicast tree play an active role in loss recovery. Additionally, ARM utilizes soft-state storage within the network to improve performance and scalability. In the upstream direction, routers suppress duplicate NACKs from multiple receivers to control the implosion problem. By suppressing duplicate NACKs, ARM also lessens the traffic that propagates back through the network, In the downstream direction, routers limit the delivery of repair packets to receivers experiencing loss, thereby reducing network bandwidth consumption. Finally, to reduce wide-area recovery latency and to distribute the retransmission load, routers cache multicast data on a "best effort" basis. ARM is flexible and robust in that it does not require all nodes to be active, nor does it require any specific router or receiver to perform loss recovery. Analysis and simulation results show that ARM yields significant benefits even when less than half the routers within the multicast tree can perform ARM processing. The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe an ideal, fully scalable protocol for these applications that we call a digital fountain. A digital fountain allows any number of heterogeneous clients to acquire bulk data with optimal efficiency at times of their choosing. Moreover, no feedback channels are needed to ensure reliable delivery, even in the face of high loss rates.We develop a protocol that closely approximates a digital fountain using a new class of erasure codes that for large block sizes are orders of magnitude faster than standard erasure codes. We provide performance measurements that demonstrate the feasibility of our approach and discuss the design, implementation and performance of an experimental system. Continuously enriched distributed systems in data centers generate much network traffic in push-style one-to-many group mode, raising new requirements for multicast transport in terms of efficiency and robustness. Existing reliable multicast solutions, which suffer from low robustness and inefficiency in either host-side protocols or multicast routing, are not suitable for data centers. In order to address the problems of inefficiency and low robustness, we present a sender-initiated, efficient, congestion-aware and robust reliable multicast solution mainly for small groups in SDN-based data centers, called MCTCP. The main idea behind MCTCP is to manage the multicast groups in a centralized manner, and reactively schedule multicast flows to active and low-utilized links, by extending TCP as the host-side protocol and managing multicast groups in the SDN-controller. The multicast spanning trees are calculated and adjusted according to the network status to perform a better allocation of resources. Our experiments show that, MCTCP can dynamically bypass the congested and failing links, achieving high efficiency and robustness. As a result, MCTCP outperforms the state-of-the-art reliable multicast schemes. Moreover, MCTCP improves the performance of data replication in HDFS compared with the original and TCP-SMO based ones, e.g., achieves 101 and 50 improvements in terms of bandwidth, respectively. This document describes the messages and procedures of the Negative- ACKnowledgment (NACK) Oriented Reliable Multicast (NORM) Protocol. This protocol is designed to provide end-to-end reliable transport of bulk data objects or streams over generic IP multicast routing and forwarding services. NORM uses a selective, negative acknowledgment mechanism for transport reliability and offers additional protocol mechanisms to allow for operation with minimal a priori coordination among senders and receivers. A congestion control scheme is specified to allow the NORM protocol to fairly share available network bandwidth with other transport protocols such as Transmission Control Protocol (TCP). It is capable of operating with both reciprocal multicast routing among senders and receivers and with asymmetric connectivity (possibly a unicast return path) between the senders and receivers. The protocol offers a number of features to allow different types of applications or possibly other higher level transport protocols to utilize its service in different ways. The protocol leverages the use of FEC-based repair and other IETF reliable multicast transport (RMT) building blocks in its design. Scalable reliable multicast protocols have been the focus of recent research, tackling the problem of efficient reliable data delivery to an arbitrarily large number of receivers. Yet, the common applications of multicast, such as multi-point file delivery, or video streaming from a media server, typically only involve a moderate number of receivers, such as a thousand or fewer. Moreover, because of the limited deployment of these specialized multicast protocols, it is common, when feasible, for applications to use multiple TCP connections instead, one for each receiver, to implement multi-point delivery, causing a significant demand on the transmission server and the downstream links. We describe a multicast extension to TCP, called single-source multicast optimization (SMO), that optimizes this case of multipoint delivery, providing the benefits of multicast together with the familiar features and API of TCP. Our results from experiments based on a Linux implementation and performed on a testbed show that TCP-SMO requires just a modest extension to the TCP implementation and provides scalable performance of multicast up to over a thousand receivers, thereby satisfying the common case requirements. In addition, used with TCP-RTM (real-time mode), TCP-SMO also supports real-time multimedia multicast applications well.