From eyh5@ee.cornell.edu Wed Oct 24 21:05:20 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9P15Jo25478 for ; Wed, 24 Oct 2001 21:05:19 -0400 (EDT) Received: from james (james.ee.cornell.edu [128.84.236.65]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f9P15hN07005 for ; Wed, 24 Oct 2001 21:05:43 -0400 Date: Wed, 24 Oct 2001 21:04:04 -0400 (EDT) From: Edward Hua To: egs@CS.Cornell.EDU Subject: 615 Paper # 45 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII The Capacity of Wireless Networks Piyush Gupta, P.R.Kumar This paper presents a comprehensive analysis of the capacity in an ad hoc mobile network. In so doing, the network is categorized into two types: arbitrary, where the node locations, destinations, and traffic demands are all arbitrary, and random, where the nodes and their destinations are randomly chosen. As in the paper by Li, et. al., the evaluation is based on the assumption that the ad hoc network is static rather than dynamically changing its topology. This gives rise to a perfect scheduling algorithm that has the knowledge of all nodes and traffic demands in such a network, thereby coordinating wireless transmissions to avoid collisions in the medium. The major contribution in this paper is that the authors have developed the theoretical limits of capacity in wireless networks. For arbitrary networks, the authors define an upper and lower bound on the transport capacity; likewise, an upper and lower bound are defined on the throughput capacity for random networks. One of the conclusions suggested in this paper is that defining subnetworks, each of which has the information of only its surrounding neighbors, may be a preferred approach that will prevent the throughput of each node from degrading too much. This philosophy is consistent with the current research attention being paid to locally active, globally reactive routing schemes in ad hoc networks. The authors have developed a number of theorms and their respective proofs to compute the theoretical upper and lower bounds of network capacity. This is all very good. However, there are no simulations provided that may verify their conclusions. Also, the derivations are based on the assumption that the wireless network is essentially static, a model that may not be applicable to all cases in practice. Nevertheless, this paper is one of the most comprehensive papers on ad hoc network capacity analysis, From wbell@CS.Cornell.EDU Wed Oct 24 22:05:57 2001 Return-Path: Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9P25vo01908 for ; Wed, 24 Oct 2001 22:05:57 -0400 (EDT) Received: from [192.168.1.100] (syr-66-24-16-64.twcny.rr.com [66.24.16.64]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id WAA09287 for ; Wed, 24 Oct 2001 22:05:55 -0400 (EDT) Subject: 615 PAPER #45 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: Evolution/0.16.99+cvs.2001.10.18.15.19 (Preview Release) Date: 24 Oct 2001 22:05:33 -0400 Message-Id: <1003975558.1043.70.camel@brute> Mime-Version: 1.0 45) Capacity of Wireless Networks This work inspects the surprisingly low performance and throughput of wireless networks and attempts to put an upper bound on the throughput of a wireless network. They investigate not only a theoretical upper bound on performance, but also an empirical study to back up their observations. The first insight is that a single node can only send or receive at one time, and only a single node in a transmission area can communicate at a single time, effectively silencing all their neighbors. So any optimal (collision free) network will exhibit the optimal transmission scheduling algorithm where only one node communicates in a given overhearing area. They also note that the problem is even worse than that-- there is a range surrounding the transmission area where anyone else transmitting will have their packets corrupted by the original transmission. This only further degrades the possible upper bound on throughput. They examine chains of nodes relaying a source transmission, which is the case in our ad-hoc networks where paths are multihop between sender and receiver. A theoretical bound on the overall communication throughput is 1/4 because of the observations earlier. They also show that even this bound is overly optimistic because nodes at the ends of the chains have less contention for the network than chains in the middle, and the source at the end of the chain can transmit packets much faster than the relays in the middle. A simple empirical simulation puts this bound at about 1/7. >From these observations, they move on to ideal node locations to provide the highest throughput in a lattice and from there move to a random node layout and a random traffic pattern. From these patterns, they show that although 802.11 doesn't have the optimal scheduling algorithm, it does do a reasonable job of scheduling packets for transmission. They show that the key scalability problem with ad-hoc networks is the locality of traffic, that as networks get larger, paths between communicating nodes get larger, and more network resources are utilized to deal with these communication channels, hence more local traffic will allow ad-hoc networks to scale. From daehyun@csl.cornell.edu Thu Oct 25 11:10:38 2001 Return-Path: Received: from wilkes.csl.cornell.edu (wilkes.csl.cornell.edu [132.236.71.69]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9PFAbo29981 for ; Thu, 25 Oct 2001 11:10:37 -0400 (EDT) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id LAA11988 for egs@cs.cornell.edu; Thu, 25 Oct 2001 11:10:32 -0400 (EDT) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200110251510.LAA11988@wilkes.csl.cornell.edu> Subject: 615 PAPER 45 To: egs@CS.Cornell.EDU Date: Thu, 25 Oct 2001 11:10:32 -0400 (EDT) X-Mailer: ELM [version 2.4ME+ PL54 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit This paper designed/analyzed a mathematical model of the capacity of wireless networks and gave a theoretical limit of the throughout. For the analysis, wireless networks are divided into two types. In Arbitrary Networks, nodes' locations, destinations and traffic pattern are arbitrary. In random networks, those are random, i.e. independently and uniformly distributed. For these two networks, mathematical models are designed and the upper bound and lower bound of capacity are analyzed. Because this paper is purely mathematical and I couldn't understand it, I may not be at a good position to review this paper. But I'd like give the following comments. 1. The main contribution of this paper is that it give theoretical limit of the capacity of wireless network. I think it is very important because this study can give a insight which simulation study cannot provide. 2. This paper showed that splitting the channel does not change the capacity limit. This was quite different from my thought that splitting the channel will reduce the collision and increase the capacity. 3. As far as I understand, the network model of this paper is static. Actually, the other paper I reviewed also assumed the static model. It might be because modeling/analyzing dynamic models are too difficult. Though Static model gives very useful knowledge, I'm not sure how well it will match with practical ad hoc networks. From c.tavoularis@utoronto.ca Thu Oct 25 11:14:30 2001 Return-Path: Received: from bureau6.utcc.utoronto.ca (bureau6.utcc.utoronto.ca [128.100.132.16]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9PFEUo00576 for ; Thu, 25 Oct 2001 11:14:30 -0400 (EDT) Received: from webmail1.ns.utoronto.ca ([128.100.132.24] EHLO webmail1.ns.utoronto.ca ident: IDENT-NOT-QUERIED [port 51449]) by bureau6.utcc.utoronto.ca with ESMTP id <240583-23264>; Thu, 25 Oct 2001 11:14:09 -0400 Received: by webmail1.ns.utoronto.ca id <126208-22902>; Thu, 25 Oct 2001 11:14:01 -0400 To: COM S 615 Subject: 615 PAPER 45 Message-ID: <1004022831.3bd82c2f7f663@webmail1.ns.utoronto.ca> Date: Thu, 25 Oct 2001 11:13:51 -0400 (EDT) From: c.tavoularis@utoronto.ca MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT User-Agent: IMP/PHP IMAP webmail program 2.2.3 This paper provides many theoretical results on the capacity of wireless networks, supported by simulation. Specifically, it considers random and arbitrary networks, and determines the maximum throughput capacity using the protocol model and the physical model. These results help us see the constraints of wireless networks, particularly in terms of scalability. Random networks distribute nodes with a uniform distribution and have random traffic patterns, while arbitrary networks choose node distribution, and traffic arbitrarily in the workspace. The theoretical upper bound on capacity assumes perfect scheduling without collision and no node mobility. Obviously, this upper bound is far from reality and will degrade severely once nodes contend for the channel. The upper bound is independent of whether a single channel is used, or divided into sub channels. This is an important result due to the difficulties of employing FDMA and CDMA in wireless networks. Capacity of the system was found to improve if the power decays faster as a function of distance. This is because fast decaying signals allow more frequency reuse throughout the network. Throughput decreases with n, and therefore increasing the size of networks greatly degrades performance. Scaling also increases power consumption per node, since each node will have to participate in more packet forwarding. The authors suggest that ad hoc networks can accommodate larger scale networks as long as source destination pairs remain local. Using Voronoi tessellation of cells, and straight lines to model paths, an upper bound is found on the traffic load passing through each cell or cluster of nodes. Also, they suggest that forming clusters or cells with an active cluster head will be profitable and possibly reduce power consumption. I think the most important result is that wireless networks cannot be scaled easily, and effort should be made to keep them small. In general, it reinforces the intuition that wireless networks have very limited resources that only become worse with channel contention and mobility, which occur frequently in ad hoc networks. From teifel@csl.cornell.edu Thu Oct 25 11:46:09 2001 Return-Path: Received: from disney.csl.cornell.edu (disney.csl.cornell.edu [132.236.71.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9PFk9o04774 for ; Thu, 25 Oct 2001 11:46:09 -0400 (EDT) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f9PFk4u70278 for ; Thu, 25 Oct 2001 11:46:04 -0400 (EDT) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Thu, 25 Oct 2001 11:46:03 -0400 (EDT) From: "John R. Teifel" To: Subject: 615 PAPER 45 Message-ID: <20011025113314.G62337-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Li, Blake, De Couto, Lee, Morris: This paper discuses the capacity of ad hoc wireless networks. It mainly examines the interactions of the MAC layer with ad hoc forwarding. The authors use simluation and analysis from first principles to examine the capacitance of ad hoc networks depending on the network size, traffic patterns, and radio interactions. They present results analyzing the per node capacity as an ad hoc network scales. It turns out that the average distance between source and destination nodes must remain small as the network increases in size, in order for the total network capacity to grow. The 802.11 MAC layer acheives 1/7 of the raw channel bandwidth of a long chain of nodes, whereas in theory 1/4 of the raw channel bandwidth is possible. 802.11 is more efficient at routing orderly local traffic patterns and approaches the theoreticaly capacity per node in large random networks (which is slightly puzzling to me, given the first assertion in this sentence). The key thing for the feasibility of large ad hoc networks is the locality of traffic. From samar@ece.cornell.edu Thu Oct 25 11:57:06 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9PFv5o06276 for ; Thu, 25 Oct 2001 11:57:05 -0400 (EDT) Received: from descartes (descartes.ee.cornell.edu [128.84.236.60]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f9PFvPN20301 for ; Thu, 25 Oct 2001 11:57:25 -0400 Date: Thu, 25 Oct 2001 11:56:34 -0400 (EDT) From: Prince Samar X-Sender: samar@descartes.ee.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 45 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 45) The Capacity of Wireless Networks This SEMINAL work by Gupta and Kumar presents theoretical bounds for the capacity of wireless networks. The network is assumed to be stationary where nodes are randomly located on a disc/sphere and the paper allows for ideal scheduling algorithm which knows the locations of all the nodes and all the traffic demands. The paper shows a rather pessimistic result that as the number of nodes (which are communicating with each other) in the wireless network become large, the throughput of the network diminishes to zero. The throughput constriction comes from the pervasive need for all the nodes to share the channel locally with other nodes while forwarding packets originating at the node or at other nodes. The paper shows that even with full knowledge of the network and perfect scheduling of the nodes, temporally and spatially, the throughput of the multi-hop wireless network decreases with increase in the number of nodes in the network. However, the authors have considered stationary networks. In a very interesting work by David Tse, it has been shown that mobility actually increases the throughput if one can allow for long delays in the actual delivery of the packets (Ah! a glimmer of hope.. but probably not very practical). Their argument is that due to random mobility, eventually the source (or one of the small number of nodes to which the node forwarded the packet) would move close enough to the destination so that the packet can actually be delivered directly (or in a very small number of hops). The authors discuss some possible implications of their work. They state that the performance of large networks may be unacceptable and so network designers should perhaps focus of designing small networks or networks where hosts limit their communication to their neighborhood. They show that if all the nodes transmit data to only their neighbors, the data rate can be maintained constant irrespective of the actual size of the network. The show that in a network with n nodes, the fraction of time that a node's modem is busy decreases with n in a inverse log fashion. Another implication of their work is the feasibility of clustering in multi-hop wireless networks. Division of a channel into subchannels (frequency division, time division or code division) does not have any effect on their results. They show that adding purely relaying nodes into the network may increase the capacity, but a large number of such nodes may be required for a noticeable change in capacity. It has also been pointed out that the transport capacity improves if the rf power fall-off exponent is large. The authors point out a few areas of further research. They are including mobility, link failures and multiple access into the analysis. Delay in delivering the data packets to the destination also needs to be taken into account. Spatial directivity or beamforming may improve the performance. Also, having an information theoretic picture of this problem would be immensely interesting. From papadp@ece.cornell.edu Thu Oct 25 12:07:19 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9PG7Ho07578 for ; Thu, 25 Oct 2001 12:07:18 -0400 (EDT) Received: from hegel (hegel.ee.cornell.edu [128.84.236.63]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f9PG7bN20602; Thu, 25 Oct 2001 12:07:37 -0400 Date: Thu, 25 Oct 2001 12:06:56 -0400 (EDT) From: "Panagiotis (Panos) Papadimitratos" X-Sender: papadp@hegel.ee.cornell.edu To: Emin Gun Sirer cc: Panagiotis Papadimitratos Subject: 615 PAPER 45 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Review of: "The capacity of wireless networks," by P.Gupta, P.R. Kumar IEEE trans. on information theory, vol. 46, no2., march 2000. papadp@ece.cornell.edu Panagiotis Papadimtratos The paper investigates the maximum achievable transmission rate by a node in a multihop wireless topology. The communication model is random pairwise multihop transmission, under two absrtact models ('protoco, physical'), that determine the criteria for correct reception. The network models considered are 'arbitrary' and 'random', the difference being not so much the selection of the destination but more the homogeneity of node parameters (xmission radius, rate etc). The paper shows that the achievable upper bound, under the assumption of an optimal placement of nodes, choice of transmission radius, and for a *single* shared channel, cannot be improved even if multiple channels were used. (Even if an optimal scheduling of transmissions was feasible; of course, note that the aggregate throughput of the set of channels *cannot* exceed that of the initial channel.) A key point is the set up of the model itself: the n randomly chosen nodes chose a random destination (i.e., possibly high average path length) and transmit at a *constant* rate W. Neither assumption is necessarily valid for a wide range of MANET instances. To that extent, the 'shadow' on the ad hoc networking paradigm might not be that heavy (:-). Scalabilty is undeniably harmed as achievable node-throughput is forced to a lower value, inversely proportional to the sqrt() of the network size, but under the above assumptions. The direction that the authors made, i.e., the design of smaller networks, is in essence the realisation of the simple fact that MANET traffic is localized, or MANET subdomains are (may be) stub AS's. If this is compared with the outline of the [Li, Morris] paper result, things start to look better. (Note: the Grossglausser] paper is inticing, but its communication model does not appear more realistic, to say the least) From viran@csl.cornell.edu Thu Oct 25 12:09:07 2001 Return-Path: Received: from moore.csl.cornell.edu (moore.csl.cornell.edu [132.236.71.83]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9PG97o07690 for ; Thu, 25 Oct 2001 12:09:07 -0400 (EDT) Received: from localhost (viran@localhost) by moore.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f9PG92s15761 for ; Thu, 25 Oct 2001 12:09:02 -0400 (EDT) (envelope-from viran@moore.csl.cornell.edu) X-Authentication-Warning: moore.csl.cornell.edu: viran owned process doing -bs Date: Thu, 25 Oct 2001 12:09:02 -0400 (EDT) From: "Virantha N. Ekanayake" To: Subject: 615 Paper 45 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper gives a theoretical approach to estimating throughput of wireless networks. It brings several insights to light: That each node's throughput is limited by the load imposed by other nodes, and that even when the nodes are located optimally (albeit on a disk) a node's throughput is reduced by a factor of 1/sqrt(n) which becomes insignificant as the number of nodes increases. However, for communicating with neighbors, a constant bit rate is predicted. This paper was very well written, and addresed a long standing need for more formal models for ad-hoc networks. It had a lot of formal proofs, most of which I skipped over, but it seems their conclusions have merit. It also points towards the future of ad-hoc networks, and the perhaps the need for core-based routing protocols where the size of the local networks can be kept small enough such that a throughput degradation is kept manageable. In this case, the pattern of communication will be non-random (i.e. communication will mainly (hopefully!) be local) and the result here may not apply. From jcb35@cornell.edu Thu Oct 25 14:38:37 2001 Return-Path: Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9PIcbo27160 for ; Thu, 25 Oct 2001 14:38:37 -0400 (EDT) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id OAA12730 for ; Thu, 25 Oct 2001 14:38:32 -0400 (EDT) From: jcb35@cornell.edu Date: Thu, 25 Oct 2001 14:38:32 -0400 (EDT) X-Sender: jcb35@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 paper 45 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper looked at the theoretical capacity limits of wireless networks without any centralized structure. The evaluate the limitations of 802.11 and find a theoretical upper limit for networks with arbitrarily and randomly located nodes and traffic patterns. The most significant finding of this paper is that a wireless network modeled with no interference with nodes capable of transmitting at W bits/sec employing a common range, each with a randomly chose destination, is limited by the number of nodes proportional to 1/sqrt(nlogn). The only real problem with this is that it probably doesn't model ad-hoc networks very well - it just provides a specific upper bound - I doubt any ad-hoc networking application has this communication pattern, and this is assuming that all nodes do not move. Never the less, it does provide a limit for this particular setup.