We investigate the resiliency of wireless sensor networks against sensor capture attacks when the network uses the random pairwise key distribution scheme of Chan et al. We present conditions on the model parameters so that the network is: 1) unassailable and 2) unsplittable, both with high probability, as the number n of sensor nodes becomes large. Both notions are defined against an adversary who has unlimited computing resources and full knowledge of the network topology, but can only capture a negligible fraction o(n) of sensors. We also show that the number of cryptographic keys needed to ensure unassailability and unsplittability under the pairwise key predistribution scheme is an order of magnitude smaller than it is under the key predistribution scheme of Eschenauer and Gligor.

We consider random threshold graphs where the fitness variables are exponentially distributed. Simulations show that the zero-one law for graph connectivity exhibits a sharp phase transition. We formalize this observation by providing exact asymptotics for the width of the phase transition in the many node regime.

We explore the scaling properties for graph connectivity in random threshold graphs. In the many node limit, we provide a complete characterization for the existence and type of the underlying zero-one laws, and identify the corresponding critical scalings. These results are consequences of well-known facts in Extreme Value Theory concerning the asymptotic behavior of running maxima on i.i.d. random variables. In the important special case of exponentially distributed fitness, we show that the (essentially unique) critical scaling which ensures a power-law degree distribution, does not result in graph connectivity in the asymptotically almost sure (a.a.s.) sense.

We investigate the secure connectivity of wireless sensor networks under the random pairwise key predistribution scheme of Chan, Perrig, and Song. Unlike recent work carried out under the assumption of full visibility, here we assume a (simplified) communication model where unreliable wireless links are represented as independent on/off channels. We present conditions on how to scale the model parameters so that the network 1) has no secure node that is isolated and 2) is securely connected, both with high probability, when the number of sensor nodes becomes large. The results are given in the form of zero-one laws, and exhibit significant differences with corresponding results in the full-visibility case. Through simulations, these zero-one laws are shown to also hold under a more realistic communication model, namely the disk model.

We investigate the connectivity of wireless sensor networks under the random pairwise key predistribution scheme of Chan Under the assumption of full visibility, this reduces to studying the connectivity in the so-called random K-out graph H (n;K); here, n is the number of nodes and K <; n is an integer parameter affecting the number of keys stored at each node. We show that if K ≥ 2 (respectively, K=1), the probability that H (n;K) is a connected graph approaches 1 (respectively, 0) as n goes to infinity. For the one-law this is done by establishing an explicitly computable lower bound on the probability of connectivity. Using this bound, we see that with high probability, network connectivity can already be guaranteed (with K ≥ 2) by a relatively small number of sensors. This corrects earlier predictions made on the basis of a heuristic transfer of connectivity results available for Erdös-Rényi graphs.

We investigate the connectivity of wireless sensor networks under the random pairwise key predistribution scheme of Chan et al. Under the assumption of full visibility, this reduces to studying connectivity in the so-called random K-out graph H(n;K); here n is the number of nodes and K < n is an integer parameter affecting the number of keys stored at each node. We show that if K ≥ 2 (resp. K = 1), the probability that H(n; K) is a connected graph approaches 1 (resp. 0) as n goes to infinity. This is done by establishing an explicitly computable lower bound on the probability of connectivity. From this bound we conclude that with K ≥ 2, the connectivity of the network can already be guaranteed by a relatively small number of sensors with very high probability. This corrects an earlier analysis based on a heuristic transfer of classical connectivity results for Erdős-Rényi graphs.

The random key graph is a random graph naturally associated with the random key predistribution scheme introduced by Eschenauer and Gligor in the context of wireless sensor networks (WSNs). For this class of random graphs, we establish a new version of a conjectured zero-one law for graph connectivity as the number of nodes becomes unboundedly large. The results reported here complement and strengthen recent work on this conjecture by Blackburn and Gerke. In particular, the results are given under conditions which are more realistic for applications to WSNs.

We investigate the secure connectivity of wireless sensor networks under the pairwise key distribution scheme of Chan et al.. Unlike recent work which was carried out under the assumption of full visibility, here we assume a (simplified) communication model where unreliable wireless links are represented as on/off channels. We present conditions on how to scale the model parameters so that the network i) has no secure node which is isolated, and ii) is securely connected, both with high probability when the number of sensor nodes becomes large. The results are given in the form of zero-one laws, and exhibit significant differences with corresponding results in the full visibility case.

