The advent of Large Language Models (LLMs) and generative AI is fundamentally transforming information retrieval and processing on the Internet, bringing both great potential and significant concerns regarding content authenticity and reliability.This paper presents a novel quantitative approach to shed light on the complex information dynamics arising from the growing use of generative AI tools.Despite their significant impact on the digital ecosystem, these dynamics remain largely uncharted and poorly understood.We propose a stochastic model to characterize the generation, indexing, and dissemination of information in response to new topics.This scenario particularly challenges current LLMs, which often rely on real-time Retrieval-Augmented Generation (RAG) techniques to overcome their static knowledge limitations.Our findings suggest that the rapid pace of generative AI adoption, combined with increasing user reliance, can outpace human verification, escalating the risk of inaccurate information proliferation across digital resources.An in-depth analysis of Stack Exchange data confirms that high-quality answers inevitably require substantial time and human effort to emerge.This underscores the considerable risks associated with generating persuasive text in response to new questions and highlights the critical need for responsible development and deployment of future generative AI tools.

We propose a simple model of an idealized online cultural market in which N items, endowed with a hidden quality metric, are recommended to users by a ranking algorithm possibly biased by the current items’ popularity. Our goal is to better understand the underlying mechanisms of the well-known fact that popularity bias can prevent higher-quality items from becoming more popular than lower-quality items, producing an undesirable misalignment between quality and popularity rankings. We do so under the assumption that users, having limited time/attention, are able to discriminate the best-quality only within a random subset of the items. We discover the existence of a harmful regime in which improper use of popularity can seriously compromise the emergence of quality, and a benign regime in which wise use of popularity, coupled with a small discrimination effort on behalf of users, guarantees the perfect alignment of quality and popularity ranking. Our findings clarify the effects of algorithmic popularity bias on quality outcomes, and may inform the design of more principled mechanisms for techno-social cultural markets.

A similarity cache can reply to a query for an object with similar objects stored locally. In some applications of similarity caches, queries and objects are naturally represented as points in a continuous space. This is for example the case of 360° videos where user’s head orientation—expressed in spherical coordinates—determines what part of the video needs to be retrieved, or of recommendation systems where a metric learning technique is used to embed the objects in a finite dimensional space with an opportune distance to capture content dissimilarity. Existing similarity caching policies are simple modifications of classic policies like LRU, LFU, and${q}$LRU and ignore the continuous nature of the space where objects are embedded. In this paper, we propose GRADES, a new similarity caching policy that uses gradient descent to navigate the continuous space and find appropriate objects to store in the cache. We provide theoretical convergence guarantees and show GRADES increases the similarity of the objects served by the cache in both applications mentioned above.

This paper focuses on similarity caching systems, in which a user request for an object$o$that is not in the cache can be (partially) satisfied by a similar stored object$o'$, at the cost of a loss of user utility. Similarity caching systems can be effectively employed in several application areas, like multimedia retrieval, recommender systems, genome study, and machine learning training/serving. However, despite their relevance, the behavior of such systems is far from being well understood. In this paper, we provide a first comprehensive analysis of similarity caching in the offline, adversarial, and stochastic settings. We show that similarity caching raises significant new challenges, for which we propose the first dynamic policies with some optimality guarantees. We evaluate the performance of our schemes under both synthetic and real request traces.

A relevant fraction of human interactions occurs on online social networks. Freshness of content seems to play an important role, with content popularity rapidly vanishing over time. In this paper, we investigate how influencers' generated content (i.e., posts) attracts interactions, measured by number of likes or reactions. We analyse the activity of Italian influencers and followers over more than 5 years, focusing on two popular social networks: Facebook and Instagram, including more than 13 billion interactions and about 4 million posts. We characterise the influencers' and followers' behaviour over time, show that influencers' posts are short-lived with an exponential temporal decay, and characterise the time evolution of the interactions from their initial peak till the end of a post lifetime. Finally, leveraging our findings, we discuss how they can be exploited to develop an analytical model of the interactions temporal dynamics.

A similarity cache can reply to a query for an object with similar objects stored locally. In some applications of similarity caches, queries and objects are naturally represented as points in a continuous space. Examples include 360° videos where user's head orientation-expressed in spherical coordinates- determines what part of the video needs to be retrieved, and recommendation systems where the objects are embedded in a finite-dimensional space with a distance metric to capture content dissimilarity. Existing similarity caching policies are simple modifications of classic policies like LRU, LFU, and qLRU and ignore the continuous nature of the space where objects are embedded. In this paper, we propose Grades, a new similarity caching policy that uses gradient descent to navigate the continuous space and find the optimal objects to store in the cache. We provide theoretical convergence guarantees and show Grades increases the similarity of the objects served by the cache in both applications mentioned above.

