Search

New real-time applications frequently involve timing constraints related to accurate services from communication protocols. Concretely, real-time communication protocols utilize timers to implement these constraints between system event occurrences. In this context, the study of congestion control for Internet reliable multicast is at present an active research field related to real-time protocols. In this paper, the authors present an innovative real-time transport protocol named Scalable Reliable Multicast Stair Hybrid (SRMSH) as new hybrid multiple layer mechanism for multicast congestion control providing detection and recovery loss. This work is focused on formal specification of SRMSH approach using Communicating Real-Time State Machines as a formal method. Besides, SRMSH validation is presented within a formal proof framework in order to check the functional safety and liveness properties. As a result, authors outline a dynamical system framework in order to model behavior of their presented solution.

This paper presents Araneola (Araneola means ''little spider'' in Latin.), a scalable reliable application-level multicast system for highly dynamic wide-area environments. Araneola supports multi-point to multi-point reliable communication in a fully distributed manner, while incurring constant load (in terms of message and space complexity) on each node. For a tunable parameter k>=3, Araneola constructs and dynamically maintains a basic overlay structure in which each node's degree is either k or k+1, and roughly 90% of the nodes have degree k. Empirical evaluation shows that Araneola's basic overlay achieves three important mathematical properties of k-regular random graphs (i.e., random graphs in which each node has exactly k neighbors) with N nodes: (i) its diameter grows logarithmically with N; (ii) it is generally k-connected; and (iii) it remains highly connected following random removal of linear-size subsets of edges or nodes. The overlay is constructed and maintained at a low cost: each join, leave, or failure is handled locally, and entails the sending of only about 3k messages in total, independent of N. Moreover, this cost decreases as the churn rate increases. The low degree of Araneola's basic overlay structure allows for allocating plenty of additional bandwidth for specific application needs. In this paper, we give an example for such a need - communicating with nearby nodes; we enhance the basic overlay with additional links chosen according to geographic proximity and available bandwidth. We show that this approach, i.e., a combination of random and nearby links, reduces the number of physical hops messages traverse without hurting the overlay's robustness, as compared with completely random Araneola overlays (in which all the links are random) with the same average node degree. Given Araneola's overlay, we sketch out several message dissemination techniques that can be implemented on top of this overlay. We present a full implementation and evaluation of a gossip-based multicast scheme, with up to 10,000 nodes. We show that compared with a (non-overlay-based) gossip-based multicast protocol, gossiping over Araneola achieves substantial improvements in load, reliability, and latency.

In recent years, we have witnessed a growing interest in the synchronous collaboration based class of applications. Several techniques for collaborative virtual environments (CVE), haptic, audio and visual environments (C-HAVE) have been designed. However, several challenging issues remain to be resolved before CVE and C-HAVE become a common place. In this paper, we focus on applications that are based on closely coupled and highly synchronized haptic tasks that require a high-level of coordination among the participants. Four main protocols have been designed to resolve the synchronization issues in such environments: the synchronous collaboration transport protocol, the selective reliable transmission protocol, the reliable multicast transport protocol and the scalable reliable multicast. While these four protocols have shown good performance for CVE and C-HAVE class of applications, none of these protocols has been able to meet all of the basic CVE requirements, i.e., scalability, reliability, synchronization, and minimum delay. In this paper, we present a hybrid protocol that is able to satisfy all of the CVE and C-HAVE requirements and discuss its implementation and results in two tele-surgery applications.

Transport level multicast protocols providing reliability and scalability properties are certainly essential building blocks for several distributed group applications. We consider the effect of reliable multicast transport mechanisms on traffic characteristics and hence network performance. Although self-similarity property of unicast traffic, in particular TCP, has been analyzed extensively, multicast traffic has not been incorporated from this perspective. In this study, we focus on traffic characterization of transport level reliable multicasting. In particular, we concentrate on two scalable and reliable multicast protocols as case studies, namely Bimodal Multicast and Scalable Reliable Multicast (SRM), and analyze the traffic generated by them. Our study consists of a complete simulation analysis supported by theoretical work, which shows that self-similarity is protocol dependent. We demonstrate that the Markovian character of Bimodal Multicast's epidemic loss recovery distinguishes an inherently superior protocol. It discretely feeds well-behaved traffic and copes with the existing self-similarity. On the other hand, the feedback controlled loss recovery mechanism of SRM triggers self-similarity. Drawing upon both theoretical and simulation analysis, our results substantiate that transport level can induce long-range dependence even in the absence of application/user level causes.

In this paper, we propose the design of a scalable reliable mobile multicast scheme-SRMoM. SRMoM uses well-known Scalable Reliable Multicast (SRM) in the wired networks and a NAK-based ARQ with adaptive Forward Error Correction (AFEC) in the wireless networks. In AFEC, the probability of needing retransmission of original multicast packets after FEC recovery is selectable. This selective property enables the control of channel utilization in the wireless segment for different numbers of Mobile Hosts (MHs). Using this property, the channel utilization of SRMoM is made to be virtually independent of the number of MHs, thus making it extremely scalable. The performance of SRMoM is analyzed with three adaptive FEC algorithms based on three wireless loss models, namely a Gilbert-Elliott channel, a simplified Cilbert-Elliott channel, and a binary symmetric channel, analytically as well as through simulation. Furthermore, the performance of SRMoM is compared with SRM and MRMoM (NAK-based protocol without FEC) through simulation. Using the average number of transmissions per original multicast packet, and wireless link utilization as metrics, we demonstrate that the performance of SRMoM is indeed virtually independent of the number of MHs, and that it results in the lowest number of packet transmissions and lowest channel utilization of reliable mobile multicast protocols thai have been proposed to date.

