We propose a history-driven target (HDT) framework in Markov Chain Monte Carlo (MCMC) to improve any random walk algorithm on discrete state spaces, such as general undirected graphs, for efficient sampling from target distribution $\\boldsymbol{\\mu}$. With broad applications in network science and distributed optimization, recent innovations like the self-repellent random walk (SRRW) achieve near-zero variance by prioritizing under-sampled states through transition kernel modifications based on past visit frequencies. However, SRRW’s reliance on explicit computation of transition probabilities for all neighbors at each step introduces substantial computational overhead, while its strict dependence on time-reversible Markov chains excludes advanced non-reversible MCMC methods. To overcome these limitations, instead of direct modification of transition kernel, HDT introduces a history-dependent target distribution $\\boldsymbol{\\pi}[\\mathbf{x}]$ to replace the original target $\\boldsymbol{\\mu}$ in any graph sampler, where $\\mathbf{x}$ represents the empirical measure of past visits. This design preserves lightweight implementation by requiring only local information between the current and proposed states and achieves compatibility with both reversible and non-reversible MCMC samplers, while retaining unbiased samples with target distribution $\\boldsymbol{\\mu}$ and near-zero variance performance. Extensive experiments in graph sampling demonstrate consistent performance gains, and a memory-efficient Least Recently Used (LRU) cache ensures scalability to large general graphs.

Patching nodes is an effective network defense strategy for malware control at early stages, and its performance is primarily dependent on how accurately the infection propagation is characterized. In this paper, we aim to design a novel patching policy based on the susceptible-infected epidemic network model by incorporating the influence of patching delay–the type of delay that has been largely overlooked in designing patching policies in the literature, while being prevalent in practice. We first identify ‘critical edges’ that form a boundary to separate the most likely infected nodes from the nodes which would still remain healthy after the patching delay. We next leverage the critical edges to determine which nodes to be patched in light of limited patching resources at early stages. To this end, we formulate a constrained graph partitioning problem and use its solution to identify a set of nodes to patch or vaccinate under the limited resources, to effectively prevent malware propagation from getting through the healthy region. We numerically validate that our patching policy significantly outperforms other baseline policies in protecting the healthy nodes under limited patching resources and in the presence of patching delay.

Two-timescale stochastic approximation (TTSA) is among the most general frameworks for iterative stochastic algorithms. This includes well-known stochastic optimization methods such as SGD variants and those designed for bilevel or minimax problems, as well as reinforcement learning like the family of gradient-based temporal difference (GTD) algorithms. In this paper, we conduct an in-depth asymptotic analysis of TTSA under controlled Markovian noise via central limit theorem (CLT), uncovering the coupled dynamics of TTSA influenced by the underlying Markov chain, which has not been addressed by previous CLT results of TTSA only with Martingale difference noise. Building upon our CLT, we expand its application horizon of efficient sampling strategies from vanilla SGD to a wider TTSA context in distributed learning, thus broadening the scope of Hu et al. 2020. In addition, we leverage our CLT result to deduce the statistical properties of GTD algorithms with nonlinear function approximation using Markovian samples and show their identical asymptotic performance, a perspective not evident from current finite-time bounds.

We study a family of distributed stochastic optimization algorithms where gradients are sampled by a token traversing a network of agents in random-walk fashion. Typically, these random-walks are chosen to be Markov chains that asymptotically sample from a desired target distribution, and play a critical role in the convergence of the optimization iterates. In this paper, we take a novel approach by replacing the standard *linear* Markovian token by one which follows a *non-linear* Markov chain - namely the Self-Repellent Radom Walk (SRRW). Defined for any given 'base' Markov chain, the SRRW, parameterized by a positive scalar $\\alpha$, is less likely to transition to states that were highly visited in the past, thus the name. In the context of MCMC sampling on a graph, a recent breakthrough in Doshi et al. (2023) shows that the SRRW achieves $O(1/\\alpha)$ decrease in the asymptotic variance for sampling. We propose the use of a `generalized' version of the SRRW to drive token algorithms for distributed stochastic optimization in the form of stochastic approximation, termed SA-SRRW. We prove that the optimization iterate errors of the resulting SA-SRRW converge to zero almost surely and prove a central limit theorem, deriving the explicit form of the resulting asymptotic covariance matrix corresponding to iterate errors. This asymptotic covariance is always smaller than that of an algorithm driven by the base Markov chain and decreases at rate $O(1/\\alpha^2)$ - the performance benefit of using SRRW thereby *amplified* in the stochastic optimization context. Empirical results support our theoretical findings.

When a new product enters a market already dominated by an existing product, will it survive along with this dominant product? Most of the existing works have shown the coexistence of two competing products spreading/being adopted on overlaid graphs with same set of users. However, when it comes to the survival of a weaker product on the same graph, it has been established that the stronger one dominates the market and wipes out the other. This paper makes a step towards narrowing this gap so that a new/weaker product can also survive along with its competitor with a positive market share. Specifically, we identify a locally optimal set of users to induce a community that is targeted with advertisement by the product launching company under a given budget constraint. To this end, we model the system as competing Susceptible-Infected-Susceptible (SIS) epidemics and employ perturbation techniques to quantify and attain a positive market share in a cost-efficient manner. Our extensive simulation results with real-world graph dataset show that with our choice of target users, a new product can establish itself with positive market share, which otherwise would be dominated and eventually wiped out of the competitive market under the same budget constraint.

Distributed learning is essential to train machine learning algorithms across *heterogeneous* agents while maintaining data privacy. We conduct an asymptotic analysis of Unified Distributed SGD (UD-SGD), exploring a variety of communication patterns, including decentralized SGD and local SGD within Federated Learning (FL), as well as the increasing communication interval in the FL setting. In this study, we assess how different sampling strategies, such as *i.i.d.* sampling, shuffling, and Markovian sampling, affect the convergence speed of UD-SGD by considering the impact of agent dynamics on the limiting covariance matrix as described in the Central Limit Theorem (CLT). Our findings not only support existing theories on linear speedup and asymptotic network independence, but also theoretically and empirically show how efficient sampling strategies employed by individual agents contribute to overall convergence in UD-SGD. Simulations reveal that a few agents using highly efficient sampling can achieve or surpass the performance of the majority employing moderately improved strategies, providing new insights beyond traditional analyses focusing on the worst-performing agent.

We study the file transfer problem in opportunistic spectrum access (OSA) model, which has been widely studied in throughput-oriented applications for max-throughput strategies and in delay-related works that commonly assume identical channel rates and fixed file sizes. Our work explicitly considers minimizing the file transfer time for a given file in a set of heterogeneous-rate Bernoulli channels, showing that max-throughput policy doesn't minimize file transfer time in general. We formulate a mathematical framework for static extend to dynamic policies by mapping our file transfer problem to a stochastic shortest path problem. We analyze the performance of our proposed static and dynamic optimal policies over the max-throughput policy. We propose a mixed-integer programming formulation as an efficient alternative way to obtain the dynamic optimal policy and show a huge reduction in computation time. Then, we propose a heuristic policy that takes into account the performance-complexity tradeoff and consider the online implementation with unknown channel parameters. Furthermore, we present numerical simulations to support our analytical results and discuss the effect of switching delay on different policies. Finally, we extend the file transfer problem to Markovian channels and demonstrate the impact of the correlation of each channel.

We consider random walks on discrete state spaces, such as general undirected graphs, where the random walkers are designed to approximate a target quantity over the network topology via sampling and neighborhood exploration in the form of Markov chain Monte Carlo (MCMC) procedures. Given any Markov chain corresponding to a target probability distribution, we design a self-repellent random walk (SRRW) which is less likely to transition to nodes that were highly visited in the past, and more likely to transition to seldom visited nodes. For a class of SRRWs parameterized by a positive real $\alpha$, we prove that the empirical distribution of the process converges almost surely to the the target (stationary) distribution of the underlying Markov chain kernel. We then provide a central limit theorem and derive the exact form of the arising asymptotic co-variance matrix, which allows us to show that the SRRW with a stronger repellence (larger $\alpha$) always achieves a smaller asymptotic covariance, in the sense of Loewner ordering of co-variance matrices. Especially for SRRW-driven MCMC algorithms, we show that the decrease in the asymptotic sampling variance is of the order $O(1/\alpha)$, eventually going down to zero. Finally, we provide numerical simulations complimentary to our theoretical results, also empirically testing a version of SRRW with $\alpha$ increasing in time to combine the benefits of smaller asymptotic variance due to large $\alpha$, with empirically observed faster mixing properties of SRRW with smaller $\alpha$.

We study convergence properties of competing epidemic models of the Susceptible-Infected-Susceptible ($SIS$) type. The SIS epidemic model has seen widespread popularity in modelling the spreading dynamics of contagions such as viruses, infectious diseases, or even rumors/opinions over contact networks (graphs). We analyze the case of two such viruses spreading on overlaid graphs, with non-linear rates of infection spread and recovery. We call this the non-linear bi-virus model and, building upon recent results, obtain precise conditions for global convergence of the solutions to a trichotomy of possible outcomes: a virus-free state, a single-virus state, and to a coexistence state. Our techniques are based on the theory of monotone dynamical systems (MDS), in contrast to Lyapunov based techniques that have only seen partial success in determining convergence properties in the setting of competing epidemics. We demonstrate how the existing works have been unsuccessful in characterizing a large subset of the model parameter space for bi-virus epidemics, including all scenarios leading to coexistence of the epidemics. To the best of our knowledge, our results are the first in providing complete convergence analysis for the bi-virus system with non-linear infection and recovery rates on general graphs.

We consider the stochastic gradient descent (SGD) algorithm driven by a general stochastic sequence, including i.i.d noise and random walk on an arbitrary graph, among others; and analyze it in the asymptotic sense. Specifically, we employ the notion of `efficiency ordering', a well-analyzed tool for comparing the performance of Markov Chain Monte Carlo (MCMC) samplers, for SGD algorithms in the form of Loewner ordering of covariance matrices associated with the scaled iterate errors in the long term. Using this ordering, we show that input sequences that are more efficient for MCMC sampling also lead to smaller covariance of the errors for SGD algorithms in the limit. This also suggests that an arbitrarily weighted MSE of SGD iterates in the limit becomes smaller when driven by more efficient chains. Our finding is of particular interest in applications such as decentralized optimization and swarm learning, where SGD is implemented in a random walk fashion on the underlying communication graph for cost issues and/or data privacy. We demonstrate how certain non-Markovian processes, for which typical mixing-time based non-asymptotic bounds are intractable, can outperform their Markovian counterparts in the sense of efficiency ordering for SGD. We show the utility of our method by applying it to gradient descent with shuffling and mini-batch gradient descent, reaffirming key results from existing literature under a unified framework. Empirically, we also observe efficiency ordering for variants of SGD such as accelerated SGD and Adam, open up the possibility of extending our notion of efficiency ordering to a broader family of stochastic optimization algorithms.