This paper focuses on similarity caching systems, in which a user request for an object o that is not in the cache can be (partially) satisfied by a similar stored object o', at the cost of a loss of user utility. Similarity caching systems can be effectively employed in several application areas, like multimedia retrieval, recommender systems, genome study, and machine learning training/serving. However, despite their relevance, the behavior of such systems is far from being well understood. In this paper, we provide a first comprehensive analysis of similarity caching in the offline, adversarial, and stochastic settings. We show that similarity caching raises significant new challenges, for which we propose the first dynamic policies with some optimality guarantees. We evaluate the performance of our schemes under both synthetic and real request traces.

In this paper, we present the first cross-layer analysis of wireless LANs operating under downlink multi-user multi-in multi-out (MU-MIMO), considering the fundamental role played by the closed-loop (TCP) traffic. In particular, we consider a scenario in which the access point transmits on the downlink via MU-MIMO, whereas stations must employ single-user transmissions on the uplink, as is the case in IEEE 802.11ac. With the help of analytical models built for different regimes that can occur in the considered system, we identify and explain crucial performance anomalies that can result in very low throughput in some scenarios, completely offsetting the theoretical gains achievable by MU-MIMO. We discuss solutions to mitigate the risk of this performance degradation and alternative uplink strategies allowing WLANs to approach their maximum theoretical capacity under MU-MIMO.

Online social networks offer the opportunity to collect a huge amount of valuable information about billions of users. The analysis of this data by service providers and unintended third parties are posing serious treats to user privacy. In particular, recent work has shown that users participating in more than one online social network can be identified based only on the structure of their links to other users. An effective tool to de-anonymize social network users is represented by graph matching algorithms. Indeed, by exploiting a sufficiently large set of seed nodes, a percolation process can correctly match almost all nodes across the different social networks. In this article, we show the crucial role of clustering, which is a relevant feature of social network graphs (and many other systems). Clustering has both the effect of making matching algorithms more prone to errors, and the potential to greatly reduce the number of seeds needed to trigger percolation. We show these facts by considering a fairly general class of random geometric graphs with variable clustering level. We assume that seeds can be identified in particular sub-regions of the network graph, while no a priori knowledge about the location of the other nodes is required. Under these conditions, we show how clever algorithms can achieve surprisingly good performance while limiting the number of matching errors.

In this paper we present the first cross-layer analysis of wireless LANs operating under downlink multi-user MIMO (MU-MIMO), considering the fundamental role played by closed-loop (TCP) traffic. In particular, we consider an 802.11ac scenario in which the access point transmits on the downlink via MU-MIMO, whereas stations must employ single-user transmissions on the uplink. With the help of analytical models built for the different regimes that can occur in the considered system, we identify and explain crucial performance anomalies that can result in very low throughput in some scenarios, completely offsetting the theoretical gains achievable by MU-MIMO. We discuss solutions to mitigate the risk of this performance degradation and alternative uplink strategies allowing WLANs to approach their maximum theoretical capacity under MU-MIMO.

Bootstrap percolation is a well-known activation process in a graph, in which a node becomes active when it has at least r active neighbors. Such process, originally studied on regular structures, has been recently investigated also in the context of random graphs, where it can serve as a simple model for a wide variety of cascades, such as the spreading of ideas, trends, viral contents, etc. over large social networks. In particular, it has been shown that in G(n,p) the final active set can exhibit a phase transition for a sub-linear number of seeds. In this paper, we propose a unique framework to study similar sub-linear phase transitions for a much broader class of graph models and epidemic processes. Specifically, we consider i) a generalized version of bootstrap percolation in G(n,p) with random activation thresholds and random node-to-node influences; ii) different random graph models, including graphs with given degree sequence and graphs with community structure (block model). The common thread of our work is to show the surprising sensitivity of the critical seed set size to extreme values of distributions, which makes some systems dramatically vulnerable to large-scale outbreaks. We validate our results running simulation on both synthetic and real graphs.

We analyze throughput-delay scaling laws of mobile ad hoc networks under a content-centric traffic scenario, where users are mainly interested in retrieving contents cached by other nodes. We assume limited buffer size available at each node and Zipf-like content popularity. We consider nodes uniformly visiting the network area according to a random-walk mobility model, whose flight size varies from the typical distance among the nodes (quasi-static case) up to the edge length of the network area (reshuffling mobility model). Our main findings are: (1) the best throughput-delay tradeoffs are achieved in the quasi-static case: increasing the mobility degree of nodes leads to worse and worse performance; (ii) the best throughput-delay tradeoffs can be recovered by power control (i.e., by adapting the transmission range to the content) even in the complete reshuffling case.