Traditional reliable multicast protocols depend on assumptions about flow control and reliability mechanisms, and they suffer flom a kind of interference between these mechanisms. This in turn affects the overall performance, throughput and scalability of group applications utilizing these protocols. However, there exists a substantial class of distributed applications for which the throughput stability and scalability guarantees are indispensable. Bimodal Multicast (Pbcast) is a new option in scalable reliable multicast protocols that uses an inverted protocol stack approach, in which probabilistic mechanisms are used at low layers, and reliability properties introduced closer to the application. The main contributions of this study are development of simulation models for performance evaluation of Bimodal Multicast, demonstration of how the inverted protocol stack approach works well on several network settings, and its comparison with best-effort reliable multicast mechanisms. Analysis results reveal that Bimodal Multicast, together with optimizations for improving its latency and reliability characteristics, scales well, exhibits stable throughput and in contrast to the other scalable reliable multicast mechanisms it gives predictable reliability even under highly perturbed conditions.

In this paper, we design a new scalable reliable multicast transport protocol for satellite networks (RMT). This paper is the extensions of paper in [18]. The proposed protocoldoes not require inspection and/or interception of packets at intermediate nodes. The protocol would not require anymodification of satellites, which could be bent-pipe satellites or onboard processing satellites. The proposed protocol is divided in 2 parts: error control part and congestion control part. In error control part, we intend to solve feedback implosion and improve scalability by using a new hybrid of ARQ (Auto Repeat Request) and adaptive forward error correction (AFEC). The AFEC algorithm adapts proactive redundancy levels following the number of receivers and average packet loss rate. This leads to a number of transmissions and the number of feedback signals are virtually independent of the number of receivers. Therefore, wireless link utilization used by the proposed protocol is virtually independent of the number of multicast receivers. In congestion control part, the proposed protocol employs a new window-based congestion control scheme, which is optimized for satellite networks. To be fair to the other traffics, the congestion control mimics congestion control in the wellknown Transmission Control Protocol (TCP) which relies on “packet conservation” principle. To reduce feedback implosion, only a few receivers, ACKers, are selected to report the receiving status. In addition, in order to avoid “drop-to-zero” problem, we use a new simple wireless loss filter algorithm. This loss filter algorithm significantly reduces the probability of the congestion window size to be unnecessarily reduced because of common wireless losses. Furthermore, to improve achievable throughput, we employ slow start threshold adaptation based on estimated bandwidth. The congestion control also deals with variations in network conditions by dynamically electing ACKers.

We examine an approach for providing reliable, scalable multicast communication, involving the use of multiple multicast channels for reducing receiver processing costs and reducing network bandwidth consumption in a multicast session. In this approach a single multicast channel is used for the original transmission of packets. Retransmissions of packets are done on separate multicast channels, which receivers dynamically join and leave. We first show that protocols using an infinite number of multicast channels incur much less processing overhead at the receivers compared to protocols that use only a single multicast channel. This is due to the fact that receivers do not receive retransmissions of packets they have already received correctly. Next, we derive the number of unwanted redundant packets at a receiver due to using only a finite number of multicast channels, for a specific negative acknowledgment (NAK)-based protocol. We then explore the minimum number of multicast channels required to keep the cost of processing unwanted packets to a sufficiently low value. For an application consisting of a single sender transmitting reliably to many receivers we find that only a small number of multicast channels are required for a wide range of system parameters. In the case of an application where all participants simultaneously act as both senders and receivers a moderate number of multicast channels is needed. Finally, we present two mechanisms for implementing multiple multicast channels, one using multiple IP multicast groups and the other using additional router support for selective packet forwarding. We discuss the impact of both mechanisms on performance in terms of end-host and network resources.

There are many methods for making a multicast protocol “reliable.” At one end of the spectrum, a reliable multicast protocol might offer tomicity guarantees, such as all-or-nothing delivery, delivery ordering, and perhaps additional properties such as virtually synchronous addressing. At the other are protocols that use local repair to overcome transient packet loss in the network, offering “best effort” reliability. Yet none of this prior work has treated stability of multicast delivery as a basic reliability property, such as might be needed in an internet radio, television, or conferencing application. This article looks at reliability with a new goal: development of a multicast protocol which is reliable in a sense that can be rigorously quantified and includes throughput stability guarantees. We characterize this new protocol as a “bimodal multicast” in reference to its reliability model, which corresponds to a family of bimodal probability distributions. Here, we introduce the protocol, provide a theoretical analysis of its behavior, review experimental results, and discuss some candidate applications. These confirm that bimodal multicast is reliable, scalable, and that the protocol provides remarkably stable delivery throughput.

