Asymptotic Connectivity Properties of Cooperative Wireless Ad Hoc Networks

Extensive research has demonstrated the potential improvement in physical layer performance when multiple radios transmit concurrently in the same radio channel. We consider how such cooperation affects the requirements for full connectivity and percolation in large wireless ad hoc networks. Both noncoherent and coherent cooperative transmission are considered. For one-dimensional (1-D) extended networks, in contrast to noncooperative networks, for any path loss exponent less than or equal to one, full connectivity occurs under the noncoherent cooperation model with probability one for any node density. Conversely, there is no full connectivity with probability one when the path loss exponent exceeds one, and the network does not percolate for any node density if the path loss exponent exceeds two. In two-dimensional (2-D) extended networks with noncoherent cooperation, for any path loss exponent less than or equal to two, full connectivity is achieved for any node density. Conversely, there is no full connectivity when the path loss exponent exceeds two, but the cooperative network percolates for node densities above a threshold which is strictly less than that of the noncooperative network. A less conclusive set of results is presented for the coherent case. Hence, even relatively simple noncoherent cooperation improves the connectivity of large ad hoc networks.     

Comments on "Modeling TCP reno performance: a simple model and its empirical Validation"

In this Comments, several errors in Padhye , 2000, are pointed out. The more serious of these errors result in an over prediction of the send rate. The expression obtained for send rate in this Comments leads to greater accuracy when compared with the measurement data than the originals end rate expression in Padhye et al.     

Scalable fair reliable multicast using active services

Scalability is of paramount importance in the design of reliable multicast transport protocols, and requires careful consideration of a number of problems such as feedback implosion, retransmission scoping, distributed loss recovery, and congestion control. In this article, we present a reliable multicast architecture that invokes active services at strategic locations inside the network to comprehensively address these challenges. Active services provide the ability to quickly and efficiently recover from loss at the point of loss. They also exploit the physical hierarchy for feedback aggregation and effective retransmission scoping with minimal router support. We present two protocols, one for packet loss recovery and another for congestion control, and describe an experimental testbed where these have been implemented. Analytical and experimental results are used to demonstrate that the active services architecture improves resource usage, reduces latency for loss recovery, and provides TCP-friendly congestion control     

Modeling TCP Reno performance: a simple model and its empiricalvalidation

The steady-state performance of a bulk transfer TCP flow (i.e., a flow with a large amount of data to send, such as FTP transfers) may be characterized by the send rate, which is the amount of data sent by the sender in unit time. In this paper we develop a simple analytic characterization of the steady-state send rate as a function of loss rate and round trip time (RTT) for a bulk transfer TCP flow. Unlike the models of Lakshman and Madhow (see IEE/ACM Trans. Networking, vol.5, p.336-50, 1997), Mahdavi and Floyd (1997), Mathis, Semke, Mahdavi and Ott (see Comput. Commun. Rev., vol.27, no.3, 1997) and by by Ott et al., our model captures not only the behavior of the fast retransmit mechanism but also the effect of the time-out mechanism. Our measurements suggest that this latter behavior is important from a modeling perspective, as almost all of our TCP traces contained more time-out events than fast retransmit events. Our measurements demonstrate that our model is able to more accurately predict TCP send rate and is accurate over a wider range of loss rates. We also present a simple extension of our model to compute the throughput of a bulk transfer TCP flow, which is defined as the amount of data received by the receiver in unit time     

Scalable reliable multicast using multiple multicast channels

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     

Multicast-based inference of network-internal loss characteristics

Robust measurements of network dynamics are increasingly important to the design and operation of large internetworks like the Internet. However, administrative diversity makes it impractical to monitor every link on an end-to-end path. At the same time, it is difficult to determine the performance characteristics of individual links from end-to-end measurements of unicast traffic. In this paper, we introduce the use of end-to-end measurements of multicast traffic to infer network-internal characteristics. The bandwidth efficiency of multicast traffic makes it suitable for large-scale measurements of both end-to-end and internal network dynamics. We develop a maximum-likelihood estimator for loss rates on internal links based on losses observed by multicast receivers. It exploits the inherent correlation between such observations to infer the performance of paths between branch points in the tree spanning a multicast source and its receivers. We derive its rate of convergence as the number of measurements increases, and we establish robustness with respect to certain generalizations of the underlying model. We validate these techniques through simulation and discuss possible extensions and applications of this work     

Efficient rate-controlled bulk data transfer using multiple multicast Groups

Controlling the rate of bulk data multicast to a large number of receivers is difficult, due to the heterogeneity among the end systems' capabilities and their available network bandwidth. If the data transfer rate is too high, some receivers will lose data, and retransmissions will be required. If the data transfer rate is too slow, an inordinate amount of time will be required to transfer the data. In this paper, we examine an approach toward rate-controlled multicast of bulk data in which the sender uses multiple multicast groups to transmit data at different rates to different subgroups of receivers. We present simple algorithms for determining the transmission rate associated with each multicast channel, based on static resource constraints, e.g., network bandwidth bottlenecks. Transmission rates are chosen so as to minimize the average time needed to transfer data to all receivers. Analysis and simulation are used to show that our policies for rate selection perform well for large and diverse receiver groups and make efficient use of network bandwidth. Moreover, we find that only a small number of multicast groups are needed to reap most of the possible performance benefits.     

The Stutter Go Back-N ARQ Protocol

In this paper we consider the problem of designing a good ARQ protocol for a message transmission environment characterized by high error rates and/or long propagation delays. We derive the average queue length for an idealized ARQ protocol for such an environment. We also describe a modification that can be made to existing ARQ protocols which can significantly decrease queue lengths in such an environment. We show that for the case of low message traffic rates, the modified Go Back-Nprotocol approaches the idealized scheme in performance.     

A comparison of sender-initiated and receiver-initiated reliablemulticast protocols

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