We tackle the problem of user de-anonymization in social networks characterized by scale-free relationships between users. The network is modeled as a graph capturing the impact of power-law node degree distribution, which is a fundamental and quite common feature of social networks. Using this model, we present a de-anonymization algorithm that exploits an initial set of users, called seeds, that are known a priori. By employing the bootstrap percolation theory and a novel graph slicing technique, we develop a rigorous analysis of the proposed algorithm under asymptotic conditions. Our analysis shows that large inhomogeneities in the node degree lead to a dramatic reduction in the size of the seed set that is necessary to successfully identify all the other users. We characterize this set size when seeds are properly selected based on the node degree as well as when seeds are uniformly distributed. We prove that, given n nodes, the number of seeds required for network de-anonymization can be as small as n∈, for any small ∈ > 0. In addition, we discuss the complexity of our de-anonymization algorithm and validate our results through numerical experiments on a real social network graph.

We address the problem of social network de-anonymization when relationships between people are described by scale-free graphs. In particular, we propose a rigorous, asymptotic mathematical analysis of the network de-anonymization problem while capturing the impact of power-law node degree distribution, which is a fundamental and quite ubiquitous feature of many complex systems such as social networks. By applying bootstrap percolation and a novel graph slicing technique, we prove that large inhomogeneities in the node degree lead to a dramatic reduction of the initial set of nodes that must be known a priori (the seeds) in order to successfully identify all other users. We characterize the size of this set when seeds are selected using different criteria, and we show that their number can be as small as n% for any small ε > 0. Our results are validated through simulation experiments on real social network graphs.

In this paper we develop a novel technique to analyze both isolated and interconnected caches operating under different caching strategies and realistic traffic conditions. The main strength of our approach is the ability to consider dynamic contents which are constantly added into the system catalogue, and whose popularity evolves over time according to desired profiles. We do so while preserving the simplicity and computational efficiency of models developed under stationary popularity conditions, which are needed to analyze several caching strategies. Our main achievement is to show that the impact of content popularity dynamics on cache performance can be effectively captured into an analytical model based on a fixed content catalogue (i.e., a catalogue whose size and objects' popularity do not change over time).

To assess the performance of caching systems, the definition of a proper process describing the content requests generated by users is required. Starting from the analysis of traces of YouTube video requests collected inside operational networks, we identify the characteristics of real traffic that need to be represented and those that instead can be safely neglected. Based on our observations, we introduce a simple, parsimonious traffic model, named shot noise model (SNM), that allows us to capture temporal and geographical locality of content popularity. The SNM is sufficiently simple to be effectively employed in both analytical and scalable simulative studies of caching systems. We demonstrate this by analytically characterizing the performance of the LRU caching policy under the SNM, for both a single cache and a network of caches. With respect to the standard independent reference model (IRM), some paradigmatic shifts, concerning the impact of various traffic characteristics on cache performance, clearly emerge from our results.

We propose an analytical framework to tightly characterize the scaling laws for the additional bandwidth that servers must supply to guarantee perfect service in peer-assisted Video-on-Demand systems, taking into account essential aspects such as peer churn, bandwidth heterogeneity, and Zipf-like video popularity. Our results reveal that the catalog size and the content popularity distribution have a huge effect on the system performance. We show that users' cooperation can effectively reduce the servers' burden for a wide range of system parameters, confirming to be an attractive solution to limit the costs incurred by content providers as the system scales to large populations of users.

We propose a unified methodology to analyse the performance of caches (both isolated and interconnected), by extending and generalizing a decoupling technique originally known as Che's approximation, which provides very accurate results at low computational cost. We consider several caching policies, taking into account the effects of temporal locality. In the case of interconnected caches, our approach allows us to do better than the Poisson approximation commonly adopted in prior work. Our results, validated against simulations and trace-driven experiments, provide interesting insights into the performance of caching systems.

One of the main research directions along which the future Internet is evolving can be identified in the paradigmatic shift from a network of hosts toward a network of caches. Yet, several questions remain concerning the scalability of individual algorithms (e.g., name based lookup and routing) and components (e.g., caches) of these novel Information Centric Networking (ICN) architectures. Exploiting a peculiar characteristics of ICN (i.e., the fact that contents are split in chunks), and the nature of video streaming (which dominates Internet traffic), this paper proposes a novel two-layers caching scheme that allows multi-Terabyte caches to sustain content streaming at multi-Gbps speed. We model the system as an extension, to the case of chunked contents, of the well known Che approximation, that has the advantage of being very simple and accurate at the same time. Simulations under synthetic and realistic trace-driven traffic confirm the accuracy of the analysis and the feasibility of the proposed architecture.

We consider extended wireless networks characterized by a random topology of access points (APs) contending for medium access over the same wireless channel. Recently, stochastic geometry has emerged as a powerful tool to analyze random networks adopting MAC protocols such as ALOHA and CSMA. The main strength of this methodology lies in its ability to account for the randomness in the nodes' location jointly with an accurate description at the physical layer, based on the SINR, that allows considering also random fading on each link. In this paper, we extend previous stochastic geometry models of CSMA networks, developing computationally efficient techniques to obtain throughput distributions, in addition to spatial averages, which permit us to get interesting insights into the impact of protocol parameters and channel variability on the spatial fairness among the nodes. Moreover, we extend the analysis to a significant class of topologies in which APs are not placed according to a Poisson process.

We analyze a peer-assisted Video-on-Demand (VoD) system in which users contribute their upload bandwidth to the redistribution of a video that they are downloading or that they have cached locally. Our target is to characterize the additional bandwidth that servers must supply to immediately satisfy all requests to watch a given video. We develop an approximate fluid model to compute the required server bandwidth in the sequential delivery case, as well as in controlled nonsequential swarms. Our approach is able to capture several stochastic effects related to peer churn, upload bandwidth heterogeneity, and nonstationary traffic conditions, which have not been documented or analyzed before. Finally, we provide important hints for the design of efficient peer-assisted VoD systems under server capacity constraints.

We analyze throughput-delay scaling laws of mobile ad-hoc networks under a content-centric traffic scenario, where users are mainly interested in retrieving contents cached by other nodes. We assume limited buffer size available at each node and Zipf-like content popularity. We consider nodes uniformly visiting the network area according to a random-walk mobility model, whose flight size is varied from the typical distance among the nodes (quasi-static case) up to the edge length of the network area (reshuffling mobility model). Our main findings are i) the best throughput-delay trade-offs are achieved in the quasi-static case: increasing the mobility degree of nodes leads to worse and worse performance; ii) the best throughput-delay trade-offs can be recovered by power control (i.e., by adapting the transmission range to the content) even in the complete reshuffling case.