The dynamics of the spread of contagions such as viruses, infectious diseases or even rumors/opinions over contact networks (graphs) have effectively been captured by the well known Susceptible-Infected-Susceptible (SIS) epidemic model in recent years. When it comes to competition between two such contagions spreading on overlaid graphs, their propagation is captured by so-called bi-virus epidemic models. Analysis of such dynamical systems involve the identification of equilibrium points and its convergence properties, which determine whether either of the viruses dies out, or both survive together. We demonstrate how the existing works are unsuccessful in characterizing a large subset of the model parameter space, including all parameters for which the competitiveness of the bi-virus system is significant enough to attain coexistence of the epidemics. In this paper, we fill in this void and obtain convergence results for the entirety of the model parameter space; giving precise conditions (necessary and sufficient) under which the system globally converges to a trichotomy of possible outcomes: a virus-free state, a single-virus state, and to a coexistence state - the first such result.

The Opportunistic Spectrum Access (OSA) model has been developed for the secondary users (SUs) to exploit the stochastic dynamics of licensed channels for file transfer in an opportunistic manner. Common approaches to design channel sensing strategies for throughput-oriented applications tend to maximize the long-term throughput, with the hope that it provides reduced file transfer time as well. In this paper, we show that this is not correct in general, especially for small files. Unlike prior delay-related works that seldom consider the heterogeneous channel rate and bursty incoming packets, our work explicitly considers minimizing the file transfer time of a single file consisting of multiple packets in a set of heterogeneous channels. We formulate a mathematical framework for the static policy, and extend to dynamic policy by mapping our file transfer problem to the stochastic shortest path problem. We analyze the performance of our proposed static optimal and dynamic optimal policies over the policy that maximizes long-term throughput. We then propose a heuristic policy that takes into account the performance-complexity tradeoff and an extension to online implementation with unknown channel parameters, and also present the regret bound for our online algorithm. We also present numerical simulations that reflect our analytical results.

With the ease of deployment, capabilities of evading the jammers and obscuring their existence, unmanned aerial vehicles (UAVs) are one of the most suitable candidates to perform surveillance. There exists a body of literature in which the inspectors follow a deterministic trajectory to conduct surveillance, which results in a predictable environment for malicious entities. Thus, introducing randomness to the surveillance is of particular interest. In this work, we propose a novel framework for stochastic UAV-assisted surveillance that i) inherently considers the battery constraints of the UAVs, ii) proposes random moving patterns modeled via random walks, and iii) adds another degree of randomness to the system via considering probabilistic inspections. We formulate the problem of interest, i.e., obtaining the energy-efficient random walk and inspection policies of the UAVs subject to probabilistic constraints on inspection criteria of the sites and battery consumption of the UAVs, which turns out to be signomial programming that is highly non-convex. To solve it, we propose a centralized and a distributed algorithm along with their performance guarantee. This work contributes to both UAV-assisted surveillance and classic random walk literature by designing random walks with random inspection policies on weighted graphs with energy limited random walkers.

In this paper, we study a problem of trapping malicious web crawlers in social networks to minimize the attacks from crawlers with malicious intents to steal personal/private information. The problem is to find where to place a given set of traps over a graph so as to minimize the expected number of users who possibly fall prey to a (possibly random) set of malicious crawlers, each of which traverses the graph in a random-walk fashion for a random finite time. We first show that this problem is NP-hard and also a monotone submodular maximization problem. We then present a greedy algorithm that achieves a ($1-1/e$)-approximation. We also develop an $(ε,δ)$-approximation Monte Carlo estimator to ease the computation of the greedy algorithm and thus make the algorithm scalable for large graphs. We finally present extensive simulation results to show that our algorithm significantly outperforms other baseline algorithms based on various centrality measures.

