In a Hierarchical Inference (HI) system, an end device processes data samples using a local Deep Learning (DL) model. Only when the confidence of the local DL is less than a chosen threshold, it offloads the sample for remote DL inference on an edge server. By balancing the misclassifications and offloading costs, a HI system can improve accuracy and responsiveness and reduce bandwidth usage. To this end, prior work studied a HI learning problem for classification tasks, aiming to learn an optimal threshold on the confidence to minimize the cumulative costs. However, existing formulations considered (i) abstract offloading costs and (ii) assumed that the remote DL inference for an offloaded task is available by the end of each round. In contrast, considering that end devices are wirelessly connected to edge servers, we study a HI system with an offload queue where the offloading cost is implicitly modeled by the queue length. Also, we consider the practical setting, where the remote DL inference is obtained only after the task is served from the offload queue. For bounded but unknown arrival and service processes, we formulate the problem of average mismatch error minimization subject to queue stability. We propose a BOLD Hedge-Q policy based on Lyapunov optimization. The novelty of BOLD Hedge-Q lies in solving a delayed-feedback online learning problem — with sub-linear regret — that results from the Lyapunov drift-plus-penalty analysis. Given a penalty parameter V ≥ 1, we show that under BOLD Hedge-Q, the queue is upper bounded by V + λm, and the mismatch error is within an additive factor of O(1/V) from that of the optimal policy, where λm is the maximum number of arrivals in a round.

Security is a major challenge in Internet-of-Things (IoT) systems, and network intrusion detection systems (NIDS) play a key role in proposed solutions. In this paper, we propose VarSec which is a centralised unsupervised algorithm for network anomaly detection. It uses two variational autoencoders (VAEs) to process packet-level data, and combines their output to detect anomalous packets. We evaluate the performance of our proposed algorithm on a variety of attack datasets and compare it with existing solutions.

Consider$n$nodes communicating over an unreliable broadcast channel. Each node has a single packet that needs to be communicated to all other nodes. Time is slotted, and a time slot is long enough for each node to broadcast one packet. Each broadcast reaches a random subset of nodes. The objective is to minimise the time until all nodes have received all packets. We study two schemes, (i) random relaying, and (ii) random linear network coding, and analyse their performance in an asymptotic regime in which$n$tends to infinity. Simulation results for a wide range of$n$are also presented.

We consider a decentralized multi-agent Multi Armed Bandit (MAB) setup consisting of $N$ agents, solving the same MAB instance to minimize individual cumulative regret. In our model, agents collaborate by exchanging messages through pairwise gossip style communications. We develop two novel algorithms, where each agent only plays from a subset of all the arms. Agents use the communication medium to recommend only arm-IDs (not samples), and thus update the set of arms from which they play. We establish that, if agents communicate $\Omega(\log(T))$ times through any connected pairwise gossip mechanism, then every agent’s regret is a factor of order $N$ smaller compared to the case of no collaborations. Furthermore, we show that the communication constraints only have a second order effect on the regret of our algorithm. We then analyze this second order term of the regret to derive bounds on the regret-communication tradeoffs. Finally, we empirically evaluate our algorithm and conclude that the insights are fundamental and not artifacts of our bounds. We also show a lower bound which gives that the regret scaling obtained by our algorithm cannot be improved even in the absence of any communication constraints. Our results demonstrate that even a minimal level of collaboration among agents greatly reduces regret for all agents.

The emergence of new connectivity services for automated transportation marks a paradigm shift for the operation of wireless networks. Furthermore, the advent of blockchain technology promises to enable a plethora of smart mobility services, which are not contingent on any central authorities. Concepts such as distributed ledger require efficient and reliable data dissemination between vehicles. Traditional techniques based on Automatic Repeat Request (ARQ) are well known to scale poorly in all-cast networks due to the feedback implosion problem. Fountain and network coding techniques are arguably the most promising alternative solutions. In this paper we derive new analytical bounds on transmit message lengths and quantify bandwidth delay trade-offs for fountain coding based data dissemination for CAVs.

This paper proposes a dynamic user association method to address the load balancing problem in dense IEEE 802.11ax networks with uneven user distribution, where a user determines which AP to connect to taking into consideration of multiple factors such as RSS, potential relative capacity, achievable data rate and location of users. The method is user-centric and does not incur much signaling overhead, while performance optimization can be achieved without inter-AP coordination. Simulation results have been presented to show that the proposed solution can improve load balancing and have higher average throughput for 10% worst users as well as maintain the maximal total system throughput. Our evaluation also suggests that the location-awareness of users considered in the proposed solution plays an important role to improve the performance.