We propose an analytical framework to tightly characterize the scaling laws for the additional bandwidth that servers must supply to guarantee perfect service in peer-assisted Video-on-Demand systems, taking into account essential aspects such as peer churn, bandwidth heterogeneity, and Zipf-like video popularity. Our results reveal that the catalog size and the content popularity distribution have a huge effect on the system performance. We show that users' cooperation can effectively reduce the servers' burden for a wide range of system parameters, confirming to be an attractive solution to limit the costs incurred by content providers as the system scales to large populations of users.

We consider a communication system in which a given digital content has to be delivered sequentially at constant rate to a set of users who asynchronously request it according to a Poisson process. Users can retrieve data: 1) from one or more sources that statically store the entire content; and 2) from users who have previously requested the content, and contribute (for limited time) a random amount of upload bandwidth to the system. We propose a stochastic fluid framework that allows characterizing the aggregate streaming rate necessary at the sources to satisfy all active requests. In particular, we establish the conditions under which the system becomes asymptotically scalable as the number of users grows. Our theoretical results apply to increasingly popular video-on-demand systems exploiting users' cooperation.

We consider a peer-assisted Video-on-demand system, in which video distribution is supported both by peers caching the whole video and by peers concurrently downloading it. We propose a stochastic fluid framework that allows to characterize the additional bandwidth requested from the servers to satisfy all users watching a given video. We obtain analytical upper bounds to the server bandwidth needed in the case in which users download the video content sequentially. We also present a methodology to obtain exact solutions for special cases of peer upload bandwidth distribution. Our bounds permit to tightly characterize the performance of peer-assisted VoD systems as the number of users increases, for both sequential and non-sequential delivery schemes. In particular, we rigorously prove that the simple sequential scheme is asymptotically optimal both in the bandwidth surplus and in the bandwidth deficit mode, and that peer-assisted systems become totally self-sustaining in the surplus mode as the number of users grows large.

We analyze a peer-assisted Video-on-Demand system in which users contribute their upload bandwidth to the redistribution of a video that they are downloading or that they have cached locally. Our target is to characterize the additional bandwidth that servers must supply to immediately satisfy all requests to watch a given video. We develop an approximate fluid model to compute the required server bandwidth in the sequential delivery case. Our approach is able to capture several stochastic effects related to peer churn, upload bandwidth heterogeneity, non-stationary traffic conditions, which have not been documented or analyzed before. We provide an analytical methodology to design efficient peer-assisted VoD systems and optimal resource allocation strategies.

Stochastic geometry proves to be a powerful tool for modeling dense wireless networks adopting random MAC protocols such as ALOHA and CSMA. The main strength of this methodology lies in its ability to account for the randomness in the nodes' location jointly with an accurate description at the physical layer, based on the SINR, that allows to consider also random fading on each link. Existing models of CSMA networks adopting the stochastic geometry approach suffer from two important weaknesses: 1) they permit to evaluate only spatial averages of the main performance measures, thus hiding possibly huge discrepancies in the performance achieved by individual nodes; 2) they are analytically tractable only when nodes are distributed over the area according to simple spatial processes (e.g., the Poisson point process). In this paper we show how the stochastic geometry approach can be extended to overcome the above limitations, allowing to obtain node throughput distributions as well as to analyze a significant class of topologies in which nodes are not independently placed.

