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