We investigate the security of wireless sensor networks under the pairwise key distribution scheme of Chan et al. [2]. We present conditions on how to scale the model parameters so that the network is i) unassailable, and ii) unsplittable, both with high probability, as the number of sensor nodes becomes large. We show that the required number of secure keys to be stored in the memory of each sensors is an order of magnitude smaller than what is required for the Eschenauer-Gligor scheme [5].

The pairwise key distribution scheme of Chan et al. is a randomized key predistribution scheme which enables cryptographic protection in wireless sensor networks (WSNs). This pairwise scheme has many advantages over other randomized key predistribution schemes but has been deemed non-scalable due to (i) the large number of keys required to ensure secure connectivity; and (ii) implementation difficulties when sensors are required to be deployed in multiple stages. Here, we address this issue by proposing an implementation of the pairwise scheme that supports the gradual deployment of sensor nodes in several consecutive phases. We show how the scheme parameter should be adjusted with the number n of sensors so that secure connectivity is maintained in the network throughout all the stages of the deployment. We also discuss briefly the relation between the scheme parameter and the amount of memory that each sensor needs to spare for storing their keys. By showing that O(log n) many keys per node suffice to achieve secure connectivity at every step of the deployment, we confirm the scalability of the pairwise scheme in the context of WSNs.

We consider an extension to the disk model in one dimension where communication links established between nodes may fail. With the help of the method of first and second moments, we investigate the zero-one laws for the property that there are no isolated nodes in the underlying random graph. Two specific situations are discussed: For the unit circle we prove a full zero-one law and determine its critical scaling. For the unit interval we derive a zero-law and a one-law which capture deviations from different critical scalings; a completely symmetric zero-one law is established under an additional condition. Analysis and simulations both indicate the possible presence of a gap between the one-law critical scalings for the unit interval and the unit circle. This discrepancy is quite surprising given that the zero-one laws for the absence of isolated nodes are identical in the geometric random graphs on the unit interval and on the unit circle. Connections to recent results by Yi et al. are discussed.

The random key graph is the random graph induced by the random key predistribution scheme of Eschenauer and Gligor under the assumption of full visibility. We report on recent results concerning a conjectured zero-one law for graph connectivity, and provide an outline for its proof.

We consider the geometric random graph where n points are distributed independently on the unit interval [0, 1] according to some probability distribution function F with density f. Two nodes are adjacent (i.e., communicate with each other) if their distance is less than some transmission range. We survey results, some classical and some recently obtained by the authors, concerning the existence of zero-one laws for graph connectivity, the type of zero-one laws under the specific assumptions made, the form of its critical scaling and its dependence on the density f. We also present results and conjectures concerning the width of the corresponding phase transition. Engineering implications are discussed for power allocation.

We consider a collection of n independent points which are distributed on the unit interval [0,1] according to some probability distribution function F. Two nodes are said to be adjacent if their distance is less than some given threshold value. When F admits a nonvanishing density f , we show under a weak continuity assumption on f that the property of graph connectivity for the induced geometric random graph exhibits a strong zero-one law, and we identify the corresponding critical scaling. This is achieved by generalizing to nonuniform distributions a limit result obtained by Levy for maximal spacings under the uniform distribution.

We consider the random graph induced by the random key predistribution scheme of Eschenauer and Gligor under the assumption of full visibility. We show the existence of a zero-one law for the absence of isolated nodes, and complement it by a Poisson convergence for the number of isolated nodes. Leveraging earlier results and analogies with Erdos-Renyi graphs, we explore similar results for the property of graph connectivity.

We consider the random network where n points are placed independently on the unit interval [0,1] according to some probability distribution function F. Two nodes communicate with each other if their distance is less than some transmission range. When F admits a continuous density f with f*= inf (f(x), x isin [0,1]) > 0, the property of graph connectivity for the underlying random graph is known to admit a strong critical threshold. Through a counterexample, we show that only a weak critical threshold exists when f*= 0 and we identify it. Implications for the critical transmission range are discussed.

We investigate how quickly phase transitions can occur in one-dimensional geometric random graph models of MANETs. In the case of graph connectivity and the absence of isolated nodes, we show that the transition width behaves like n-1 (when the number n of nodes is large), a significant improvement over asymptotic bounds given recently by Goel et al. for arbitrary monotone graph properties. We also outline how the approach used here could be applied in higher dimensions and for other graph properties.