We analyze the capacity scaling laws of clustered ad hoc networks comprising significant inhomogeneities in the node spatial distribution over the area. In particular, we consider the class of networks in which nodes are distributed according to a doubly stochastic shot-noise Cox process, which allows to model a wide variety of inhomogeneous topologies. For this class of networks, we derive information theoretic upper-bounds to the capacity, identifying six operational regions. We also provide constructive lower bounds by devising, for each region, an optimal communication strategy to achieve the maximum network throughput. The performance of our communication schemes match, in terms of scaling exponent, the theoretical upper-bounds.

We extend the analysis of the scaling laws of wireless ad hoc networks to the case of correlated nodes movements, which are commonly found in real mobility processes. We consider a simple version of the Reference Point Group Mobility model, in which nodes belonging to the same group are constrained to lie in a disc area, whose center moves uniformly across the network according to the i.i.d. model. We assume fast mobility conditions and take as a primary goal the maximization of per-node throughput. We discover that correlated node movements have a huge impact on asymptotic throughput and delay and can sometimes lead to better performance than the one achievable under independent nodes movements.

We extend the analysis of the scaling laws of wireless ad hoc networks to the case of correlated nodes movements, which are commonly found in real mobility processes. We consider a simple version of the Reference Point Group Mobility model, in which nodes belonging to the same group are constrained to lie in a disc area, whose center moves uniformly across the network according to the i.i.d. model. We assume fast mobility conditions, and take as primary goal the maximization of per-node throughput. We discover that correlated node movements have huge impact on asymptotic throughput and delay, and can sometimes lead to better performance than the one achievable under independent nodes movements.

We analyze the capacity scaling laws of clustered ad hoc networks in which nodes are distributed according to a doubly stochastic shot-noise Cox process. We identify five different operational regimes, and for each regime we devise a communication strategy that allows to achieve a throughput featuring the same scaling exponent as the maximum theoretical capacity.

In this paper, we analyze asymptotic delay-throughput tradeoffs in mobile ad hoc networks comprising heterogeneous nodes with restricted mobility. We show that node spatial heterogeneity has the ability to drastically improve upon existing scaling laws established under the assumption that nodes are identical and uniformly visit the entire network area. In particular, we consider the situation in which each node moves around its own home-point according to a restricted mobility process which results into a spatial stationary distribution that decays as a power law of exponent δ with the distance from the home-point. For such restricted mobility model, we propose a novel class of scheduling and routing schemes, which significantly outperforms all delay-throughput results previously obtained in the case of identical nodes. In particular, for δ = 2 it is possible to achieve almost constant delay and almost constant per-node throughput (except for a polylogarithmic factor) as the number of nodes increases, even without resorting to sophisticated coding or signal processing techniques.

We consider static ad hoc wireless networks comprising significant inhomogeneities in the node spatial distribution over the area and analyze the scaling laws of their transport capacity as the number of nodes increases. In particular, we consider nodes placed according to a shot-noise Cox process (SNCP), which allows to model the clustering behavior usually recognized in large-scale systems. For this class of networks, we propose novel scheduling and routing schemes that approach previously computed upper bounds to the per-flow throughput as the number of nodes tends to infinity.

We consider static ad hoc wireless networks comprising significant inhomogeneities in the node spatial distribution over the area, and analyze the scaling laws of their transport capacity as the number of nodes increases. In particular, we consider nodes placed according to a shot-noise Cox process, which allows to model the clustering behavior usually recognized in large-scale systems. For this class of networks, we propose novel scheduling and routing schemes which approach previously computed upper bounds to the per-flow throughput as the number of nodes tends to infinity.

In this paper, we analyze asymptotic delay-throughput performance of mobile ad-hoc networks comprising heterogeneous nodes with restricted mobility. In particular, we consider a scenario in which each node moves around one or more home-points (in a finite number) randomly placed over the area. For such restricted mobility model, we propose a new class of scheduling and routing schemes, which significantly outperforms all delay-throughput results previously obtained.

We analyze the capacity scaling laws of wireless ad hoc networks comprising significant inhomogeneities in the node spatial distribution over the network area. In particular, we consider nodes placed according to a shot-noise Cox process, which allows to model the clustering behavior usually recognized in large-scale systems. For this class of networks, we introduce novel techniques to compute upper bounds to the available per-flow throughput as the number of nodes tends to infinity, which are tight in the case of interference limited systems.

A fundamental issue arising in mobile ad hoc networks (MANETs) is the selection of the optimal path between any two nodes. A method that has been advocated to improve routing efficiency is to select the most stable path so as to reduce the latency and the overhead due to route reconstruction. In this work, we study both the availability and the duration probability of a routing path that is subject to link failures caused by node mobility. In particular, we focus on the case where the network nodes move according to the Random Direction model, and we derive both exact and approximate (but simple) expressions of these probabilities. Through our results, we study the problem of selecting an optimal route in terms of path availability. Finally, we propose an approach to improve the efficiency of reactive routing protocols.

