waashk/dblp huggingface dataset:
routing primitives for wireless mesh networks: design, analysis and experiments. in this paper, we consider routing in multi-hop wireless mesh networks. we analyze three standardized and commonly deployed routing mechanisms that we term "node-pair discovery" primitives. we show that use of these primitives inherently yields inferior route selection, irrespective of the protocol that implements them. this behavior originates due to overhead reduction actions that systematically yield insufficient distribution of routing information, effectively hiding available paths from nodes. to address this problem, we propose a set of "deter and rescue" routing primitives that enable nodes to discover their hidden paths by exploiting already available historic routing information. we use extensive measurements on a large operational wireless mesh network to show that with node-pair discovery primitives, inferior route selections occur regularly and cause long-term throughput degradations for network users. in contrast, the deter and rescue primitives largely identify and prevent selection of inferior paths. moreover, even when inferior paths are selected, the new primitives reduce their duration by several orders of magnitude, often to sub-second time scales.
p2p trading in social networks: the value of staying connected. the success of future p2p applications ultimately depends on whether users will contribute their bandwidth, cpu and storage resources to a larger community. in this paper, we propose a new incentive paradigm, networked asynchronous bilateral trading (nabt), which can be applied to a broad range of p2p applications. in nabt, peers belong to an underlying social network, and each pair of friends keeps track of a credit balance between them. when user alice provides a service (a file, storage space, computation and so on) to her friend bob, she charges bob credits. thus, in nabt, there is no global currency; instead, there are only credit balances maintained between pairs of friends. nabt allows peers to supply each other asynchronously and further allows peers to trade with remote peers through intermediaries. we theoretically show that nabt is perfectly efficient with balanced demands and supports "networked tit-for-tat". the efficiency of nabt with unbalanced demands is determined by the min-cut of credit limits of the underlying social network. using simulations driven by myspace traces, we demonstrate that a simple two-hop nabt design can have high trading efficiency, provide service differentiation, exploit trading intermediaries, and discourage free-riders.
on the connectivity analysis over large-scale hybrid wireless networks. many real systems are hybrid networks which include infrastructure nodes in multi-hop wireless networks, such as sinks in sensor networks and mesh routers in mesh networks. however, we have very little understanding of network connectivity in such networks. therefore, in this paper, we consider hybrid networks denoted by h(α, β) with ad hoc nodes and base stations and prove how base stations can improve the connectivity of ad hoc nodes in subcritical phase, that is, the ad hoc node density, λα is lower than the critical density λαc. we find that with the existence of a positive density of base stations, i.e., the density of base stations λβ > 0 which have the same transmission range as ad hoc nodes, the number of connected ad hoc nodes is θ(n) with probability nearly 1, where n is the number of ad hoc nodes. however, the size of connected ad hoc component scales linearly with λβ when it is lower than c1(λα) with probability nearly 1, which demonstrates a tremendous benefit of using base stations to enhance the connectivity of ad hoc nodes. further, we study a hybrid network architecture that makes a significant connectivity improvement with transmission range rβ larger than rα for ad hoc nodes. therefore, our results provide a theoretical understanding of to what extent ad hoc nodes can benefit from base stations in multihop wireless networks.
dac: distributed asynchronous cooperation for wireless relay networks. cooperative relay is a communication paradigm that aims to realize the capacity of multi-antenna arrays in a distributed manner. however, the symbol-level synchronization requirement among distributed relays limits its use in practice. we propose to circumvent this barrier with a cross-layer protocol called distributed asynchronous cooperation (dac). with dac, multiple relays can schedule concurrent transmissions with packet-level (hence coarse) synchronization. the receiver then extracts multiple versions of each relayed packet via a collision-resolution algorithm, thus realizing the diversity gain of cooperative communication. we demonstrate the feasibility of dac by prototyping and testing it on the gnuradio/usrp software radio platform. to explore its relevance at the network level, we introduce a dac-based mac, and a generic approach to integrate the dac mac/phy layer into a typical routing algorithm. considering the use of dac for multiple network flows, we analyze the fundamental tradeoff between the improvement in diversity gain and the reduction in multiplexing opportunities. dac is shown to improve the throughput and delay performance of lossy networks with medium-level link quality. our analytical results are also confirmed by network-level simulation in ns-2.
two samples are enough: opportunistic flow-level latency estimation using netflow. the inherent support in routers (snmp counters or netflow) is not sufficient to diagnose performance problems in ip networks, especially for flow-specific problems where the aggregate behavior within a router appears normal. to address this problem, in this paper, we propose a consistent netflow (cnf) architecture for measuring per-flow performance measurements within routers. cnf utilizes existing netflow architecture that already reports the first and last timestamps per-flow, and proposes hash-based sampling to ensure that two adjacent routers record the same flows. we devise a novel multiflow estimator that approximates the intermediate delay samples from other background flows to improve the per-flow latency estimates significantly compared to the naive estimator that only uses actual flow samples. in our experiments using real backbone traces and realistic delay models, we show that the multiflow estimator is accurate with a median relative error of less than 20% for flows of size greater than 100 packets. we also show that prior approach based on trajectory sampling performs about 2-3x worse.
bgp churn evolution: a perspective from the core. the scalability limitations of bgp have been a major concern in the networking community lately. an important issue in this respect is the rate of routing updates (churn) that bgp routers must process. this paper presents an analysis of the evolution of churn in four networks in the backbone of the internet over the last six years, using update traces from the routeviews project. the churn rate varies widely over time and between networks, and cannot be understood through "blackbox" statistical analysis. instead we take a different approach with a focus on investigating the underlying reasons for bgp churn evolution. through our analysis we are able to identify and isolate the main reasons behind many of the anomalies in the churn time series. we find that duplicate announcements is a major churn contributor, and responsible for most large spikes in the churn time series. other intense periods of churn are caused by misconfigurations or other special events in or close to the monitored as, and hence limiting these is an important mean to limit churn. we then analyze the remaining "baseline" churn, and find that it is increasing with a rate much slower than the increase in the routing table size.
exploiting multiple-antenna diversity for shared secret key generation in wireless networks. generating a secret key between two parties by extracting the shared randomness in the wireless fading channel is an emerging area of research. previous works focus mainly on single-antenna systems. multiple-antenna devices have the potential to provide more randomness for key generation than single-antenna ones. however, the performance of key generation using multiple-antenna devices in a real environment remains unknown. different from the previous theoretical work on multiple-antenna key generation, we propose and implement a shared secret key generation protocol, multiple-antenna key generator (make) using off-the-shelf 802.11n multiple-antenna devices. we also conduct extensive experiments and analysis in real indoor and outdoor mobile environments. using the shared randomness extracted from measured received signal strength indicator (rssi) to generate keys, our experimental results show that using laptops with three antennas, make can increase the bit generation rate by more than four times over single-antenna systems. our experiments validate the effectiveness of using multi-level quantization when there is enough mutual information in the channel. our results also show the trade-off between bit generation rate and bit agreement ratio when using multi-level quantization. we further find that even if an eavesdropper has multiple antennas, she cannot gain much more information about the legitimate channel.
queuing analysis in multichannel cognitive spectrum access: a large deviation approach. the queueing performance of a (secondary) cognitive user is investigated for a hierarchical network where there are n independent and identical primary users. each primary user employs a slotted transmission protocol, and its channel usage forms a two-state (busy,idle) discrete-time markov chain. the cognitive user employs the optimal policy to select which channel to sense (and use if found idle) at each slot. in the framework of effective bandwidths, the stationary queue tail distribution of the cognitive user is estimated using a large deviation approach for which closed-form expressions are obtained when n = 2. upper and lower bounds are obtained for the general n primary user network. for positively correlated primary transmissions, the bounds are shown to be asymptotically tight. monte carlo simulations using importance sampling techniques are used to validate the obtained large deviation estimates.
high quality sensor placement for shm systems: refocusing on application demands. there are heavy studies recently on applying wireless sensor networks for structural health monitoring. these works usually focus on the computer science aspect, and the considerations include energy consumption, network connectivity, etc. it is commonly believed that for the current resource limited wireless sensors, system design could be more efficient if the application requirements are incorporated. nevertheless, we often find that, rather than integration, assumptions have to be made due to lack of knowledge of civil engineering; for example, to evaluate routing algorithms, the sensor placement is assumed to be random or on grids/trees. these may not be practically meaningful to the respective application demands, and make the great efforts by the computer science community on developing efficient methods from the sensor network aspect less useful. in this paper, we study the very first problem of the shm systems: the sensor placement and focus on the civil requirements. we first study the current general framework of structure health monitoring. we redevelop the framework that includes a new sensor placement module. this module implements the most widely accepted sensor placement scheme from civil engineering but focusing on its usefulness for computer science. it provides such interfaces that can rank the placement quality of the candidate locations in a step by step manner. we then optimize system performance by considering network connectivity and data routing issues; with the objective on energy efficiency. we evaluate our scheme using the data from the structural health monitoring system on the ting kau bridge, hong kong. we show that a uniform and a state-of-the-art placement are not very meaningful in placement quality. our scheme achieves almost the same sensor placement quality with that of the civil engineering with five-fold improvement in system lifetime. we conduct an experiment on the in-built guangzhou new tv tower, china; and the results validate the effectiveness of our scheme.
delay performance of scheduling with data aggregation in wireless sensor networks. in-network aggregation has become a promising technique for improving the energy efficiency of wireless sensor networks. aggregating data at various nodes in the network results in a reduction in the amount of bits transmitted over the network, and hence, saves energy. in this paper, we focus on another important aspect of aggregation, i.e., delay performance. in conjunction with link scheduling, in-network aggregation can reduce the delay by lessening the demands for wireless resources and thus expediting data transmissions. we formulate the problem that minimizes the sum delay of sensed data, and analyze the performance of optimal scheduling with innetwork aggregation in tree networks under the node-exclusive interference model. we provide a system wide lower bound on the delay and use it as a benchmark for evaluating different scheduling policies. we numerically evaluate the performance of myopic and non-myopic scheduling policies, where myopic one considers only the current system state for a scheduling decision while non-myopic one simulates future system states. we show that the one-step non-myopic policies can substantially improve the delay performance. in particular, the proposed nonmyopic greedy scheduling achieves a good tradeoff between performance and implementability.
reliable broadcasting in random networks and the effect of density. broadcasting algorithms are of fundamental importance for distributed systems engineering. in this paper we revisit the classical and well-studied push protocol for message broadcasting and we investigate a faulty version of it. assuming that initially only one node has some piece of information, at each stage every one of the informed nodes chooses randomly and independently one of its neighbors and passes the message to it with some probability q; that is, it fails to do so with probability 1 - q. the performance of the push protocol on a fully connected network, where each node is joined by a link to every other node, with q = 1 is very well understood. in particular, frieze and grimmett proved that with probability 1 - o(1) the push protocol completes the broadcasting of the message within (1 ± ɛ)(log2 n + ln n) stages, where n is the number of nodes in the network. however, there are no tight bounds for the broadcast time on networks that are significantly sparser than the complete graph. in this work we consider random networks on n nodes, where every edge is present with probability p, independently of every other edge. we show that if p ≥ α(n) ln n/n, where α(n) is any function that tends to infinity as n grows, then the push protocol with faulty transmissions broadcasts the message within (1 ± ɛ) (log1+q n + 1/q ln n) stages with probability 1 - o(1). in other words, in almost every network of density d such that d ≥ α(n) ln n, the push protocol broadcasts a message as fast as in a fully connected network and the speed is only affected by the success probability q. this is quite surprising in the sense that the time needed remains essentially unaffected by the fact that most of the links are missing. our results are accompanied by experimental evaluation.
malicious shellcode detection with virtual memory snapshots. malicious shellcodes are segments of binary code disguised as normal input data. such shellcodes can be injected into a target process's virtual memory. they overwrite the process's return addresses and hijack control flow. detecting and filtering out such shellcodes is vital to prevent damage. in this paper, we propose a new malicious shellcode detection methodology in which we take snapshots of the process's virtual memory before input data are consumed, and feed the snapshots to a malicious shellcode detector. these snapshots are used to instantiate a runtime environment that emulates the target process's input data consumption to monitor shellcodes' behaviors. the snapshots can also be used to examine the system calls that shellcodes invoke, these system call parameters, and the process's execution flow. we implement a prototype system in debian linux with kernel version 2.6.26. our extensive experiments with real traces and thousands of malicious shellcodes illustrate our system's performance with low overhead and few false negatives and few false positives.
throughput and delay analysis on uncoded and coded wireless broadcast with hard deadline constraints. multimedia streaming applications have stringent qos requirements. typically each packet is associated with a packet delivery deadline. this work models and considers realtime streaming broadcast for stored-video over the downlink of a single cell. the broadcast capacity of the system subject to deadline constraints are derived for both uncoded and coded wireless broadcast schemes. even under the deadline requirements, it is shown in this work that network coding is asymptotically throughput-optimal and can strictly outperform the best noncoding policy by analytically quantifying the optimal capacity when the file size is sufficiently large. a simple network coding policy is also proposed that achieves the asymptotic capacity while maintaining finite transmission delay (queueing + decoding delay). a new temporal-queue-length-based lyapunov function is used to prove the optimality of this policy. simulation shows that the simple coding policy outperforms the best non-coding policies even for broadcasting files of small sizes.
characterizing the spread of correlated failures in large wireless networks. correlated failures pose a great challenge for the normal functioning of large wireless networks, because an initial local failure may trigger a global sequence of related failures. given their potentially devastating impact, we characterize the spread of correlated failures in this paper, which lays the foundation for evaluating and improving the failure resilience of existing wireless networks. we model the failure contagiousness as two generic functions: the failure impact radius distribution function fr(x) and the failure connection function g(x). by using the percolation theory, we determine the respective characteristic regimes of fr(x) and g(x) in which correlated failures will and will not percolate in the network. as our model represents various failure scenarios, the results are generally applicable in understanding the spread of a wide range of correlated failures.
information quality aware routing in event-driven sensor networks. upon the occurrence of a phenomenon of interest in a wireless sensor network, multiple sensors may be activated, leading to data implosion and redundancy. data aggregation and/or fusion techniques exploit spatio-temporal correlation among sensory data to reduce traffic load and mitigate congestion. however, this is often at the expense of loss in information quality (iq) of data that is collected at the fusion center. in this work, we address the problem of finding the leastcost routing tree that satisfies a given iq constraint. we note that the optimal least-cost routing solution is a variation of the classical np-hard steiner tree problem in graphs, which incurs high overheads as it requires knowledge of the entire network topology and individual iq contributions of each activated sensor node. we tackle these issues by proposing: (i) a topology-aware histogram-based aggregation structure that encapsulates the cost of including the iq contribution of each activated node in a compact and efficient way; and (ii) a greedy heuristic to approximate and prune a least-cost aggregation routing path. we show that the performance of our iq-aware routing protocol is: (i) bounded by a distance-based aggregation tree that collects data from all the activated nodes; and (ii) comparable to another iq-aware routing protocol that uses an exhaustive brute-force search to approximate and prune the least-cost aggregation tree.
magnetworks: how mobility impacts the design of mobile ad hoc networks. in this paper we study the optimal placement and optimal number of active relay nodes through the traffic density in mobile sensor ad hoc networks. we consider a setting in which a set of mobile sensor sources is creating data and a set of mobile sensor destinations is receiving that data through multihop wireless paths. we make the assumption that the network is massively dense, i.e., there are so many sources, destinations, and relay nodes, that it is best to describe the network in terms of macroscopic parameters rather than in terms of microscopic parameters. a simple one-dimensional scenario is used to introduce the problem. we solve the two-dimensional scenario where the mobility of the nodes is deterministic and when it follows the brownian mobility model.
a self-organized mechanism for thwarting malicious access in ad hoc networks. this paper introduces a self-organized mechanism to control user access in ad hoc networks without requiring any infrastructure or a central administration entity. the proposed mechanism authenticates and monitors nodes with the so-called controller sets, which are resistant to the dynamic network membership. the analysis shows that the proposed scheme is robust even to collusion attacks and provides availability up to 90% better than proposals based on threshold cryptography. the performance improvement arises mostly from the controller sets autonomy to recover after network partitions.
the k-constrained bipartite matching problem: approximation algorithms and applications to wireless networks. in communication networks, resource assignment problems appear in several different settings. these problems are often modeled by a maximum weight matching problem in bipartite graphs and efficient matching algorithms are well known. in several applications, the corresponding matching problem has to be solved many times in a row as the underlying system operates in a time-slotted fashion and the edge weights change over time. however, changing the assignments can come with a certain cost for reconfiguration that depends on the number of changed edges between subsequent assignments. in order to control the cost of reconfiguration, we propose the k-constrained bipartite matching problem for bipartite graphs, which seeks an optimal matching that realizes at most k changes from a previous matching. we provide fast approximation algorithms with provable guarantees for this problem. furthermore, to cope with the sequential nature of assignment problems, we introduce an online variant of the k- constrained matching problem and derive online algorithms that are based on our approximation algorithms for the k-constrained bipartite matching problem. finally, we establish the applicability of our model and our algorithms in the context of ofdma wireless networks finding a significant performance improvement for the proposed algorithms.