In this paper, we aim to understand the transient dynamics of a susceptible-infected (SI) epidemic spreading process on a large network. The SI model has been largely overlooked in the literature, while it is naturally a better fit for modeling the malware propagation in early times when patches/vaccines are not available, or over a wider range of timescales when massive patching is practically infeasible. Nonetheless, its analysis is simply non-trivial, as its important dynamics are all transient and the usual stability/steady-state analysis no longer applies. To this end, we develop a theoretical framework that allows us to obtain an accurate closed-form approximate solution to the original SI dynamics on any arbitrary network, which captures the temporal dynamics over all time and is tighter than the existing approximation, and also to provide a new interpretation via reliability theory. As its applications, we further develop vaccination policies with or without knowledge of already-infected nodes, to mitigate the future epidemic spreading to the extent possible, and demonstrate their effectiveness through numerical simulations.

We study how the so-called Rao-Blackwellization, which is a variance reduction technique via “conditioning” for Monte Carlo methods, can be judiciously applied for graph sampling through neighborhood exploration. Despite its popularity for Monte Carlo methods, it is little known for Markov chain Monte Carlo methods and has never been discussed for random walk-based graph sampling. We first propose two forms of Rao-Blackwellization that can be used as a swap-in replacement for virtually all (reversible) random-walk graph sampling methods, and prove that the ‘Rao-Blackwellized’ estimators reduce the (asymptotic) variances of their original estimators yet maintain their inherent unbiasedness. The variance reduction can translate into lowering the number of samples required to achieve a desired sampling accuracy. However, the sampling cost for neighborhood exploration, if required, may outweigh such improvement, even leading to higher total amortized cost. Considering this, we provide a generalization of Rao-Blackwellization, which allows one to choose a suitable extent of obtaining Rao-Blackwellized samples in order to achieve a right balance between sampling cost and accuracy. We finally provide simulation results via real-world datasets that confirm our theoretical findings.

Graph sampling techniques via random walk crawling have been popular for analyzing statistical characteristics of large online social networks due to simple implementation and provable guarantees on unbiased estimates. Despite the growing popularity, the `cost' of sampling and its true impact on the accuracy of estimates still have not been carefully studied. In addition, the random walk-based methods inherently suffer from the sluggish nature of random walks and the `slow-mixing' structure of social graphs, thereby leading to high correlation in the samples obtained. With these in mind, in this paper, we develop a mathematical framework such that the cost of sampling is properly taken into account, which in turn re-defines a widely used asymptotic variance into a cost-based asymptotic variance. Our new metric enables us to compare a class of sampling policies under the same cost constraint, integrating “random skipping” (bypassing nodes without sampling) into the random walk-based sampling. We obtain an optimal policy striking the right balance between sampling quality (less correlation) and sampling quantity (higher cost per sample), which greatly improves over the usual skip-free crawling-based samplers. We further extend our framework, enabling one to design more sophisticated sampling strategies with an array of control knobs, which all produce unbiased estimates under the same cost constraint.

In this paper, we consider the optimal design of interlinks for an interdependent system of networks. In contrast to existing literature, we explicitly exploit the information of intra-layer node degrees to design interdependent structures such that their robustness against cascading failures, triggered by randomized attacks, is maximized. Utilizing percolation theory-based system equations relating the robustness of the network to its degree sequence, we characterize the optimal design for the one-to-one structure, with complete interdependence and partial interdependence, under randomized attack. We also extend our study to the one-to-many interdependence structure and the targeted attack model. The theoretically derived optimal interdependence structures have been verified using simulations on scale-free networks.

In recent years, a suite of Glauber dynamics-based CSMA algorithms have attracted great attention due to their simple, distributed implementations with guaranteed throughput-optimality. However, these algorithms often suffer from poor delay performance and the starvation problem. Among several attempts to improve the delay performance, a remarkable improvement has recently been made in a class of CSMA algorithms that utilize multiple instances of the algorithm (or Markov chains). In this paper, we develop a new approach via an antithetic coupling (AC) method, which can further improve the delay performance of those that virtually emulate multiple chains. The key enabler of utilizing AC method lies in our skilful choice of manipulating the driving sequences of random variables that govern the evolution of schedule instances, in such a way that those multiple instances of chains become negatively correlated as oppose to having them run independently. This contributes faster change of the link state, rendering it more like a periodic process and thus leading to better queueing performance. We rigorously establish an ordering relationship for the effective bandwidth of each net-input process to the queue, between our proposed algorithm (AC-CSMA) and other state-of-the-art existing algorithms in the literature, under a mild set of assumptions. The proposed algorithm involves very simple modification onto existing CSMA-based algorithms, and can be implemented in a fully distributed manner without any additional message overhead. Our extensive simulation results also confirm that AC-CSMA always delivers better queueing performance over a variety of network scenarios.

Heterogeneity arises in a wide range of scenarios in mobile opportunistic networks and is one of the key factors that govern the performance of forwarding algorithms. While the heterogeneity has been empirically investigated and exploited in the design of new forwarding algorithms, it has been typically ignored or marginalized when it comes to rigorous performance analysis of such algorithms. In this paper, we develop an analytical framework to quantify the performance gain achievable by exploiting the heterogeneity in mobile nodes' contact dynamics. In particular, we derive a delay upper bound of a heterogeneity-aware static forwarding policy per each given number of message copies and obtain its closed-form expression, which enables our quantitative study on the benefit of leveraging underlying heterogeneity structure in the design of forwarding algorithms. In addition, we develop a dynamic forwarding policy that performs as an extension of the static forwarding policy while proven to improve the delay performance. We then demonstrate that only a small fraction of total (unlimited) message copies, via both static and dynamic forwarding policies, are enough under various heterogeneous network settings to achieve the same delay as that obtained using the unlimited message copies when the networks become homogeneous. We also show that, given the same number of message copies, our dynamic forwarding policy significantly outperforms the `homogeneous-optimal' forwarding policy (up to about 50 percent improvement in the delay performance), especially when the number of message copies allowed in the networks is small.

An essential condition precedent to the success of mobile applications based on Wi-Fi (e.g., iCloud) is an energy-efficient Wi-Fi sensing. Clearly, a good Wi-Fi sensing policy should factor in both inter-access point (AP) arrival time (IAT) and contact duration time (CDT) distributions of each individual. However, prior work focuses on limited cases of those two distributions (e.g., exponential) or proposes heuristic approaches such as Additive Increase (AI). In this paper, we first formulate a generalized functional optimization problem on Wi-Fi sensing under general inter-AP and contact duration distributions and investigate how each individual should sense Wi-Fi APs to strike a good balance between energy efficiency and performance, which is in turn intricately linked with users mobility patterns. We then derive a generic optimal condition that sheds insights into the aging property, underpinning energy-aware Wi-Fi sensing polices. In harnessing our analytical findings and the implications thereof, we develop a new sensing algorithm, called Wi-Fi Sensing with AGing (WiSAG), and demonstrate that WiSAG outperforms the existing sensing algorithms up to 37% through extensive trace-driven simulations for which real mobility traces gathered from hundreds of smartphones is used.