We provide the scaling laws for the transport capacity of a wide class of mobile wireless ad hoc networks. Our analysis generalizes previous results obtained under restrictive assumptions on the node mobility process and overall node density over the network area. The broader family of mobile networks that we consider is able to account for many important characteristics usually recognized in real traces of both human and vehicular mobility. In particular, we consider clustered, sparse networks of heterogeneous nodes, in which the shape of the spatial distribution of each node around one or more home-points plays a fundamental role in determining the overall transport capacity. We identify different operational regimes that arise within our general class of mobile networks, and for each regime we propose optimal scheduling and routing strategies achieving the maximum asymptotic capacity.

In this paper, we study the performance of the 2-hop routing scheme proposed for ad hoc wireless networks with mobile nodes, considering realistic node mobility patterns. First, we provide a formal definition of optimal routing maximizing the throughput of a mobile ad hoc network, in terms of a multi-commodity flow problem over the associated contact graph. Then, we relate the effectiveness of the 2-hop routing strategy to structural properties of the contact graph. We present experimental results showing that, in real networks, contact times among the nodes are largely inhomogeneous. Our results show that, in networks with inhomogeneous contact times, the 2-hop routing strategy can result strongly inefficient in terms of network throughput.

We address the problem of identifying high throughput paths in 802.11 wireless mesh networks. We introduce an analytical model that accurately captures the 802.11 MAC protocol operation and predicts both throughput and delay of multi-hop flows under changing traffic load or routing decisions. The main idea is to characterize each link by the packet loss probability and by the fraction of busy time sensed by the link transmitter, and to capture both intra-flow and inter-flow interference. Our model reveals that the busy time fraction experienced by a node, a locally measurable quantity, is essential in finding maximum throughput paths. Furthermore, metrics that do not take this quantity into account can yield low throughput by routing over congested paths or by filtering-out non-congested paths. Based on our analytical model, we propose a novel routing metric that can be used to discover high throughput path in a congested network. Using city-wide mesh network topologies we demonstrate that our model-based metric can achieve significant performance gains with respect to existing metrics.

We revisit the problem of characterizing the capacity of an ad hoc wireless network with n mobile nodes. Grossglauser and Tse (2001) showed that, by exploiting user mobility, it is possible to maintain a constant per-node throughput as the number of nodes grows. Their scheme allows to overcome the throughput decay (at least as 1/radicn) that affects networks with static nodes, which was first pointed out by Gupta and Kumar (2000). Subsequent works have analyzed the delay-capacity trade-off that arises in mobile networks under various mobility models. Almost invariably, however, available asymptotic results strongly rely on the assumption that nodes are identical, and move according to some ergodic process that is equally likely to visit any portion of the network area. In this paper, we relax such 'homogeneous mixing' assumption on the node mobility process, and analyze the network capacity in the more realistic case in which nodes are heterogeneous, and the motion of a node does not necessarily cover uniformly the entire space. We propose a general framework to characterize the capacity of networks with arbitrary mobility patterns, considering both the case of finite number of nodes (also with the support of experimental traces), as well as asymptotic results when the number of nodes grows to infinity.

We consider the problem of self-deployment and relocation in mobile wireless networks, where nodes are both sensors and actuators. We propose a unified, distributed algorithm that has the following features. During deployment, our algorithm yields a regular tessellation of the geographical area with a given node density, called monitoring configuration. Upon the occurrence of a physical phenomenon, network nodes relocate themselves so as to properly sample and control the event, while maintaining the network connectivity. Then, as soon as the event ends, all nodes return to the monitoring configuration. To achieve these goals, we use a virtual force-based strategy, which proves to be very effective even when compared to an optimal centralized solution.

We provide a general framework for the analysis of the capacity scaling properties in mobile ad-hoc networks with heterogeneous nodes and spatial inhomogeneities. Existing analytical studies strongly rely on the assumption that nodes are identical and uniformly visit the entire network space. Experimental data, however, have shown that the mobility pattern of individual nodes is typically restricted over the area, while the overall node density is often largely inhomogeneous, due to prevailing clustering behavior resulting from hot-spots. Such ubiquitous features of realistic mobility processes demand to reconsider the scaling laws for the per-user throughput achievable by the store-carry-forward communication paradigm which provides the foundation of many promising applications of delay tolerant networking. We show how the analysis of the asymptotic capacity of dense mobile ad-hoc networks can be transformed, under mild assumptions, into a Maximum Concurrent Flow (MCF) problem over anassociated Generalized Random Geometric Graph (GRGG). Our methodology allows to identify the scaling laws for a general class of mobile wireless networks, and to precisely determine under which conditions the mobility of nodes can indeed be exploited to increase the per-node throughput. At last we propose a simple, asymptotically optimal, scheduling and routing scheme that achieves the maximum transport capacity of the network.