Reliable multicast protocols scale only as well as their ability to localize traffic. This is true for repair requests, repairs, and the session traffic that enables receivers to suppress extraneous requests and repairs. We propose a new reliable multicast traffic localization technique called Scoped Hybrid Automatic Repeat reQuest with Forward Error Correction (SHARQFEC). SHARQFEC operates in an end-to-end fashion and localizes traffic using a hierarchy of administratively scoped regions. Session traffic is further reduced through the use of a novel method for indirectly determining the distances between session members. For large sessions, this mechanism reduces the amount of session traffic by several orders of magnitude over non-scoped protocols such as Scalable Reliable Multicast (SRM). Forward Error Correction is selectively added to regions which are experiencing greater loss, thereby reducing the volume of repair traffic and recovery times. Receivers request additional repairs as necessary. Simulations show that SHARQFEC out performs both SRM and non-scoped hybrid Automatic Repeat reQuest / Forward Error Correction protocols. Assuming the widespread deployment of administrative scoping, SHARQFEC could conceivably provide scalable reliable delivery to tens of millions of receivers without huge increases in network bandwidth.

Scalable reliable multicast (SRM) is a framework for reliable multicast delivery. In order to maximize the collaboration among the group members in error recovery, both retransmission requests and replies are multicast to the entire group. While SRM effectively uses random timers to suppress duplicate requests and replies, the global nature of the request and replies means that every packet loss results in at least one request and reply message sent to the entire group. To further improve the scalability of SRM, one must localize the scope of error recovery traffic. In this paper, we present two approaches to local recovery: hop-based scope control and use of local recovery groups. The first approach uses hop count to limit the distribution of requests and replies whereas the second approach confines error recovery traffic using separately addressed local recovery groups. The local recovery groups and hop count settings are automatically created and dynamically adjusted based on observed loss patterns. The use simulation experiments to examine the performance of both approaches.

We investigate how FEC (Forward Error Correction) can be combined with ARQ (Automatic Repeat Request) to achieve scalable reliable multicast transmission. We consider the two scenarios where FEC is introduced as a transparent layer underneath a reliable multicast layer that uses ARQ, and where FEC and ARQ are both integrated into a single layer that uses the retransmission of parity data to recover from the loss of original data packets.To evaluate the performance improvements due to FEC, we consider different types of loss behaviors (spatially or temporally correlated loss, homogeneous or heterogeneous loss) and loss rates for up to 10 6 receivers. Our results show that introducing FEC as a layer below ARQ can improve multicast transmission efficiency and scalability and that there are substantial additional improvements when the two are integrated.

This paper presents the design, implementation, and performance of a reliable multicast transport protocol (RMTP). The RMTP is based on a hierarchical structure in which receivers are grouped into local regions or domains and in each domain there is a special receiver called a designated receiver (DR) which is responsible for sending acknowledgments periodically to the sender, for processing acknowledgment from receivers in its domain, and for retransmitting lost packets to the corresponding receivers. Since lost packets are recovered by local retransmissions as opposed to retransmissions from the original sender, end-to-end latency is significantly reduced, and the overall throughput is improved as well. Also, since only the DRs send their acknowledgments to the sender, instead of all receivers sending their acknowledgments to the sender, a single acknowledgment is generated per local region, and this prevents acknowledgment implosion. Receivers in RMTP send their acknowledgments to the DRs periodically, thereby simplifying error recovery. In addition, lost packets are recovered by selective repeat retransmissions, leading to improved throughput at the cost of minimal additional buffering at the receivers. This paper also describes the implementation of RMTP and its performance on the Internet.

This paper describes SRM (Scalable Reliable Multicast), a reliable multicast framework for application level framing and light-weight sessions. The algorithms of this framework are efficient, robust, and scale well to both very large networks and very large sessions. The framework has been prototyped in wb, a distributed whiteboard application, and has been extensively tested on a global scale with sessions ranging from a few to more than 1000 participants. The paper describes the principles that have guided our design, including the IP multicast group delivery model, an end-to-end, receiver-based model of reliability, and the application level framing protocol model. As with unicast communications, the performance of a reliable multicast delivery algorithm depends on the underlying topology and operational environment. We investigate that dependence via analysis and simulation, and demonstrate an adaptive algorithm that uses the results of previous loss recovery events to adapt the control parameters used for future loss recovery. With the adaptive algorithm, our reliable multicast delivery algorithm provides good performance over a wide range of underlying topologies.

Reliable multicast communication is important in large-scale distributed applications. For example, reliable multicast is used to transmit terrain and environmental updates in distributed simulations. To date, proposed protocols have not supported these applications' requirements, which include wide-area data distribution, low-latency packet loss detection and recovery, and minimal data and management over-head within fine-grained multicast groups, each containing a single data source.In this paper, we introduce the notion of Log-Based Receiver-reliable Multicast (LBRM) communication, and we describe and evaluate a collection of log-based receiver reliable multicast optimizations that provide an efficient, scalable protocol for high-performance simulation applications. We argue that these techniques provide value to a broader range of applications and that the receiver-reliable model is an appropriate one for communication in general.

