waashk/dblp huggingface dataset:
analyzing the performance of greedy maximal scheduling via local pooling and graph theory. efficient operation of wireless networks and switches requires using simple scheduling algorithms. in general, simple greedy algorithms (known as greedy maximal scheduling - gms) are guaranteed to achieve only a fraction of the maximum possible throughput. it was recently shown that in networks in which the local pooling conditions are satisfied, gms achieves 100% throughput. moreover, in networks in which the σ-local pooling conditions hold, gms achieves σ% throughput. in this extended abstract, we characterize all the network graphs in which local pooling holds under primary interference constraints. we then show that in all bipartite graphs (i.e., input-queued switches) of size up to 7×n, gms is guaranteed to achieve 66% throughput, thereby improving upon the previously known 50% lower bound. finally, we study the performance of gms in interference graphs and show that in certain specific topologies its performance could be very bad. overall, we demonstrate that using graph theoretical techniques can significantly contribute to our understanding of greedy scheduling algorithms. the proofs of the results have been omitted for brevity and can be found in [1].
isp-enabled behavioral ad targeting without deep packet inspection. online advertising is a rapidly growing industry currently dominated by the search engine 'giant' google. in an attempt to tap into this huge market, internet service providers (isps) started deploying deep packet inspection techniques to track and collect user browsing behavior. however, such techniques violate wiretap laws that explicitly prevent intercepting the contents of communication without gaining consent from consumers. in this paper, we show that it is possible for isps to extract user browsing patterns without inspecting contents of communication. our contributions are threefold. first, we develop a methodology and implement a system that is capable of extracting web browsing features from stored non-content based records of online communication, which could be legally shared. when such browsing features are correlated with information collected by independently crawling the web, it becomes possible to recover the actual web pages accessed by clients. second, we systematically evaluate our system on the internet and demonstrate that it can successfully recover user browsing patterns with high accuracy. finally, our findings call for a comprehensive legislative reform that would not only enable fair competition in the online advertising business, but more importantly, protect the consumer rights in a more effective way.
online scheduling of targeted advertisements for iptv. behavioral targeting of content to users is a huge and lucrative business, valued as a $20 billion industry that is growing rapidly. so far dominant players in this field like google and yahoo examine the user requests coming to their servers and place appropriate ads based on the user's search keywords. triple play service providers have access to all the traffic generated by the users and can generate more comprehensive profiles of users based on their tv, broadband and mobile usage. using such multi-source profile information they can generate new revenue streams by smart targeting of ads to their users over multiple screens (computer, tv and mobile handset). this paper proposes methods to place targeted ads to a tv based on user's interests. it proposes an ad auction model that can leverage multi-source profile and can handle dynamic profile-based targeting like google's adwords vis-a-vis static demography-based targeting of legacy tv. we then propose a 0.502-competitive revenue maximizing scheduling algorithm that chooses a set of ads in each time slot and assigns users to one of these selected ads.
dplc: dynamic packet length control in wireless sensor networks. previous packet length optimizations for sensor networks often employ a fixed optimal length scheme, while in this study we present dplc, a dynamic packet length control scheme. to make dplc more efficient in terms of channel utilization, we incorporate a lightweight and accurate link estimation method that captures both physical channel conditions and interferences. we further provide two easy-touse services, i.e., small message aggregation and large message fragmentation, to facilitate upper-layer application programming. the implementation of dplc based on tinyos 2.1 is lightweight, with respect to computation, memory, and header overhead. our experiments using a real indoor testbed running ctp show that dplc results in a 13% reduction in transmission overhead and a 41.8% reduction in energy consumption compared with the original protocol, and a 21% reduction in transmission overhead and a 15.1% reduction in energy consumption compared with simple aggregation schemes.
minimum power energy spanners in wireless ad hoc networks. a power assignment is an assignment of transmission power to each of the nodes of a wireless network, so that the induced communication graph has some desired properties. the cost of a power assignment is the sum of the powers. the energy of a transmission path from node u to node v is the sum of the squares of the distances between adjacent nodes along the path. for a constant t > 1, an energy t-spanner is a graph g′, such that for any two nodes u and v, there exists a path from u to v in g′, whose energy is at most t times the energy of a minimum-energy path from u to v in the complete euclidean graph. in this paper, we study the problem of finding a power assignment, such that (i) its induced communication graph is a 'good' energy spanner, and (ii) its cost is 'low'. we show that for any constant t > 1, one can find a power assignment, such that its induced communication graph is an energy t-spanner, and its cost is bounded by some constant times the cost of an optimal power assignment (where the sole requirement is strong connectivity of the induced communication graph). this is a very significant improvement over the best current result due to shpungin and segal [1], presented in last year's conference.
p-coding: secure network coding against eavesdropping attacks. though providing an intrinsic secrecy, network coding is still vulnerable to eavesdropping attacks, by which an adversary may compromise the confidentiality of message content. existing studies mainly deal with eavesdroppers that can intercept a limited number of packets. however, real scenarios often consist of more capable adversaries, e.g., global eavesdroppers, which can defeat these techniques. in this paper, we propose p-coding, a novel security scheme against eavesdropping attacks in network coding. with the lightweight permutation encryption performed on each message and its coding vector, p-coding can efficiently thwart global eavesdroppers in a transparent way. moreover, p-coding is also featured in scalability and robustness, which enable it to be integrated into practical network coded systems. security analysis and simulation results demonstrate the efficacy and efficiency of the p-coding scheme.
reliability in layered networks with random link failures. we consider network reliability in layered networks where the lower layer experiences random link failures. in layered networks, each failure at the lower layer may lead to multiple failures at the upper layer. we generalize the classical polynomial expression for network reliability to the multi-layer setting. using random sampling techniques, we develop polynomial time approximation algorithms for the failure polynomial. our approach gives an approximate expression for reliability as a function of the link failure probability, eliminating the need to resample for different values of the failure probability. furthermore, it gives insight on how the routings of the logical topology on the physical topology impact network reliability. we show that maximizing the min cut of the (layered) network maximizes reliability in the low failure probability regime. based on this observation, we develop algorithms for routing the logical topology to maximize reliability.
castor: scalable secure routing for ad hoc networks. wireless ad hoc networks are inherently vulnerable, as any node can disrupt the communication of potentially any other node in the network. many solutions to this problem have been proposed. in this paper, we take a fresh and comprehensive approach that addresses simultaneously three aspects: security, scalability and adaptability to changing network conditions. our communication protocol, castor, occupies a unique point in the design space: it does not use any control messages except simple packet acknowledgements, and each node makes routing decisions locally and independently without exchanging any routing state with other nodes. its novel design makes castor resilient to a wide range of attacks and allows the protocol to scale to large network sizes and to remain efficient under high mobility. we compare castor against four representative protocols from the literature. our protocol achieves up to two times higher packet delivery rates, particularly in large and highly volatile networks, while incurring no or only limited additional overhead. at the same time, castor is able to survive more severe attacks and recovers from them faster.
retiring replicants: congestion control for intermittently-connected networks. the widespread availability of mobile wireless devices offers growing opportunities for the formation of temporary networks with only intermittent connectivity. these intermittently-connected networks (icns) typically lack stable end-to-end paths. in order to improve the delivery rates of the networks, new store-carry-and-forward protocols have been proposed which often use message replication as a forwarding mechanism. message replication is effective at improving delivery, but given the limited resources of icn nodes, such as buffer space, bandwidth and energy, as well as the highly dynamic nature of these networks, replication can easily overwhelm node resources. in this work we propose a novel node-based replication management algorithm which addresses buffer congestion by dynamically limiting the replication a node performs during each encounter. the insight for our algorithm comes from a stochastic model of message delivery in icns with constrained buffer space. we show through simulation that our algorithm is effective, nearly tripling delivery rates in some scenarios, and imposes no or little overhead.
efficient active probing for fault diagnosis in large scale and noisy networks. active probing is an effective tool for monitoring networks. by measuring probing responses, we can perform fault diagnosis actively and efficiently without instrumentation on managed entities. in order to reduce the traffic generated by probing messages and the measurement infrastructure costs, an optimal set of probes is desirable. however, the computational complexity for obtaining such an optimal set is very high. existing works assume single-fault scenarios, apply only to small size networks, or use simplistic methods that are vulnerable to noises. in this paper, by exploiting the conditionally independent property in bayesian networks, we prove a theorem on the information provided by a set of probes. based on this theorem and structure property of bayesian networks, we propose two approaches which can effectively reduce the computation time. a highly efficient adaptive probing algorithm is then presented. compared with previous techniques, experiments have shown that our approach is more efficient in selecting an optimal set of probes without degrading diagnosis quality in large scale and noisy networks.
joint routing and scheduling in multi-hop wireless networks with directional antennas. long-distance multi-hop wireless networks have been used in recent years to provide connectivity to rural areas. the salient features of such networks include tdma channel access, nodes with multiple radios, and point-to-point long-distance wireless links established using high-gain directional antennas mounted on high towers. it has been demonstrated previously that in such network architectures, nodes can transmit concurrently on multiple radios, as well as receive concurrently on multiple radios. however, concurrent transmission on one radio, and reception on another radio causes interference. under this scheduling constraint, given a set of source-destination demand rates, we consider the problem of satisfying the maximum fraction of each demand (also called the maximum concurrent flow problem). we give a novel joint routing and scheduling scheme for this problem, based on linear programming and graph coloring. we analyze our algorithm theoretically and prove that at least 50% of a satisfiable set of demands is satisfied by our algorithm for most practical networks (with maximum node degree at most 5).
measuring availability in the domain name system. the domain name system (dns) is critical to internet functionality. the availability of a domain name refers to its ability to be resolved correctly. we develop a model for server dependencies that is used as a basis for measuring availability. we introduce the minimum number of servers queried (msq) and redundancy as availability metrics and show how common dns misconfigurations impact the availability of domain names. we apply the availability model to domain names from production dns and observe that 6.7% of names exhibit sub-optimal msq, and 14% experience false redundancy. the msq and redundancy values can be optimized by proper maintenance of delegation records for zones.
collaborative data compression using clustered source coding for wireless multimedia sensor networks. data redundancy caused by correlation has motivated the application of collaborative multimedia in-network processing for data filtering and compression in wireless multimedia sensor networks (wmsns). this paper proposes an information theoretic data compression framework with an objective to maximize the overall compression of the visual information gathered in a wmsn. to achieve this, an entropy-based divergence measure (edm) scheme is proposed to predict the compression efficiency of performing joint coding on the images collected by spatially correlated cameras. the novelty of edm relies on its independence of the specific image types and coding algorithms, thereby providing a generic mechanism for prior evaluation of compression under different coding solutions. utilizing the predicted results from edm, a distributed multi-cluster coding protocol (dmcp) is proposed to construct a compression-oriented coding hierarchy. the dmcp aims to partition the entire network into a set of coding clusters such that the global coding gain is maximized. moreover, in order to enhance decoding reliability at data sink, the dmcp also guarantees that each sensor camera is covered by at least two different coding clusters. experiments on h.264 standards show that the proposed edm can effectively predict the joint coding efficiency from multiple sources. further simulations demonstrate that the proposed compression framework can reduce 10% - 23% total coding rate compared with the individual coding scheme, i.e., each camera sensor compresses its own image independently.
surfing the blogosphere: optimal personalized strategies for searching the web. we propose a distributed mechanism for finding websurfing strategies that is inspired by the stumbleupon recommendation engine. each day, a websurfer visits a sequence of websites recommended by our mechanism, and selects one that matches her daily interests. we formally show that even with this minimal feedback from the surfer--the selected website-- our mechanism finds a websurfing strategy that matches the surfer's interests optimally. the surfer does not need to know--or declare--what her daily interests are before she is presented with content she likes. moreover, our mechanism is content-agnostic: it is oblivious to the nature of the content the surfer selects. in addition, we study how the performance of this mechanism can be improved if surfers with similar interests share their feedback. such surfers can be found indirectly, e.g., if they are all registered as friends in a social networking application. our analysis characterizes the improvement in the mechanism's accuracy, based on the size of the group and the degree of similarity between the surfers' interests. in particular, we show that sharing feedback can significantly accelerate the convergence of our mechanism. our results are derived analytically using stochastic approximation techniques, but are also validated through a numerical study.
prisense: privacy-preserving data aggregation in people-centric urban sensing systems. people-centric urban sensing is a new paradigm gaining popularity. a main obstacle to its widespread deployment and adoption are the privacy concerns of participating individuals. to tackle this open challenge, this paper presents the design and evaluation of prisense, a novel solution to privacypreserving data aggregation in people-centric urban sensing systems. prisense is based on the concept of data slicing and mixing and can support a wide range of statistical additive and non-additive aggregation functions such as sum, average, variance, count, max/min, median, histogram, and percentile with accurate aggregation results. prisense can support strong user privacy against a tunable threshold number of colluding users and aggregation servers. the efficacy and efficiency of prisense are confirmed by thorough analytical and simulation results.
know thy neighbor: towards optimal mapping of contacts to social graphs for dtn routing. delay tolerant networks (dtn) are networks of self-organizing wireless nodes, where end-to-end connectivity is intermittent. in these networks, forwarding decisions are generally made using locally collected knowledge about node behavior (e.g., past contacts between nodes) to predict future contact opportunities. the use of complex network analysis has been recently suggested to perform this prediction task and improve the performance of dtn routing. contacts seen in the past are aggregated to a social graph, and a variety of metrics (e.g., centrality and similarity) or algorithms (e.g., community detection) have been proposed to assess the utility of a node to deliver a content or bring it closer to the destination. in this paper, we argue that it is not so much the choice or sophistication of social metrics and algorithms that bears the most weight on performance, but rather the mapping from the mobility process generating contacts to the aggregated social graph. we first study two well-known dtn routing algorithms - simbet and bubblerap - that rely on such complex network analysis, and show that their performance heavily depends on how the mapping (contact aggregation) is performed. what is more, for a range of synthetic mobility models and real traces, we show that improved performances (up to a factor of 4 in terms of delivery ratio) are consistently achieved for a relatively narrow range of aggregation levels only, where the aggregated graph most closely reflects the underlying mobility structure. to this end, we propose an online algorithm that uses concepts from unsupervised learning and spectral graph theory to infer this "correct" graph structure; this algorithm allows each node to locally identify and adjust to the optimal operating point, and achieves good performance in all scenarios considered.
impact of correlated mobility on delay-throughput performance in mobile ad-hoc networks. 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 pernode 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.
solarcode: utilizing erasure codes for reliable data delivery in solar-powered wireless sensor networks. solar-powered sensor nodes have incentive to spend extra energy, especially when the battery is fully charged, because this energy surplus would be wasted otherwise. in this paper, we consider the problem of utilizing such energy surplus to adaptively adjust the redundancy level of erasure codes used in communication, so that the delivery reliability is improved while the network lifetime is still conserved. we formulate the problem as maximizing the end-to-end packet delivery probability under energy constraints. this formulated problem is hard to solve because of the combinatorics involved and the special curvature of its objective function. by exploiting its inherent properties, we propose an effective solution called solarcode, which has a constant approximation ratio. we evaluate solarcode in the context of our solar-powered sensor network testbed. experiments show that solarcode is successful in utilizing energy surplus and leads to higher data delivery reliability.
performing joint learning for passive intrusion detection in pervasive wireless environments. recent years have witnessed increasing interests in passive intrusion detection for wireless environments, e.g., asset protection in industrial facilities and emergency rescue of trapped people. most previous studies have focused primarily on exploiting a single intrusion indicator, such as moving variance, for capturing an intrusion pattern at a time. however, in real-world, there are many intrusion patterns which may be only detectable by combining different intrusion indicators and performing detection jointly. to this end, we propose a joint intrusion learning approach, which has the ability in combining the detection power of several complementary intrusion indicators and detects different intrusion patterns at the same time. we developed the greek algorithm, which utilizes grid-based clustering over kneighborhood to effectively diagnose the presence of intrusions. further, we show that the performance of intrusion detection can be enhanced by utilizing the collaborative detecting efforts among multiple transmitter-receiver pairs. to validate the effectiveness of the joint intrusion learning method, we conducted experiments in a real-office environment using an ieee 802.15.4 (zigbee) network. our experimental results provide strong evidence of the effectiveness of our joint learning approach in performing passive intrusion detection with a minimized false positive rate.
pressure routing for underwater sensor networks. a sea swarm (sensor equipped aquatic swarm) is a sensor cloud that drifts with water currents and enables 4d (space and time) monitoring of local underwater events such as contaminants, marine life and intruders. the swarm is escorted at the surface by drifting sonobuoys that collect the data from underwater sensors via acoustic modems and report it in realtime via radio to a monitoring center. the goal of this study is to design an efficient anycast routing algorithm for reliable underwater sensor event reporting to any one of the surface sonobuoys. major challenges are the ocean current and the limited resources (bandwidth and energy). in this paper, we address these challenges and propose hydrocast, a hydraulic pressure based anycast routing protocol that exploits the measured pressure levels to route data to surface buoys. the paper makes the following contributions: a novel opportunistic routing mechanism to select the subset of forwarders that maximizes greedy progress yet limiting co-channel interference; and an efficient underwater dead end recovery method that outperforms recently proposed approaches. the proposed routing protocols are validated via extensive simulations.