waashk/dblp huggingface dataset:
optimal linear network coding design for secure unicast with multiple streams. linear network coding is a promising technology that can maximize the throughput capacity of communication network. despite this salient feature, there are still many challenges to be addressed, and security is clearly one of the most important challenges. in this paper, we will address the design of secure linear network coding. specifically, we will investigate the network coding design that can both satisfy the weakly secure requirements and maximize the transmission data rate of multiple unicast streams between the same source and destination pair, which has not been addressed in the literature. in our study, we first prove that the secure unicast routing problem is equivalent to a constrained link-disjoint path problem. we then develop efficient algorithm that can find the optimal unicast topology in a polynomial amount of time. based on the topology, we design deterministic linear network code that is weakly secure and can be constructed at the source node. and finally, we investigate the potential of random linear code for weakly secure unicast and prove the low bound of the probability that a random linear code is weakly secure.
robust and fast pattern matching for intrusion detection. the rule language of an intrusion detection system (ids) plays a critical role in its effectiveness. a rule language must be expressive, in order to describe attack patterns as precisely as possible. it must also allow for a matching algorithm with predictable and low complexity, in order to ensure robustness against denial-of-service attacks. unfortunately, these requirements often conflict. we show, for instance, that a single rule, when coupled with a backtracking matching algorithm, can bring the processing rate down to nearly one packet per second. performance vulnerabilities of this type are known for patterns described using regular expressions, and can be avoided by using a deterministic matching algorithm. increasingly, however, rules are being written using the more powerful regex syntax, which includes non-regular features such as back-references. the matching algorithm for general regex's is based on backtracking, and is thus vulnerable to attacks. the main contribution of this paper is a deterministic algorithm for the full regex syntax, which builds upon the deterministic algorithm for regular expressions. we provide a (rough) complexity bound on the worst-case performance, and show that this bound can be tightened through compile-time analysis of the regex structure. these bounds can be used as an admissibility check, to isolate expressions that require further analysis. finally, we present an implementation of these algorithms in the context of the snort ids, and experimental results on several packet traces which show substantial improvement over the backtracking algorithm.
minimizing energy consumption with probabilistic distance models in wireless sensor networks. minimizing energy consumption in wireless sensor networks has been a challenging issue, and grid-based clustering and routing schemes have attracted a lot of attention due to their simplicity and feasibility. thus how to determine the optimal grid size in order to minimize energy consumption and prolong network lifetime becomes an important problem during the network planning and dimensioning phase. so far most existing work uses the average distances within a grid and between neighbor grids to calculate the average energy consumption, which we found largely underestimates the real value. in this paper, we propose, analyze and evaluate the energy consumption models in wireless sensor networks with probabilistic distance distributions. these models have been validated by numerical and simulation results, which shows that they can be used to optimize grid size and minimize energy consumption accurately. we also use these models to study variable-size grids, which can further improve the energy efficiency by balancing the relayed traffic in wireless sensor networks.
source-location privacy through dynamic routing in wireless sensor networks. wireless sensor networks (wsns) have the potential to be widely used in many areas for unattended event monitoring. mainly due to lack of a protected physical boundary, wireless communications are vulnerable to unauthorized interception and detection. privacy is becoming one of the major issues that jeopardize the successful deployment of wireless sensor networks. while confidentiality of the message can be ensured through content encryption, it is much more difficult to adequately address the source-location privacy. for wsns, source-location privacy service is further complicated by the fact that the sensor nodes consist of low-cost and low-power radio devices, computationally intensive cryptographic algorithms and large scale broadcasting-based protocols are not suitable for wsns. in this paper, we propose source-location privacy schemes through routing to randomly selected intermediate node(s) before the message is transmitted to the sink node. we first describe routing through a single a single randomly selected intermediate node away from the source node. our analysis shows that this scheme can provide great local source-location privacy. we also present routing through multiple randomly selected intermediate nodes based on angle and quadrant to further improve the global source location privacy. while providing source-location privacy for wsns, our simulation results also demonstrate that the proposed schemes are very efficient in energy consumption, and have very low transmission latency and high message delivery ratio. our protocols can be used for many practical applications.
critical sensor density for partial connectivity in large area wireless sensor networks. assume sensor deployment follows the poisson distribution. for a given partial connectivity requirement ρ, 0.5 < ρ < 1, we prove, for a hexagon model, that there exists a critical sensor density λ0, around which the probability that at least 100ρ% of sensors are connected in the network increases sharply from ɛ to 1- ɛ within a short interval of sensor density λ. the location of λ0 is at the sensor density where the above probability is about 1/2. we also extend the results to the disk model. simulations are conducted to confirm the theoretical results.
a practical on-line pacing scheme at edges of small buffer networks. for the optical packet-switching routers to be widely deployed in the internet, the size of packet buffers on routers has to be significantly small. such small-buffer networks rely on traffic with low levels of burstiness to avoid buffer overflows and packet losses. we present a pacing system that proactively shapes traffic in the edge network to reduce burstiness. our queue length based pacing uses an adaptive pacing on a single queue and paces traffic indiscriminately where deployed. in this work, we show through analysis and simulation that this pacing approach introduces a bounded delay and that it effectively reduces traffic burstiness. we also show that it can achieve higher throughput than end-system based pacing.
topology discovery for virtual local area networks. in this paper we investigate the problem of finding the physical layer topology of large, heterogeneous networks that comprises multiple vlans and may include uncooperative network nodes. we prove that finding a layer-2 network topology for a given incomplete input is an np-hard problem even when the network comprises only two vlans and the network contains one loop and deciding whether a given input defines a unique vlans topology is a co-np-hard problem. we design several heuristic algorithms to find vlans topology. our first algorithm is designed for geographically wide-spread networks that may contain uncooperative devices. for such networks the algorithm discovers the topology for each vlan then merges them to infer the network topology in o(n3) time, where n is the number of internal network nodes. our second algorithm is designed for smaller, active networks where each device in the network provides access to their mib and few aft entries are missing. for such networks, the algorithm finds the unique topology of vlans in o(n3) time. we have implemented both the algorithms described in this paper and conducted extensive experiments on multiple networks. our experiments demonstrate that our approach is quite practical and discovers the accurate vlans topology of large and heterogeneous networks whose input may not necessarily be complete. to the best of our knowledge, this is the first paper investigating topology discovery for vlans.
pricing under constraints in access networks: revenue maximization and congestion management. this paper investigates pricing of internet connectivity services in the context of a monopoly isp selling broadband access to consumers. we first study the optimal combination of flat-rate and usage-based access price components for maximization of isp revenue, subject to a capacity constraint on the datarate demand. next, we consider time-varying consumer utilities for broadband data rates that can result in uneven demand for data-rate over time. practical considerations limit the viability of altering prices over time to smoothen out the demanded datarate. despite such constraints on pricing, our analysis reveals that the isp can retain the revenue by setting a low usage fee and dropping packets of consumer demanded data that exceed capacity. regulatory attention on isp congestion management discourages such "technical" practices and promotes economics based approaches. we characterize the loss in isp revenue from an economics based approach. regulatory requirements further impose limitations on price discrimination across consumers, and we derive the revenue loss to the isp from such restrictions. we then develop partial recovery of revenue loss through non-linear pricing that does not explicitly discriminate across consumers. while determination of the access price is ultimately based on additional considerations beyond the scope of this paper, the analysis here can serve as a benchmark to structure access price in broadband access networks.
practical scheduling algorithms for concurrent transmissions in rate-adaptive wireless networks. optimal scheduling for concurrent transmissions in rate-nonadaptive wireless networks is np-hard. optimal scheduling in rate-adaptive wireless networks is even more difficult, because, due to mutual interference, each flow's throughput in a time slot is unknown before the scheduling decision of that slot is finalized. the capacity bound derived for rate-nonadaptive networks is no longer applicable either. in this paper, we first formulate the optimal scheduling problems with and without minimum per-flow throughput constraints. given the hardness of the problems and the fact that the scheduling decisions should be made within a few milliseconds, we propose two simple yet effective searching algorithms which can quickly move towards better scheduling decisions. thus, the proposed scheduling algorithms can achieve high network throughput and maintain long-term fairness among competing flows with low computational complexity. for the constrained optimization problem involved, we consider its dual problem and apply lagrangian relaxation. we then incorporate a dual update procedure in the proposed searching algorithm to ensure that the searching results satisfy the constraints. extensive simulations are conducted to demonstrate the effectiveness and efficiency of the proposed scheduling algorithms which are found to achieve throughputs close to the exhaustive searching results with much lower computational complexity.
towards cooperative localization of wearable sensors using accelerometers and cameras. this work describes a new approach for localizing people by cooperative sensor fusion of lightweight camera and wearable accelerometer measurements. we present the algorithm to identify people moving around as they are detected by cameras deployed in the infrastructure. the algorithm uses a correlation metric to develop an id matching algorithm that can associate people in the scene to their global id emitted from a wireless accelerometer sensor node worn on their belts. first we conduct a set of preliminary experiments to verify that the quantities of interest easily measurable by off-the-shelf components. we validate our metric and the performance of the proposed id matching algorithm using simulations on testbed data that also includes a crowded scenario.
distributed dynamic speed scaling. in recent years we have witnessed a great interest in large distributed computing platforms, also known as clouds. while these systems offer enormous computing power, they are major energy consumers. in existing data centers cpus are responsible for approximately half of the energy consumed by the servers. a promising technique for saving cpu energy consumption is dynamic speed scaling, in which the speed at which the processor is run is adjusted based on demand and performance constraints. in this paper we look at the problem of allocating the demand in the network of processors (each being capable to perform dynamic speed scaling) to minimize the global energy consumption/cost subject to a performance constraint. the nonlinear dependence between the energy consumption and the performance as well as the high variability in the energy prices result in a nontrivial resource allocation. the problem can be abstracted as a fully distributed convex optimization with a linear constraint. on the theoretical side, we propose two low-overhead fully decentralized algorithms for solving the problem of interest and provide closed-form conditions that ensure stability of the algorithms. then we evaluate the efficacy of the optimal solution using simulations driven by the real-world energy prices. our findings indicate a possible cost reduction of 10-40% compared to power-oblivious 1/n load balancing, for a wide range of load factors.
verifiable fine-grained top-k queries in tiered sensor networks. most large-scale sensor networks are expected to follow a two-tier architecture with resource-poor sensor nodes at the lower tier and resource-rich master nodes at the upper tier. master nodes collect data from sensor nodes and then answer the queries from the network owner on their behalf. in hostile environments, master nodes may be compromised by the adversary and then instructed to return fake and/or incomplete data in response to data queries. such application-level attacks are more harmful and difficult to detect than blind dos attacks on network communications, especially when the query results are the basis for making critical decisions such as military actions. this paper presents three schemes whereby the network owner can verify the authenticity and completeness of fine-grained topk query results in tired sensor networks, which is the first work of its kind. the proposed schemes are built upon symmetric cryptographic primitives and force compromised master nodes to return both authentic and complete top-k query results to avoid being caught. detailed theoretical and quantitative results confirm the high efficacy and efficiency of the proposed schemes.
capauth: a capability-based handover scheme. existing handover schemes in wireless lans, 3g/4g networks, and femtocells rely upon protocols involving centralized authentication servers and one or more access points. these protocols are invariably complex and use extensive signaling on the wireless backhaul since they aim to be be efficient (minimal handover latency) without sacrificing robustness. however, the mobile user has little involvement especially with the so-called context transfer stage; this stage involves the transfer of necessary state to the new access point as well as the enforcement of security goals such as user authentication and single point of access. we propose the incorporation of user capabilities, network-asserted proofs of user identity and access control, as a general mechanism to simplify the context transfer stage. to this end, we have designed capauth, a capability-based scheme that has reduced complexity, low overhead, high level of fault tolerance and is general enough to implement a range of security policies.
reciprocity and barter in peer-to-peer systems. this work investigates reciprocity in peer-to-peer systems. the scenario is one where users arrive to the network with a set of contents and content demands. peers exchange contents to satisfy their demands, following either a direct reciprocity principle (i help you and you help me) or indirect reciprocity principle (i help you and someone helps me). first, we prove that any indirect reciprocity schedule of exchanges, in the absence of relays, can be replaced by a direct reciprocity schedule, provided that users (1) are willing to download undemanded content for bartering purposes and (2) use up to twice the bandwidth they would use under indirect reciprocity. motivated by the fact that, in the absence of relays, the loss of efficiency due to direct reciprocity is at most two, we study various distributed direct reciprocity schemes through simulations, some of them involving a broker to facilitate exchanges.
resilient routing for sensor networks using hyperbolic embedding of universal covering space. we study how to characterize the families of paths between any two nodes s, t in a sensor network with holes. two paths that can be deformed to one another through local changes are called homotopy equivalent. two paths that pass around holes in different ways have different homotopy types. with a distributed algorithm we compute an embedding of the network in hyperbolic space by using ricci flow such that paths of different homotopy types are mapped naturally to paths connecting s with different images of t. greedy routing to a particular image is guaranteed with success to find a path with a given homotopy type. this leads to simple greedy routing algorithms that are resilient to both local link dynamics and large scale jamming attacks and improve load balancing over previous greedy routing algorithms.
minimum energy per bit for wideband wireless multicasting: performance of decode-and-forward. we study the minimum energy per bit required for communicating a message to all the destination nodes in a wireless network. the physical layer is modeled as an additive white gaussian noise channel affected by circularly symmetric fading. the fading coefficients are known at neither transmitters nor receivers. we provide an information-theoretic lower bound on the energy requirement of multicasting in arbitrary wireless networks as the solution of a linear program. we study the broadcast performance of decode-and-forward operating in the non-coherent wideband scenario, and compare it with the lower bounds. for arbitrary networks with k nodes, the energy requirement of decode-and-forward is within a factor of k - 1 of the lower bound regardless of the magnitude of channel gains. we also show that decode-and-forward achieves the minimum energy per bit in networks that can be represented as directed acyclic graphs, thus establishing the exact minimum energy per bit for this class of networks. we also study regular networks where the area is divided into cells, each cell containing at least k and at most k nodes placed arbitrarily within the cell. a path loss model (with path loss exponent α > 2) dictates the channel gains between the nodes. it is shown that the ratio between the upper bound using decode-and-forward based flooding, and the lower bound is at most a constant times kα+2/k.
capacity region of a wireless mesh backhaul network over the csma/ca mac. this paper studies the maximum throughput that can be supported by a given wireless mesh backhaul network, over a practical csma/ca medium access control (mac) protocol. we resort to the multi-commodity flow (mcf) formulation, augmented with the conflict-graph constraints, to jointly compute the maximum throughput and the associated optimal network dimensioning; while use a novel approach to take into account the collision overhead in the distributed csma/ca mac. such overhead has been ignored by the existing mcf-based capacity studies, which assume impractical centralized scheduling and result in aggressive network dimensioning, unachievable over the csma/ca mac. we develop a generic method to integrate the csma/ca mac analysis with the mcf formulation for optimal network capacity analysis, and derive both an upper bound and a lower bound of the network throughput over a practical csma/ca protocol. to the best of our knowledge, this paper is the first rigorous theoretical study of the achievable capacity over a multi-hop csma/ca based wireless network.
a reaction-diffusion model for epidemic routing in sparsely connected manets. we propose and investigate a deterministic traveling wave model for the progress of epidemic routing in disconnected mobile ad hoc networks. in epidemic routing, broadcast or unicast is achieved by exploiting mobility: message-carrying nodes "infect" non message-carrying nodes when they come within communication range of them. early probabilistic analyses of epidemic routing follow a "well-mixed" model which ignores the spatial distribution of the infected nodes, and hence do not provide good performance estimates unless the node density is very low. more recent work has pointed out that the infection exhibits wave-like characteristics, but does not provide a detailed model of the wave propagation. in this paper, we model message propagation using a reaction-diffusion partial differential equation that has a traveling wave solution, and show that the performance predictions made by the model closely match simulations in regimes where the well-mixed model breaks down. in particular, we show that well-mixed models are generally overly optimistic in regard to the scaling of the message delivery delay with problem parameters such as communication range, node density, and total area. in contrast to prior work, our model provides insight into the spatial distribution of the "infection," and reveals that the performance is sensitive to the geometry of the deployment region, not just its area.
joint power and secret key queue management for delay limited secure communication. in recent years, the famous wiretap channel has been revisited by many researchers and information theoretic secrecy has become an active area of research in this setting. in this paper, we design a wireless communication system that achieves constant bit rate data transmission over a block fading channel, securely from an eavesdropper that listens to the transmitter over another independent block fading channel. it is well known that, the method of sending secure information using the binning techniques inspired by the wiretap channel fails to secure the information at times when the eavesdropper channel has favorable conditions over the main channel. this phenomenon is called secrecy outage. in our system, however, we exploit the times at which the main channel is favorable over the eavesdropper channel for us to be able to transmit some random secret key bits along with the data bits. these key bits are stored in a separate key queue at the transmitter as well as the receiver, and are utilized to secure data bits, whenever the channel conditions favor the eavesdropper. we show that, our system achieves a high performance at any given desired outage probability by jointly controlling the key queue and the transmit power. we show that the optimal power control involves a time sharing between secure waterfilling and channel inversion strategies and the key queue operates in the heavy traffic regime to achieve the maximum delay limited rate possible, under a small outage constraint. this work can be viewed as a first step in providing a framework that combines both information theory and queueing analysis for the study of information theoretic security.