In this paper, we revisit two classes of mobility models which are widely used to represent users' mobility in wireless networks: random waypoint (RWP) and random direction (RD). For both models, we obtain systems of partial differential equations which describe the evolution of the users' distribution. For the RD model, we show how the equations can be solved analytically both in the stationary and transient regime, adopting standard mathematical techniques. Our main contributions are 1) simple expressions which relate the transient duration to the model parameters and 2) the definition of a generalized random direction model whose stationary distribution of mobiles in the physical space corresponds to an assigned distribution.

Multi-hop wireless networks employing random access protocols have been shown to incur large discrepancies in the throughputs achieved by the flows sharing the network. Indeed, flow throughputs can span orders of magnitude from near starvation to many times greater than the mean. In this paper, we address the foundations of this disparity. We show that the fundamental cause is not merely differences in the number of contending neighbors, but a generic coordination problem of CSMA-based random access in a multi-hop environment. We develop a new analytical model that incorporates this lack of coordination, identifies dominating and starving flows and accurately predicts per-flow throughput in a large-scale network. We then propose metrics that quantify throughput imbalances due to the MAC protocol operation. Our model and metrics provide a deeper understanding of the behavior of CSMA protocols in arbitrary topologies and can aid the design of effective protocol solutions to the starvation problem.

We focus on a vehicular network supporting safety applications, and we present an application and a channel access mechanism for efficient multihop broadcasting. We study the performance of the proposed solution by developing an analytical framework, which provides several metrics relevant to message dissemination. Analytical results are compared with the performance obtained through ns

Sparse network of fixed or mobile wireless devices, where most of the time there does not exist a complete path from a source to a destination are often referred to as delay tolerant networks. The store-carry-and-forward principle, according to which messages can be stored at mobile nodes moving around the network area before being forwarded to the destination, allows the transmission of messages in such systems. In this paper, we use an analytical framework to study delay tolerant networks, based on asCSL model checking techniques. In particular we focus on the case in which fixed sensors exhibit on-off behavior to overcome battery capacity limitations.

This paper presents an application of basic concepts of statistical physics to devise an approximate model describing the dynamics of large peer-to-peer networks, based on fluid-diffusive equations. The model we propose is quite general and highly modular, and allows to represent several effects related to resources distribution among peers, user behavior, resource localization algorithms and dynamic structure of the overlay topology. Since the complexity of the model is largely independent of the system size, it provides a viable alternative to Montecarlo approaches for the analysis of very large P2P systems.

In this paper we revisit two classes of mobility models which are widely used to represent users' mobility in wireless networks: Random Waypoint (RWP) and Random Direction (RD). For both models we obtain systems of partial differential equations which describe the evolution of the users' distribution. For the RD model, we show how the equations can be solved analytically both in the stationary and transient regime adopting standard mathematical techniques. Our main contributions are i) simple expressions which relate the transient duration to the model parameters; ii) the definition of a generalized random direction model whose stationary distribution of mobiles in the physical space corresponds to an assigned distribution.

We consider a wireless sensor network whose nodes may enter the so-called sleep mode, corresponding to low power consumption and reduced operational capabilities. We develop a Markov model of the network representing: 1) the behavior of a single sensor as well as the dynamics of the entire network, 2) the channel contention among sensors, and 3) the data routing through the network. We use this model to evaluate the system performance in terms of energy consumption; network capacity, and data delivery delay. Analytical results present a very good matching with simulation results for a large variety of system scenarios, showing the accuracy of our approach

The behavior of large-scale wireless sensor networks has been shown to be surprisingly complex and difficult to analyze, both by empirical experiment and simulation. In this paper we develop a new analytical model of the behavior of wireless sensor networks, based on a fluid approach, i.e., we represent the sensor network by a continuous fluid entity distributed on the network area. The model accounts for node energy consumption, channel contention, as well as traffic routing; thus, it is well suited for describing the properties of sensor networks and understanding their complex behavior.

In this paper, we decompose a large- or small-scale multi-hop wireless network into embedded subgraphs, each consisting of four nodes and two flow pairs. We systematically study all twelve possible topologies that arise according to whether the different nodes are in radio range of each other. We show that under both a random spatial distribution of nodes and random waypoint mobility with shortest-path routing, a critical and highly probable scenario is a class in which the channel state shared by the two flows is not only incomplete (i.e., the graph is not fully connected), but there is also asymmetry in the state between the two flows. We develop an accurate analytical model validated by simulations to characterize the long-term unfairness that naturally arises when CSMA with two- or four-way handshake is employed as a random access protocol. Moreover, we show that another key class of topologies consists of incomplete but symmetric shared state. We show via modeling and simulations that in this case, the system achieves long-term fairness, yet endures significant durations in which one flow dominates channel access with many repeated transmissions before relinquishing the channel. The model predicts the time-scales of this unfairness as a function of system parameters such as the maximum retransmission limit.

In this paper we propose a new fluid model approach in which a different description of the dynamics of traffic sources is adopted, exploiting partial differential equations. This new description of the source dynamics allows the natural representation of short-lived as well as long-lived TCP connections, with no sacrifice in the scalability of the model. In addition, the use of partial differential equations permits the description of distributions, instead of averages, thus providing better accuracy in the results. The comparison between the performance estimates obtained with fluid models and with ns-2 simulations proves the accuracy of the proposed modeling approach.