Sender-initiated reliable multicast protocols based on the use of positive acknowledgments (ACKs) can suffer performance degradation as the number of receivers increases. This degradation is due to the fact that the sender must bear much of the complexity associated with reliable data transfer (e.g., maintaining state information and timers for each of the receivers and responding to receivers' ACKs). A potential solution to this problem is to shift the burden of providing reliable data transfer to the receivers-thus resulting in receiver-initiated multicast error control protocols based on the use of negative acknowledgments (NAKs). We determine the maximum throughputs for generic sender-initiated and receiver-initiated protocols for two classes of applications: (1) one-many applications where one participant sends data to a set of receivers and (2) many-many applications where all participants simultaneously send and receive data to/from each other. We show that a receiver-initiated error control protocol which requires receivers to transmit NAKs point-to-point to the sender provides higher throughput than a sender-initiated counterpart for both classes of applications. We further demonstrate that, in the case of a one many application, replacing point-to-point transfer of NAKs with multicasting of NAKs coupled with a random backoff procedure provides a substantial additional increase in the throughput of a receiver-initiated error control protocol over a sender-initiated protocol. We also find, however, that such a modification leads to a throughput degradation in the case of many-many applications.

Many networking applications such as video-on-demand services, video conferencing, and distributed database replications require multicast communications. Providing scalable and reliable multicast are basic requirements to develop a better routing protocols which is used for disaster management, emergency relief, mobile conferencing among many other applications. As mobile host changes its access point over a time interval, multicast routes have to be updated frequently. This poses several challenges to provide an efficient multicast routing. In this paper, we propose a Scalable Reliable Multicast Ad hoc On Demand Distance Vector (SRMAODV) protocol based on Ad hoc On Demand Distance Vector (AODV) and Multicast AODV (MAODV) protocol to support scalability and reliability for online routing of delivery-guaranteed multicasts. Exhaustive simulation experiments reveal that Packet Delivery Ratio (PDR) which is an important measure of reliability for SRMAODV is much better together with improved end-to-end delay.

Content Delivery Networks (CDNs) provide an efficient support for serving http and streaming media content while minimizing the network impact of content delivery as well as overcoming the server overload problem. Not too much research effort has been placed in the analysis of the access network and the impact and benefits of multicast. This paper proposes an innovative real-time protocol offering an hybrid congestion control algorithm called Scalable Reliable Multicast Stair Hybrid (SRMSH) which combines the benefits of TCP AIMD with Rate-based (STAIR) [2] for layered multicast with Scalable Reliable Multicast (SRM) [6] in order to offer loss recovery methods if receivers detect loss events. The mechanism has been simulated and implemented to proof its benefits.

Multimedia social network analysis is an emerging research area, which analyzes the behaviour of users who share multimedia content and investigates the impact of human dynamics on multimedia systems. In collaborative mobile networks, receivers cooperate with each other to provide a distributed, highly scalable and robust platform for live streaming applications. However, every user wishes to use as much bandwidth as possible to receive a high-quality video; then, congestion control should be addressed. This paper proposes a collaborative mobile architecture to model receiver (in this case user) behaviour using congestion control and reliable strategies to stimulate user cooperation in multicast live streaming. Thus, an author's protocol named Scalable Reliable Multicast Stair Hybrid (SRMSH) is presented as new hybrid multiple layer mechanism for multicast congestion control providing detection and recovery loss. Simulation results show that the proposed strategies can effectively stimulate user cooperation, achieve cheat free and provide reliable services within a mobile multimedia social network.

The ISIS toolkit is a distributed programming environment based on support for virtually synchronous process groups and group communication. A suite of protocols is presented to support this model. The approach revolves around a multicast primitive, called CBCAST, which implements a fault-tolerant, causally ordered message delivery. This primitive can be used directly or extended into a totally ordered multicast primitive, called ABCAST. It normally delivers messages immediately upon reception, and imposes a space overhead proportional to the size of the groups to which the sender belongs, usually a small number. It is concluded that process groups and group communication can achieve performance and scaling comparable to that of a raw message transport layer. This finding contradicts the widespread concern that this style of distributed computing may be unacceptably costly.

Hierarchical reliable multicast transport protocols partition group members into local groups and allocate one local repair node for each local group to distribute the task of detecting and recovering lost packets. This repair node uses the data stored in its buffer to retransmit the requested packets to the requesting receivers. The problem is that they keep these packets for a long time until they get acknowledgments from all their children receivers of correctly receiving these packets. Keeping these packets creates a congestion problem which decreases the network throughput. This paper proposes a new scheme to solve this problem, by distributing the required packets between the repair node which we call it here the control receiver and some selected receives that have already received these packets correctly. The distribution of the packets decreases the number of packets in the repair node buffer, thus solve the congestion problem and increase the network throughput.

A fast loss recovery scheme for IP multicast services is presented in this paper. In this scheme, the head field of retransmission request packets contains the one-way delay between the requestor and the sender of the lost packet, and the head field of repair packets contains the one-way delay between the repairer and the requestor. Each member in the multicast group compares its own one-way delay to the sender or the requestor with those advertised in the request or repair packets, and decides how long it should wait before sending a request or repair packet in the next recovery round. This distributed request/repair timer setting algorithm shows significant performance gains in terms of loss recovery latency and the number of duplicated requests and repairs, compared with the SRM scheme and its adaptive version. Being a pure application-layer scheme, it can be deployed quickly over existing IP multicast infrastructures without extra router assistance. The ability to recover from errors in typical one round-trip time makes this scheme a good candidate for loss recovery in real-time multimedia multicast.

IP-multicast is a bandwidth efficient transmission mechanism for multimedia communication. Reliability in IP-multicast, however, remains a significant challenge. This paper addresses the reliability and scalability issues in IP-multicast by exploring a novel, highly distributed overlay peer-to-peer retransmission architecture that exploits path-diversity. A simple unicast-based "tracert" tool is proposed to help to identify peers with disjoint path to the sender as potential retransmission nodes. Probing can help to adapt to the dynamics of the network. We show that a hybrid system with both "tracert" and probing can perform better than probing only or "tracert" only approach. In addition, we identify the proper probing interval that does not introduce significant probing overhead yet can collect sufficiently updated information to help recover most of the lost packets. The proposed hybrid multicast system is practical, scalable, and easy to deploy, requiring no change to the existing network infrastructure.

Haptic interfaces have been designed for brain surgery simulation may prove to be especially useful for training surgeons to conduct minimally invasive procedures and remote surgery using tele-operators. However, it well known that collaborative, haptic, audio and visual environments (C-HAVE) suffer from setbacks due to network delay, scalability, reliability and synchronization problem when the users are geographically distributed. In this paper, we focus upon a Brain Tumor Tele-Surgery application that is based on closely coupled and highly synchronized haptic tasks that require a high-level of coordination among the participants. We considered four main protocols: the synchronous collaboration transport protocol (SCTP), the selective reliable transmission protocol (SRTP), the reliable multicast transport protocol (RMTP) and the scalable reliable multicast (SRM) and presented a hybrid protocol that is able to satisfy all the CVE and C-HAVE requirements and discuss its implementation using brain tumor tele-surgery application as a case study.

In recent years, we have witnessed a growing interest in synchronous collaboration based class of applications. Several techniques for collaborative virtual environments CVE, haptic, audio and visual environments C-HAVE were designed. However several challenging issues remain to be resolved before CVE and C-HAVE become a common place. In this paper, we focus upon applications that are based on closely coupled and highly synchronized haptic tasks that require a high- level of coordination among the participants. Four main protocols were designed to resolve the synchronization issues in such environments: the synchronous collaboration transport protocol (SCTP), the selective reliable transmission protocol (SRTP), the reliable multicast transport protocol (RMTP) and the scalable reliable multicast (SRM). While these four protocols have shown good performance for CVE and C-HAVE class of applications, none of these protocols was able to meet all the of the basic CVE requirement i.e., scalability, reliability, synchronization and minimum delays. In this paper, we present a hybrid protocol that is able to satisfy all the CVE and C-HAVE requirements and discuss its implementation

With the increasing deployment of multimedia real-time Internet applications, evaluating transport protocol metrics of quality of service (QoS) has gained rapidly increasing importance. In this paper, a novelty protocol named scalable reliable multicast stair hybrid (SRMSH) is presented as new hybrid multiple layer mechanism for multicast congestion control providing detection and recovery loss. Then SRMSH is simulated with video streaming traffic source to measure fundamental components to real-time multimedia applications: throughput, latency and jitter. Work is focused on performance analysis and results obtained from NS-2 traces clearly conclude that SRMSH exhibits interesting insights using these metrics of real-time multimedia applications

Due to the distribution nature and multi-customer interaction characteristic of the CSCW system, multicast becomes an ideal transmission instrument. Thus we have put into effect a multicast protocol named TORM (totally ordered reliable multicast). In order to evaluate its performance, we conduct the analysis and comparison between TORM and another multicast protocol, SRM (scalable reliable multicast), in respect of their error recovery mechanism. With queuing theory, we establish a queue model, based on which the expression of error recovery latency are worked out. The analytical result demonstrates TORM with the higher error recovery efficiency is often preferable in the CSCW application. Moreover, we simulate the two protocols with NS2, a network simulation tool, and get the same conclusion.

The study of congestion control for Internet reliable multicast is at present an active research field. In this paper we present scalable reliable multicast stair hybrid (SRMSH) as a multiple layer mechanism for multicast congestion control providing detection and recovery loss. We simulated SRMSH with different traffic sources to measure heterogeneity, scalability and fairness. Our work focus on bandwidth analysis and results clearly conclude that SRMSH exhibits reasonable throughput using these metrics and a good performance competing with typical traffic flow from Internet like TCP.

Reliable multicast protocols are an important class of protocols for reliably disseminating information from a sender to multiple receivers in the face of node and link failures. A tree-based reliable multicast protocol (TRAM) provides scalable reliable multicast by grouping receivers in hierarchical repair groups and using a selective acknowledgment mechanism. We present an improvement to TRAM to minimize the resource utilization at intermediate hosts and to localize the effect of slow or malicious receivers on normal receivers. We present an evaluation of TRAM and TRAM++ on a campus-wide WAN without errors and with message errors. The evaluation brings out that, given a constraint on the buffer availability at intermediate hosts, TRAM++ can tolerate the constraint at the expense of increasing the end-to-end latency for the normal receivers by only 3.2% compared to TRAM in error-free cases. When slow or faulty receivers are present, TRAM++ is able to provide the same uninterrupted quality of service to the normal nodes while localizing the effect of the faulty ones without incurring any additional memory overhead.

This project developed theory and systems support to aid in the construction of adaptive, survivable distributed systems. The systems are designed to run in highly dynamic environments such as the internet, wireless networks, and sensor networks. Participating processes may join, leave, and fail during computation. The systems that were considered solve problems of data sharing and management, resource sharing and management, communication, and coordination. Specifically, the project involved developing reusable "building blocks" global service specifications and distributed algorithms-for dynamic distributed systems. The work included an extensive study of view- oriented group communication services and algorithms, which is now "transitioning" into use at Lincoln Laboratories. A major focus was on design and analysis of algorithms for implementing reliable atomic shared memory in highly dynamic networks. Other algorithmic work covered dynamic algorithms for atomic broadcast, scalable reliable multicast, and topology control. In addition, the project produced results on mathematical semantic foundations to support modeling and analysis of highly dynamic distributed systems, and on tools to support this effort.

Group communications (multicast) are foreseen to be one of the most critical yet challenging technologies to meet the exponentially growing demands for data distribution in a large variety of applications of the Internet (such as grid computing, web applications and distributed simulations). When reliability is required, there is no straightforward solutions and meeting the objectives of reliable multicast is not an easy task. Active networks open a new perspective in providing more efficient solutions for the problem of reliability. In this context, routers are able to perform customized computations on the packets flowing through them. In this report, we propose a receiver-based (replier) local recovery multicast protocol with dynamic repliers elected on a per-packet basis. Designed to provide an efficient reliable multicast service without any cache facilities inside the network, our approach, uses low-overhead active services in routers. The current report addresses the design, evaluation and the implementation of an efficient and scalable reliable multicast protocol noted DyRAM standin for Dynamic Replier Active reliable Multicast.

For the last decade, a number of hierarchical reliable multicast schemes have been proposed in the literature due to their efficiency and scalability. They normally partition the group members into local groups and allocate one server for each local group to detect and recover packet loss. One common problem is how the server recovers the lost packet in the case that the server itself does not receive it. The usual solution is either to send requests to some upstream servers/source or to construct a tree-based hierarchy to organize the servers for recovery. However, these solutions may lead to long recovery latency. This paper presents a server relay recovery strategy (SRRS) for servers to achieve low recovery latency and low bandwidth usage for recovery. The basic idea is for each server to distributively compute and maintain a prioritized peer list that leads to minimal expected relay recovery latency. Our simulation results show that when the server distribution is not dense, SRRS outperforms SRM (scalable reliable multicast) and RMA (reliable multicast architecture) on both recovery latency and bandwidth usage in Internet-like topologies.

A number of reliable multicast (RM) protocols have been proposed previously. However, when used in conferencing control over the Internet, they are all faced with challenges of poor scalability and robustness, or too much redundant packets and abuse of network bandwidth, especially with the growth of group size and scope. We present a new RM protocol named HSRM (hierarchical scalable reliable multicast) for distributed conferencing control over the Internet. We group hosts into subgroups according to their packet loss characteristics. Consequently, the heterogeneity of the hosts is reduced in each subgroup, and then the number of retransmission is decreased efficiently. Furthermore, since feedback and recovery packets are restricted to subgroups, they will never be spread to the whole multicast group. This is very advantageous to conferencing control, which always contains thousands of hosts distributed in a large area. We then present a mechanism to construct and maintain an adaptive hierarchical structure dynamically. The numeric analysis demonstrates that HSRM can improve the performance of RM compared with SRM, in the sense of redundant packets and the number of retransmissions. It is also shown that HSRM is much better than other hierarchical RM protocols in scalability and robustness.

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.

As the scale of a network becomes larger in terms of both the number of users and geographic span, reliable multicast protocols suffer more severely from acknowledgement implosion and exposure to retransmissions. In this paper, we propose a scalable, efficient recovery scheme for a tree-based reliable multicast transport protocol. The scheme first constructs a logical tree of receivers as close to a multicast routing tree as possible by using error bitmap information. This ensures that the receivers residing at a higher level in a multicast routing tree than ones requesting retransmissions be appointed as parents in a corresponding logical tree. In our scheme, the logical tree is adaptively reconfigured as the session membership or the multicast route changes. Our scheme also forms local groups with separate multicast addresses in the tree for efficient recovery. We compare our scheme with a static tree-based reliable multicast protocol. Results of the simulation show that our adaptive tree-based recovery scheme outperforms the compared protocol in terms of the implosion and exposure as the session size increases.

Any reliable multicast protocol requires some recovery mechanism. A generic description of a recovery mechanism consists of a prioritized list of recovery servers/receivers (clients), hierarchically and/or geographically and/or randomly organized. Recovery requests are sent to the recovery clients on the list one-by-one until the recovery effort is successful. There are many recovery strategies available in literature fitting the generic description. We propose a polynomial time algorithm for choosing the recovery strategy with law recovery latency without sacrificing much bandwidth. We compared our method with two existing recovery methods, SRM (scalable reliable multicast) and RMA (reliable multicast architecture), by simulation and found that our method performs better. Although our theoretical analyses are based on a reliable network, our simulation results show that our strategy performs as well with the per link loss probability in a network up to 20% or more

The development of high-speed networks and the expansion of the Internet have increased both geographical extent and participant population of applications such as videoconferencing, multimedia dissemination, electronic stock exchange, and distributed cooperative work. The key property of this type of applications is the need to distribute data among multiple participants together with application specific quality of service needs which fact makes multicast protocols an essential underlying communication structure. In this paper, we analyze traffic characteristics of two scalable multicast protocols, namely Bimodal Multicast (Pbcast) and Scalable Reliable Multicast (SRM), each having different approaches for loss recovery and providing reliability. Particularly, our simulation studies demonstrate that epidemic approach of Bimodal Multicast generates a more desirable traffic than SRM with lower overhead traffic and transport delays. SRM delays show long-range dependence and self-similarity whereas Bimodal Multicast delays are shortrange dependent. Self-similarity and long-range dependence are ubiquitous in wide area networks, which lead to adverse consequences in network performance. We elaborate on the protocol mechanisms as the underlying factor in our empirical results. The intrinsic relation of these mechanisms to traffic characteristics is explored.

We analyze the maximum throughput that the known classes of reliable multicast protocols can attain. A new taxonomy of reliable multicast protocols is introduced based on the premise that the mechanisms used to release data at the source after correct delivery should be decoupled from the mechanisms used to pace the transmission of data and to effect error recovery. Receiver-initiated protocols, which are based entirely on negative acknowledgments (NAKs) sent from the receivers to the sender, have been proposed to avoid the implosion of acknowledgments (ACKs) to the source. However, these protocols are shown to require infinite buffers in order to prevent deadlocks. Two other solutions to the ACK-implosion problem are tree-based protocols and ring-based protocols. The first organize the receivers in a tree and send ACKs along the tree; the latter send ACKs to the sender along a ring of receivers. These two classes of protocols are shown to operate correctly with finite buffers. Following our taxonomy, the maximum attainable throughput by the known classes of reliable multicast protocols is analyzed. It is shown that tree-based protocol constitute the most scalable class of all reliable multicast protocols proposed to date.

The success of multicast applications such as Internet teleconferencing illustrates the tremendous potential of applications built upon wide-area multicast communication services. A critical issue for such multicast applications and the higher layer protocols required to support them is the manner in which packet losses occur within the multicast network. We present and analyze packet loss data collected on multicast-capable hosts at 17 geographically distinct locations in Europe and the US and connected via the MBone. We experimentally and quantitatively examine the spatial and temporal correlation in packet loss among participants in a multicast session. Our results show that there is some spatial correlation in loss among the multicast sites. However, the shared loss in the backbone of the MBone is, for the most part, low. We find a fairly significant amount of of burst loss (consecutive losses) at most sites. In every dataset, at least one receiver experienced a long loss burst greater than 8 seconds (100 consecutive packets). A predominance of solitary loss was observed in all cases, but periodic losses of length approximately 0.6 seconds and at 30 second intervals were seen by some receivers.

This paper describes the design and implementation of a multi-cast transport protocol called RMTP. RMTP provides sequenced, lossless delivery of bulk data from one sender to a group of receivers. RMTP achieves reliability by using a packet-based selective repeat retransmission scheme, in which each acknowledgment (ACK) packet carries a sequence number and a bitmap. ACK handling is based on a multi-level hierarchical approach, in which the receivers are grouped into a hierarchy of local regions, with a designated receiver (DR) in each local region. Receivers in each local region periodically send ACKs to their corresponding DR, DRs send ACKs to the higher-level DRs, until the DRs in the highest level send ACKs to the sender, thereby avoiding the ACK-implosion problem. DRs cache received data and respond to retransmission requests of the receivers in their corresponding local regions, thereby decreasing end-to-end latency and improving resource usage. This paper also provides the measurements of RMTP's performance with receivers located at various sites in the Internet.

In reliable multicast communications, lost information due to packet loss should be re-multicast. The NAK-based retransmission scheme is said to be effective for scalable reliable multicast communications because it can avoid implosion of the control packet. When the source sends packets faster than the receiver's capacity, packet loss due to buffer overflow occurs constantly at the corresponding receivers. With this constant packet loss, implosion of the control packet degrades the total throughput seriously even in the case of the NAK-based retransmission scheme. In order to prevent this kind of constant packet loss at the receivers, the flow control scheme should be implemented for reliable multicast communications. In the paper we propose a new flow control scheme, which is suitable for the NAK-based retransmission scheme. From the viewpoint of flow control, receiving a NAK intends that the transmission rate is too high. However in multicast communications, multiple NAKs may be generated for a corresponding packet. If simply receiving a NAK decreases the transmission rate, the rate may be decreased excessively. In the paper, log information of the transmission rate stored at the sender is proposed in order to prevent the transmission rate from decreasing excessively. Performance evaluation by computer simulation shows that our proposed scheme notably improves throughput performance compared with the case of no flow control.

Retransmission based error control for large scale multicast applications is difficult because of implosion and exposure. Existing schemes (SRM, RMTP, TMTP LBRRM) have good solutions to implosion, but only approximate solutions to exposure. We present a scheme that achieves finer grain fault recovery by exploiting new forwarding services that allow us to create a dynamic hierarchy of receivers. We extend the IP multicast service model so that routers provide a more refined form of multicasting (which may be useful to other applications), that enables local recovery. The new services are simple to implement and do not require routers to examine or store application packets; hence, they do not violate layering. Besides providing better implosion control and less exposure than other schemes, our scheme integrates well with the current IP model, has small recovery latencies (it requires no back-off delays), and completely isolates group members from topology. Our scheme can be used with a variety of multicast routing protocols, including DVMRP and PIM. We have implemented our scheme in NetBSD Unix, using about 250 lines of new C-code. The implementation requires two new IP options, 4 additional bytes in each routing entry and a slight modification to IGMP reports. The forwarding overhead incurred by the new services is actually lower than forwarding normal multicast traffic.

We have developed a scalable reliable multicast architecture for delivering one-to-many telepresentations. In contrast to audio and video, which are often transmitted unreliably other media, such as slides, images and animations require reliability. Our approach transmits the data in two layers. One layer is for session-persistent data, with reliability achieved by FEC alone, using the Fcast protocol. The other layer is for dynamic data, with reliability achieved using the ECSRM protocol, which combines FEC with NACK suppression. Our approach is scalable to large heterogeneous receiver sets, and supports late-joining receivers. We have implemented our approach in a multicast version of PowerPoint, a graphical slide presentation tool.

Local recovery approaches for reliable multicast have the potential to provide significant performance gains in terms of reduced bandwidth and delay, and higher system throughput. In this paper we examine two local recovery approaches-one server-based, and the other receiver-based, and compare their performance. The server-based approach makes use of specially designated hosts, called repair servers, co-located with routers inside the network. In the receiver-based approach, only the end hosts (sender and receivers) are involved in error recovery. Using analytical models, we first show that the two local recovery approaches yield significantly higher protocol throughput and lower bandwidth usage than an approach that does not use local recovery. Next, we demonstrate that server-based local recovery yields higher protocol throughput and lower bandwidth usage than receiver-based local recovery when the repair servers have processing power slightly higher than that of a receiver and several hundred kilobytes of buffer per multicast session.

Reliable multicast protocols on top of the MBone are presently subject to intensive research. In the past, numerous protocols have been developed and their respective performance been analysed. Little progress has been made, though, to compare different approaches. We use the network simulator ns-2 to evaluate the performance of three protocols, namely scalable reliable multicast (SRM), multicast file transfer protocol (MFTP) and an enhanced version of the latter, called multicast file transfer protocol with erasure correction (MFTP/EC). We also compare the results to each other and test the suitability for multicast file distribution.

End-to-end protocols measure network characteristics and react based on their estimates of network performance. Network dynamics can alter the topology significantly, and thereby affect protocol operation. Topology changes may result in routing pathologies (such as route loops, packet interleaving), changes to the end-to-end path characteristics, network partition etc., that then impact the performance of end-to-end protocols. This paper presents methodologies to evaluate an end-to-end protocol in the presence of network dynamics using a simulator. We evaluate a reliable multicast transport protocol over dynamic topologies and study its adaptivity to topology change. We present a systematic evaluation of the adaptive timer mechanisms in scalable reliable multicast (SRM). The timer mechanisms are evaluated under simple topology changes, as well as under network partition conditions. The paper concludes by posing a number of open research questions about the behaviour of different reliable multicast mechanisms when operating over dynamic topologies.

There are many scenarios in which the same data must be delivered over a packet switched network to a large set of receivers. The Internet enables efficient multipoint transmissions through IP multicast by allowing data transmission to all receivers with a single send. Most approaches to scalable reliable multicast utilize receiver-oriented retransmissions. Defining an API for receiver-oriented reliable multicast is difficult because it is not clear how to manage the sender's cache and to schedule repairs. We outline an approach to defining an API based on logical cache persistence that addresses these problems. We also we explore the issues involved in defining an API for reliable multicast protocol on the Internet that can scale to millions of receivers.

Error recovery by retransmission for large scale multicast faces two intrinsic scalability challenges: acknowledgment implosion and exposure to retransmission. This paper proposes a new scheme to reduce the cost of error recovery by using the idea of cumulative negative acknowledgment (CNAK). In the scheme, we assume a window control of size W. A receiver does not send back a NAK immediately upon the discovery of a packet loss. Instead, the receiver accumulates the losses and returns a CNAK to the source at about half of the window interval. Retransmission is carried out on multiple multicast channels which are mapped to window size W. The A /sub i/ multicast channel is mapped to the sequence number i where i = 1,2,...,W. Our scheme has these advantages: one CNAK replaces W/2 number of conventional NAK, thus, greatly reducing the NAK overhead. Moreover, the use of multiple multicast channels for packet retransmission completely eliminates the exposure hazard. We apply the CNAK scheme to the DR local recovery model and show that the proposed C4 protocol is the most efficient protocol among all. The protocol is highly scalable and free of unwanted repair packets.

Summary form only given. Computer networks are becoming increasingly common, and are used in sensitive applications in which serious damage could be done by a network failure. There is a need for design principles that would enable a new generation of solutions having the required properties. Needed are technologies that would be inherently robust, provably scalable, and sufficiently self-organizing to adapt as conditions change in the network. The Spinglass project has been successful in solving an important class of such problems. At the core of our work is a new style of gossip-based communication protocol. We are using this protocol in support of a variety of systems programming tools. The article discusses two of them: Bimodal Multicast, a scalable reliable multicast protocol having probabilistic reliability properties, and Astrolabe, a virtual distributed database constructed entirely through peer-to-peer interactions among the components of a large system. Both technologies are shown to be stable under stress, arbitrarily scalable without growth in communication or processing loads, and to have real-time properties.