Recently, several CSMA algorithms based on the Glauber dynamics model have been proposed for wireless link scheduling, as viable solutions to achieve the throughput optimality, yet simple to implement. However, their delay performance still remains unsatisfactory, mainly due to the nature of the underlying Markov chains that imposes a fundamental constraint on how the link state can evolve over time. In this paper, we propose a new approach toward better queueing delay performance, based on our observation that the algorithm needs not be Markovian, as long as it can be implemented in a distributed manner. Our approach hinges upon utilizing past state information observed by local link and then constructing a high-order Markov chain for the evolution of the feasible link schedules. We show that our proposed algorithm, named delayed CSMA, achieves the throughput optimality, and also provides much better delay performance by effectively “decorrelating” the link state process (and thus resolves link starvation). Our simulation results demonstrate that the delay under our algorithm can be reduced by a factor of 20 in some cases, compared to the standard Glauber-dynamics-based CSMA algorithm.

In this paper, we address how to design a distributed movement strategy for mobile collectors, which can be either physical mobile agents or query/collector packets periodically launched by the sink, to achieve successful data gathering in wireless sensor networks. Formulating the problem as general random walks on a graph composed of sensor nodes, we analyze how much data can be successfully gathered in time under any Markovian random-walk movement strategies for mobile collectors moving over a graph (or network), while each sensor node is equipped with limited buffer space and data arrival rates are heterogeneous over different sensor nodes. In particular, from the analysis, we obtain the optimal movement strategy among a class of Markovian strategies so as to minimize the data loss rate over all sensor nodes, and explain how such an optimal movement strategy can be made to work in a distributed fashion. We demonstrate that our distributed optimal movement strategy can lead to about two times smaller loss rate than a standard random walk strategy under diverse scenarios. In particular, our strategy results in up to 70 percent cost savings for the deployment of multiple collectors to achieve the target data loss rate than the standard random walk strategy.

The Metropolis-Hastings (MH) algorithm, in addition to its application for Markov Chain Monte Carlo sampling or simulation, has been popularly used for constructing a random walk that achieves a given, desired stationary distribution over a graph. Applications include crawling-based sampling of large graphs or online social networks, statistical estimation or inference from massive scale of networked data, efficient searching algorithms in unstructured peer-to-peer networks, randomized routing and movement strategies in wireless sensor networks, to list a few. Despite its versatility, the MH algorithm often causes self-transitions of its resulting random walk at some nodes, which is not efficient in the sense of the Peskun ordering - a partial order between off-diagonal elements of transition matrices of two different Markov chains, and in turn results in deficient performance in terms of asymptotic variance of time averages and expected hitting times with slower speed of convergence. To alleviate this problem, we present simple yet effective distributed algorithms that are guaranteed to improve the MH algorithm over time when running on a graph, and eventually reach `efficiency-optimality', while ensuring the same desired stationary distribution throughout.

Recently, several CSMA algorithms based on the Glauber dynamics model have been proposed for multihop wireless scheduling, as viable solutions to achieve the throughput optimality, yet simple to implement. However, their delay performance still remains unsatisfactory, mainly due to the nature of the underlying Markov chains that imposes a fundamental constraint on how the link state can evolve over time. In this paper, we propose a new approach toward better queueing delay performance, based on our observation that the algorithm needs not be Markovian, as long as it can be implemented in a distributed manner. Our approach hinges upon utilizing past state information observed by local link and then constructing a high-order Markov chain for the evolution of the feasible link schedules. We show in theory and simulation that our proposed algorithm, named delayed CSMA, achieves the throughput optimality, and also provides much better delay performance by effectively `de-correlating' the link state process (and thus resolves link starvation). Our extensive simulations demonstrate that the delay under our algorithm can be often reduced by a factor of 20 over a wide range of scenarios, compared to the standard Glauber-dynamics-based CSMA algorithm.

Being able to capture the properties of massive real graphs and also greatly reduce data scale and processing complexity, graph sampling techniques provide an efficient tool for complex network analysis. Random walk-based sampling has become popular to obtain asymptotically uniform samples in the recent literature. However, it produces highly correlated samples and often leads to poor estimation accuracy in sampling large networks. Another widely-used approach is to launch random jump by querying randomly generated user/node ID, but also has the drawback of unexpected cost when the ID space is sparsely populated. In this paper, we develop a hybrid graph sampling framework that inherits the benefit of returning immediate samples from random walk-based crawling, while incorporating the advantage of reducing the correlation in the obtained samples from random jump. We aim to strike the right balance between random jump and crawling by analyzing the resulting asymptotic variance of an estimator of any graph nodal property, in order to give guidelines on the design of better graph sampling methods. We also provide simulation results on real network (graph) to confirm our theoretical findings.

An essential condition precedent to the success of mobile applications based on Wi-Fi (e.g., iCloud) is an energy-efficient Wi-Fi sensing. From a user's perspective, a good WiFi sensing policy should depend on both inter-AP arrival and contact duration time distributions. Prior work focuses on limited cases of those two distributions (e.g., exponential) or introduces heuristic approaches such as AI (Additive Increase). In this paper, we formulate a functional optimization problem on Wi-Fi sensing under general inter-AP and contact duration distributions, and propose how each user should sense Wi-Fi APs to strike a balance between energy efficiency and performance, depending on the users' mobility pattern. To that end, we derive an optimal condition which sheds insights into the aging property, the key feature required by efficient Wi-Fi sensing polices. Guided by the analytical studies and the implications, we develop a new sensing algorithm, called WiSAG (Wi-Fi Sensing with AGing), which is demonstrated to outperform the existing sensing algorithms up to 34% through extensive trace-driven simulations using the real mobility traces gathered from smartphones.