Inter-cell interference mitigation techniques are playing important roles to improve the system performance, especially for dense network. Among them, the coordinated transmission has been used to tackle the interference problem. In this paper, we investigated the performances of coordinated transmission with stochastic network modeling and derived its expression on coverage probability and average rate with different number of base station coordination. The numerical results have been presented to compare the performance with frequency reuse technique. The results suggest that the coordinated transmission can perform better than frequency reuse in terms of coverage probability and average rate depending on the scheduling of the transmission of coordinated base stations.

In a random key graph (RKG) of n nodes each node is randomly assigned a key ring of Kncryptographic keys from a pool of Pnkeys. Two nodes can communicate directly if they have at least one common key in their key rings. We assume that the n nodes are distributed uniformly in [0, l]2. In addition to the common key requirement, we require two nodes to also be within rnof each other to be able to have a direct edge. Thus we have a random graph in which the RKG is superposed on the familiar random geometric graph (RGG). For such a random graph, we obtain tight bounds on the relation between Kn, Pnand rnfor the graph to be asymptotically almost surely connected.

In this paper, we analyze the performance of random load resampling and migration strategies in parallel server systems. Clients initially attach to an arbitrary server, but may switch servers independently at random instants of time in an attempt to improve their service rate. This approach to load balancing contrasts with traditional approaches where clients make smart server selections upon arrival (e.g., Join-the-Shortest-Queue policy and variants thereof). Load resampling is particularly relevant in scenarios where clients cannot predict the load of a server before being actually attached to it. An important example is in wireless spectrum sharing where clients try to share a set of frequency bands in a distributed manner.

This paper studies the performance of contention based medium access control (MAC) protocols. In particular, a simple and accurate technique for estimating the throughput of the IEEE 802.11 DCF protocol is developed. The technique is based on a rigorous analysis of the Markov chain that corresponds to the time evolution of the back-off processes at the contending nodes. An extension of the technique is presented to handle the case where service differentiation is provided with the use of heterogeneous protocol parameters, as, for example, in IEEE 802.11e EDCA protocol. Our results provide new insights into the operation of such protocols. The techniques developed in the paper are applicable to a wide variety of contention based MAC protocols.

Interference from other users limits the capacity, and possibly the connectivity, of wireless networks. A simple model of a wireless ad hoc network, in which node locations are described by a homogeneous Poisson point process, and node transmission powers are random, is considered in this paper. A large deviation principle for the interference is presented under different assumptions on the distribution of transmission powers.

Abstract — Current generation worms have caused considerable damage, despite their use of unsophisticated scanning strategies for detecting vulnerable hosts. A number of adaptive techniques have been proposed for quarantining hosts whose behaviour is deemed suspicious. Such techniques have been proven to be effective against fast scanning worms. However, worms could evade detection by being less aggressive. In this paper we consider the interplay between worm strategies and detection techniques, which can be described in game-theoretic terms. We use epidemiological modelling to characterise the outcome of the game (the pay-off function), as a function of the strategies of the worm and the detector. We design detection rules that are optimal against scanning worms with known characteristics. We then identify specific detection rules that are close to optimal, in some mathematically precise sense, against any scanning worm. Finally, we design methods for coordinating information among a set of end-hosts, using Bayesian decision theory. We evaluate the proposed rules using simulations driven by traces from a corporate environment of 600 hosts, and assess the benefits of coordination. I.

Abstract — We study the performance of contention based medium access control (MAC) protocols. In particular, we pro-vide a simple and accurate method for estimating the throughput of IEEE 802.11 DCF and IEEE 802.11e EDCA. Our method is based on a rigorous analysis of the Markov chain associated with the back-off process at the contending nodes. Our results provide new insights into the operation of IEEE 802.11 DCF and IEEE 802.11e EDCA. Although we focus on IEEE 802.11 MAC protocol in this paper, the techniques developed are applicable to a wide variety of contention based MAC protocols. I.

In this article we address the problem of counting the number of peers in a peer-to-peer system, and more generally of aggregating statistics of individual peers over the whole system. This functionality is useful in many applications, but hard to achieve when each node has only a limited, local knowledge of the whole system. We propose two generic techniques to solve this problem. The Random Tour method is based on the return time of a continuous time random walk to the node originating the query. The Sample and Collide method is based on counting the number of random samples gathered until a target number of redundant samples are obtained. It is inspired by the birthday paradox technique of [6], upon which it improves by achieving a target variance with fewer samples. The latter method relies on a sampling sub-routine which returns randomly chosen peers. Such a sampling algorithm is of independent interest. It can be used, for instance, for neighbour selection by new nodes joining the system. We use a continuous time random walk to obtain such samples. We analyse the complexity and accuracy of the two methods. We illustrate in particular how expansion properties of the overlay affect their performance.