To study the resequencing delay caused by multipath routing, we consider a system of parallel queues under random routing as a model of network routing behavior. The impact of resequencing on packet end-to-end delay is explored through the newly introduced resequencing index. We compute this new metric under several distributional asumptions (e.g., light vs. heavy tails) on routing delays.

We introduce the notion of Temporal Correlations (TC) ordering as a way to compare strength of temporal correlations in streams of requests. This notion is based on the supermodular ordering, a concept of positive dependence used for comparing dependence structures in sequences of rvs. We explore how the TC ordering captures the strength of temporal c correlations in several Web request models, namely, the higher-order Markov chain model (HOMM), the partial Markov chain model (PMM) and the Least-Recently-Used stack model (LRUSM). We also show how the comparison in the TC ordering is compatible with comparisons of some well-known locality of reference metrics, namely, the working set size and the inter-reference time. We establish a folk theorem to the effect that the stronger the temporal correlations, the smaller the miss rate for the PMM. Conjectures and simulations are offered regarding this folk theorem under the HOMM and under the LRUSM. The validity of this folk theorem is also discussed for general input streams under the Working Set algorithm.

We characterize the optimal M-ary pulse amplitude modulation (PAM) constellation under a general energy constraint. It is shown that uniform M-ary PAM may not always yield the best signal design, e.g., under the average energy constraint. We also identify situations where uniform PAM is optimal, e.g., the peak energy constraint

We consider the problem of bounding the loss rate of the aggregation of independent on-off sources in a bufferless model by the loss rate resulting from the aggregation of i.i.d. on-off sources. This is done through a unified framework based on the interplay of well-known results from the theory of variability orderings with the concept of majorization ordering. We use a basic comparison result to readily derive a bound of Rasmussen et al. for heterogeneous sources and an upper bound of Mao and Habibi for homogeneous sources, and to discuss a second upper bound proposed by these authors. It is argued that this conjectured upperbound is too tight in general, and should be replaced by a new and provably correct upper bound.

In communication networks, packets from the same source-destination pair may be routed along several paths and arrive at their receiver out of order. This often necessitates the use of a resequencing buffer at the destination. We consider such a network of parallel links with a general packet arrival and service processes, and resequencing. We establish stochastic comparisons for the end-to-end delay (including the time at the resequencing buffer) in the heavy and light traffic regimes, between two different static scheduling mechanisms, namely Bernoulli and round-robin routing. The results show that round-robin outperforms Bernoulli routing, as yet another instance of the folk theorem that "determinism minimizes delays".

The performance of demand-driven caching depends on the locality of reference exhibited by the stream of requests made to the cache. In particular, it is expected that the stronger the locality of reference, the smaller the miss rate of the cache. For the independent reference model, this amounts to a smaller miss rate when the popularity distribution of requested objects in the stream is more skewed. We formalize this "folk theorem" through the companion concepts of majorization and Schur-concavity. This folk theorem is established for caches operating under a random on-demand replacement algorithm (RORA). However, the result fails to hold in general under the (popular) LRU and CLIMB policies, but can he established when the input has a Zipf-like popularity pmf with large skewness parameter. In addition, we explore how the majorization of popularity distributions translates into comparisons of three well-known locality of reference metrics, namely the inter-reference time, the working set size and the stack distance.

We consider a cache operating under a demand-driven replacement policy when document requests are modeled according to the Independent Reference Model (IRM). We characterize the popularity pmf of the stream of misses from the cache, the so-called output of the cache, for a large class of demand-driven cache replacement policies. We measure strength of locality of reference in a stream of requests through the skewness of its popularity distribution. Using the notion of majorization to capture this degree of skewness, we show that for the policy A0 and the random policy, the output always has less locality of reference than the input. However, we show by counterexamples that this is not always the case under the LRU and CLIMB policies when the input is selected according to a Zipf-like pmf. In that case, conjectures are offered (and supported by simulations) as to when LRU or CLIMB caching indeed reduces locality of reference.

Replacement policies for general caching applications and Web caching in particular have been discussed extensively in the literature. Many ad-hoc policies have been proposed that attempt to take adavantage of the retrieval latency of documents, their size, the popularity of references and temporal locality of requested documents. However, the problem of finding optimal replacement policies under these factors has not been pursued in any systematic manner. In this paper, we take a step in that direction: we first show, still under the independent reference model, that a simple Markov stationary replacement policy, called the policy C*/sub 0/, minimizes the long-run average metric induced by nonuniform document costs when document eviction is optional. We then propose a framework for operating caching systems with multiple performance metrics. We do so by solving a constrained caching problem with a single constraint. The resulting constrained optimal replacement policy is obtained by simple randomization between two Markov stationary optimal replacement policies C*/sub 0/ but induced by different costs.

