1,721,615 research outputs found
Asymptotic Performance Limits of Switches with Buffered Crossbars supporting Multicast Traffic
No full textInput queued (IQ) switches exploiting buffered crossbars (CICQ switches) are widely considered very promising architectures that outperform IQ switches with bufferless switching fabrics both in terms of architectural scalability and performance. Indeed the problem of scheduling packets for transfer through the switching fabric is significantly simplified by the presence of internal buffers in the crossbar, which makes possible the adoption of efficient, simple and fully distributed scheduling algorithms. This paper studies the throughput performance of CICQ switches supporting multicast traffic, showing that, similarly to IQ architectures, also CICQ switches with arbitrarily large number of ports may suffer of significant throughput degradation under "pathological" multicast traffic patterns. Despite the asymptotic nature of these results, the authors believe that they can contribute to a deeper understanding of the behavior of CICQ architectures supporting multicast traffi
Large deviations of the interference in the Ginibre network model
Full text linkUnder different assumptions on the distribution of the fading random variables, we derive large deviation estimates for the tail of the interference in a wireless network model whose nodes are placed, over a bounded region of the plane, according to the β-Ginibre process, 0
When the fading random variables are bounded or Weibull superexponential, large values of the interference are typically originated by the sum of several equivalent interfering contributions due to nodes in the vicinity of the receiver. In this case, the tail of the interference has, on the log-scale, the same asymptotic behavior for any value of 0
When the fading random variables are exponential or subexponential, instead, large values of the interference are typically originated by a single dominating interferer node and, on the log-scale, the asymptotic behavior of the tail of the interference is insensitive to the distribution of the nodes, as long as the number of nodes is guaranteed to be light-tailed
Simulating the tail of the interference in a Poisson network model
Full text linkInterference among simultaneous transmissions represents the main limitation factor for the capacity and connectivity of dense wireless networks. In this paper we provide efficient simulation laws for the tail of the interference in a simple wireless ad hoc network model. Particularly, we consider node locations distributed according to a Poisson point process and various classes of light-tailed fading distribution
Generalized Threshold-Based Epidemics in Random Graphs: the Power of Extreme Values
Full text linkBootstrap percolation is a well-known activation process in a graph,
in which a node becomes active when it has at least 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 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 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
Content-centric wireless networks with limited buffers: when mobility hurts
Full text linkWe 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 cas
Similarity Caching: Theory and Algorithms
Full text linkThis 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
Throughput Region of Finite-Buffered Networks
No full textMost of the current communication networks, including the Internet, are packet switched networks. One of the main reasons behind the success of packet switched networks is the possibility of performance gain due to multiplexing of network bandwidth. The multiplexing gain crucially depends on the size of the buffers available at the nodes of the network to store packets at the congested links. However, most of the previous work assumes the availability of infinite buffer-size. In this paper, we study the effect of finite buffer-size on the performance of networks of interacting queues. In particular, we study the throughput of flow-controlled loss-less networks with finite buffers. The main result of this paper is the characterization of a dynamic scheduling policy that achieves the maximal throughput with a minimal finite buffer at the internal nodes of the network under memory-less (e.g., Bernoulli IID) exogenous arrival process. However, this ideal performance policy is rather complex and, hence, difficult to implement. This leads us to the design of a simpler and possibly implementable policy. We obtain a natural trade-off between throughput and buffer-size for such implementable policy. Finally, we apply our results to packet switches with buffered crossbar architecture
Bootstrap percolation on the stochastic block model
Full text linkWe analyze the bootstrap percolation process on the stochastic
block model (SBM), a natural extension of the ErdH{o}s--R'{e}nyi random graph
that incorporates the community structure observed in many real systems.
In the SBM, nodes are partitioned into two subsets, which represent different communities,
and pairs of nodes are independently connected with a probability that depends on the communities they belong to.
Under mild assumptions on the system parameters, we prove the existence of a sharp phase transition
for the final number of active nodes and characterize the sub-critical and the super-critical regimes
in terms of the number of initially active nodes, which are selected uniformly at random in each community
Competition of Influencers: A Model for Maximizing Online Social Impact
Full text linkx The landscape of human interaction has undergone a profound transformation % has been profoundly transformed since the advent of Online Social Networks (OSNs). Not only are they changing interpersonal dynamics, but they are also redefining the way businesses, political figures, and media organizations engage with the broader population. In today's digital landscape, OSNs have spawned a new class of social media influencers who play a crucial role in shaping opinion. These influencers actively compete within social media to seize users' attention. Through these targeted efforts, influencers seek to captivate users and build a loyal and engaged fan base, solidifying their position as an authoritative voice in the digital world. In this work, we develop a game-theoretic model for the interactions between users and influencers, where the latter compete to maximize their impact on the population's opinions. The goal of this work is twofold: first, we formalize the problem of maximizing social media impact and study the structure of the optimal solution. Then, taking inspiration from the optimal strategy, we develop a game with two opposing players trying to maximize their influence on users' opinions, for which we characterize the Nash equilibria in pure strategy. The model allows us to evaluate the impact of influencer differences and user population characteristics. In addition, we study the effect of the speed at which user popularity evolves in such a competitive environment. The proposed model proves valuable for brand competition, marketing campaigns, and the ever-evolving political arena
- …