With recent drastic growth in the number of users carrying smart mobile devices, it is not hard to envision opportunistic ad-hoc communications taking place with such devices carried by humans. This leads to, however, a new challenge to the conventional link-level metrics, solely defined based on user mobility, such as inter-contact time, since there are many constraints including limited battery power that prevent the wireless interface of each user from being always `on' for communication. By taking into account the process of each user's availability jointly with mobility-induced contact/inter-contact process, we investigate how each of them affects the link-level connectivity depending on their relative operating time scales. We then identify three distinct regimes in each of which (1) the so-called impact of mobility on network performance prevails; (2) such impact of mobility disappears or its extent is not that significant; (3) the user availability process becomes dominant. Our findings not only caution that mobility alone is not sufficient to characterize the link-level dynamics, which in turn can lead to highly misleading results, but also suggest the presence of many uncharted research territories for further exploration.

Recently several CSMA algorithms based on the Glauber dynamics model have been proposed for multihop wireless scheduling, as viable solutions to achieve the throughput optimality, yet are simple to implement. However, their delay performances still remain unsatisfactory, mainly due to the nature of the underlying Markov chains that imposes a fundamental constraint on how the link state can evolve over time. In this paper, we propose a new approach toward better queueing and delay performance, based on our observation that the algorithm needs not be Markovian, as long as it can be implemented in a distributed manner, achieving the same throughput optimality and better delay performance. Our approach hinges upon utilizing past state information observed by local link and then constructing a high-order Markov chain for the evolution of the feasible link schedules. Our proposed algorithm, named delayed CSMA, adds virtually no additional overhead onto the existing CSMA-based algorithms, achieves the throughput optimality under the usual choice of link weight as a function of queue length, and also provides much better delay performance by effectively resolving temporal link starvation problem. From our extensive simulations we observe that the delay under our algorithm can be often reduced by a factor of 20 over a wide range of scenarios, compared to the standard Glauber-dynamics-based CSMA algorithm.

In this paper, we focus on how the heterogeneous contact dynamics of mobile nodes impact the performance of forwarding algorithms in mobile opportunistic networks (MONs). To this end, we consider two representative heterogeneous network models, each of which captures heterogeneity among node pairs (individual) and heterogeneity in underlying environment (spatial), respectively, and examine the full extent of difference in delay performance they cause on forwarding algorithms through formal stochastic comparisons. We first show that these heterogeneous models correctly capture non-Poisson contact dynamics observed in real traces. We then rigorously establish stochastic/convex ordering relationships on the delay performance of direct forwarding and multicopy two-hop relay protocol under these heterogeneous models and the corresponding homogeneous model, all of which have the same average intercontact time of a random pair of nodes. In particular, we demonstrate that the heterogeneous models predict an entirely opposite ordering relationship in delay performance depending on which of the two heterogeneity structures is captured. We also provide simulation results including the delay performance of epidemic routing protocol to support the analytical findings. Our results thus suggest that the heterogeneity in mobile nodes' contact dynamics should be properly taken into account for the performance evaluation of forwarding algorithms. Our results will also be useful for better design of forwarding algorithms correctly exploiting the heterogeneity structure.

Glauber dynamics, a method of sampling a given probability distribution via a Markov chain, has recently made considerable contribution to the MAC scheduling research, providing a tool to solve a long-standing open issue - achieving throughput-optimality with light message passing under CSMA. In this paper, we propose a way of reducing delay by studying generalized Glauber dynamics parameterized by βϵ[0, 1], ranging from Glauber dynamics (β=0) to the Metropolis algorithm (β =1). The same stationary distribution is sustained across this generalization, thus maintaining the long-term optimality. However, a different choice of β results in a significantly different second-order behavior (or variability) that has large impact on delay, which is hardly captured by the recent research focusing on delay in the large n (the number of nodes) asymptotic. We formally study such second-order behavior and its resulting delay performance, and show that larger β achieves smaller delay. Our results provide new insight into how to operate CSMA for large throughput and small delay in real, finite-sized systems.

In this paper, we address how to design the distributed movement strategy for mobile collectors, which can be either physical mobile agents or query/collector packets periodically launched by the sink, to achieve successful data gathering in wireless sensor networks. Formulating the problem as general random walks on a graph composed of sensors, we analyze how many data can be successfully gathered in time under any Markovian movement strategies for mobile collectors moving over a graph (or network), while each sensor is equipped with limited buffer space and data arrival rate to each node is heterogeneous. In particular, from the analysis, we obtain the optimal movement strategy among a class of Markovian strategies so as to minimize the data loss rate over all sensors, and explain how such optimal movement strategy can be made to work in a distributed fashion. We demonstrate that our distributed optimal movement strategy leads to about 2 times smaller loss rate than the simple random walk strategy under diverse scenarios. In particular, our strategy can result in about 50% cost savings for the deployment of multiple collectors to achieve the target data loss rate than the simple random walk.

Graph sampling via crawling has been actively considered as a generic and important tool for collecting uniform node samples so as to consistently estimate and uncover various characteristics of complex networks. The so-called simple random walk with re-weighting (SRW-rw) and Metropolis-Hastings (MH) algorithm have been popular in the literature for such unbiased graph sampling. However, an unavoidable downside of their core random walks -- slow diffusion over the space, can cause poor estimation accuracy. In this paper, we propose non-backtracking random walk with re-weighting (NBRW-rw) and MH algorithm with delayed acceptance (MHDA) which are theoretically guaranteed to achieve, at almost no additional cost, not only unbiased graph sampling but also higher efficiency (smaller asymptotic variance of the resulting unbiased estimators) than the SRW-rw and the MH algorithm, respectively. In particular, a remarkable feature of the MHDA is its applicability for any non-uniform node sampling like the MH algorithm, but ensuring better sampling efficiency than the MH algorithm. We also provide simulation results to confirm our theoretical findings.

In wireless sensor networks (WSNs), sensor nodes are typically power-constrained with limited lifetime, and thus it is necessary to know how long the network sustains its networking operations. We consider the network lifetime as the time until that a majority of functional nodes remains connected of one another, forming a giant component, in the network. We then analytically examine such network lifetime of a large-scale WSN via the theory of site percolation on a random graph model with a given degree distribution. In particular, we develop an analytical framework to quantify the network lifetime if the node lifetime can be controlled based on its degree, and show in theory and simulation that, by properly exploiting the heterogeneity over the node degrees, we can always increase the network lifetime when compared with that under the comparable degree-independent node lifetime.

A simple random walk (SRW) has been considered as an effective forwarding method for many applications in wireless sensor networks (WSNs) due to its desirable properties. However, a critical downside of SRW - slow diffusion or exploration over the space, typically leads to longer packet delay and undermines its own benefits. Such slow-mixing problem becomes even worse under random duty cycling adopted for energy conservation. In this paper, we study how to overcome this problem without any sacrifice or tradeoff, and propose a simple modification of random duty cycling, named Smart Sleep, which achieves more power-saving as well as faster packet diffusion (or smaller delay) while retaining the benefits of SRW. We also introduce a class of p-backtracking random walks and establish its properties to analytically explain the fast packet diffusion induced by Smart Sleep. We further obtain a necessary condition to achieve an optimal performance under our Smart Sleep, and finally demonstrate remarkable performance improvement via independent simulation results over various network topologies.

In the multi-source content update scenario where each mobile node can be both a publisher and subscriber and opportunistic contacts are used for spreading out up-to-date contents, the age of contents would be the main interest in performance evaluation. We can simplify the overall age dynamics in this scenario by two parameters, which are content update rate and contact rate among mobile users. In this paper, we analyze how the age of time-evolving contents changes in publish/subscribe scenario when Poisson update and contact are assumed, and show that there exists an age-invariant regime where the average age does not depend on content update rate or contact rate. We also compare the age-invariant regime in publish/subscribe scenario with that of service provider content update case, and show a stark contact in those regimes. Then, we extend our study into existing mobility models that generate non-Poisson contacts, show that there still exists an age-invariant regime where Poisson assumptions suffice to capture the age dynamics, and specify a general rule of thumb that decides the scope of this regime. Our work that shows the existence of an age-invariant regime is in sharp contact to previous works that highlighted the impact of mobility models under single message scenario.

In wireless sensor networks (WSNs), sensor nodes are typically subjected to energy constraints and often prone to topology changes. While duty cycling has been widely used for energy conservation in WSNs, random walks have been popular for many delay-tolerant applications in WSNs due to their many inherent desirable properties. In this paper, we consider an opportunistic forwarding under an asynchronous and heterogeneous duty cycling. We first show that its resulting packet trajectory can be interpreted as a continuous-time random walk, and then provide an analytical formula for its end-to-end delay. Since the extremely large end-to-end delay is still undesirable even for most delay-tolerant applications, we develop a distributed wake-up scheduling algorithm in which each node autonomously adjusts its (heterogeneous) wake-up rate based only on its own degree information so as to improve the worst-case end-to-end delay. In particular, we prove that our algorithm outperforms pure homogeneous duty cycling, where every node uses the same wake-up rate, in its guaranteed asymptotic upper bound of the worst-case delay for any graph. In addition, we show that our proposed algorithm brings out more than 35% performance improvement on average when compared with pure homogeneous duty cycling, under various settings of random geometric graphs via numerical evaluations and independent simulation results.

Heterogeneity arises in a wide range of scenarios in mobile opportunistic networks and is one of key factors that govern the performance of packet forwarding algorithms. While the heterogeneity has been empirically investigated and exploited in the design of new forwarding algorithms, it has been typically ignored or marginalized when it comes to rigorous performance analysis of such algorithms. In this paper, we develop an analytical framework to quantify the performance gain achievable by exploiting the heterogeneity in mobile nodes' contact dynamics. In particular, we derive a delay upper bound of a heterogeneity-aware forwarding policy per a given number of message copies and obtain its closed-form expression, which enables our quantitative study on the benefit of leveraging underlying heterogeneity structure in the design of forwarding algorithms. We then analytically show that less than 20% of total (unlimited) message copies is only enough under various heterogeneous network settings to achieve the same delay as that obtained using the unlimited message copies when the networks become homogeneous. We also provide independent simulation results including real trace-driven evaluation to support our analytical results.

Mobility is the most important component in mobile ad hoc networks (MANETs) and delay-tolerant networks (DTNs). In this paper, we first investigate numerous GPS mobility traces of human mobile nodes and observe superdiffusive behavior in all GPS traces, which is characterized by a ¿faster-than-linear¿ growth rate of the mean square displacement (MSD) of a mobile node. We then investigate a large amount of access point (AP) based traces, and develop a theoretical framework built upon continuous time random walk (CTRW) formalism, in which one can identify the degree of diffusive behavior of mobile nodes even under possibly heavy-tailed pause time distribution, as in the case of reality. We study existing synthetic models and trace-based models in terms of the capability of producing various degrees of diffusive behavior, and use a set of Levy walk models due to its simplicity and flexibility. In addition, we show that diffusive properties make a huge impact on contact-based metrics and the performance of routing protocols in various scenarios, and that existing models such as random waypoint, random direction model, or Brownian motion lead to overly optimistic or pessimistic results when diffusive properties are not properly captured. Our work in this paper, thus, suggests that the diffusive behavior of mobile nodes should be correctly captured and taken into account for the design and comparison study of network protocols.

Peer-to-peer (P2P) network is widely used for transferring large files nowadays. Measurement results show that most downloading peers are patient as the average download session is usually very long. It is sometimes even longer than downloading from a dedicated server using a modem. Existing results in the literature indicate that the stochastic fluctuation and the heterogeneity in the service capacity of each peer are two of the major reasons that make the average download time far longer than expected. In those studies, it has been often assumed that there is only one downloading peer in the network, ignoring the interaction and competition among peers. In this paper, we investigate the impact of the interaction and competition among peers on downloading performance under stochastic, heterogeneous, and unstructured P2P settings, thereby greatly extending the existing results on stochastic P2P networks made only under a single downloading peer in the network. To analyze the average download time in a P2P network with multiple competing downloading peers, we first introduce the notion of system utilization tailored to a P2P network. We investigate the relationship among the average download time, system utilization, and the level of competition among downloading peers in a stochastic P2P network. We then derive an achievable lower bound on the average download time and propose algorithms to give the peers the minimum average download time. Our result can much improve the download performance compared to earlier results in the literature. The performance of the different algorithms is compared under NS-2 simulations. Our results also provide theoretical explanation to the inconsistency of performance improvement by using parallel connections (parallel connections sometimes do not outperform a single connection) observed in some measurement studies.

The study in mobile ad-hoc networks (MANET) is facing challenges brought by recent discovery of non-exponential behavior of the inter-contact time distribution of mobile nodes. In this paper, we analyze various characteristics of the relative mobility of a random pair of nodes in MANET to show that they produce inter-contact time with different aging properties. First, by fixing one node and resorting to the random walks on directed graphs, we mathematically prove that under four classes of stochastic mobility patterns, the resulting inter-contact times have constant/decreasing/increasing failure rate and new-better-than-used property. Then, we consider the case when both nodes are mobile and use simulation results to uncover the aging property of their inter-contact times under random waypoint models and random walk mobility models. This aging property tells us how to correctly relate the past experience of mobile nodes with their future behavior, thereby allowing tremendous opportunities brought by the memory structure in the non-exponential inter contact time, which would be impossible under the widely assumed exponentially distributed (memoryless) inter-contact time. As an application of our results, we establish for the first time that the approach based on exponential inter-contact time assumption can either under-estimate or over-estimate the actual system performance, under different stochastic mobility patterns indexed by their aging properties. Our results on aging properties also provide theoretic guidelines on how to exploit the memory structure toward better design of protocols under general mobility.

In this paper we focus on how the heterogeneous contact dynamics of mobile nodes impact the performance of forwarding/routing algorithms in delay/disruption-tolerant networks (DTNs). To this end, we consider two representative heterogeneous network models, each of which captures heterogeneity among node pairs (individual) and heterogeneity in underlying environment (spatial), respectively, and examine the full extent of difference in delay performances they cause on forwarding/routing algorithms through formal stochastic comparisons. We first show that these heterogeneous models correctly capture non-Poisson contact dynamics observed in real traces. Then, we consider direct forwarding and multicopy two-hop relay protocol and rigorously establish stochastic/convex ordering relationships on their delay performances under these heterogeneous models and the corresponding homogeneous model, all of which have the same average inter-contact time over all node pairs. We show that heterogeneous models predict an entirely opposite ordering relationship in the delay performances depending on which of the two heterogeneities is captured. This suggests that merely capturing non-Poisson contact dynamics - even if the entire distribution of aggregated inter-contact time is precisely matched, is not enough and that one should carefully evaluate the performance of forwarding/routing algorithms under a properly chosen heterogeneous network setting. Our results will also be useful in correctly exploiting the underlying heterogeneity structure so as to achieve better performance in DTNs.

Multicast is an efficient means of transmitting the same content to multiple receivers while minimizing network resource usage. Applications that can benefit from multicast such as multimedia streaming and download, are now being deployed over 3G wireless data networks. Existing multicast schemes transmit data at a fixed rate that can accommodate the farthest located users in a cell. However, users belonging to the same multicast group can have widely different channel conditions. Thus existing schemes are too conservative by limiting the throughput of users close to the base station. We propose two proportional fair multicast scheduling algorithms that can adapt to dynamic channel states in cellular data networks that use time division multiplexing: inter-group proportional fairness (IPF) and multicast proportional fairness (MPF). These scheduling algorithms take into account (1) reported data rate requests from users which dynamically change to match their link states to the base station, and (2) the average received throughput of each user inside its cell. This information is used by the base station to select an appropriate data rate for each group. We prove that IPF and MPF achieve proportional fairness among groups and among all users inside a cell respectively. Through extensive packet-level simulations, we demonstrate that these algorithms achieve good balance between throughput and fairness among users and groups.

Scheduling algorithms assign contention probability for each link in wireless ad hoc networks and plays a key role in deciding the system performance. Recently, many low-cost distributed scheduling algorithms are proposed. In this paper, we propose to improve the performance of a class of distributed collision-based scheduling algorithms, called constant-time distributed scheduling algorithms, by exploring the advantage brought by the unevenness of links' contention probabilities. Specifically, we prove that there exists ordering relationship for the success probability of any neighborhood when the contention probability vectors are ordered in the sense of majorization. We show how to modify the existing algorithms so as to find a new contention probability vector that majorizes the original one in a distributed manner. Our simulation results indicate that by using our modified algorithms, the average queue-lengths of a stable system can be reduced by 25% to 50%, while the capacity region remains the same. Our modification to the existing algorithms is extremely simple and entails essentially zero additional cost.

The class of isotropic random walk mobility models, including random direction mobility model, random walk mobility model and Brownian motion mobility model, has been widely used in the study of Mobile Ad-Hoc Networks for mobility modeling and control. In this paper, we show an important property for contact time of isotropic random walk mobility models. Specifically, we find that the mean contact time of two mobile nodes following isotropic random walk mobility models is invariant with respect to the step-length distribution under both the simplest distance-based (Boolean) interference model and the more realistic SINR-based interference model. We also study the effect of system parameters on the contact and inter-meeting time of mobile nodes and discuss their higher-order statistics.

Recent discovery of the mixture (power-law and exponential) behavior of inter-meeting time distribution of mobile nodes presents new challenge to the problem of mobility modeling and its effect on the network performance. Existing studies on this problem via the average inter-meeting time become insufficient when the inter-meeting time distribution starts to deviate from exponential one. This insufficiency necessarily leads to the increasing difficulty in the performance analysis of forwarding algorithms in mobile ad-hoc networks (MANET). In this paper, we analyze the effect of mobility patterns on the inter-meeting time distribution. We first identify the critical timescale in the inter-meeting distribution, at which the transition from power-law to exponential takes place, in terms of the domain size and the statistics of the mobility pattern. We then prove that stronger correlations in mobility patterns lead to heavier (non-exponential) 'head' of the inter-meeting time distribution. We also prove that there exists an invariance property for several contact-based metrics such as inter-meeting, contact, inter-any-contact time under both distance-based (Boolean) and physical interference (SINR) based models, in that the averages of those contact-based metrics do not depend on the degree of correlations in the mobility patterns. Our results collectively suggest a convex ordering relationship among inter-meeting times of various mobility models indexed by their degrees of correlation, which is in good agreement with the ordering of network performance under a set of mobility patterns whose inter-meeting time distributions have power-law 'head' followed by exponential 'tail'.

We investigate the relationship between average download time, system utilization and the level of competition among downloaders in a P2P like network. We show that when the system is nearly 100% utilized, the average download time increases with the level of competition. When the system is under-utilized, using parallel connections can help increase the utilization and hence reduce the average download time. However, contrary to common belief, we show that parallel downloading does not always help; it only helps if the system is under-utilized. We also show that even when the global metrics, such as competition factor and system utilization, are identical from a macroscopic point of view, the microscopic performance for each downloader can be very different depending on different downloading strategies.

Window growth function for congestion control is a strong determinant of protocol behaviors, especially its second and higher-order behaviors associated with the distribution of transmission rates, its variances, and protocol stability. This paper presents a new stochastic tool, called convex ordering, that provides an ordering of any convex function of transmission rates of two protocols and valuable insights into high order behaviors of protocols. As the ordering determined by this tool is consistent with any convex function of rates, it can be applied to any unknown metric for protocol performance that consists of some high-order moments of transmission rates, as well as those already known such as rate variance. Using the tool, it is analyzed that a protocol with a growth function that starts off with a concave function and then switches to a convex function (e.g., an odd order function such as x3and x5) around the maximum window size in the previous loss epoch, gives the smallest rate variation under a variety of network conditions. Among existing protocols, BIC and CUBIC have this window growth function. Experimental and simulation results confirm the analytical findings.

Multicast is an efficient means of transmitting the same content to multiple receivers while minimizing network resource usage. Applications that can benefit from multicast such as multimedia streaming and download, are now being deployed over 3G wireless data networks. Existing multicast schemes transmit data at a fixed rate that can accommodate the farthest located users in a cell. However, users belonging to the same multicast group can have widely different channel conditions. Thus existing schemes are too conservative by limiting the throughput of users close to the base station. We propose two proportional fair multicast scheduling algorithms that can adapt to dynamic channel states in cellular data networks that use time division multiplexing: Inter-group Proportional Fairness (IPF) and multicast proportional fairness (MPF). These scheduling algorithms take into account (1) reported data rate requests from users which dynamically change to match their link states to the base station, and (2) the average received throughput of each user inside its cell. This information is used by the base station to select an appropriate data rate for each group. We prove that IPF and MPF achieve proportional fairness among groups and among all users in a group inside a cell respectively. Through extensive packet-level simulations, we demonstrate that these algorithms achieve good balance between throughput and fairness among users and groups.

Inter-meeting time between mobile nodes is one of the key metrics in a Mobile Ad-hoc Network (MANET) and central to the end-to-end delay and forwarding algorithms. It is typically assumed to be exponentially distributed in many performance studies of MANET or numerically shown to be exponentially distributed under most existing mobility models in the literature. However, recent empirical results show otherwise: the inter-meeting time distribution in fact follows a power-law. This outright discrepancy potentially undermines our understanding of the performance tradeoffs in MANET obtained under the exponential distribution ofthe inter-meeting time, and thus calls for further study on the power-law inter-meeting time including its fundamental cause, mobility modeling, and its effect. In this paper, we rigorously prove that a finite domain, on which most of the current mobility models are defined, plays an important role in creating the exponential tail of the inter-meeting time. We also prove that by simply removing the boundary in a simple two-dimensional isotropic random walk model, we are able to obtain the empirically observed power-law decay of the inter-meeting time. We then discuss the relationship between the size of the boundary and the relevant time scale of the network scenario under consideration. Our results thus provide guidelines on the design of new mobility models with power-law inter-meeting time distribution, new protocols including packet forwarding algorithms, as well as their performance analysis.

Traditional call admission control (CAC) schemes only consider call-level performance and are mainly designed for circuit-switched wireless network. Since future wireless communications will become packet-switched systems, the packet-level features could be explored to improve the system performance. This is especially true when the TCP-type of elastic applications are running over such packet-switched wireless networks, as the elasticity of TCP applications has more tolerance toward the throughput/delay variation than non-elastic traffic does. In order to efficiently utilize the system resource from an admission control perspective, we propose a TCP-aware CAC scheme to regulate the packet-level dynamics of TCP flows. We analyze the system performance under realistic scenarios in which (i) the call holding time for non-elastic traffic like voice is independent of system states and (ii) the call holding time for TCP type of traffic depends on the system state, i.e., on the TCP flow's transmission rate. Extensive simulations are presented under different scenarios to show that the proposed scheme can effectively improve the system performance in terms of call blocking probability, call-level throughput (call/min) and link utilization, in accordance with our theoretical results.

For TCP/AQM systems, the issue of buffer sizing has recently received much attention. In the recent literature, it is suggested that the buffer size be O(radicN) for high link utilization contrasting to the traditional bandwidth-delay product, i.e., O(N) for 100% utilization where the link has capacity NC serving N flows. However, these results are all limited to the drop-tail scheme and there has been no systematic modeling framework for any buffer sizing between O(radicN) and O(N). In this paper, we study the limiting behavior of a TCP/AQM system for an intermediate buffer sizing of O(Ngamma) (0.5lesgamma<1). We develop a stochastic model in a discrete-time setting to characterize the system dynamics and then show that we can have 100% link utilization and zero packet loss probability for a large number of flows when the buffer size requirement is anywhere between O(radicN) and O(N). Our model is general enough to cover any queue-based AQM scheme with ECN marking (including the drop-tail) and various generalized AIMD algorithms for each TCP flow

Traditional call admission control (CAC) schemes only consider call-level performance and are believed to be sufficient for the circuit-switched wireless network. Since the future wireless network will become packet-switched, the packet-level performance should not be ignored. This is especially true when the TCP-type of applications are running over such packet-switched wireless networks, because TCP congestion control algorithm will exhaust all the available resource until packet loss occurs. In order to regulate the TCP applications to friendly coexist with other types of services, we propose a TCP-aware CAC scheme. We analyze the system performance under the scenario that call holding time is independent of the system state. Simulations results for different performance metrics are presented to show that the proposed scheme can effectively improve the system performance in terms of call blocking probability, call-level throughput (call/min) and the link utilization

We consider a TCP/AQM system shared by many flows under general packet marking schemes. Traditional approaches in the literature require that the marking function p/sup N/ (x) be scaled linearly in the number of flows N, i.e., p/sup N/ (Nx)=p(x) for some function p, and they all invariably fail to predict the system performance if the marking function is scaled more aggressively, i.e. p/sup N/(N/sup /spl alpha//x)=p(x) with /spl alpha//spl isin/(0,1). In this paper, by noting that there are two different sources of randomness in packet arrivals to the queue, we develop a simple stationary model for a TCP/AQM system with N flows under the aggressive packet marking. Our main results show that, under any aggressive marking scale, the system always behaves nicely in the sense that the link utilization goes to I and the queueing delay decreases to zero as the system size N increases. We verify our results using ns-2 simulation under different AQM schemes, and show that the buffer size can be chosen much smaller than O(/spl radic/N) as recently predicted by G. Appenzeller et al (ACM Sigcomm, 2004) without affecting all the key performance metrics.

We study the global stability of TCP/RED under the many flows regime. The traditional approach based on Lyapunov functions is not suitable for a system with many flows due to its complexity. In this paper, we present a normalized model to capture the essential system dynamics. Based on this normalized model, we find its equilibrium point and local stability criterion, which closely match the existing results. This, in turn, reinforce the correctness of our normalized model. We then proceed with a numerical analysis to obtain the global stability. Our results show that by properly choosing RED parameters, we can always make the TCP/RED system globally stable. In addition, our numerical results also show that any locally stable TCP/RED system is mostly globally stable as long as the number of flows is large.

Fluid models have been the main tools for Internet congestion control. By capturing how the average rate of each flow evolves, the fluid model proves to be useful as it predicts the equilibrium point to which system trajectory converges and also provides conditions under which the convergence is ensured, i.e., the system is stable. However, due to inherent randomness in the network caused by random packet arrivals or random packet marking, the actual system evolution is always of a stochastic nature. In this paper, we show that we can be better off using a stochastic approach toward the congestion control. We first prove that the equilibrium point of a fluid model can be quite different from the true average rate of the corresponding stochastic system. After we describe the notion of stability for two different approaches, we show that a stable fluid model can impose too much restriction on our choice of system parameters such as buffer size or link utilization. In particular, under fluid models, we show that there exists a fundamental tradeoff between the link utilization and buffer size requirement for large systems, while in a more realistic setting with stochastic models, there is no such tradeoff. This implies that the current congestion control design can be much more flexible, to the benefit of efficient usage of network resources.

We show that significant simplicities can be obtained for the analysis of a network when link capacities are large enough to carry many flows. We develop a network decomposition approach in which network analysis can be greatly simplified. We prove that the queue length at the downstream queue converges to that of a single queue obtained by removing the upstream queue, as the capacity and the number of flows at the upstream queue increase. The precise modes of convergence vary depending on the type of input traffic, i.e., from regulated traffic arrivals to point process inputs. Our results thus help simplify network analysis by decomposing the original network into a simplified network in which all the nodes with large capacity have been eliminated. By means of extensive numerical investigation under various network scenarios, we demonstrate different aspects and implications of our network decomposition approach. Some of our findings are that our techniques perform well especially for the cases when: i) many flows are multiplexed as they enter the queue and/or ii) departing flows are routed to different downstream nodes, i.e., no single flow dominates at any node.

In this paper, we show that significant simplicities can arise in the analysis of a network when link capacities are large enough to carry many flows. In particular, we prove that, when an upstream queue serves a large number of regulated traffic sources, the queue-length of the downstream queue converges almost surely to the queue-length of a simplified queueing system (single queue) obtained by removing the upstream queue. We provide similar results (convergence of the queue-length in distribution) for general (including nonregulated) traffic arrivals. In both cases, the convergence of the overflow probability is uniform and at least exponentially fast. Through an extensive numerical investigation, we demonstrate several aspects and implications of our results in simplifying network analysis.

We describe a measurement-analytic approach for estimating the overflow probability, an important measure of the quality of service (QoS), at a given multiplexing point in the network. A multiplexing point in the network could be a multiplexer or an output port of a switch or router where resources such as bandwidth and buffers are shared. Our approach impinges on using the notion of the dominant time scale (DTS), which corresponds to the most probable time scale over which overflow occurs. The DTS provides us with a measurement window for the statistics of the traffic, but is in fact itself defined in terms of the statistics of the traffic over all time. This, in essence, results in a chicken-and-egg type of unresolved problem. For the DTS to be useful for on-line measurements, we need to be able to break this chicken-and-egg cycle, and to estimate the DTS with only a bounded window of time over which the statistics of the traffic are to be measured. We present a stopping criterion to successfully break this cycle and find a bound on the DTS. Thus, the result has significant implications for network measurements. Our approach is quite different from other works in the literature that require off-line measurements of the entire trace of the traffic. In our case, we need to measure only the statistics of the traffic up to a bound on the DTS. We also investigate the characteristics of this upper bound on the DTS, and provide numerical results to illustrate the utility of our measurement analytic approach.

In this paper we describe a measurement-analytic framework for estimating the overflow probability, an important measure of quality of service (QoS), at a given multiplexing point in the network. A multiplexing point in the network could be a multiplexer or an output port of a switch where resources such as bandwidth and buffers are shared. Our approach impinges on using the notion of the dominant or critical time scale, which corresponds to the time-scale relevant for describing the queueing behavior based on particular network configurations. The dominant time-scale provides us with a measurement window for the statistics of the traffic, but is unfortunately itself defined in terms of the statistics of the traffic over all time. This in essence results in a chicken and an egg type of unresolved problem. For the dominant time scale to be useful for on-line measurements, we need to be able to break this chicken and egg type of cycle. In this paper, we present a stopping criterion to successfully break this cycle through online measurements and find a bound on the dominant time scale. Thus, the result has significant implications for network measurements. Our approach is quite different from other works in the literature that require off-line measurements of the entire trace of the traffic (since in our case, we need to measure only the statistics of the traffic up to a bound on the dominant time scale.) We also investigate the characteristics of this upper bound on the dominant time scale, and provide numerical results to illustrate the utility of our measurement analytic approach.