A stochastic model of an ECN/RED gateway with competing TCP sources sharing the capacity is considered. As the number of competing flows becomes large, the queue behavior at the gateway can be described by a two-dimensional recursion and the throughput behavior of individual TCP flows becomes asymptotically independent. The steady-state regime of the limiting behavior can be calculated from a well-known TCP throughput model with fixed loss probability. In addition, a central limit theorem is presented, yielding insight into the relationship between the queue fluctuation and the marking probability function. We confirm the results by simulations and discuss their implications for network dimensioning.

We use recent advances from the theory of multivariate stochastic orderings to formalize the "folk theorem" to the effect that positive correlations lead to increased buffer occupancy and larger buffer levels at a discrete-time infinite capacity multiplexer queue. Input sequences are compared in the supermodular (sm) ordering and buffer contents in the increasing convex (icx) ordering, respectively. Three popular classes of (discrete-time) traffic models are discussed, namely the fractional Gaussian noise traffic model, the on-off source model and the M|G|/spl infin/ traffic model. The independent version of an input process in each of these classes of traffic models is a member of the same class. In varying degree of generality, we show that this independent version is smaller than the input sequence itself, and that the corresponding buffer content processes are similarly ordered.

We briefly review the dynamics of TCP when combined with explicit congestion notification/ECN/REDrandom early detection (ECN/RED). Under the assumption that ECN/RED is utilized at the bottleneck, the TCP congestion control algorithm dynamically adjusts the size of the congestion window (the amount of unacknowledged packets in the network per round-trip) by the following mechanism. In a round-trip, if all the packets transmitted are not marked, then the size of the congestion window is increased by one packet for the next round-trip. On the other hand, if at least one packet is marked in the roundtrip, the congestion window is halved. The probability that the router will mark packets in the buffer depends on the average queue length of the time of packet arrival. The average queue length is calculated by an exponential average filter with large memory to prevent RED from reacting too fast. As a result, consecutive incoming packets into RED are marked with almost identical probability. With these dynamics in mind, we construct a simple discrete-time model which captures basic features of the interaction between TCP and ECN/RED.

We consider a stochastic model of a RED gateway under competing TCP-like sources sharing the capacity. As the number of competing flows becomes large, the queue behavior of RED can be described by a two-dimensional recursion. We confirm the result by simulations and discuss their implications for the network dimensioning problem.

We present an approximate analysis of a discrete-time queue with correlated arrival processes of the so-called M/G//spl infin/ type. The proposed heuristic approximations are developed around asymptotic results in the heavy and light traffic regimes. Investigation of the system behavior in light traffic quantifies the differences between the gradual M/G//spl infin/ inputs and the instantaneous arrivals of a classical GI/GI/1 queue. In heavy traffic, salient features are effectively captured by the exponential distribution and the Mittag-Leffler special function, under short- and long-range dependence, respectively. By interpolating between the heavy and light traffic extremes we derive approximations to the queue size distribution, applicable to all traffic intensities. We examine the accuracy of these expressions and discuss possible extensions of our results in several numerical examples.

Statistical evidence suggests that the autocorrelation function of a compressed-video sequence is better captured by /spl rho/(k)=e/sup -/spl beta//spl radic/(k)/ than by /spl rho/(k)=/sup -/spl beta//=e/sup -/spl beta/ log k/ (long-range dependence) or /spl rho/(k)=e/sup -/spl beta/k/. A video model with such a correlation structure is introduced based on the so-called M/G//spl infin/ input processes. Though not Markovian, the model exhibits short-range dependence. Using the queueing performance under "real" video traffic as a reference, we study via simulations the queueing performance under two video models: the M/G//spl infin/ model and the fractional ARIMA (F-ARIMA) model (which exhibits LRD). Our results indicate that the M/G//spl infin/ model is much more accurate in predicting the actual queueing performance than the F-ARIMA model. Furthermore, only /spl Oscr/(n) computations are required to generate an M/G//spl infin/ trace of length n, compared to /spl Oscr/(n/sup 2/) for a F-ARIMA trace.