A critical issue in wireless sensor networks is represented by the limited availability of energy within network nodes; therefore making good use of energy is a must. A widely employed energy-saving technique is to place nodes in sleep mode, corresponding to a low-power consumption as well as to reduced operational capabilities. In this work, we develop a Markov model of a sensor network whose nodes may enter a sleep mode, and we use this model to investigate the system performance in terms of energy consumption, network capacity, and data deliver delay. Furthermore, the proposed model enables us to investigate the trade-offs existing between these performance metrics and the sensor dynamics in sleep/active mode. Analytical results present an excellent matching with simulation results for a large variety of system scenarios showing the accuracy of our approach.

Fluid models of IP networks have been recently proposed as a way to break the scalability barrier of traditional discrete state-space models, both simulative (e.g., ns-2) and analytical (e.g., queues and Markov chains). Fluid models adopt an abstract deterministic description of the average network dynamics through a set of ordinary differential equations that are then solved numerically, obtaining estimates of the time-dependent network behavior. However, an important limit of the fluid model approaches presented so far in the literature is their unnatural representation of scenarios comprising the short-lived TCP flows that dominate in today's Internet. In this paper we propose a new fluid model approach in which a different description of the dynamics of traffic sources is adopted, exploiting partial differential equations. This new description of the source dynamics allows the natural representation of short-lived as well as long-lived TCP connections, with little sacrifice in the scalability of the model. In addition, the use of partial differential equations permits the description of distributions, instead of averages, thus providing better accuracy in the results. The comparison between the performance estimates obtained with fluid models and with ns simulations proves the accuracy of the proposed modeling approach.

This paper presents a new analytical model for the estimation of the performance of TCP connections. The model is based on the description of the behavior of TCP in terms of a closed queueing network. The model is very accurate, deriving directly from the finite state machine description of the protocol. The assessment of the accuracy of the analytical model is based on comparisons against detailed simulation experiments developed with the ns-2 package. The protocol model interacts with an IP network model that can take into account meshed topologies with several bottlenecks. Numerical results indicate that the proposed closed queueing network model provides accurate performance estimates in all situations. A novel and interesting property of the model is the possibility of deriving ensemble distributions of relevant parameters, such as, for instance, the transmission window size or the timeout probability, which provide useful insight into the protocol behavior and properties.

Analytical approaches for the performance investigation of portions of the Internet often consider the behavior of TCP over congested (or bottleneck) links. In several cases, the analysis is based on an iterative fixed point approximation (FPA) to compute the equilibrium point, in terms of packet loss rate and offered load, that represents the operating point of the network. Almost invariably, the FPA is conjectured to converge, but no proof of convergence is provided. This paper proves that a general model of a reliable protocol (such as TCP) over congested links converges to a unique stable solution under mild regularity conditions. This provides a justification of the convergence observed in the literature and a solid base for the further development of analytical approaches based on FPAs.

In this paper we present analytical techniques that can be used to better understand the behavior of malware, a generic term that refers to all kinds of malicious software programs propagating on the Internet, such as e-mail viruses and worms. We develop a modeling methodology based on Interactive Markov Chains that is able to capture many aspects of the problem, especially the impact of the underlying topology on the spreading characteristics of malware. We propose numerical methods to obtain useful bounds and approximations in the case of very large systems, validating our results through simulation. An analytic methodology represents a fundamentally important step in the development of effective countermeasures for future malware activity. Furthermore, we believe our approach can help to understand a wide range of "dynamic interactions on networks", such as routing protocols and peer-to-peer applications.

In this paper we describe an analytical approach for estimating the queuing delay distribution on an Internet link carrying realistic TCP traffic, such as that produced by a large number of finite-size connections transferring files whose sizes are taken from a long-tail distribution. The analytical predictions are validated against detailed simulation experiments and real network measurements. Despite its simplicity, our model proves to be accurate and robust under a variety of operating conditions, and offers novel insights into the impact on the network of long-tail flow length distributions. Our contribution is a performance evaluation methodology that could be usefully employed in network dimensioning and engineering.

This paper presents a new analytical model for the estimation of the performance of TCP connections. The model is based on the description of the behavior of TCP-Tahoe in terms of a closed queueing network, whose solution can be obtained with very low cost, even when the number of TCP connections that interact over the underlying IP network is huge. The protocol model can be very accurate, deriving directly from the finite state machine description of the protocol. The assessment of the accuracy of the analytical model is based on comparisons against detailed simulation experiments developed with the ns-2 package. Numerical results indicate that the proposed closed queueing network model provides extremely accurate performance estimates, not only for average values, but even for distributions, in the case of the classical single-bottleneck configuration, as well as in more complex networking setups.