waashk/dblp huggingface dataset:
optimizing throughput and latency under given power budget for network packet processing. current state-of-the-art task scheduling algorithms for network packet processing schedule the program into a parallel-pipeline topology on network processors to maximize the throughput. however, there has been no existing work targeting power budget for packet processing on off-the-shelf multicore architectures. as energy consumption, reliability and cooling cost for packet processing systems become increasingly important, it is necessary to integrate power-awareness into a scheduler to meet the power budget. in this paper, we propose a novel scheduling algorithm to optimize both throughput and latency given a power budget for network packet processing on multicore architectures. this algorithm addresses power-aware parallel-pipeline scheduling problem by applying per-core dvfs to optimally adjust frequency on each core. we implement our algorithm on an amd machine with two quad-core opteron 2350 processors and compare the results with existing algorithms given the same power budget. for six real packet processing applications, our algorithm improves throughput and reduces latency by an average of 64.6% and 25.2%, respectively.
towards efficient designs for in-network computing with noisy wireless channels. in this paper we study distributed function computation in a noisy multi-hop wireless network, in which n nodes are uniformly and independently distributed in a unit square. we adopt the adversarial noise model, for which independent binary symmetric channels are assumed for any point-to-point transmissions, with (not necessarily identical) crossover probabilities bounded above by some constant ε. each node holds an m-bit integer per instance and the computation is started after each node collects n readings. the goal is to compute a global function with a certain fault tolerance, in this distributed setting; we mainly deal with divisible functions, which essentially covers the main body of interest for wireless applications. we focus on protocol designs that are efficient in terms of communication complexity. we first devise a general protocol for evaluating any divisible functions, addressing both one-shot (n = o(1)) and block computation, and both constant and large m scenarios; its bottleneck in different scenarios is also analyzed. based on this analysis, we then endeavor to improve the design for two special cases: identity function, and some restricted type-threshold functions, both focusing on the constant m and n scenario.
multi-round sensor deployment for guaranteed barrier coverage. deploying wireless sensor networks to provide guaranteed barrier coverage is critical for many sensor networks applications such as intrusion detection and border surveillance. to reduce the number of sensors needed to provide guaranteed barrier coverage, we propose multi-round sensor deployment which splits sensor deployment into multiple rounds and can better deal with placement errors that often accompany sensor deployment. we conduct a comprehensive analytical study on multi-round sensor deployment and identify the tradeoff between the number of sensors deployed in each round of multiround sensor deployment and the barrier coverage performance. both numerical and simulation studies show that, by simply splitting sensor deployment into two rounds, guaranteed barrier coverage can be achieved with significantly less sensors comparing to singleround sensor deployment. moreover, we propose two practical solutions for multi-round sensor deployment when the distribution of a sensor's residence point is not fully known. the effectiveness of the proposed multi-round sensor deployment strategies is demonstrated by numerical and simulation results.
high performance dictionary-based string matching for deep packet inspection. dictionary-based string matching (dbsm) is used in network deep packet inspection (dpi) applications virus scanning [1] and network intrusion detection [2]. we propose the pipelined affix search with tail acceleration (pasta) architecture for solving dbsm with guaranteed worst-case performance. our pasta architecture is composed of a pipelined affix search relay (pasr) followed by a tail acceleration finite automaton (tafa). pasr consists of one or more pipelined binary search tree (pbst) modules arranged in a linear array. tafa is constructed with the aho-corasick goto and failure functions [3] in a compact multi-path and multi-stride tree structure. both pasr and tafa achieve good memory efficiency of 1.2 and 2 b/ch (bytes per character) respectively and are pipelined to achieve a high clock rate of 200 mhz on fpgas. because pasta does not depend on the effectiveness of any hash function or the property of the input stream, its performance is guaranteed in the worst case. our prototype implementation of pasta on an fpga with 10 mb on-chip block ram achieves 3.2 gbps matching throughput against a dictionary of over 700k characters. this level of performance surpasses the requirements of next-generation security gateways for deep packet inspection.
cooperative boundary detection for spectrum sensing using dedicated wireless sensor networks. spectrum sensing is one of the key enabling technologies in cognitive radio networks (crns). in crns, secondary users (sus) are allowed to exploit the spectrum opportunities by sensing and accessing the spectrum, which exhibit many critical limitations in practical environments. in this paper, we propose a new sensing service model that uses dedicated wireless spectrum sensor networks (wssn) for spectrum sensing. the major challenge in wssn is the design of data fusion, for which the traditional fusion scheme will produce a large amount of errors. we formulate the problem as a boundary detection problem with notable unknown erroneous inputs. to solve the problem, we propose a novel cooperative boundary detection scheme that intelligently incorporates the cooperative spectrum sensing concept and the recent advances in support vector machine (svm). cooperative boundary detection consists of two major components, a declaration calibration algorithm and a boundary derivation algorithm. we prove that cooperative spectrum sensing can asymptotically approach the optimal solution. a prototype system as well as simulation experiments show that compared with the traditional approaches, cooperative boundary detection can reduce the errors by up to 95% with an average reduction about 85%.
maximizing the contact opportunity for vehicular internet access. with increasing popularity of media enabled handhelds, the need for high data-rate services for mobile users is evident. large-scale wireless lans (wlans) can provide such a service, but they are expensive to deploy and maintain. open wlan access-points (aps), on the other hand, need no new deployments, but can offer only opportunistic services with no guarantees on short term throughput. in contrast, a carefully planned sparse deployment of roadside wifi provides an economically scalable infrastructure with quality of service assurance to mobile users. in this paper, we propose to study deployment techniques for providing roadside wifi services. in particular, we present a new metric, called contact opportunity, as a characterization of a roadside wifi network. informally, the contact opportunity for a given deployment measures the fraction of distance or time that a mobile user is in contact with some ap when moving through a certain path. such a metric is closely related to the quality of data service that a mobile user might experience while driving through the system. we then present an efficient deployment method that maximizes the worst case contact opportunity under a budget constraint. we further show how to extend this concept and the deployment techniques to a more intuitive metric - the average throughput - by taking various dynamic elements into account. simulations over a real road network and experimental results show that our approach achieves more than 200% higher minimum contact opportunity, 30%-100% higher average contact opportunity and a significantly improved distribution of average throughput compared with two commonly used algorithms.
assessing the vanet's local information storage capability under different traffic mobility. wireless networking enabled vehicles can form vehicular ad hoc mesh networks (vmeshs). using cooperative communication among vmeshs, a local transient information could be "retained" within a given geographic region for a certain period of time, without any infrastructure help. in this paper, we study this "storage capability" of vmeshs. we analyze the scenarios of highway traffic (both one-way and two-way highway free flow traffic) and vehicular traffic in a city environment. for highway traffic, we study different properties of the "vmesh storage", using a simulation tool that accurately models the freeway vehicular mobility. for city traffic, we first perform simulations based on real traffic trace of san francisco yellow cabs. then we compare the results with the scenario where a general random way point (rwp) mobility model is used. our results show that transmission range has high impact on the storage lifetime for one-way highway traffic, and the size of the region in which we want the information stored has high impact for two-way highway traffic. for city-wide traffic, the storage's lifetime generated using san francisco yellow cab trace is shorter than that obtained using the rwp mobility model. this is due to the regular movement of the cabs as compared to the random vehicle movement in the rwp mobility model.
intrusion-resilience in mobile unattended wsns. wireless sensor networks (wsns) are susceptible to a wide range of attacks due to their distributed nature, limited sensor resources and lack of tamper-resistance. once a sensor is corrupted, the adversary learns all secrets and (even if the sensor is later released) it is very difficult for the sensor to regain security, i.e., to obtain intrusion-resilience. existing solutions rely on the presence of an on-line trusted third party, such as a sink, or on the availability of secure hardware on sensors. neither assumption is realistic in large-scale unattended wsns (uwsns), characterized by long periods of disconnected operation and periodic visits by the sink. in such settings, a mobile adversary can gradually corrupt the entire network during the intervals between sink visits. as shown in some recent work, intrusionresilience in uwsns can be attained (to a degree) via cooperative self-healing techniques. in this paper, we focus on intrusion-resilience in mobile unattended wireless sensor networks (µuwsns) where sensors move according to some mobility model. we argue that sensor mobility motivates a specific type of adversary and defending against it requires new security techniques. concretely, we propose a cooperative protocol that - by leveraging sensor mobility - allows compromised sensors to recover secure state after compromise. this is obtained with very low overhead and in a fully distributed fashion. we provide a thorough analysis of the proposed protocol and support it by extensive simulation results.
optimal control of constrained cognitive radio networks with dynamic population size. in this paper, we consider the problem of optimal control for throughput utility maximization in cognitive radio networks with dynamic user arrivals and departures. the cognitive radio network considered in this paper consists of a number of heterogeneous sub-networks. these sub-networks may be power-constrained and are required to operate in such a way that the average total interference received on primary channels are kept below given thresholds. we develop a control policy that performs joint admission control and resource scheduling. through lyapunov optimization techniques, we show that the proposed policy achieves a utility performance within o(δ) of optimality for any positive δ. we further show that this arbitrarily closeness to optimality comes at the price of having a delay that is o(1/δ) in admitting users. we also propose constant factor approximations of the policy for distributed implementation.
non-preemptive buffer management for latency sensitive packets. the delivery of latency sensitive packets is a crucial issue in real time applications of communication networks. such packets often have a firm deadline and a packet becomes useless if it arrives after its deadline. the deadline, however, applies only to the packet's journey through the entire network; individual routers along the packet's route face a more flexible deadline. we consider policies for admitting latency sensitive packets at a router. each packet is tagged with a value and a packet waiting at a router loses value over time as its probability of arriving at its destination decreases. the router is modeled as a nonpreemptive queue, and its objective is to maximize the total value of the forwarded packets. when a router receives a packet, it must either accept it (and possibly delay future packets), or reject it immediately. the best policy depends on the set of values that a packet can take. we consider three natural settings: unrestricted model, real-valued model, where any value above 1 is allowed, and an integral-valued model. we obtain the following results. for the unrestricted model, we prove that there is no constant competitive ratio algorithm. the real valued model has a randomized 4-competitive algorithm and a matching lower bound. we also give for the last model a deterministic lower bound of φ3 ≈ 4.236, almost matching the previously known 4.24-competitive algorithm. for the integralvalued model, we show a deterministic 4-competitive algorithm, and prove that this is tight even for randomized algorithms.
mimo-aware routing in wireless mesh networks. multiple-input and multiple-output (mimo) technique is considered as one of the most promising emerging wireless technologies that can significantly improve transmission capacity and reliability in wireless mesh networks. while mimo has been widely studied for single link transmission scenarios in physical layer as well as from mac perspective, its impact on network layer, especially its interaction with routing has not drawn enough research attention. in this paper, we investigate the problem of routing in mimo-based wireless mesh networks. we mathematically formulate the mimo-enabled multi-source multidestination multi-hop routing problem into a multicommodity flow problem by identifying the specific opportunities and constraints brought by mimo transmissions, in order to provide the fundamental basis for mimo-aware routing design. we then use this formulation to develop a polynomial time approximation solution that maximizes the scaling factor for the concurrent flows in the network. moreover, we also consider a more practical case where controllers are distributed, and propose a distributed algorithm to minimize the congestion in the network links based on steepest descent framework, which is proved to provide a fixed approximation ratio. the performance of the algorithms is evaluated through simulations and demonstrated to outperform the counterpart strategies without considering mimo features.
distributed algorithms for approximating wireless network capacity. in this paper we consider the problem of maximizing wireless network capacity (a.k.a. one-shot scheduling) in both the protocol and physical models. we give the first distributed algorithms with provable guarantees in the physical model, and show how they can be generalized to more complicated metrics and settings in which the physical assumptions are slightly violated. we also give the first algorithms in the protocol model that do not assume transmitters can coordinate with their neighbors in the interference graph, so every transmitter chooses whether to broadcast based purely on local events. our techniques draw heavily from algorithmic game theory and machine learning theory, even though our goal is a distributed algorithm. indeed, our main results allow every transmitter to run any algorithm it wants, so long as its algorithm has a learning-theoretic property known as no-regret in a game-theoretic setting.
interactions, competition and innovation in a service-oriented internet: an economic model. this paper presents a new economic approach for studying competition and innovation in a complex and highly interactive system of network providers, users, and suppliers of digital goods and services (i.e., service providers). it employs cournot and bertrand games to model competition among service providers and network providers, respectively, and develops a novel unified model to capture the interaction and competition among these players in a "service-oriented" internet. incentives for service and network innovation are studied in this model.
utility functionals associated with available congestion control algorithms. this paper is concerned with understanding the connection between the existing internet congestion control algorithms and the optimal control theory. the available resource allocation controllers are mainly devised to derive the state of the system to a desired equilibrium point and, therefore, they are oblivious to the transient behavior of the closed-loop system. to take into account the real-time performance of the system, rather than merely its steady-state performance, the congestion control problem should be solved by maximizing a proper utility functional as opposed to a utility function. for this reason, this work aims to investigate what utility functionals the existing congestion control algorithms maximize. in particular, it is shown that there exist meaningful utility functionals whose maximization leads to the celebrated primal, dual and primal/dual algorithms. an implication of this result is that a real network problem may be solved by regarding it as an optimal control problem on which some practical constraints, such as a real-time link capacity constraint, are imposed.
chip error pattern analysis in ieee 802.15.4. ieee 802.15.4 standard specifies physical layer (phy) and medium access control (mac) sublayer protocols for low-rate and low-power communication applications. in this protocol, every 4-bit symbol is encoded into a sequence of 32 chips that are actually transmitted over the air. the 32 chips as a whole is also called a pseudo-noise code (pn-code). due to complex channel conditions such as attenuation and interference, the transmitted pn-code will often be received with some pn-code chips corrupted. in this paper, we conduct a systematic analysis on these errors occurring at chip-level. we find that there are notable error patterns corresponding to different cases. recognizing these patterns will enable us to identify the channel condition in great details. we believe that understanding what happened to the transmission in our setup can potentially bring benefit to channel coding, routing and error correction protocol design.
building scalable virtual routers with trie braiding. many popular algorithms for fast packet forwarding and filtering rely on the tree data structure. examples are the trie-based ip lookup and packet classification algorithms. with the recent interest in network virtualization, the ability to run multiple virtual router instances on a common physical router platform is essential. an important scaling issue is the number of virtual router instances that can run on the platform. one limiting factor is the amount of high-speed memory and caches available for storing the packet forwarding and filtering data structures. an ideal goal is to achieve good scaling while maintaining total isolation amongst the virtual routers. however, total isolation requires maintaining separate data structures in high-speed memory for each virtual router. in this paper, we study the case where some sharing of the forwarding and filtering data structures is permissible and develop algorithms for combining tries used for ip lookup and packet classification. specifically, we develop a mechanism called trie-braiding that allows us to combine tries from the data structures of different virtual routers into just one compact trie. two optimal braiding algorithms are presented and the effectiveness is demonstrated using the real world data sets.
spatio-temporal fusion for small-scale primary detection in cognitive radio networks. in cognitive radio networks (crns), detecting small-scale primary devices--such as wireless microphones (wms)-- is a challenging, but very important, problem that has not yet been addressed well. we identify the data-fusion range as a key factor that enables effective cooperative sensing for detection of small-scale primary devices. in particular, we derive a closed-form expression for the optimal data-fusion range that minimizes the average detection delay. we also observe that the sensing performance is sensitive to the accuracy in estimating the primary's location and transmit-power. based on these observations, we propose an efficient sensing framework, called deloc, that iteratively performs location/transmit-power estimation and dynamic sensor selection for cooperative sensing. our extensive simulation results in a realistic crn environment show that deloc achieves near-optimal detection performance, while meeting the detection requirements specified in the ieee 802.22 standard draft.
cpmc: an efficient proximity malware coping scheme in smartphone-based mobile networks. smartphones are envisioned to provide promising applications and services. at the same time, smartphones are also increasingly becoming the target of malware. many emerging malware can utilize the proximity of devices to propagate in a distributed manner, thus remaining unobserved and making detections substantially more challenging. different from existing malware coping schemes, which are either totally centralized or purely distributed, we propose a community-based proximity malware coping scheme, cpmc. cpmc utilizes the social community structure, which reflects a stable and controllable granularity of security, in smartphone-based mobile networks. the cpmc scheme integrates short-term coping components, which deal with individual malware, and long-term evaluation components, which offer vulnerability evaluation towards individual nodes. a closeness-oriented delegation forwarding scheme combined with a community level quarantine method is proposed as the short-term coping components. these components contain a proximity malware by quickly propagating the signature of a detected malware into all communities while avoiding unnecessary redundancy. the long-term components offer vulnerability evaluation towards neighbors, based on the observed infection history, to help users make comprehensive communication decisions. extensive real- and synthetic-trace driven simulation results are presented to to evaluate the effectiveness of cpmc.
lightweight mutual authentication and ownership transfer for rfid systems. the promise of rfid technology has been evidently foreseeable due to the low cost and high convenience value of rfid tags. however, the low-cost rfid tags poses new challenges to security and privacy. some solutions utilize expensive cryptographic primitives such as hash or encryption functions, and some lightweight approaches have been reported to be broken. in this paper, we propose a lightweight solution to mutual authentication for rfid systems in which only the authenticated readers and tags can successfully communicate with each other. then, we adapt our mutual authentication scheme to secure the ownership transfer of rfid tags. our mutual authentication and ownership transfer protocols are realized utilizing minimalistic cryptography such as physically unclonable functions (puf) and linear feedback shift registers (lfsr). pufs and lfsrs are very efficient in hardware and particularly suitable for the low-cost rfid tags. compared to existing solutions built on top of hash functions that require 8000 to 10000 gates, our schemes demand only 784 gates for 64-bit variables and can be easily accommodated by the cheapest rfid tags with only 2000 gates available for security functions.