Statistical evidence suggests that the autocorrelation function p(k) (k=0,1,...) of a compressed-video sequence is better captured by p(k)=e/sup -/spl beta//spl radic/k/ than by p(k)=k/sup -/spl beta//=e/sup -/spl beta/logk/ (long-range dependence) or p(k)=e/sup -/spl beta/k/ (Markovian). A video model with such a correlation structure is introduced based on the so-called M/G//spl infin/ input processes. In essence, the M/G//spl infin/ process is a stationary version of the busy-server process of a discrete-time M/G//spl infin/ queue. By varying G, many forms of time dependence can be displayed, which makes the class of M/G//spl infin/ input models a good candidate for modeling many types of correlated traffic in computer networks. For video traffic, we derive the appropriate G that gives the desired correlation function p(k)=e/sup -/spl beta//spl radic/k/. Though not Markovian, this model is shown to exhibit short-range dependence. Poisson variates of the M/G//spl infin/ model are appropriately transformed to capture the marginal distribution of a video sequence. Using the performance of a real video stream as a reference, we study via simulations the queueing performance under three video models: our M/G//spl infin/ model, the fractional ARIMA model (which exhibits LRD), and the DAR(1) model (which exhibits a Markovian structure). Our results indicate that only the M/G//spl infin/ model is capable of consistently providing acceptable predictions of the actual queueing performance. Furthermore, only O(n) computations are required to generate an M/G//spl infin/ trace of length n, compared to O(n/sup 2/) for an F-ARIMA trace.

We suggest the M|G|/spl infin/ input process as a viable model for network traffic due to its versatility and tractability. We characterize the process as short- or long-range dependent by means of a simple test. To gauge its performance, we study the large buffer asymptotics of a multiplexer driven by an M|G|/spl infin/ input process. The decay rate of the tail probabilities for the buffer content (in steady-state) is investigated using large deviations techniques suggested by Duffield and O'Connell (see Mathematical Proceedings of the Cambridge Philosophical Society, no.118, p.363-74, 1995). We show that the selection of the appropriate large deviations scaling is related to the forward recurrence time of the service time distribution, and a closed-form expression is derived for the corresponding generalized limiting log-moment generating function associated with the input process. We apply our results to cases where the service time distribution in the M|G|/spl infin/ input model is (i) Rayleigh, (ii) gamma, (iii) geometric, (iv) Weibull, (v) log-normal and (vi) Pareto-cases (v) and (vi) have been found adequate for modeling packet traffic streams in certain networking applications. Finally, we comment on the insufficiency of the short- vs. long-range dependence characterization of an input process as a means to accurately describe the corresponding buffer dynamics.

We propose a novel paging strategy based on the theory of optimal search with discrete efforts. When compared to conventional paging methods, the proposed scheme increases the mobile station discovery rate while decreasing the average number of times that a mobile station has to be paged in a location area. The proposal is fully compatible with existing cellular structures, and requires minimal computational power in the mobile switching centers.

We consider the large buffer asymptotics of a multiplexer under two different self-similar traffic input models, viz., the infinite server model of Cox and the fractional Gaussian noise input model. In the former case the tail probabilities for the buffer content (in steady state) are shown to decay at most hyperbolically, while in the latter they are asymptotically Weibullian. Therefore, for given input rate and Hurst parameter, these dissimilar asymptotics result in vastly differing buffer engineering practices, thereby pointing to the inadequacy of the Hurst parameter as the sole parameter to characterize long-range dependence in traffic input models.

A dynamic programming formulation is used to obtain an optimal strategy for the handoff problem in cellular radio systems. The formulation includes the modeling of the underlying randomness in received signal strengths as well as the movements of the mobile. The cost function is designed such that there is a cost associated with switching and a reward for improving the quality of the call. The optimum decision is characterized by a threshold on the difference between the measured power that the mobile receives from the base stations. Also we study the problem of choosing the "best" fixed threshold that minimizes the cost function. The performance of the optimal and suboptimal strategies are compared.>

The authors consider queueing that occur naturally in the study of a class of resource-sharing problems under synchronization constraints such as resequencing and fork-join primitives. These queueing models are amenable to a representation in terms of a state recursion. The proposed methods of analysis are complementary and draw on classical ideas of queuing theory as well as on mathematical tools from the theory of stochastic ordering and ergodic theory. The state recursion is at the center of all aspects of the analysis, be it for developing the exact solutions, obtaining bounds on system performance or establishing the stability conditions. The ideas are illustrated on simple models of resequencing and fork-join synchronization, which emphasis put on deriving computable bounds on the performance measures.>