From eyh5@ee.cornell.edu Wed Oct 24 21:05:20 2001
Return-Path: <eyh5@ee.cornell.edu>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; Wed, 24 Oct 2001 21:05:43 -0400
Date: Wed, 24 Oct 2001 21:04:04 -0400 (EDT)
From: Edward Hua <eyh5@ee.cornell.edu>
To: egs@CS.Cornell.EDU
Subject: 615 Paper # 45
Message-ID: <Pine.GSO.4.21.0110242103320.18644-100000@james.ee.cornell.edu>
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: <wbell@CS.Cornell.EDU>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; Wed, 24 Oct 2001 22:05:55 -0400 (EDT)
Subject: 615 PAPER #45
From: Walter Bell <wbell@CS.Cornell.EDU>
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: <daehyun@csl.cornell.edu>
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 <egs@cs.cornell.edu>; 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 <daehyun@csl.cornell.edu>
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: <c.tavoularis@utoronto.ca>
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 <egs@cs.cornell.edu>; 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 <egs@CS.Cornell.EDU>
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: <teifel@csl.cornell.edu>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; 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" <teifel@csl.cornell.edu>
To: <egs@CS.Cornell.EDU>
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: <samar@ece.cornell.edu>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; Thu, 25 Oct 2001 11:57:25 -0400
Date: Thu, 25 Oct 2001 11:56:34 -0400 (EDT)
From: Prince Samar <samar@ece.cornell.edu>
X-Sender: samar@descartes.ee.cornell.edu
To: egs@CS.Cornell.EDU
Subject: 615 PAPER 45
Message-ID: <Pine.GSO.4.21.0110251155590.12898-100000@descartes.ee.cornell.edu>
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: <papadp@ece.cornell.edu>
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 <egs@CS.Cornell.EDU>; 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" <papadp@ece.cornell.edu>
X-Sender: papadp@hegel.ee.cornell.edu
To: Emin Gun Sirer <egs@CS.Cornell.EDU>
cc: Panagiotis Papadimitratos <papadp@ece.cornell.edu>
Subject: 615 PAPER 45
Message-ID: <Pine.GSO.4.21.0110251141350.19832-100000@hegel.ee.cornell.edu>
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: <viran@csl.cornell.edu>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; 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" <viran@csl.cornell.edu>
To: <egs@CS.Cornell.EDU>
Subject: 615 Paper 45
Message-ID: <Pine.BSF.4.33.0110251208270.14081-100000@moore.csl.cornell.edu>
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: <jcb35@cornell.edu>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; 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: <Pine.SOL.3.91.1011025141626.25164C-100000@travelers.mail.cornell.edu>
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.