Institut National des Télécommunications
9, rue Charles Fourier, 91011 EVRY, France.
Reliable multicast, Application Layer Multicast, protocol design, overlay tree construction, adaptive congestion avoidance
In this seminar we present our work on the design and implementation of a reliable multicast service using Application Layer Multicast. Our objectives are twofold: (1) To improve the efficiency and performance of peer-to-peer applications which transmit the same data to multiple remote sites; (2) to overcome the problems related to the use of IP multicast faced by similar reliable multicast protocols.
This work consists of two main tasks: (1) A protocol which forwards a data stream reliably over a multicast tree spanning endsystems and using only unicast network primitives; (2) a tree building block which calculates and deploys an optimal reliable multicast tree. The REALM protocol consists of a core protocol logic that ensures reliability, scalability and fairness, and an orthogonal tree building block that calculates and deploys a multicast tree that maximizes reliable data throughput. The core REALM protocol attempts to achieve three primary properties: reliability, scalability and fairness. Reliability refers to ensuring that each receiver receives the sender data stream in-order and error-free. The main challenges to overcome in ensuring reliability are network losses and volatile endsystems that forward data in the multicast tree. Scalability refers to a highly localized mechanism of data loss recovery and the use of a rapid, distributed recovery mechanism in the event of node failure(s). Fairness refers to ensuring a TCP-like congestion avoidance mechanism, and ensuring that slower branches in the tree are not flooded by the demands of faster branches.
In this seminar we describe the re-use of TCP, a distributed loss recovery buffer, desirable multicast tree properties and an end-to-end flow control algorithm which are the primary mechanisms enabling the REALM protocol to achieve these properties. The tree building block is given the responsibility of calculating and deploying the multicast tree. It operates independently from the core protocol logic and consists of a tree calculation algorithm and a protocol for automated tree deployment. We have analyzed reliable multicast transfer properties and developed a novel Maximum Bottleneck Throughput Tree algorithm that improves on the throughput capabilities (for reliable multicast) of the IP multicast Shortest Path Tree. This algorithm uses real-time network traffic measures to achieve local congestion avoidance properties. We have also developed a fully automated algorithm for deployment of this tree. This algorithm generates low amounts of control traffic at a central point and works well for medium-sized groups. A tree building block incorporating a more scalable, distributed algorithm could easily replace the current one.
The REALM protocol is implemented as a middleware in Java. It is useful for the class of multicast file transfer applications which includes peer-to-peer file sharing (images, sound, video), electronic software distribution, distributed database synchronization, and network content mirroring / replication. In addition, REALM makes innovative use of the reverse multicast tree and aggregation to provide a feedback channel that enables the sender to scalably collect feedback from the receiver set. This makes it useful for client-server applications in which the server frequently conducts polls over the client set. REALM has so far been used in two applications: A Distributed Voting Architecture and a Multicast File Transfer Application.