INTERNET-DRAFT Onur Arpacioglu, Cornell University
Tara Small, Cornell University
Zygmunt J. Haas, Cornell University
Expires in six months on February 2, 2004 August 2, 2003
Notes on Scalability of Wireless Ad Hoc Networks
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC 2026, except the right to produce
derivative works is not granted.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that other
groups may also distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference material
or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Distribution of this memo is unlimited.
Abstract
This document provides a working definition of "absolute scalability" and "weak
scalability" of a method of an ad hoc network, and also a way of comparing the
scalability of two different methods. A method may be a protocol, an algorithm,
or a scheme whose scalability needs to be evaluated. For example, it may be a
routing protocol or a MAC protocol. "Absolute scalability" emphasizes the
asymptotic behavior of a set of metrics, which define the efficiency of the
network as a network parameter tends to infinity. "Weak scalability" refers
to the comparison of the metrics over a given range. Finally, fairness in the
comparison of these metrics is discussed.
1. Introduction
The current focus of the IRTF MANET WG is the investigation of scalability
techniques, in order to develop standards for large-scale ad hoc networks. The
scalability of a method in an ad hoc network is a measure of its ability to
maintain efficiency, as some parameters of the network increase to very large
values. Many metrics contribute to the determination of scalability of a method
with respect to a given parameter in a particular environment. For this reason,
we say that a method is scalable with respect to a [parameter, metric, environment]
triple. For example, a method may be scalable with respect to [number of nodes,
required storage at each node, only single-hop communications]. It is also
possible to define the relative scalability of one method compared to another.
ABSOLUTE SCALABILITY involves asymptotic results, in which the efficiency does
not vanish as a chosen parameter approaches infinity. WEAK SCALABILITY considers
the effectiveness of the method within a finite range. Weak scalability may be
of interest, since it could be impossible for a parameter to exceed some value.
For example, the arrivals of packets into the network may be physically limited
to some maximum rate. In this case, the scalability over a finite range may be
a more applicable measure than asymptotic results.
Scalability is particularly important in the emerging field of sensor networks.
These networks can potentially consist of millions of very small nodes, which
communicate wirelessly among themselves. As the number of nodes increases, one
must determine whether the degradation in system performance can be tolerated.
Gupta and Kumar show in [1] that such a system may not be feasible; i.e., the
maximum achievable per node end-to-end throughput, L, decays to zero as the
number of nodes in the network, N, becomes increasingly large. This work is
one of the most challenging theoretical results on scalability.
[1] analyzes the scaling of L with respect to N via two network models. In the
first network model, the arbitrary network model, there are no restrictions on
the locations of the N nodes in the network domain, which is a circular disk of
area 1 meter^2. Each node is capable of maintaining at most one omnidirectional
transmission or reception at any time. There are no restrictions on the choice
of transmission powers, routing protocol, or spatial-temporal transmission
scheduling policy. The second network model is the random network model, in
which the node locations are uniformly distributed, the traffic pattern is
random and the fixed transmission power is adjusted to ensure connectivity of
the network as N becomes large.
Under the collision based reception model, [1] concludes that L is O(1/N^0.5)
for arbitrary networks, and O(1/[Nlog(N)]^0.5) for random networks. [1] also
finds scaling laws using a more realistic Signal-To-Interference-and-Noise
Ratio (SINR) threshold-based model by assuming that the path loss exponent,
g, exceeds 2. With the SINR threshold-based model, [1] concludes that L is
O(1/N^(1/g)) for arbitrary networks and O(1/N^(0.5)) for random networks.
In [2], Grossglauser and Tse conclude that the situation is more optimistic
if the nodes are mobile instead of static as in [1]. In addition to the random
network model and the SINR threshold-based model, [2] assumes also that nodes'
locations form a stationary ergodic process with a uniform distribution in the
network domain, that source-destination pairs never change, and that very long
end-to-end delays are tolerable. [2] concludes that there exists a routing and
scheduling policy that delivers a packet to its destination with no more than
two hops and allows L to stay above a positive constant while N goes to infinity.
Above all, both [1] and [2] claim that the maximum number of simultaneously
successful transmissions in a wireless network, Nt_max, is on the order of N;
i.e., Theta(N).
More recently, in [3], it was proven that L is O(1/N) even when the mobility
pattern of the nodes, the spatial-temporal transmission scheduling policy, the
temporal variation of transmission powers, the source-destination pairs, and
the possibly multi-path routes between them are all optimally chosen. This
result continues to hold even when the nodes are capable of maintaining
multiple transmissions and/or receptions simultaneously. In contrast with
[1] and [2], it was also shown that Nt_max has an upper bound that does not
depend on N. This upper bound is the transmission capacity of the network
domain, Nt_Q. For a circular network domain of area A, it has been demonstrated
that Nt_Q is O(A^min{g/2,1}) if g!=2 and O(A/log(A)) if g=2. In addition, Nt_Q
is O(g^2), and for processing gain G and threshold reception SINR b, Nt_Q
is O(G/b). Regarding scalability of practical systems, it was shown that a
desired per node end-to-end throughput is not achievable as N tends to infinity,
unless the following conditions apply: average number of hops between a source
and a destination does not exceed a constant (i.e., Theta(1)), the area A grows
with N, and N is O(A^min{g/2,1}) if g!=2 and O(A/log(A)) if g=2.
On the other hand, there have also been works on scalability, which focus on the
implementation of a routing scheme that offers satisfactory performance as N
increases [5-9]. To assess how satisfactorily their proposed schemes perform,
each of these works developed its own set of metrics such as packet delivery
ratio, throughput, end-to-end delay, routing overhead, average path length, or
storage requirements. Based on these metrics, and usually through the use of
simulation tools, these works compared the scalability of their schemes with
others while increasing N. The main limitation of these works is the subjective
choice of the metrics and other parameters used in the simulations. For example,
some researchers observe that their scheme offers lower control overhead compared
to some other schemes, up to a certain number of nodes, thus they claim their
scheme is scalable. Other researchers reach the same conclusion about their own
respective schemes by using different metrics and different number of nodes.
This problem was realized by Santivanez et al. in [4]. This paper was the first
step towards developing a more objective and theoretical framework for analyzing
scalability of wireless networks. [4] defines a network as scalable with respect
to a parameter if the offered load to the network does not exceed the maximum load
that the network can support under optimal conditions (ideal scheduling, ideal
routing, no overhead, etc.) as the parameter approaches infinity. [4] also defines
a routing protocol as scalable if as the parameter approaches infinity, the total
overhead of the routing protocol does not exceed the traffic load of the network
under optimal conditions. Moreover, [4] provides an approach for scalability
comparison of two routing protocols by comparing the growth rates of their overheads
with respect to a given parameter. The main contribution of the paper was the idea
of developing an analytical approach to evaluate scalability, rather than the use of
simulations. Some of the restrictions of this work include: (1) focusing on the
routing aspect of the problem, (2) comparing/evaluating scalability using routing
overhead exclusively, and (3) choosing a specific set of environmental parameters.
In the following sections, we propose a general framework to analyze scalability
of wireless networks.
2. Definitions
We define INDEPENDENT PARAMETERS as parameters that can be freely varied, and the
PRIMARY METRICS as quantities that are observed in the network. We also define
ENVIRONMENTAL PARAMETERS as parameters that define the operational conditions of
the network. The following are non-exhaustive lists of these attributes and
descriptions of their roles in the network. Though the lists focus primarily on
routing protocols, the scalability of other methods follows the same process.
2.1 Independent parameters
Methods are termed scalable with respect to certain parameters, as the parameters
approach infinity. These parameters are aspects of the network that an evaluator
of a method has the ability to change. Some of such possible parameters,
applicable to different types of methods, are listed below:
- Number of nodes
- Node density
- Traffic load
- Mobility
- 1/(Physical size of nodes)
- Accuracy [of the results of an algorithm]
2.2 Primary metrics
PRIMARY METRICS of the system are the dependent variables that are observed as
the network is scaled with respect to an independent parameter. Before using
any of these metrics for testing, they must be well defined. Possible specific
definitions of the metrics are provided below. Since, most often, for a particular
evaluation, an evaluator will choose more than one primary metric, the primary
metrics are arranged in a SCALABILITY VECTOR. In general, scalability of
individual metrics is insufficient to consider, but rather the scalability of
all of the components in the vector must be simultaneously considered. Examination
of the scalability vector can be indicative of which method (such as an algorithm
or a protocol) is most appropriate for a given application.
- (1/throughput) of the network
* Hop-by-hop throughput of a flow (includes packets which may be eventually
dropped)
* End-to-end throughput of a flow (does not include dropped packets)
* Throughput of the entire network
* Minimum throughput over all flows
* Average throughput over all flows
- Delay in the network
* Maximum or average hop-by-hop delay
* Maximum or average end-to-end delay
- Battery power required at the network nodes
- Memory/storage required at the network nodes
- Processing power required at the network nodes
- 1/(network lifetime)
* Network dies when one of the nodes dies
* Network dies when certain fraction of the nodes dies
* Network dies when all of the nodes die
* Network dies when the maximum number of possible connections decreases
below a threshold value
The complete set of primary metrics and their definitions may depend on the
application; however this minimal set of primary metrics should be addressed
first. Finite values of these metrics are necessary to ensure sufficient
communication in the network.
2.3 Environmental parameters
The theoretical results of [1-3] highlight the importance of the environmental
conditions and technological choices of the wireless network in the context of
scalability. For example, the traffic pattern, the path loss exponent, or the
area of the network domain can impose limitations on scalability. In general,
the following environmental parameters may affect scalability:
- Network characteristics:
* Mobility pattern of the nodes
* Initial distribution of node locations
* Area of the network domain
* Existence of a wired backbone; relation between numbers of nodes and base
stations
- Traffic pattern:
* Choice of destinations: random, local, etc
* Average number of hops between a source and a destination
- Routing layer:
* Method used to choose the next hop node of the received data
* Overhead introduced to facilitate these next hop decisions
* Method to identify nodes; e.g., uniquely identifying N nodes requires
Theta(log(N)) IDs, which grows with N indefinitely.
* Response to errors and failures
* Fairness in forwarding decisions
- Medium access layer:
* Reception model: collision-based, SINR threshold-based, BER-based or
probability-based, adaptive rate models
* Transmission model: ability to maintain multiple transmissions and/or
receptions simultaneously
* Scheduling of transmissions
* Response to unsuccessful transmissions
* Fairness in medium acquisition
- Physical layer:
* Link bandwidth
* Transmission and reception modes: omnidirectional, directional; beamwidth,
side lobes
* Propagation model: path loss exponent, fading, shadowing
* Modulation scheme: narrowband, wideband; processing gain, interference c
ancellation
* Power control, maximum transmission power, noise conditions
- Node design:
* Memory/storage at nodes: maximum storage space, certain amount of buffer overflow
permitted, loss is not allowed, or QoS buffering used
* Processing power: maximum number of CPU cycles per unit time, identical allocation
to all nodes, preference given to some nodes
2.4 Vanishing efficiency
EFFICIENCY of a network is said to VANISH as an independent parameter tends to infinity
if ANY of the primary metrics becomes arbitrarily large.
2.5 Absolute scalability
A method is termed ABSOLUTELY SCALABLE with respect to a given parameter, if the
efficiency of the network DOES NOT VANISH as the parameter tends to infinity. To
evaluate whether or not a method is absolutely scalable, precise definitions of all
primary metrics are required.
It should be noted that though, in some cases, the efficiency does not vanish, it is
possible that the primary metrics are finite, but very large. Other techniques and
tradeoffs may be used to improve their values, though these techniques are not
addressed here.
2.5.1 Example of absolute scalability
Consider the following example: we choose the number of nodes, N, as the independent
parameter. An entire scalability vector should be considered with the different
primary metrics as components, but for simplicity, we consider here only the
"total overhead" (as defined in [4]) component.
For constant average node degree, maximum path lengths increasing as Theta(N^0.5) and
other assumptions described in [4], the total overhead of HSLS (Hazy Sighted Link
State Routing Protocol) is Theta(N^1.5). Also, in the network model of [4], maximum
achievable throughput of the entire network is Theta(N). This means that as
N -> infinity, the total overhead of HSLS exceeds the amount the network can actually
support, so the throughput and efficiency vanish. Thus, we say that HSLS is not a
bsolutely scalable with respect to the triple [number of nodes, total overhead,
Theta(N^0.5) maximum path lengths…([4]'s environmental parameters)].
2.6 Relative scalability
An method e1 is termed MORE SCALABLE than another method e2 with respect to a given
parameter p and primary metric m (completely specified), if the limit as p approaches
infinity of m(e1)/m(e2) is zero. If the result of this limit is a positive constant,
then we say e1 and e2 are EQUALLY scalable.
Note that without also specifying the metric m, we are unable to define the relative
scalability of e1 and e2 in terms of a parameter p. e1 may be more scalable than e2
with respect to one metric, but less scalable with respect to another metric.
2.6.1 Example of relative scalability
Returning to the example from [4], we again use the number of nodes as the independent
parameter, and compare HSLS total overhead with SLS (Standard Link State). The entire
scalability vectors should be considered, but we choose to evaluate the "total overhead"
component only.
Using all the assumptions from the previous example, the total overhead of e1 = HSLS
is Theta(N^1.5) and the total overhead of e2 = SLS is Theta(N^2). This means that,
lim [m(e1)/m(e2)] = lim [Theta(N^1.5)/Theta(N^2)] = lim Theta(N^{-0.5}) = 0
N->inf. N->inf. N->inf.
Using the above definitions, this means that HSLS is more scalable than SLS with respect
to the triple [number of nodes, total overhead, Theta(N^0.5) maximum path lengths…([4]'s
environmental parameters)].
2.7 Relative weak scalability
It is possible that a parameter grows large in an ad hoc network, but cannot grow
arbitrarily large. In particular, it might be impossible/impractical for a parameter
to grow larger than some value, M. In this case, we consider only an interval [a, M],
where a is the minimum value of the parameter and M is its maximum value. A method e1
is termed MORE WEAKLY SCALABLE than another method e2 with respect to a given
parameter p and primary metric m, if the rate of decay of the metric measuring e1, m(e1),
is slower than that metric measuring e2, m(e2).
Let [m(e1(b))]' be the derivative (with respect to the independent parameter p) of m
measuring e1, when p=b. If the rate [m(e1) - m(e2)]' is negative at some point, it
means that m(e1) is increasing more slowly than m(e2), so that e1 is more scalable at
point p=b. To find the scalability over a range, we average the scalabilities at all
points in the interval over which p can assume values. {Int_a^M [[m(e1(p))]'] dp}/(M-a)
is the average value of the derivative of m(e1(p)) over the interval [a, M], and
{Int_a^M [[m(e1(p))-m(e2(p))]'] dp}/(M-a) is the average value of the derivative of
m(e1(p))-m(e2(p)) over the interval [a, M]. Evaluating this expression by the
fundamental law of Calculus, {Int_a^M [[m(e1(p))-m(e2(p))]'] dp}/(M-a) =
{[m(e1(M)) - m(e2(M))] - [m(e1(a)) - m(e2(a))]}/(M-a).
Therefore, e1 is MORE WEAKLY SCALABLE than e2 with respect to the metric m and the
parameter p over the range [a, M] if m(e1(M))-m(e1(a)) < m(e2(M))-m(e2(a)).
Similarly, if m(e1(M))-m(e1(a)) = m(e2(M))-m(e2(a)), then e1 and e2 are EQUALLY SCALABLE
with respect to the metric m and the parameter p over the range [a, M].
3. Challenges in application of results
The framework we suggest in this document allows users to compare the scalability of
methods, but we have yet to include the idea of a fair comparison. Clearly, absolute
scalability, relative scalability, and relative weak scalability of a method are heavily
dependent on the environmental parameters. Hence, when considering any of the primary
metrics, the environmental parameters must be specified with as much detail as possible.
A certain set of environmental parameters may lend itself well to one method compared
to another. For example, if the number of nodes is increased, then increasing the area
of the network domain and keeping the node density constant could lead to good scalability
patterns, while keeping the area of the network domain constant would cause the system
to suffer from high node density and would not likely be scalable. It may be difficult
to find a set of environmental parameters, which can lead to a fair comparison among
methods. Furthermore, interactions among environmental parameters and between independent
and environmental parameters may also affect fairness of a comparison. For example,
while comparing relative scalability of two routing protocols, the choice of the MAC
layer protocol may change the result of the comparison. As a result, although we have
provided a framework to evaluate scalability of methods, standardization of a set of
environmental parameters remains a challenge to achieve fair comparison among different
methods.
References:
[1] P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Trans. on
Info. Theory, vol. 46, no.2, pp. 388-404, March 2000.
[2] M. Grossglauser and D. Tse, "Mobility increases the capacity of wireless adhoc
networks," IEEE/ACM Trans. on Networking, vol. 10, no. 4, pp. 477-486, August 2002.
[3] O. Arpacioglu and Z. J. Haas, "On the scalability and capacity of wireless
networks with omnidirectional antennas", submitted to IEEE INFOCOM'04, Hong Kong,
China.
[4] C. Santivanez, B. McDonald, I. Stavrakakis, R. Ramanathan, "On the scalability
of ad hoc routing protocols", IEEE INFOCOM'02, New York, June 2002.
[5] A. Iwata, C. Chiang, G. Pei, M. Gerla, T. Chen, "Scalable routing strategies for
ad hoc wireless networks", IEEE Journal on Selected Areas in Communications, vol. 17,
issue: 8, August 1999, pp: 1369 -1379.
[6] C. Santivanez, R. Ramanathan, I. Stavrakakis, "Making link-state routing scale
for ad hoc networks", MobiHoc 2001, Long Beach, CA, USA, Oct. 4-5, 2001.
[7] X. Hong, M. Gerla, Y. Yi, K. Xu, and T. Kwon, "Scalable ad hoc routing in large,
dense wireless networks using passive clustering and landmarks", Proceedings of ICC 2002,
NY, April 2002.
[8] I. D. Aron, S. K. S. Gupta, "On the scalability of on-demand routing protocols for
mobile ad hoc networks: an analytical study", Journal of Interconnection Networks,
vol. 2, No. 1, pp: 5-29, 2001.
[9] J. Li, J. Jannotti, D. S. J. De Couto, D. R. Karger, R. Morris, "A scalable location
service for geographic ad hoc routing", Proceedings of the 6th ACM MobiCom, 2000.
Authors' Address
Onur Arpacioglu, Tara Small, and Zygmunt J. Haas
Wireless Networks Laboratory
School of Electrical and Computer Engineering
323 Frank Rhodes Hall
Cornell University
Ithaca, NY 14853
Phone: +1-607-255-3454
E-Mails: o.arpacioglu@cornell.edu, tsmall@cam.cornell.edu, haas@ece.cornell.edu
Comments
Please send comments to haas@ece.cornell.edu.
Expiry
This draft expires on Febuary 2, 2004