Epidemic-style (gossip-based) techniques have recently emerged as a class of scalable and reliable protocols for peer-to-peer multicast dissemination in large process groups. However, popular implementations of epidemic-style dissemination suffer from two major drawbacks: 1) Network overhead: when deployed on a WAN-wide or VPN-wide scale, they generate a large number of packets that transit across the boundaries of multiple network domains (e.g., LANs, subnets, ASs), causing an overload on core network elements such as bridges, routers, and associated links. 2) Lack of adaptivity: they impose the same load on process group members and the network even under reduced failure rates (viz., packet losses, process failures). In this paper, we describe two protocols to address these problems: 1) a hierarchical gossiping protocol and 2) an adaptive dissemination framework (for multicasts) that allows use of any gossiping primitive within it. These protocols work within a virtual peer-to-peer hierarchy called the leaf box hierarchy. Processes can be allocated in a topologically aware manner to the leaf boxes of this structure, so that protocols 1 and 2 produce low traffic across domain boundaries in the network and induce minimal overhead when there are no failures

Many network phenomena are well modeled as spreads of epidemics through a network. Prominent examples include the spread of worms and email viruses, and, more generally, faults. Many types of information dissemination can also be modeled as spreads of epidemics. In this paper we address the question of what makes an epidemic either weak or potent. More precisely, we identify topological properties of the graph that determine the persistence of epidemics. In particular, we show that if the ratio of cure to infection rates is larger than the spectral radius of the graph, then the mean epidemic lifetime is of order log n, where n is the number of nodes. Conversely, if this ratio is smaller than a generalization of the isoperimetric constant of the graph, then the mean epidemic lifetime is of order e/sup na/, for a positive constant a. We apply these results to several network topologies including the hypercube, which is a representative connectivity graph for a distributed hash table, the complete graph, which is an important connectivity graph for BGP, and the power law graph, of which the AS-level Internet graph is a prime example. We also study the star topology and the Erdos-Renyi graph as their epidemic spreading behaviors determine the spreading behavior of power law graphs.

The flow control algorithms currently used in the Internet have been tailored to share available capacity between users on the basis of the physical characteristics of the network links they use rather than the characteristics of their applications. However, real-time applications typically have very different requirements from file transfer or Web browsing, and treating them identically can result in a perception of poor quality of service even when adequate bandwidth is available. This is the motivation for differentiated services. In this paper, we explore service differentiation between persistent (fixed duration) and transient (fixed volume) flows, and also between transient flows of markedly different sizes; the latter is stimulated by current discussion on Web mice and elephants. We propose decentralized bandwidth allocation algorithms that can be implemented by end-systems without requiring the support of a complex network architecture, and show that they achieve performance very close to what is achievable by the optimal centralized scheme.

The growth of peer-to-peer applications on the Internet motivates interest in general purpose overlay networks. The construction of overlays connecting a large population of transient nodes poses several challenges. First, connections in the overlays should reflect the underlying network topology, in order to avoid overloading the network and to allow god application performance. Second, connectivity among active nodes of the overlay should be maintained, even in the presence of high failure rates or when a large proportion of nodes are not active. Finally, the cost of using the overlay should be spread evenly among peer nodes for fairness reasons as well as for the sake of application performance. To preserve scalability, we seek solutions to these issues that can be implemented in a fully decentralized manner and rely on local knowledge from each node. In this paper, we propose an algorithm called the localizer which addresses these three key challenges. The localizer refines the overlay in a way that reflects geographic locality so as to reduce network overload. Simultaneously, it helps to evenly balance the number of neighbors of each node in the overlay, thereby sharing the load evenly as well as improving the resilience to random node failures or disconnections. The proposed algorithm is presented and evaluated in the context of an unstructured peer-to-peer overlay network produced using the Scamp protocol. We provide a theoretical analysis of the various aspects of the algorithm. Simulation results based on a realistic network topology model confirm the analysis and demonstrate the localizer efficiency.

Gossip-based protocols for group communication have attractive scalability and reliability properties. The probabilistic gossip schemes studied so far typically assume that each group member has full knowledge of the global membership and chooses gossip targets uniformly at random. The requirement of global knowledge impairs their applicability to very large-scale groups. In this paper, we present SCAMP (Scalable Membership protocol), a novel peer-to-peer membership protocol which operates in a fully decentralized manner and provides each member with a partial view of the group membership. Our protocol is self-organizing in the sense that the size of partial views naturally converges to the value required to support a gossip algorithm reliably. This value is a function of the group size, but is achieved without any node knowing the group size. We propose additional mechanisms to achieve balanced view sizes even with highly unbalanced subscription patterns. We present the design, theoretical analysis, and a detailed evaluation of the basic protocol and its refinements. Simulation results show that the reliability guarantees provided by SCAMP are comparable to previous schemes based on global knowledge. The scale of the experiments attests to the scalability of the protocol.

The growth of the Internet raises new challenges for the design of distributed systems and applications. In the context of group communication protocols, gossip-based schemes have attracted interest as they are scalable, easy to deploy, and resilient to network and process failures. However, traditional gossip-based protocols have two major drawbacks: 1) they rely on each peer having knowledge of the global membership; and 2) being oblivious to the network topology, they can impose a high load on network links when applied to wide-area settings. In this paper, we provide a theoretical analysis of gossip-based protocols which relates their reliability to key system parameters (the system size, failure rates, and number of gossip targets). The results provide guidelines for the design of practical protocols. In particular, they show how reliability can be maintained while alleviating drawback by: 1) providing each peer with only a small subset of the total membership information and drawback; and 2) organizing members into a hierarchical structure that reflects their proximity according to some network-related metric. We validate the analytical results by simulations and verify that the hierarchical gossip protocol considerably reduces the load on the network compared to the original, non-hierarchical protocol.

Epidemic-style (gossip-based) techniques have recently emerged as a scalable class of protocols for peer-to-peer reliable multicast dissemination in large process groups. These protocols provide probabilistic guarantees on reliability and scalability. However, popular implementations of epidemic-style dissemination are reputed to suffer from two major drawbacks: (a) (Network Overhead) when deployed on a WAN-wide or VPN-wide scale they generate a large number of packets that transit across the boundaries of multiple network domains (e.g., LANs, subnets, ASs), causing an overload on core network elements such as bridges, routers, and associated links; (b) (Lack of Adaptivity) they impose the same load on process group members and the network even under reduced failure rates (viz., packet losses, process failures). lit this paper we report on the (first) comprehensive set of solutions to these problems. The solution is comprised of two protocols: (1) a hierarchical gossiping protocol, and (2) an adaptive multicast dissemination framework that allows use of any gossiping primitive within it. These protocols work within a virtual peer-to-peer hierarchy called the Leaf Box hierarchy. Processes can be allocated in a topologically aware manner to the leaf boxes of this structure, so that (1) and (2) produce low traffic across domain boundaries in the network. In the interests of space, this paper focuses on a detailed discussion and evaluation (through simulations) of only the hierarchical gossiping protocol. We present an overview of the adaptive dissemination protocol and its properties.

The problem of sharing bandwidth in a communication network has been the focus of much research aimed at guaranteeing an appropriate quality of service to users. This is particularly challenging in an environment with a great diversity of users and applications, which makes it difficult, if not impossible, to tightly constrain user attributes and requirements. This motivates shifting the burden of rate allocation from the network to the end-systems. We propose a decentralized scheme for user adaptation and study its dynamics. The proposed scheme uses congestion prices as a mechanism for providing both feedback and incentives to end-systems.

The problem is to allocate a fixed number of buffers among the nodes of an open network of exponential servers with Bernoulli routing and Poisson arrivals so as to optimize some performance criterion associated with the time to buffer overflow, such as maximizing its mean or maximizing the probability that it exceeds some value. In earlier work, the authors used pathwise probabilistic arguments to derive a simple rule of thumb for this problem: allocate the buffers in inverse proportion to the logarithms of the effective service rates at the nodes. Effective service rate denotes the ratio of the service rate to the stationary arrival rate in the network with infinite buffers. They showed that this rule of thumb is accurate to within a known constant times the logarithm of the number of buffers as the number of buffers to be allocated becomes large. In the present paper, the authors use time reversal and Poisson clumping arguments to show that their rule of thumb is, in fact, much better than previously demonstrated. They show that the optimal buffer allocation is within a constant of the rule of thumb as the number of buffers to be allocated becomes large, although now they cannot estimate the constant. In numerical terms, the earlier result reduced the search space for the optimal buffer allocation from O(N/sup J-1/) to O((log N)/sup J-1/), where J denotes the number of nodes and N the number of buffers to be allocated. The improvement reduces the search space to O(1).>